#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. | |
Tolerance | The tolerance 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 Tolerance &_sr=Tolerance()) | |
The constructor of the class. | |
Tolerance & | 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... |
enum FlowEnum |
Indicates the property of the starting flow map.
enum StatusEnum |
Preflow | ( | const Graph & | _gr, | |
Node | _s, | |||
Node | _t, | |||
const CapacityMap & | _cap, | |||
FlowMap & | _f, | |||
const Tolerance & | _sr = Tolerance() | |||
) | [inline] |
The constructor of the class.
_gr | The directed graph the algorithm runs on. | |
_s | The source node. | |
_t | The target node. | |
_cap | The capacity of the edges. | |
_f | The flow of the edges. | |
tol | Tolerance class. Except the graph, all of these parameters can be reset by calling source, target, capacityMap and flowMap, resp. |
Tolerance& tolerance | ( | ) | [inline] |
Give a reference to the tolerance handler class
void run | ( | ) | [inline] |
Runs the preflow algorithm.
void run | ( | FlowEnum | fp | ) | [inline] |
Runs the preflow algorithm.
fp
is ZERO_FLOW
,fp
is GEN_FLOW
,fp
is PRE_FLOW
,fp
is NO_FLOW. If the starting flow map is a flow or a preflow then the algorithm terminates faster. void phase1 | ( | FlowEnum | fp | ) | [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.
fp
is ZERO_FLOW
,fp
is GEN_FLOW
,fp
is PRE_FLOW
,fp
is NO_FLOW. void phase1 | ( | ) | [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.
void phase2 | ( | ) | [inline] |
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.
Num flowValue | ( | ) | const [inline] |
Returns the value of the maximum flow by returning the excess of the target node t
. This value equals to the value of the maximum flow already after running phase1.
void minCut | ( | _CutMap & | M | ) | const [inline] |
void minMinCut | ( | _CutMap & | M | ) | const [inline] |
Sets M
to the characteristic vector of the minimum value cut which is inclusionwise minimum. It is computed by processing a bfs from the source node s
in the residual graph.
phase2 should already be run.
void maxMinCut | ( | _CutMap & | M | ) | const [inline] |
void source | ( | Node | _s | ) | [inline] |
Sets the source node to _s
.
Node source | ( | ) | const [inline] |
Returns the source node.
void target | ( | Node | _t | ) | [inline] |
Sets the target node to _t
.
Node target | ( | ) | const [inline] |
Returns the target node.
void capacityMap | ( | const CapacityMap & | _cap | ) | [inline] |
Sets the edge map of the capacities to _cap.
const CapacityMap& capacityMap | ( | ) | const [inline] |
Returns a reference to capacity map.
void flowMap | ( | FlowMap & | _f | ) | [inline] |
Sets the edge map of the flows to _flow.
const FlowMap& flowMap | ( | ) | const [inline] |
Returns a reference to flow map.