public class EdmondsKarpMaximumFlowAlgorithm : MaximumFlowAlgorithm

Public Class EdmondsKarpMaximumFlowAlgorithm _
	Inherits MaximumFlowAlgorithm

The EdmondsKarpMaximumFlowAlgorithm class calculates the maximum flow of a network. The calculated maximum flow will be the return value of the function Compute(IVertex, IVertex). The function also calculates the flow values f[e] for all e in E, which are returned in the form of the residual capacity r[e] = c[e] - f[e].

There are several special requirements on the input graph and property map parameters for this algorithm. First, the directed graph G=(V,E) that represents the network must be augmented to include the reverse edge for every edge in E. That is, the input graph should be Gin = (V,{E U ET}). The reversedEdges argument must map each edge in the original graph to its reverse edge, that is e=(u,v) -> (v,u) for all e in E. The capacities argument must map each edge in E to a positive number, and each edge in ET to 0.

The algorithm is due to Edmonds and Karp, though we are using the variation called the labeling algorithm described in Network Flows.

This algorithm provides a very simple and easy to implement solution to the maximum flow problem. However, there are several reasons why this algorithm is not as good as the PushRelabelMaximumFlowAlgorithm algorithm.

In the non-integer capacity case, the time complexity is O(V E^2) which is worse than the time complexity of the PushRelabelMaximumFlowAlgorithm O(V^2E^1/2) for all but the sparsest of graphs.

In the integer capacity case, if the capacity bound U is very large then the algorithm will take a long time.

System..::.Object
  QuickGraph.Algorithms.MaximumFlow..::.MaximumFlowAlgorithm
    QuickGraph.Algorithms.MaximumFlow..::.EdmondsKarpMaximumFlowAlgorithm