{-|
Module      : Data.Graph.AdjacencyList.Network
Description : Flow network data type for max-flow problems
Copyright   : Thodoris Papakonstantinou, 2017-2026
License     : LGPL-3
Maintainer  : dev@tpapak.com
Stability   : experimental
Portability : POSIX

Defines the 'Network' type used as input to the Tide max-flow algorithm.

A 'Network' consists of:

* A directed 'Graph'
* A distinguished 'source' and 'sink' vertex
* Edge 'Capacities' (mapping each edge to a non-negative 'Rational')
* Edge flows (initially zero, filled in by the solver)

Capacities use 'Rational' for exact arithmetic — the Tide algorithm
terminates correctly for arbitrary rational capacities.  For integer-only
workloads, see the Rust implementation @tide-maxflow@ which uses @i64@.
 -}

module Data.Graph.AdjacencyList.Network
  ( -- * Network type
    Network (..)
    -- * Type aliases
  , Capacity
  , Capacities
  , Flow
    -- * Utilities
  , uniformCapacities
  ) where

import Data.List
import Data.Maybe
import qualified Data.Map.Lazy as M
import qualified Data.IntSet as Set

import Data.Graph.AdjacencyList

-- | Edge capacity.  Uses 'Rational' for exact arithmetic, ensuring the
-- Tide algorithm terminates correctly for arbitrary capacity values.
type Capacity = Rational 

-- | Map from edges to their capacities.
type Capacities = M.Map Edge Capacity 

-- | Edge flow.  Same type as 'Capacity' since flow values are rational.
type Flow = Capacity

showCapacities :: Capacities -> String
showCapacities :: Capacities -> String
showCapacities Capacities
cps =
  Map Edge Double -> String
forall a. Show a => a -> String
show (Map Edge Double -> String) -> Map Edge Double -> String
forall a b. (a -> b) -> a -> b
$ (Capacity -> Double) -> Capacities -> Map Edge Double
forall a b. (a -> b) -> Map Edge a -> Map Edge b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Capacity
c -> Capacity -> Double
forall a. Fractional a => Capacity -> a
fromRational Capacity
c :: Double) Capacities
cps

-- | A flow network: a directed graph with a source, sink, edge capacities,
-- and edge flows.
--
-- Construct a 'Network' with zero initial flows and pass it to
-- 'Data.Graph.AdjacencyList.PushRelabel.Pure.pushRelabel' to compute the
-- maximum flow.
data Network = Network { Network -> Graph
graph :: !Graph
                         -- ^ The underlying directed graph.
                       , Network -> Vertex
source :: Vertex
                         -- ^ Source vertex (flow originates here).
                       , Network -> Vertex
sink :: Vertex
                         -- ^ Sink vertex (flow terminates here).
                       , Network -> Capacities
capacities :: Capacities
                         -- ^ Edge capacities.  Every edge in 'graph' must
                         -- have a corresponding entry.
                       , Network -> Capacities
flow :: Capacities
                         -- ^ Edge flows.  Set to zero initially; filled in
                         -- by the solver.
                       }
                       deriving (Network -> Network -> Bool
(Network -> Network -> Bool)
-> (Network -> Network -> Bool) -> Eq Network
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Network -> Network -> Bool
== :: Network -> Network -> Bool
$c/= :: Network -> Network -> Bool
/= :: Network -> Network -> Bool
Eq)

instance Show Network where
  show :: Network -> String
show Network
net =
    String
"Network" String -> ShowS
forall a. Semigroup a => a -> a -> a
<> Graph -> String
forall a. Show a => a -> String
show (Network -> Graph
graph Network
net) String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
"\n"
    String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" source: " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> Vertex -> String
forall a. Show a => a -> String
show (Network -> Vertex
source Network
net) String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
"\n"
    String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" sink  : " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> Vertex -> String
forall a. Show a => a -> String
show (Network -> Vertex
sink Network
net) String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
"\n"
    String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" capacities: " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> Capacities -> String
showCapacities (Network -> Capacities
capacities Network
net) String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
"\n"
    String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" flows: " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> Capacities -> String
showCapacities (Network -> Capacities
flow Network
net) String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
"\n"

-- | Set all edge capacities to 1 (unit capacity network).
uniformCapacities :: Graph -> Capacities
uniformCapacities :: Graph -> Capacities
uniformCapacities Graph
g =
  [(Edge, Capacity)] -> Capacities
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList ([(Edge, Capacity)] -> Capacities)
-> [(Edge, Capacity)] -> Capacities
forall a b. (a -> b) -> a -> b
$ (Edge -> (Edge, Capacity)) -> [Edge] -> [(Edge, Capacity)]
forall a b. (a -> b) -> [a] -> [b]
map (\Edge
e -> (Edge
e,Capacity
1)) ([Edge] -> [(Edge, Capacity)]) -> [Edge] -> [(Edge, Capacity)]
forall a b. (a -> b) -> a -> b
$ Graph -> [Edge]
edges Graph
g