Loading...
Searching...
No Matches
Maximum Flow Algorithms
Algorithms

## Detailed Description

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

The maximum flow problem is to find a flow of maximum value between a single source and a single target. Formally, there is a digraph, a capacity function and source and target nodes. A maximum flow is an solution of the following optimization problem.

Preflow is an efficient implementation of Goldberg-Tarjan's preflow push-relabel algorithm [goldberg88newapproach] for finding maximum flows. It also provides 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...

## Files

file | circulation.h
file | edmonds_karp.h
| Implementation of the Edmonds-Karp algorithm.
file | preflow.h
| Implementation of the preflow algorithm.