EdmondsKarp Class Template Reference
[Path and Flow Algorithms]

#include <lemon/edmonds_karp.h>

List of all members.


Detailed Description

template<typename _Graph, typename _Number, typename _CapacityMap, typename _FlowMap, typename _Tolerance>
class lemon::EdmondsKarp< _Graph, _Number, _CapacityMap, _FlowMap, _Tolerance >

This class provides an implementation of the Edmonds-Karp algorithm producing a flow of maximum value in a directed graph. 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 $ O(n * e^2) $ 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.
_Number The number type of the capacities and the flow values.
_CapacityMap The capacity map type.
_FlowMap The flow map type.
_Tolerance The tolerance class to handle computation problems.
Author:
Balazs Dezso


Public Types

typedef _Graph Graph
 The graph type the algorithm runs on.
typedef _Number Number
 The value type of the algorithms.
typedef _CapacityMap CapacityMap
 The capacity map on the edges.
typedef _FlowMap FlowMap
 The flow map on the edges.
typedef _Tolerance Tolerance
 The tolerance used by the algorithm.

Public Member Functions

 EdmondsKarp (const Graph &graph, Node source, Node target, const CapacityMap &capacity, FlowMap &flow, const Tolerance &tolerance=Tolerance())
 The constructor of the class.
void init ()
 Initializes the algorithm.
void flowInit ()
 Initializes the algorithm.
bool checkedFlowInit ()
 Initializes the algorithm.
bool augment ()
 Augment the solution on an edge shortest path.
void start ()
 Executes the algorithm.
Number flowValue () const
 Gives back the current flow value.
void run ()
 runs the algorithm.
template<typename CutMap>
void minCut (CutMap &cut) const
 Returns a minimum value cut.
template<typename CutMap>
void minMinCut (CutMap &cut) const
 Returns the inclusionwise minimum of the minimum value cuts.
template<typename CutMap>
void maxMinCut (CutMap &cut) const
 Returns the inclusionwise minimum of the minimum value cuts.
Node source () const
 Returns the source node.
Node target () const
 Returns the target node.
const CapacityMapcapacityMap () const
 Returns a reference to capacity map.
const FlowMapflowMap () const
 Returns a reference to flow map.
const Tolerancetolerance () const
 Returns the tolerance used by algorithm.

Classes

class  InvalidArgument
 Exception for the case when the source equals the target. More...


Constructor & Destructor Documentation

EdmondsKarp ( const Graph graph,
Node  source,
Node  target,
const CapacityMap capacity,
FlowMap flow,
const Tolerance tolerance = Tolerance() 
) [inline]

The constructor of the class.

Parameters:
graph The directed graph the algorithm runs on.
source The source node.
target The target node.
capacity The capacity of the edges.
flow The flow of the edges.
tolerance Tolerance class.


Member Function Documentation

void init (  )  [inline]

It sets the flow to empty flow.

void flowInit (  )  [inline]

If the flow map initially flow this let the flow map unchanged but the flow value will be set by the flow on the outedges from the source.

bool checkedFlowInit (  )  [inline]

If the flow map initially flow this let the flow map unchanged but the flow value will be set by the flow on the outedges from the source. It also checks that the flow map really contains a flow.

Returns:
True when the flow map really a 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.

Number flowValue (  )  const [inline]

Gives back the current flow _value.

void run (  )  [inline]

It is just a shorthand for:

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

void minCut ( CutMap &  cut  )  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.

void minMinCut ( CutMap &  cut  )  const [inline]

Sets cut to the characteristic vector of the minimum value cut which is inclusionwise minimum. It is computed by processing a bfs from the source node source in the residual graph.

Return values:
cut Write node bool map.

void maxMinCut ( CutMap &  cut  )  const [inline]

Sets cut to the characteristic vector of the minimum value cut which is inclusionwise minimum. It is computed by processing a bfs from the source node source in the residual graph.

Return values:
cut Write node bool map.

Node source (  )  const [inline]

Returns the source node.

Node target (  )  const [inline]

Returns the target node.

const CapacityMap& capacityMap (  )  const [inline]

Returns a reference to capacity map.

const FlowMap& flowMap (  )  const [inline]

Returns a reference to flow map.

const Tolerance& tolerance (  )  const [inline]

Returns the tolerance used by algorithm.


The documentation for this class was generated from the following file:
Generated on Tue Oct 31 09:50:10 2006 for LEMON by  doxygen 1.5.1