#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. | |
CapMap | The capacity map type. | |
FlowMap | The flow map type. |
Definition at line 65 of file preflow.h.
Public Types | |
enum | FlowEnum |
Indicates the property of the starting flow map. More... | |
enum | StatusEnum |
Indicates the state of the preflow algorithm. More... | |
Public Member Functions | |
Preflow (const Graph &_G, Node _s, Node _t, const CapMap &_capacity, FlowMap &_flow) | |
The constructor of the 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 | setSource (Node _s) |
Sets the source node to _s . | |
void | setTarget (Node _t) |
Sets the target node to _t . | |
void | setCap (const CapMap &_cap) |
Sets the edge map of the capacities to _cap. | |
void | setFlow (FlowMap &_flow) |
Sets the edge map of the flows to _flow. |
|
Indicates the property of the starting flow map. The meanings are as follows:
|
|
Indicates the state of the preflow algorithm. The meanings are as follows:
|
|
The constructor of the class. |
Here is the call graph for this function:
|
Runs the preflow algorithm. |
Here is the call graph for this function:
|
Runs the preflow algorithm.
|
Here is the call graph for this function:
|
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, though 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.
|
Here is the call graph for this function:
|
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, though 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, flow contains 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 |
Here is the call graph for this function:
|
Sets
|
|
Sets |
|
Sets the source node to |
|
Sets the target node to |
|
Sets the edge map of the capacities to _cap. |
|
Sets the edge map of the flows to _flow. |