This group contains the algorithms for finding maximum flows and feasible circulations.
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 implements the preflow push-relabel algorithm of Goldberg and Tarjan for solving this problem. 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... | |
Files | |
file | circulation.h |
Push-relabel algorithm for finding a feasible circulation. | |
file | preflow.h |
Implementation of the preflow algorithm. |