Maximum Flow

Maximum Flow

The Edmonds 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 which 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);

// Reversed edge augmentor
var reversedEdgeAugmentorAlgorithm = new ReversedEdgeAugmentorAlgorithm<TVertex, TEdge>(graph, edgeFactory);
reversedEdgeAugmentorAlgorithm.AddReversedEdges();

// Computing the maximum flow using Edmonds Karp.
double flow = graph.MaximumFlow<TVertex, TEdge>(
    capacityFunc,
    source, sink,
    out flowPredecessors,
    edgeFactory,
    reversedEdgeAugmentorAlgorithm);
    
reversedEdgeAugmentorAlgorithm.RemoveReversedEdges();