My Project
|
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
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. | |