CP-25748: Is MaximumFlowEdmondsKarp Broken?

[fubar-coder]

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

        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);
        }