template<typename GR, typename CAP, typename TR>
class lemon::Preflow< GR, CAP, TR >
This class provides an implementation of Goldberg-Tarjan's preflow push-relabel algorithm producing a flow of maximum value in a digraph [CLRS01], [AMO93], [GT88]. The preflow algorithms are the fastest known maximum flow algorithms. The current implementation uses a mixture of the "highest label" and the "bound decrease" heuristics. The worst case time complexity of the algorithm is
.
The algorithm consists of two phases. After the first phase the maximum flow value and the minimum cut is obtained. The second phase constructs a feasible maximum flow on each arc.
- Warning
- This implementation cannot handle infinite or very large capacities (e.g. the maximum value of
CAP::Value
).
- Template Parameters
-
GR | The type of the digraph the algorithm runs on. |
CAP | The type of the capacity map. The default map type is GR::ArcMap<int>. |
TR | The traits class that defines various types used by the algorithm. By default, it is PreflowDefaultTraits<GR, CAP>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead. |
|
| Preflow (const Digraph &digraph, const CapacityMap &capacity, Node source, Node target) |
| The constructor of the class.
|
|
| ~Preflow () |
|
Preflow & | capacityMap (const CapacityMap &map) |
| Sets the capacity map.
|
|
Preflow & | flowMap (FlowMap &map) |
| Sets the flow map.
|
|
Preflow & | source (const Node &node) |
| Sets the source node.
|
|
Preflow & | target (const Node &node) |
| Sets the target node.
|
|
Preflow & | elevator (Elevator &elevator) |
| Sets the elevator used by algorithm.
|
|
const Elevator & | elevator () const |
| Returns a const reference to the elevator.
|
|
Preflow & | tolerance (const Tolerance &tolerance) |
| Sets the tolerance used by the algorithm.
|
|
const Tolerance & | tolerance () const |
| Returns a const reference to the tolerance.
|
|
|
The simplest way to execute the preflow algorithm is to use run() or runMinCut().
If you need better control on the initial solution or the execution, you have to call one of the init() functions first, then startFirstPhase() and if you need it startSecondPhase().
|
void | init () |
| Initializes the internal data structures.
|
|
template<typename FlowMap > |
bool | init (const FlowMap &flowMap) |
| Initializes the internal data structures using the given flow map.
|
|
void | startFirstPhase () |
| Starts the first phase of the preflow algorithm.
|
|
void | startSecondPhase () |
| Starts the second phase of the preflow algorithm.
|
|
void | run () |
| Runs the preflow algorithm.
|
|
void | runMinCut () |
| Runs the preflow algorithm to compute the minimum cut.
|
|
|
The results of the preflow algorithm can be obtained using these functions.
Either one of the run*() functions or one of the start*() functions should be called before using them.
|
Value | flowValue () const |
| Returns the value of the maximum flow.
|
|
Value | flow (const Arc &arc) const |
| Returns the flow value on the given arc.
|
|
const FlowMap & | flowMap () const |
| Returns a const reference to the flow map.
|
|
bool | minCut (const Node &node) const |
| Returns true when the node is on the source side of the minimum cut.
|
|
template<typename CutMap > |
void | minCutMap (CutMap &cutMap) const |
| Gives back a minimum value cut.
|
|