#include <lemon/preflow.h>
After running phase1() or run(), the maximal flow value can be obtained by calling flowValue(). The minimum value cut can be written into a bool
node map by calling minCut(). (minMinCut() and maxMinCut() writes the inclusionwise minimum and maximum of the minimum value cuts, resp.)
Graph | The directed graph type the algorithm runs on. | |
Num | The number type of the capacities and the flow values. | |
CapacityMap | The capacity map type. | |
FlowMap | The flow map type. |
Public Types | |
enum | FlowEnum { NO_FLOW, ZERO_FLOW, GEN_FLOW, PRE_FLOW } |
Indicates the property of the starting flow map. More... | |
enum | StatusEnum { AFTER_NOTHING, AFTER_PREFLOW_PHASE_1, AFTER_PREFLOW_PHASE_2 } |
Indicates the state of the preflow algorithm. More... | |
Public Member Functions | |
Preflow (const Graph &_gr, Node _s, Node _t, const CapacityMap &_cap, FlowMap &_f, const TOL &tol=TOL()) | |
The constructor of the class. | |
TOL & | tolerance () |
Give a reference to the tolerance handler class. | |
void | run () |
Runs the preflow algorithm. | |
void | run (FlowEnum fp) |
Runs the preflow algorithm. | |
void | phase1 (FlowEnum fp) |
Runs the first phase of the preflow algorithm. | |
void | phase1 () |
Runs the first phase of the preflow algorithm. | |
void | phase2 () |
Runs the second phase of the preflow algorithm. | |
Num | flowValue () const |
Returns the value of the maximum flow. | |
template<typename _CutMap> | |
void | minCut (_CutMap &M) const |
Returns a minimum value cut. | |
template<typename _CutMap> | |
void | minMinCut (_CutMap &M) const |
Returns the inclusionwise minimum of the minimum value cuts. | |
template<typename _CutMap> | |
void | maxMinCut (_CutMap &M) const |
Returns the inclusionwise maximum of the minimum value cuts. | |
void | source (Node _s) |
Sets the source node to _s . | |
Node | source () const |
Returns the source node. | |
void | target (Node _t) |
Sets the target node to _t . | |
Node | target () const |
Returns the target node. | |
void | capacityMap (const CapacityMap &_cap) |
Sets the edge map of the capacities to _cap. | |
const CapacityMap & | capacityMap () const |
Returns a reference to capacity map. | |
void | flowMap (FlowMap &_f) |
Sets the edge map of the flows to _flow. | |
const FlowMap & | flowMap () const |
Returns a reference to flow map. | |
Classes | |
class | InvalidArgument |
Exception for the case when the source equals the target. More... |
|
|
Indicates the state of the preflow algorithm. |
|
The constructor of the class.
|
|
Give a reference to the tolerance handler class
|
|
Runs the preflow algorithm. |
|
Runs the preflow algorithm.
|
|
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.
|
|
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.
|
|
The preflow algorithm consists of two phases, this method runs the second phase. After calling phase1() and then phase2(), flowMap() return a maximum flow, flowValue returns the value of a maximum flow, minCut returns a minimum cut, while the methods minMinCut and maxMinCut return the inclusionwise minimum and maximum cuts of minimum value, resp.
|
|
Returns the value of the maximum flow by returning the excess of the target node |
|
Sets |
|
Sets
|
|
Sets |
|
Sets the source node to |
|
Returns the source node. |
|
Sets the target node to |
|
Returns the target node. |
|
Sets the edge map of the capacities to _cap. |
|
Returns a reference to capacity map. |
|
Sets the edge map of the flows to _flow. |
|
Returns a reference to flow map. |