![]() |
abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
|
Algorithms for finding maximum flows. More...
Files | |
| file | circulation.h |
| file | edmonds_karp.h |
| Implementation of the Edmonds-Karp algorithm. | |
| file | preflow.h |
| Implementation of the preflow algorithm. | |
Classes | |
| class | Circulation< GR , LM , UM , SM , TR > |
| Push-relabel algorithm for the network circulation problem. More... | |
| class | EdmondsKarp< GR , CAP , TR > |
| Edmonds-Karp algorithms class. More... | |
| class | Preflow< GR , CAP , TR > |
| Preflow algorithm class. More... | |
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:
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.