Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Preflow Class Template Reference
[Path and Flow Algorithms]

#include <lemon/preflow.h>

List of all members.


Detailed Description

template<typename Graph, typename Num, typename CapMap = typename Graph::template EdgeMap<Num>, typename FlowMap = typename Graph::template EdgeMap<Num>>
class lemon::Preflow< Graph, Num, CapMap, FlowMap >

This class provides an implementation of the preflow algorithm producing a flow of maximum value in a directed graph. The preflow algorithms are the fastest max flow algorithms up to now. The source node, the target node, the capacity of the edges and the starting flow value of the edges should be passed to the algorithm through the constructor. It is possible to change these quantities using the functions setSource, setTarget, setCap and setFlow.

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.)

Parameters:
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.
Author:
Jacint Szabo

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.


Member Enumeration Documentation

enum FlowEnum
 

Indicates the property of the starting flow map. The meanings are as follows:

  • ZERO_FLOW: constant zero flow
  • GEN_FLOW: any flow, i.e. the sum of the in-flows equals to the sum of the out-flows in every node except the source and the target.
  • PRE_FLOW: any preflow, i.e. the sum of the in-flows is at least the sum of the out-flows in every node except the source.
  • NO_FLOW: indicates an unspecified edge map. flow will be set to the constant zero flow in the beginning of the algorithm in this case.

Definition at line 105 of file preflow.h.

enum StatusEnum
 

Indicates the state of the preflow algorithm. The meanings are as follows:

  • AFTER_NOTHING: before running the algorithm or at an unspecified state.
  • AFTER_PREFLOW_PHASE_1: right after running phase1
  • AFTER_PREFLOW_PHASE_2: after running phase2()

Definition at line 119 of file preflow.h.


Constructor & Destructor Documentation

Preflow const Graph &  _G,
Node  _s,
Node  _t,
const CapMap &  _capacity,
FlowMap &  _flow
[inline]
 

The constructor of the class.

Parameters:
_G The directed graph the algorithm runs on.
_s The source node.
_t The target node.
_capacity The capacity of the edges.
_flow The flow of the edges. Except the graph, all of these parameters can be reset by calling setSource, setTarget, setCap and setFlow, resp.

Definition at line 141 of file preflow.h.

Here is the call graph for this function:


Member Function Documentation

void run  )  [inline]
 

Runs the preflow algorithm.

Definition at line 153 of file preflow.h.

Here is the call graph for this function:

void run FlowEnum  fp  )  [inline]
 

Runs the preflow algorithm.

Precondition:
The starting flow map must be
  • a constant zero flow if fp is ZERO_FLOW,
  • an arbitrary flow if fp is GEN_FLOW,
  • an arbitrary preflow if fp is PRE_FLOW,
  • any map if fp is NO_FLOW. If the starting flow map is a flow or a preflow then the algorithm terminates faster.

Definition at line 168 of file preflow.h.

Here is the call graph for this function:

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, 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.

Warning:
minMinCut and maxMinCut do not give minimum value cuts unless calling phase2.
Precondition:
The starting flow must be
  • a constant zero flow if fp is ZERO_FLOW,
  • an arbitary flow if fp is GEN_FLOW,
  • an arbitary preflow if fp is PRE_FLOW,
  • any map if fp is NO_FLOW.

Definition at line 188 of file preflow.h.

Here is the call graph for this function:

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, 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.

Warning:
minCut(), minMinCut() and maxMinCut() do not give minimum value cuts unless calling phase2().

Definition at line 205 of file preflow.h.

void phase2  )  [inline]
 

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.

Precondition:
phase1 must be called before.

Definition at line 287 of file preflow.h.

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.

Definition at line 361 of file preflow.h.

void minCut _CutMap &  M  )  const [inline]
 

Sets M to the characteristic vector of a minimum value cut. This method can be called both after running phase1 and phase2. It is much faster after phase1.

Precondition:
M should be a bool-valued node-map.

If minCut() is called after phase2() then M should be initialized to false.

Definition at line 375 of file preflow.h.

Here is the call graph for this function:

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.

Precondition:
M should be a node map of bools initialized to false.

phase2 should already be run.

Definition at line 402 of file preflow.h.

void maxMinCut _CutMap &  M  )  const [inline]
 

Sets M to the characteristic vector of the minimum value cut which is inclusionwise maximum. It is computed by processing a backward bfs from the target node t in the residual graph.

Precondition:
phase2() or run() should already be run.

Definition at line 437 of file preflow.h.

void setSource Node  _s  )  [inline]
 

Sets the source node to _s.

Definition at line 472 of file preflow.h.

void setTarget Node  _t  )  [inline]
 

Sets the target node to _t.

Definition at line 482 of file preflow.h.

void setCap const CapMap &  _cap  )  [inline]
 

Sets the edge map of the capacities to _cap.

Definition at line 492 of file preflow.h.

void setFlow FlowMap &  _flow  )  [inline]
 

Sets the edge map of the flows to _flow.

Definition at line 501 of file preflow.h.


The documentation for this class was generated from the following file:
Generated on Sat Mar 19 10:58:54 2005 for LEMON by  doxygen 1.4.1