|
| | 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.
|
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 > |
| bool | 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.
|
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.
|
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 [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. |
template< typename GR , typename CAP , typename TR >
| bool 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, 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 GR , typename CAP , typename TR >
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.