Broken EdmondsKarpMaximumFlowAlgorithm

[ktnr]

Thank you for continuing the development of QuickGraph!

A colleague of mine found an error in EdmondsKarpMaximumFlowAlgorithm. The current implementation computes wrong maximum flows. Consider the example from Wikipedia:

using QuickGraph;
using QuickGraph.Algorithms;
using System;
using System.Collections.Generic;
using QuickGraph.Algorithms.MaximumFlow;

namespace MaxFlowTest
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var graph = new AdjacencyGraph<string, TaggedEdge<string, double>>(true);

            graph.AddVertex("A");
            graph.AddVertex("B");
            graph.AddVertex("C");
            graph.AddVertex("D");
            graph.AddVertex("E");
            graph.AddVertex("F");
            graph.AddVertex("G");

            string source = "A";
            string sink = "G";

            // TaggedEdge.Tag is the capacity of the edge
            graph.AddEdge(new TaggedEdge<string, double>("A", "D", 3));
            graph.AddEdge(new TaggedEdge<string, double>("A", "B", 3));
            graph.AddEdge(new TaggedEdge<string, double>("B", "C", 4));
            graph.AddEdge(new TaggedEdge<string, double>("C", "A", 3));
            graph.AddEdge(new TaggedEdge<string, double>("C", "D", 1));
            graph.AddEdge(new TaggedEdge<string, double>("D", "E", 2));
            graph.AddEdge(new TaggedEdge<string, double>("D", "F", 6));
            graph.AddEdge(new TaggedEdge<string, double>("E", "B", 1));
            graph.AddEdge(new TaggedEdge<string, double>("C", "E", 2));
            graph.AddEdge(new TaggedEdge<string, double>("E", "G", 1));
            graph.AddEdge(new TaggedEdge<string, double>("F", "G", 9));

            // edgeFactory will be used to create the reversed edges to store residual capacities using the ReversedEdgeAugmentorAlgorithm-class.
            // The edgeFactory assigns a capacity of 0.0 for the new edges because the initial (residual) capacity must be 0.0.
            EdgeFactory<string, TaggedEdge<string, double>> edgeFactory = (sourceNode, targetNode) => new TaggedEdge<string, double>(sourceNode, targetNode, 0.0);

            MaximumFlowAlgorithm<string, TaggedEdge<string, double>> algo = new EdmondsKarpMaximumFlowAlgorithm<string, TaggedEdge<string, double>>(graph, edge => edge.Tag, edgeFactory);

            algo.Compute(source, sink);

            Console.WriteLine("MaxFlow: {0}", algo.MaxFlow); // algo.MaxFlow = 4 but it should be 5!
        }
    }
}

It yields a flow of 4, but it should be 5. The reason for this is that the check on line 87 of \QuickGraph\Algorithms\MaximumFlow\EdmondsKarpMaximumFlowAlgorithm.cs if (ReversedEdges != null && ReversedEdges.ContainsKey(e)) always evaluates to false because ReverseEdges is never assigned and is therefore null. This issue also affects \QuickGraph\Algorithms\MaximumBipartiteMatchingAlgorithm.

This issue can already be found on the archived version of QuickGraph (https://archive.codeplex.com/?p=quickgraph#), see https://github.com/FubarDevelopment/QuickGraph/issues/149#issue-331292856. In an earlier version of QuickGraph the constructor of EdmondsKarpMaximumFlowAlgorithm was overloaded with ReversedEdgeAugmentorAlgorithm, see Thread #59583 | Message #228725 | 2009-08-28 on https://archive.codeplex.com/?p=quickgraph, and should have worked as intended.

In the current version the issue can be fixed by changing the constructor from

public EdmondsKarpMaximumFlowAlgorithm(
    IAlgorithmComponent host,
    IMutableVertexAndEdgeListGraph<TVertex, TEdge> g,
    Func<TEdge,double> capacities,
    EdgeFactory<TVertex, TEdge> edgeFactory
    )
    : base(host, g, capacities, edgeFactory)
{
}

to

public EdmondsKarpMaximumFlowAlgorithm(
    IAlgorithmComponent host,
    IMutableVertexAndEdgeListGraph<TVertex, TEdge> g,
    Func<TEdge,double> capacities,
    EdgeFactory<TVertex, TEdge> edgeFactory
    )
    : base(host, g, capacities, edgeFactory)
{
    var reversedEdgeAugmentorAlgorithm = new ReversedEdgeAugmentorAlgorithm<TVertex, TEdge>(g, edgeFactory);

    reversedEdgeAugmentorAlgorithm.AddReversedEdges();
    ReversedEdges = reversedEdgeAugmentorAlgorithm.ReversedEdges;
}

A different fix is proposed in #185.

[ktnr]

Unit tests for EdmondsKarpMaximumFlow have passed before: https://ci.appveyor.com/project/gsvgit/quickgraph#L3812 Are the unit tests insufficient?

Unfortunately, I cannot debug the unit tests, I get a System.Xml.XmlException https://docs.microsoft.com/en-us/dotnet/api/system.xml.xmlreadersettings.prohibitdtd?redirectedfrom=MSDN&view=netframework-4.7.2 when running them.

[ktnr]

Can be closed. Edited the issue and created a new one for the case if TEdge is a value type, see #186.