This group contains the algorithms for finding maximum flows and feasible circulations [CLRS01], [AMO93].
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 [GT88] 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 | 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 | 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 | preflow.h |
Implementation of the preflow algorithm. | |