Maximum Flow Algorithms

The same group on the Doxygen site.

group Maximum Flow Algorithms

Algorithms for finding maximum flows.

This group contains the algorithms for finding maximum flows and feasible circulations [7], [1].

The maximum flow problem is to find a flow of maximum value between a single source and a single target. Formally, there is a \(G=(V,A)\) digraph, a \(cap: A\rightarrow\mathbf{R}^+_0\) capacity function and \(s, t \in V\) source and target nodes. A maximum flow is an \(f: A\rightarrow\mathbf{R}^+_0\) solution of the following optimization problem.

\[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \]
\[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) \quad \forall u\in V\setminus\{s,t\} \]
\[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \]

LEMON contains two algorithms for solving maximum flow problems:

  • EdmondsKarp Edmonds-Karp algorithm [13].

  • Preflow Goldberg-Tarjan’s preflow push-relabel algorithm [16].

In most cases the Preflow algorithm provides the fastest method for computing a maximum flow. Both implementations also provide functions to query the minimum cut, which is the dual problem of maximum flow.

Circulation is a preflow push-relabel algorithm implemented directly for finding feasible circulations, which is a somewhat different problem, but it is strongly related to maximum flow. For more information, see Circulation.

Classes

Class

Description

Circulation

Push-relabel algorithm for the network circulation problem.

EdmondsKarp

Edmonds-Karp algorithms class.

Preflow

Preflow algorithm class.

Other classes of its headers

Class

Description

CirculationDefaultTraits

Default traits class of Circulation class.

EdmondsKarpDefaultTraits

Default traits class of EdmondsKarp class.

PreflowDefaultTraits

Default traits class of Preflow class.