| 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.PushRelabel.Pure
Description
Tide — Push (Pull) Relabel
The Tide algorithm is a push-relabel variant for solving the maximum flow problem on directed graphs.
Definitions
A network \( N = (G, s, t, C) \) consists of a directed graph \( G \), source \( s \), sink \( t \), and capacities \( C : E \to \mathbb{R}^+ \).
The residual graph \( R \) contains both forward edges (with residual capacity \( c - f \)) and backward edges (with capacity \( f \)). Each vertex carries:
- Height \( h(v) \): determines whether flow can be pushed along an edge (flow moves from higher to lower height).
- Excess \( x(v) \): records the net surplus of flow at \( v \). At termination all excesses are zero and the preflow is a valid max flow.
- Level \( \ell(v) \): the BFS distance from source in the original graph \( G \). Constant throughout the algorithm. Determines the sweep order.
Operations
The key difference from classical push-relabel is that the push operation is split into two:
- Push (on forward edges): increases flow towards the sink.
- Pull (on reverse edges): decreases flow, effectively pulling excess backwards towards the source.
Algorithm
Each iteration ("tide") consists of three global sweeps:
- globalRelabel: BFS from sink (and source) on the residual graph to recompute vertex heights. Source-side vertices get \( h = |V| + d_s(v) \); sink-side vertices get \( h = d_t(v) \).
- globalPull: right fold over overflowing vertices in descending level order, pulling flow on reverse edges (from sink towards source).
- globalPush: left fold over overflowing vertices in ascending level order, pushing flow on forward edges (from source towards sink).
The algorithm terminates when both the net flow and the set of overflowing vertices are unchanged between consecutive tides.
Skip-globalRelabel optimization
When no edge crosses a saturation boundary during push/pull (the
topologyChanged flag is False), the residual graph topology is
unchanged and globalRelabel is skipped. This saves 1.25--1.61x in
practice.
Complexity
- Per-tide cost: \( O((V+E) \log V) \) with IntMap data structures.
- Number of tides: \( O(V^2) \) worst case (requires exponential capacity ratios); \( O(V) \) in practice on non-pathological graphs.
- Total: \( O(V^2 (V+E) \log V) \) worst case; \( O(V (V+E) \log V) \) practical.
See also the Rust implementation tide-maxflow which achieves \( O(VE) \)
practical complexity using O(1) array-based data structures.
Synopsis
Main entry point
pushRelabel :: Network -> Either String ResidualGraph Source #
Solve the maximum flow problem on a Network using the Tide algorithm.
Returns Right rg on success, where rg is the ResidualGraph at
termination. The maximum flow value is netFlow rg and per-edge flows
are available via edgeFlow rg e or via flow (network rg).
Returns Left msg if an internal invariant is violated (should not happen
on valid inputs).
Example
let g = graphFromEdges [Edge 0 1, Edge 0 2, Edge 1 3, Edge 2 3]
caps = M.fromList [(Edge 0 1, 10), (Edge 0 2, 10), (Edge 1 3, 10), (Edge 2 3, 10)]
net = Network g 0 3 caps (M.fromList [(e, 0) | e <- edges g])
case pushRelabel net of
Right rg -> print (netFlow rg) -- 20
Left err -> putStrLn err
Algorithm internals (exported for testing)
tide :: ResidualGraph -> Int -> ResidualGraph Source #
Core recursive loop of the Tide algorithm.
Each call performs one tide: globalRelabel (unless skipped), then globalPull, then globalPush. Recurses until convergence (net flow and overflowing set unchanged).
The steps parameter counts completed iterations.
globalPush :: ResidualGraph -> ResidualGraph Source #
Global push: sweep overflowing vertices from source to sink.
Iterates over overflowing vertices in ascending level order (left fold
on the Overflowing IntMap), pushing flow on all eligible forward
edges from each vertex.
This moves excess flow from source-side vertices towards the sink.
globalPull :: ResidualGraph -> ResidualGraph Source #
Global pull: sweep overflowing vertices from sink to source.
Iterates over overflowing vertices in descending level order (right fold
on the Overflowing IntMap), pulling flow on all eligible reverse
edges to each vertex.
This moves excess flow from sink-side vertices back towards the source.
globalRelabel :: ResidualGraph -> ResidualGraph Source #
Global relabel: recompute vertex heights via BFS on the residual graph.
Runs BFS from both source and sink on the residual graph to compute distances. Sets vertex heights:
- Sink-side vertices:
height = distance_from_sink - Source-side vertices:
height = |V| + distance_from_source
The height gap between source-side and sink-side vertices ensures that flow can only move from source-side to sink-side (downhill).