Maximum Flow Algorithms

Detailed Description

This group contains the algorithms for finding maximum flows and feasible circulations [6], [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 several algorithms for solving maximum flow problems:

EdmondsKarp Edmonds-Karp algorithm [13].
Preflow Goldberg-Tarjan's preflow push-relabel algorithm [16].
DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees [12], [26].
GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees [16], [26].

In most cases the Preflow algorithm provides the fastest method for computing a maximum flow. All 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	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...

struct	Circulation< GR, LM, UM, SM, TR >::SetElevator< T >
	Named parameter for setting Elevator type More...

struct	Circulation< GR, LM, UM, SM, TR >::SetFlowMap< T >
	Named parameter for setting FlowMap type More...

struct	Circulation< GR, LM, UM, SM, TR >::SetStandardElevator< T >
	Named parameter for setting Elevator type with automatic allocation More...

struct	EdmondsKarp< GR, CAP, TR >::SetFlowMap< T >

struct	Preflow< GR, CAP, TR >::SetElevator< T >
	Named parameter for setting Elevator type More...

struct	Preflow< GR, CAP, TR >::SetFlowMap< T >
	Named parameter for setting FlowMap type More...

struct	Preflow< GR, CAP, TR >::SetStandardElevator< T >
	Named parameter for setting Elevator type with automatic allocation More...

Files
file	circulation.h
	Push-relabel algorithm for finding a feasible circulation.

file	edmonds_karp.h
	Implementation of the Edmonds-Karp algorithm.

file	preflow.h
	Implementation of the preflow algorithm.

Detailed Description

Classes

Files