Preflow Class Template Reference
[Path and Flow Algorithms]

#include <lemon/preflow.h>

List of all members.


Detailed Description

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

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 known max flow algorithms. 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 source, target, capacityMap and flowMap.

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.
CapacityMap The capacity map type.
FlowMap The flow map type.
Tolerance The tolerance type.
Author:
Jacint Szabo
Todo:
Second template parameter is superfluous


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


Member Enumeration Documentation

enum FlowEnum

Indicates the property of the starting flow map.

Enumerator:
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.
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.

enum StatusEnum

Indicates the state of the preflow algorithm.

Enumerator:
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()


Constructor & Destructor Documentation

Preflow ( const Graph _gr,
Node  _s,
Node  _t,
const CapacityMap &  _cap,
FlowMap &  _f,
const Tolerance _sr = Tolerance() 
) [inline]

The constructor of the class.

Parameters:
_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.


Member Function Documentation

Tolerance& tolerance (  )  [inline]

Give a reference to the tolerance handler class

See also:
Tolerance

void run (  )  [inline]

Runs the preflow algorithm.

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.

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.

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.

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.

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

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.

Precondition:
phase1 must be called before.

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]

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.

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.

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.

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.


The documentation for this class was generated from the following file:
Generated on Tue Oct 31 09:51:18 2006 for LEMON by  doxygen 1.5.1