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

---

Detailed Description

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

This class provides an implementation of the Edmonds-Karp algorithm producing a flow of maximum value in a directed graphs. The Edmonds-Karp algorithm is slower than the Preflow algorithm but it has an advantage of the step-by-step execution control with feasible flow solutions. 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.

The time complexity of the algorithm is in worst case. Always try the preflow algorithm instead of this if you just want to compute the optimal flow.

Parameters:

	_Graph	The directed graph type the algorithm runs on.
	_CapacityMap	The capacity map type.
	_Traits	Traits class to set various data types used by the algorithm. The default traits class is EdmondsKarpDefaultTraits. See EdmondsKarpDefaultTraits for the documentation of a Edmonds-Karp traits class.

Author:

Balazs Dezso

#include <lemon/edmonds_karp.h>

List of all members.

Classes
struct	DefFlowMap
class	InvalidArgument
Public Member Functions
	EdmondsKarp (const Graph &graph, const CapacityMap &capacity, Node source, Node target)
	The constructor of the class.
	~EdmondsKarp ()
	Destrcutor.
EdmondsKarp &	capacityMap (const CapacityMap &map)
	Sets the capacity map.
EdmondsKarp &	flowMap (FlowMap &map)
	Sets the flow map.
const FlowMap &	flowMap ()
	Returns the flow map.
EdmondsKarp &	source (const Node &node)
	Sets the source node.
EdmondsKarp &	target (const Node &node)
	Sets the target node.
EdmondsKarp &	tolerance (const Tolerance &tolerance) const
const Tolerance &	tolerance () const
Execution control The simplest way to execute the
algorithm is to use the run() member functions. If you need more control on initial solution or execution then you have to call one init() function and then the start() or multiple times the augment() member function.
void	init ()
	Initializes the algorithm.
template<typename FlowMap >
void	flowInit (const FlowMap &flowMap)
	Initializes the algorithm.
template<typename FlowMap >
bool	checkedFlowInit (const FlowMap &flowMap)
	Initializes the algorithm.
bool	augment ()
	Augment the solution on an edge shortest path.
void	start ()
	Executes the algorithm.
void	run ()
	runs the algorithm.
Query Functions
The result of the Edmonds-Karp 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.
Value	flow (const Edge &edge) const
	Returns the flow on the edge.
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.

---

Constructor & Destructor Documentation

EdmondsKarp	(	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.

~EdmondsKarp

(

)

[inline]

Destructor.

---

Member Function Documentation

EdmondsKarp& capacityMap

(

const CapacityMap &

map

)

[inline]

Sets the capacity map.

Returns:

(*this)

EdmondsKarp& flowMap

(

FlowMap &

map

)

[inline]

Sets the flow map.

Returns:

(*this)

const FlowMap& flowMap

(

)

[inline]

Returns:

The flow map.

EdmondsKarp& source

(

const Node &

node

)

[inline]

Sets the source node.

Returns:

(*this)

EdmondsKarp& target

(

const Node &

node

)

[inline]

Sets the target node.

Returns:

(*this)

EdmondsKarp& 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]

It sets the flow to empty flow.

void flowInit

(

const FlowMap &

flowMap

)

[inline]

Initializes the flow to the flowMap. The flowMap should contain a feasible flow, ie. in each node excluding the source and the target the incoming flow should be equal to the outgoing flow.

bool checkedFlowInit

(

const FlowMap &

flowMap

)

[inline]

Initializes the flow to the flowMap. The flowMap should contain a feasible flow, ie. in each node excluding the source and the target the incoming flow should be equal to the outgoing flow.

Returns:

False when the given flowMap does not contain feasible flow.

bool augment

(

)

[inline]

Augment the solution on an edge shortest path. It search an edge shortest path between the source and the target in the residual graph with the bfs algoritm. Then it increase the flow on this path with the minimal residual capacity on the path. If there is not such path it gives back false.

Returns:

False when the augmenting is not success so the current flow is a feasible and optimal solution.

void start

(

)

[inline]

It runs augmenting phases until the optimal solution is reached.

void run

(

)

[inline]

It is just a shorthand for:

        ek.init();
        ek.start();

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.

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 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 cut to the characteristic vector of a minimum value cut It simply calls the minMinCut member.

Return values:

cut

Write node bool map.