Broken EdmondsKarpMaximumFlowAlgorithm
ktnr opened this issue · 2 comments
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 FubarDevelopment/QuickGraph#149 (comment). 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.
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.