All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines
Classes | Public Types | Public Member Functions
EdmondsKarp< GR, CAP, TR > Class Template Reference

Detailed Description

template<typename GR, typename CAP, typename TR>
class lemon::EdmondsKarp< GR, CAP, TR >

This class provides an implementation of the Edmonds-Karp algorithm producing a flow of maximum value in a digraph [6], [1], [13]. 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 arcs and the starting flow value of the arcs should be passed to the algorithm through the constructor.

The time complexity of the algorithm is $ O(nm^2) $ in worst case. Always try the Preflow algorithm instead of this if you just want to compute the optimal flow.

Template Parameters:
GRThe type of the digraph the algorithm runs on.
CAPThe type of the capacity map. The default map type is GR::ArcMap<int>.
TRThe traits class that defines various types used by the algorithm. By default, it is EdmondsKarpDefaultTraits<GR, CAP>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead.

#include <lemon/edmonds_karp.h>

List of all members.

Classes

struct  SetFlowMap

Public Types

typedef TR Traits
 The traits class of the algorithm.
typedef Traits::Digraph Digraph
 The type of the digraph the algorithm runs on.
typedef Traits::CapacityMap CapacityMap
 The type of the capacity map.
typedef Traits::Value Value
 The type of the flow values.
typedef Traits::FlowMap FlowMap
 The type of the flow map.
typedef Traits::Tolerance Tolerance
 The type of the tolerance.

Public Member Functions

 EdmondsKarp (const Digraph &digraph, const CapacityMap &capacity, Node source, Node target)
 The constructor of the class.
 ~EdmondsKarp ()
EdmondsKarpcapacityMap (const CapacityMap &map)
 Sets the capacity map.
EdmondsKarpflowMap (FlowMap &map)
 Sets the flow map.
EdmondsKarpsource (const Node &node)
 Sets the source node.
EdmondsKarptarget (const Node &node)
 Sets the target node.
EdmondsKarptolerance (const Tolerance &tolerance)
 Sets the tolerance used by algorithm.
const Tolerancetolerance () const
 Returns a const reference to the tolerance.
Execution control

The simplest way to execute the algorithm is to use run().
If you need better control on the initial solution or the execution, you have to call one of the init() functions first, then start() or multiple times the augment() function.

void init ()
 Initializes the algorithm.
template<typename FlowMap >
void init (const FlowMap &flowMap)
 Initializes the algorithm using the given flow map.
template<typename FlowMap >
bool checkedInit (const FlowMap &flowMap)
 Initializes the algorithm using the given flow map.
bool augment ()
 Augments the solution along a 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.
Either run() or start() should be called before using them.

Value flowValue () const
 Returns the value of the maximum flow.
Value flow (const Arc &arc) const
 Returns the flow value on the given arc.
const FlowMapflowMap () const
 Returns a const reference to the flow map.
bool minCut (const Node &node) const
 Returns true when the node is on the source side of the minimum cut.
template<typename CutMap >
void minCutMap (CutMap &cutMap) const
 Gives back a minimum value cut.

Constructor & Destructor Documentation

EdmondsKarp ( const Digraph digraph,
const CapacityMap capacity,
Node  source,
Node  target 
) [inline]

The constructor of the class.

Parameters:
digraphThe digraph the algorithm runs on.
capacityThe capacity of the arcs.
sourceThe source node.
targetThe 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. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.

Returns:
(*this)
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) [inline]

Sets the tolerance used by algorithm.

Returns:
(*this)
const Tolerance& tolerance ( ) const [inline]

Returns a const reference to the tolerance object used by the algorithm.

void init ( ) [inline]

Initializes the internal data structures and sets the initial flow to zero on each arc.

void init ( const FlowMap flowMap) [inline]

Initializes the internal data structures and sets the initial flow to the given flowMap. The flowMap should contain a feasible flow, i.e. at each node excluding the source and the target, the incoming flow should be equal to the outgoing flow.

bool checkedInit ( const FlowMap flowMap) [inline]

Initializes the internal data structures and sets the initial flow to the given flowMap. The flowMap should contain a feasible flow, i.e. at 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 a feasible flow.
bool augment ( ) [inline]

Augments the solution along a shortest path. This function searches a shortest path between the source and the target in the residual digraph by the Bfs algoritm. Then it increases the flow on this path with the minimal residual capacity on the path. If there is no such path, it gives back false.

Returns:
false when the augmenting did not success, i.e. the current flow is a feasible and optimal solution.
void start ( ) [inline]

Executes the algorithm by performing augmenting phases until the optimal solution is reached.

Precondition:
One of the init() functions must be called before using this function.
void run ( ) [inline]

Runs the Edmonds-Karp algorithm.

Note:
ek.run() is just a shortcut of the following code.
        ek.init();
        ek.start();
Value flowValue ( ) const [inline]

Returns the value of the maximum flow found by the algorithm.

Precondition:
Either run() or init() must be called before using this function.
Value flow ( const Arc &  arc) const [inline]

Returns the flow value on the given arc.

Precondition:
Either run() or init() must be called before using this function.
const FlowMap& flowMap ( ) const [inline]

Returns a const reference to the arc map storing the found flow.

Precondition:
Either run() or init() must be called before using this function.
bool minCut ( const Node &  node) const [inline]

Returns true when the node is on the source side of the found minimum cut.

Precondition:
Either run() or init() must be called before using this function.
void minCutMap ( CutMap &  cutMap) const [inline]

Sets cutMap to the characteristic vector of a minimum value cut. cutMap should be a writable node map with bool (or convertible) value type.

Note:
This function calls minCut() for each node, so it runs in O(n) time.
Precondition:
Either run() or init() must be called before using this function.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines