EdmondsKarp

Declared in lemon/edmonds_karp.h, in the group Maximum Flow Algorithms; the same class on the Doxygen site.

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

Edmonds-Karp algorithms class.

This class provides an implementation of the Edmonds-Karp algorithm producing a flow of maximum value in a digraph [7], [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 and the capacity of the arcs are passed to the constructor, and a starting flow, if any, to init().

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:
  • GR – The type of the digraph the algorithm runs on.

  • CAP – The type of the capacity map. The default map type is GR::ArcMap< int >.

  • TR – The 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.

Execution control

The simplest way to execute the algorithm is to use .\n 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.

inline void init()

Initializes the algorithm.

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

template< typename FlowMap >
inline bool init( const FlowMap & flowMap )

Initializes the algorithm using the given flow map.

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, and on each arc the flow should be within zero and the capacity, as Preflow checks.

Returns:

false when the given flowMap does not contain a feasible flow, with the tolerance of the algorithm; the flow is set in any case.

template< typename FlowMap >
inline bool checkedInit( const FlowMap & flowMap )

Initializes the algorithm using the given flow map.

The same as init( const FlowMap & ), which checks the flow as well, kept under its old name.

Returns:

false when the given flowMap does not contain a feasible flow.

inline bool augment()

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.

inline void start()

Executes the algorithm.

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

Pre:

One of the init() functions must be called before using this function.

inline void run()

Runs the algorithm.

Runs the Edmonds-Karp algorithm.

Note

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

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

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.

inline Value flowValue() const

Returns the value of the maximum flow.

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

Pre:

Either run() or init() must be called before using this function.

inline Value flow( const Arc & arc ) const

Returns the flow value on the given arc.

Pre:

Either run() or init() must be called before using this function.

inline const FlowMap & flowMap() const

Returns a const reference to the flow map.

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

Pre:

Either run() or init() must be called before using this function.

inline bool minCut( const Node & node ) const

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

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

Pre:

The last call of augment() must have returned false, as at the end of run() and start(): the cut is the set of the nodes that its search reached.

template< typename CutMap >
inline void minCutMap( CutMap & cutMap ) const

Gives back a minimum value cut.

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.

Pre:

As for minCut().

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.

typedef EdmondsKarp Create

Public Functions

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

The constructor of the class.

Parameters:
  • digraph – The digraph the algorithm runs on.

  • capacity – The capacity of the arcs.

  • source – The source node.

  • target – The target node.

inline ~EdmondsKarp()

Destructor.

inline EdmondsKarp & capacityMap( const CapacityMap & map )

Sets the capacity map.

Returns:

(*this)

inline EdmondsKarp & flowMap( FlowMap & map )

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)

inline EdmondsKarp & source( const Node & node )

Sets the source node.

Returns:

(*this)

inline EdmondsKarp & target( const Node & node )

Sets the target node.

Returns:

(*this)

inline EdmondsKarp & tolerance( const Tolerance & tolerance )

Sets the tolerance used by algorithm.

Returns:

(*this)

inline const Tolerance & tolerance() const

Returns a const reference to the tolerance.

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

Protected Functions

inline EdmondsKarp()
template< typename T >
struct SetFlowMapTraits : public Traits

Public Types

typedef T FlowMap

Public Static Functions

static inline FlowMap * createFlowMap( const Digraph & )
template< typename T >
struct SetFlowMap : public EdmondsKarp< Digraph , CapacityMap , SetFlowMapTraits< T > >

Named parameter for setting FlowMap type

Public Types

typedef EdmondsKarp< Digraph , CapacityMap , SetFlowMapTraits< T > > Create