private static void TestMaximumFlowEdmondsKarp()
{
//Graph taken from http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
//We need a graph, a source and a sink
IMutableVertexAndEdgeListGraph<string, SEdge<string>> graph = new AdjacencyGraph<string, SEdge<string>>(true);
//Add some vertices to the graph
graph.AddVertex("A");
graph.AddVertex("B");
graph.AddVertex("C");
graph.AddVertex("D");
graph.AddVertex("E");
graph.AddVertex("F");
graph.AddVertex("G");
// Create the edges
SEdge<string> a_b = new SEdge<string>("A", "B");
SEdge<string> a_d = new SEdge<string>("A", "D");
SEdge<string> b_c = new SEdge<string>("B", "C");
SEdge<string> c_a = new SEdge<string>("C", "A");
SEdge<string> c_d = new SEdge<string>("C", "D");
SEdge<string> c_e = new SEdge<string>("C", "E");
SEdge<string> d_e = new SEdge<string>("D", "E");
SEdge<string> d_f = new SEdge<string>("D", "F");
SEdge<string> e_b = new SEdge<string>("E", "B");
SEdge<string> e_g = new SEdge<string>("E", "G");
SEdge<string> f_g = new SEdge<string>("F", "G");
// Add the edges
graph.AddEdge(a_b);
graph.AddEdge(a_d);
graph.AddEdge(b_c);
graph.AddEdge(c_a);
graph.AddEdge(c_d);
graph.AddEdge(c_e);
graph.AddEdge(d_e);
graph.AddEdge(d_f);
graph.AddEdge(e_b);
graph.AddEdge(e_g);
graph.AddEdge(f_g);
// Define some weights to the edges
Dictionary<SEdge<string>, double> edgeCapacityDictionary = new Dictionary<SEdge<string>, double>(graph.EdgeCount);
edgeCapacityDictionary.Add(a_b, 3);
edgeCapacityDictionary.Add(a_d, 3);
edgeCapacityDictionary.Add(b_c, 4);
edgeCapacityDictionary.Add(c_a, 3);
edgeCapacityDictionary.Add(c_d, 1);
edgeCapacityDictionary.Add(c_e, 2);
edgeCapacityDictionary.Add(d_e, 2);
edgeCapacityDictionary.Add(d_f, 6);
edgeCapacityDictionary.Add(e_b, 1);
edgeCapacityDictionary.Add(e_g, 1);
edgeCapacityDictionary.Add(f_g, 9);
//A function which maps an edge to its capacity
Func<SEdge<string>, double> edgeCapacity = AlgorithmExtensions.GetIndexer(edgeCapacityDictionary);
//A function which takes a vertex and returns the edge connecting to its predecessor in the flow network
TryFunc<string, SEdge<string>> flowPredecessors;
//A function used to create new edges during the execution of the algorithm. These edges are removed before the computation returns
EdgeFactory<string, SEdge<string>> edgeFactory = (source, target) => new SEdge<string>(source, target);
var flow = graph.MaximumFlowEdmondsKarp(
edgeCapacity,
"A",
"G",
out flowPredecessors,
edgeFactory);
Console.WriteLine("The MaximumFlowEdmondsKarp result is {0}", flow);
}
From unknown CodePlex user on Thursday, 25 September 2014 10:05:36
The following code produces a max flow of 4 when I believe the correct value should be 5. Can anyone confirm that this is indeed a QuickGraph issue?
The graph is taken from http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm