This project is read-only.

Maximum Flow

The Edmond and Karp algorithm computes a maximum flow for directed graph with positive capacities and flows.

// we need a graph, a source and a sink
IMutableVertexAndEdgeListGraph<TVertex,TEdge> graph = ...;
TVertex source = ...;
TVertex sink = ...;

// A function with maps an edge to its capacity
Func<TEdge, double> capacityFunc = (edge => 1);

// A function which takes a vertex and returns the edge connecting to its predecessor in the flow network
TryFunc<TVertex, TEdge> flowPredecessors;

// A function used to create new edges during the execution of the algorithm.  These edges are removed before the computation returns
EdgeFactory<TVertex, TEdge> edgeFactory = (source, target) => new Edge<TVertex>(source,target);

// computing the maximum flow using Edmonds Karp.
double flow = AlgorithmExtensions.MaximumFlowEdmondsKarp<TVertex, TEdge>(
    graph,
    capacityFunc,
    source, sink,
    out flowPredecessors,
    edgeFactory);

Last edited Aug 13, 2010 at 12:17 AM by rhennig, version 4

Comments

thesnark Sep 25, 2014 at 5:48 PM 
I have found the same thing. Latest version of QuickGraph for the MaximumFlowEdmondsKarp gives a 4 where it should be a 5 for the netowrk described http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm This is a show stopper for me :(

ARMENHOV Nov 20, 2011 at 5:30 AM 
Maxflow of network from http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm is 5 , but i get answer 4 from MaximumFlowEdmondsKarp

ARMENHOV Dec 12, 2010 at 6:34 PM 
apology
Last version of MaximumFlowEdmondsKarp dont work correct