Loading...
Searching...
No Matches
EdmondsKarp< GR, CAP, TR > Class Template Reference
Algorithms » Maximum Flow Algorithms

## 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 [clrs01algorithms], [amo93networkflows], [edmondskarp72theoretical]. 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 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.

`#include <lemon/edmonds_karp.h>`

## Classes

struct | SetFlowMap
| Named parameter for setting FlowMap type More...

## 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 ()
| Destructor.
EdmondsKarp & | capacityMap (const CapacityMap &map)
| Sets the capacity map.
EdmondsKarp & | flowMap (FlowMap &map)
| Sets 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)
| Sets the tolerance used by algorithm.
const Tolerance & | tolerance () const
| Returns a const reference to the tolerance.
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.
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 FlowMap & | flowMap () 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()

template<typename GR, typename CAP, typename TR>

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

inline

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.

## ~EdmondsKarp()

template<typename GR, typename CAP, typename TR>

~EdmondsKarp | ( |  | ) |

inline

Destructor.

## Member Function Documentation

## capacityMap()

template<typename GR, typename CAP, typename TR>

EdmondsKarp & capacityMap | ( | const CapacityMap & | map | ) |

inline

Sets the capacity map.

Returns
  (*this)

## flowMap() [1/2]

template<typename GR, typename CAP, typename TR>

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)

## source()

template<typename GR, typename CAP, typename TR>

EdmondsKarp & source | ( | const Node & | node | ) |

inline

Sets the source node.

Returns
  (*this)

## target()

template<typename GR, typename CAP, typename TR>

EdmondsKarp & target | ( | const Node & | node | ) |

inline

Sets the target node.

Returns
  (*this)

## tolerance() [1/2]

template<typename GR, typename CAP, typename TR>

EdmondsKarp & tolerance | ( | const Tolerance & | tolerance | ) |

inline

Sets the tolerance used by algorithm.

Returns
  (*this)

## tolerance() [2/2]

template<typename GR, typename CAP, typename TR>

const Tolerance & tolerance | ( |  | ) | const

inline

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

## init() [1/2]

template<typename GR, typename CAP, typename TR>

void init | ( |  | ) |

inline

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

## init() [2/2]

template<typename GR, typename CAP, typename TR>
template<typename FlowMap>

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.

## checkedInit()

template<typename GR, typename CAP, typename TR>
template<typename FlowMap>

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.

## augment()

template<typename GR, typename CAP, typename TR>

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.

## start()

template<typename GR, typename CAP, typename TR>

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.

## run()

template<typename GR, typename CAP, typename TR>

void run | ( |  | ) |

inline

Runs the Edmonds-Karp algorithm.

Note
  ek.run() is just a shortcut of the following code.
  ek.init();
  ek.start();

## flowValue()

template<typename GR, typename CAP, typename TR>

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.

## flow()

template<typename GR, typename CAP, typename TR>

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.

## flowMap() [2/2]

template<typename GR, typename CAP, typename TR>

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.

## minCut()

template<typename GR, typename CAP, typename TR>

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.

## minCutMap()

template<typename GR, typename CAP, typename TR>
template<typename CutMap>

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.