Circulation< _Graph, _LCapMap, _UCapMap, _DeltaMap, _Traits > Class Template Reference
[Maximum Flow algorithms]

---

Detailed Description

template<class _Graph, class _LCapMap = typename _Graph::template EdgeMap<int>, class _UCapMap = _LCapMap, class _DeltaMap = typename _Graph::template NodeMap< typename _UCapMap::Value>, class _Traits = CirculationDefaultTraits<_Graph, _LCapMap, _UCapMap, _DeltaMap>>
class lemon::Circulation< _Graph, _LCapMap, _UCapMap, _DeltaMap, _Traits >

This class implements a push-relabel algorithm for the Network Circulation Problem. The exact formulation of this problem is the following.

#include <lemon/circulation.h>

List of all members.

Classes
struct	DefElevator
struct	DefFlowMap
struct	DefStandardElevator
	Named parameter for setting Elevator type More...
Public Member Functions
	Circulation (const Graph &g, const LCapMap &lo, const UCapMap &up, const DeltaMap &delta)
	The constructor of the class.
	~Circulation ()
	Destrcutor.
Circulation &	lowerCapMap (const LCapMap &map)
	Sets the lower bound capacity map.
Circulation &	upperCapMap (const LCapMap &map)
	Sets the upper bound capacity map.
Circulation &	deltaMap (const DeltaMap &map)
	Sets the lower bound map on excess.
Circulation &	flowMap (FlowMap &map)
	Sets the flow map.
const FlowMap &	flowMap ()
	Returns the flow map.
Circulation &	elevator (Elevator &elevator)
	Sets the elevator.
const Elevator &	elevator ()
	Returns the elevator.
Circulation &	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 start() function.
void	init ()
	Initializes the internal data structures.
void	greedyInit ()
	Initializes the internal data structures.
bool	start ()
	Starts the algorithm.
bool	run ()
	Runs the circulation algorithm.
Query Functions
The result of the Circulation algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called.
template<class GT >
void	barrierMap (GT &bar)
	Returns a barrier.
bool	barrier (const Node &node)
	Returns true if the node is in the barrier.
Value	flow (const Edge &edge) const
	Returns the flow on the edge.
Checker Functions
The feasibility of the results can be checked using these functions. Before the use of these functions, either run() or start() must be called.
bool	checkFlow ()
	Check if the flow is a feasible circulation.
bool	checkBarrier ()
	Check whether or not the last execution provides a barrier.

---

Constructor & Destructor Documentation

Circulation	(	const Graph &	g,
		const LCapMap &	lo,
		const UCapMap &	up,
		const DeltaMap &	delta
	)			[inline]

The constructor of the class.

Parameters:

	g	The directed graph the algorithm runs on.
	lo	The lower bound capacity of the edges.
	up	The upper bound capacity of the edges.
	delta	The lower bound on node excess.

---

Member Function Documentation

Circulation& lowerCapMap

(

const LCapMap &

map

)

[inline]

Sets the lower bound capacity map.

Returns:

(*this)

Circulation& upperCapMap

(

const LCapMap &

map

)

[inline]

Sets the upper bound capacity map.

Returns:

(*this)

Circulation& deltaMap

(

const DeltaMap &

map

)

[inline]

Sets the lower bound map on excess.

Returns:

(*this)

Circulation& flowMap

(

FlowMap &

map

)

[inline]

Sets the flow map.

Returns:

(*this)

const FlowMap& flowMap

(

)

[inline]

Returns:

The flow map.

Circulation& elevator

(

Elevator &

elevator

)

[inline]

Sets the elevator.

Returns:

(*this)

const Elevator& elevator

(

)

[inline]

Returns:

The elevator.

Circulation& 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. This function sets all flow values to the lower bound.

Returns:

This function returns false if the initialization process found a barrier.

void greedyInit

(

)

[inline]

Initializes the internal data structures. This functions uses greedy approach to construct the initial solution.

bool start

(

)

[inline]

This function starts the algorithm.

Returns:

This function returns true if it found a feasible circulation.

See also:

barrier()

bool run

(

)

[inline]

Runs the circulation algorithm.

Note:

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

   fc.greedyInit();
   return fc.start();

void barrierMap

(

GT &

bar

)

[inline]

Barrier is a set B of nodes for which

holds. The existence of a set with this property prooves that a feasible flow cannot exists.

See also:

checkBarrier()

run()

bool barrier

(

const Node &

node

)

[inline]

Returns true if the node is in the barrier

See also:

barrierMap()

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.

bool checkBarrier

(

)

[inline]

Check whether or not the last execution provides a barrier

See also:

barrier()