This class provides an implementation of Goldberg-Tarjan's preflowpush-relabel algorithm producing a flow of maximum value in a digraph [clrs01algorithms], [amo93networkflows], [goldberg88newapproach]. 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.
The simplest way to execute the preflow algorithm is to use run() or .\n 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().
Runs the preflow algorithm to compute the minimum cut.
Query Functions
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.
Sets the flow map. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.
Sets the elevator used by algorithm. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated elevator, of course.
Initializes the internal data structures and sets the initial flow to the given flowMap. The flowMap should contain a flow or at least a preflow, i.e. at each node excluding the source node the incoming flow should greater or equal to the outgoing flow.
template<typename GR , typename CAP , typename TR >
void startFirstPhase
(
)
inline
The preflow algorithm consists of two phases, this method runs the first phase. After the first phase the maximum flow value and a minimum value cut can already be computed, although a maximum flow is not yet obtained. So after calling this method flowValue() returns the value of a maximum flow and minCut() returns a minimum cut.
Precondition
One of the init() functions must be called before using this function.
template<typename GR , typename CAP , typename TR >
void startSecondPhase
(
)
inline
The preflow algorithm consists of two phases, this method runs the second phase. After calling one of the init() functions and startFirstPhase() and then startSecondPhase(), flowMap() returns a maximum flow, flowValue() returns the value of a maximum flow, minCut() returns a minimum cut
Precondition
One of the init() functions and startFirstPhase() must be called before using this function.
Returns the value of the maximum flow by returning the excess of the target node. This value equals to the value of the maximum flow already after the first phase of the algorithm.
Precondition
Either run() or init() must be called before using this function.
template<typename GR , typename CAP , typename TR >
bool minCut
(
const Node &
node
)
const
inline
Returns true when the node is on the source side of the found minimum cut. This method can be called both after running startFirstPhase() and startSecondPhase().
Precondition
Either run() or init() must be called before using this function.
template<typename GR , typename CAP , typename TR >
template<typename CutMap >
void minCutMap
(
CutMap &
cutMap
)
const
inline
Sets cutMap to the characteristic vector of a minimum value cut. cutMap should be a writable node map with bool (or convertible) value type.
This method can be called both after running startFirstPhase() and startSecondPhase(). The result after the second phase could be slightly different if inexact computation is used.
Note
This function calls minCut() for each node, so it runs in O(n) time.
Precondition
Either run() or init() must be called before using this function.
Generated on Mon Jul 25 2022 18:36:57 for My Project by 1.12.0