Copyright	Thodoris Papakonstantinou 2017-2026
License	LGPL-3
Maintainer	dev@tpapak.com
Stability	experimental
Portability	POSIX
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Graph.AdjacencyList.Network

Contents

Network type
Type aliases
Utilities

Description

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.

Synopsis

data Network = Network {
- graph :: !Graph
- source :: Vertex
- sink :: Vertex
- capacities :: Capacities
- flow :: Capacities
}
type Capacity = Rational
type Capacities = Map Edge Capacity
type Flow = Capacity
uniformCapacities :: Graph -> Capacities

Network type

data Network Source #

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 pushRelabel to compute the maximum flow.

Constructors

Network
Fields graph :: !Graph The underlying directed graph. source :: Vertex Source vertex (flow originates here). sink :: Vertex Sink vertex (flow terminates here). capacities :: Capacities Edge capacities. Every edge in `graph` must have a corresponding entry. flow :: Capacities Edge flows. Set to zero initially; filled in by the solver.

Instances

Instances details

Show Network Source #
Instance details Defined in Data.Graph.AdjacencyList.Network Methods showsPrec :: Int -> Network -> ShowS # show :: Network -> String # showList :: [Network] -> ShowS #
Eq Network Source #
Instance details Defined in Data.Graph.AdjacencyList.Network Methods (==) :: Network -> Network -> Bool # (/=) :: Network -> Network -> Bool #

Type aliases

type Capacity = Rational Source #

Edge capacity. Uses Rational for exact arithmetic, ensuring the Tide algorithm terminates correctly for arbitrary capacity values.

type Capacities = Map Edge Capacity Source #

Map from edges to their capacities.

type Flow = Capacity Source #

Edge flow. Same type as Capacity since flow values are rational.

Utilities

uniformCapacities :: Graph -> Capacities Source #

Set all edge capacities to 1 (unit capacity network).