Preflow< _Graph, _CapacityMap, _Traits > Class Template Reference
[Maximum Flow algorithms]

---

Detailed Description

template<typename _Graph, typename _CapacityMap, typename _Traits>
class lemon::Preflow< _Graph, _CapacityMap, _Traits >

This class provides an implementation of the Goldberg's preflow algorithm producing a flow of maximum value in a directed graph. The preflow algorithms are the fastest known max flow algorithms. The current implementation use a mixture of the "highest label" and the "bound decrease" heuristics. The worst case time complexity of the algorithm is .

The algorithm consists from two phases. After the first phase the maximal flow value and the minimum cut can be obtained. The second phase constructs the feasible maximum flow on each edge.

Parameters:

	_Graph	The directed graph type the algorithm runs on.
	_CapacityMap	The flow map type.
	_Traits	Traits class to set various data types used by the algorithm. The default traits class is PreflowDefaultTraits. See PreflowDefaultTraits for the documentation of a Preflow traits class.

Author:

Jacint Szabo and Balazs Dezso

#include <lemon/preflow.h>

List of all members.

Classes
struct	DefElevator
struct	DefFlowMap
struct	DefStandardElevator
	Named parameter for setting Elevator type More...
class	UninitializedParameter
	Exception for uninitialized parameters. More...
Public Member Functions
	Preflow (const Graph &graph, const CapacityMap &capacity, Node source, Node target)
	The constructor of the class.
	~Preflow ()
	Destrcutor.
Preflow &	capacityMap (const CapacityMap &map)
	Sets the capacity map.
Preflow &	flowMap (FlowMap &map)
	Sets the flow map.
const FlowMap &	flowMap ()
	Returns the flow map.
Preflow &	elevator (Elevator &elevator)
	Sets the elevator.
const Elevator &	elevator ()
	Returns the elevator.
Preflow &	source (const Node &node)
	Sets the source node.
Preflow &	target (const Node &node)
	Sets the target node.
Preflow &	tolerance (const Tolerance &tolerance) const
const Tolerance &	tolerance () const
Execution control The simplest way to execute the
algorithm is to use one of the member functions called run(). If you need more control on initial solution or execution then you have to call one init() function and then the startFirstPhase() and if you need the startSecondPhase().
void	init ()
template<typename FlowMap >
bool	flowInit (const FlowMap &flowMap)
	Initializes the internal data structures.
void	startFirstPhase ()
	Starts the first phase of the preflow algorithm.
void	startSecondPhase ()
	Starts the second phase of the preflow algorithm.
void	run ()
	Runs the preflow algorithm.
void	runMinCut ()
	Runs the preflow algorithm to compute the minimum cut.
Query Functions
The result of the Preflow algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called.
Value	flowValue () const
	Returns the value of the maximum flow.
bool	minCut (const Node &node) const
	Returns true when the node is on the source side of minimum cut.
template<typename CutMap >
void	minCutMap (CutMap &cutMap) const
	Returns a minimum value cut.
Value	flow (const Edge &edge) const
	Returns the flow on the edge.

---

Constructor & Destructor Documentation

Preflow	(	const Graph &	graph,
		const CapacityMap &	capacity,
		Node	source,
		Node	target
	)			[inline]

The constructor of the class.

Parameters:

	graph	The directed graph the algorithm runs on.
	capacity	The capacity of the edges.
	source	The source node.
	target	The target node.

~Preflow

(

)

[inline]

Destructor.

---

Member Function Documentation

Preflow& capacityMap

(

const CapacityMap &

map

)

[inline]

Sets the capacity map.

Returns:

(*this)

Preflow& flowMap

(

FlowMap &

map

)

[inline]

Sets the flow map.

Returns:

(*this)

const FlowMap& flowMap

(

)

[inline]

Returns:

The flow map.

Preflow& elevator

(

Elevator &

elevator

)

[inline]

Sets the elevator.

Returns:

(*this)

const Elevator& elevator

(

)

[inline]

Returns:

The elevator.

Preflow& source

(

const Node &

node

)

[inline]

Sets the source node.

Returns:

(*this)

Preflow& target

(

const Node &

node

)

[inline]

Sets the target node.

Returns:

(*this)

Preflow& tolerance

(

const Tolerance &

tolerance

)

const [inline]

Sets the tolerance used by algorithm.

const Tolerance& tolerance

(

)

const [inline]

Returns the tolerance used by algorithm.

void init

(

)

[inline]

Initializes the internal data structures.

bool flowInit

(

const FlowMap &

flowMap

)

[inline]

Initializes the internal data structures and sets the initial flow to the given flowMap. The flowMap should contain a flow or at least a preflow, ie. in each node excluding the target the incoming flow should greater or equal to the outgoing flow.

Returns:

False when the given flowMap is not a preflow.

void startFirstPhase

(

)

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

Precondition:

One of the init() functions should be called.

void startSecondPhase

(

)

[inline]

The preflow algorithm consists of two phases, this method runs the second phase. After calling init() and startFirstPhase() and then startSecondPhase(), flowMap() return a maximum flow, flowValue() returns the value of a maximum flow, minCut() returns a minimum cut

Precondition:

The init() and startFirstPhase() functions should be called before.

void run

(

)

[inline]

Runs the preflow algorithm.

Note:

pf.run() is just a shortcut of the following code.

   pf.init();
   pf.startFirstPhase();
   pf.startSecondPhase();

void runMinCut

(

)

[inline]

Runs the preflow algorithm to compute the minimum cut.

Note:

pf.runMinCut() is just a shortcut of the following code.

   pf.init();
   pf.startFirstPhase();

Value 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 the first phase.

bool minCut

(

const Node &

node

)

const [inline]

Returns true when the node is on the source side of minimum cut. This method can be called both after running startFirstPhase() and startSecondPhase().

void minCutMap

(

CutMap &

cutMap

)

const [inline]

Sets the cutMap to the characteristic vector of a minimum value cut. This method can be called both after running startFirstPhase() and startSecondPhase(). The result after second phase could be changed slightly if inexact computation is used.

Precondition:

The cutMap should be a bool-valued node-map.

Value flow

(

const Edge &

edge

)

const [inline]

Sets the flowMap to the flow on the edges. This method can be called after the second phase of algorithm.