YaccConstructor / QuickGraph

Generic Graph Data Structures and Algorithms for .NET
http://yaccconstructor.github.io/QuickGraph/
Microsoft Public License
530 stars 198 forks source link

YenShortestPathsAlgorithm seems to not always produce correct results (version 3.7.3) #178

Open TomasJohansson opened 6 years ago

TomasJohansson commented 6 years ago

Here is an example with a small graph with 4 vertices (ABCD) and 5 edges which should produce 3 paths when going from A to D:

using NUnit.Framework;
using QuickGraph;
using QuickGraph.Algorithms.ShortestPath.Yen;
using System;
using System.Collections.Generic;
using System.Linq;

    [TestFixture]
    public class QuickGraphTest
    {
        [Test]
        public void Test()
        {
            // Version (retrieved with NuGet) used for this test:
            //  <package id="YC.QuickGraph" version="3.7.3" targetFramework="net472" />
            var graph = new AdjacencyGraph<string, TaggedEquatableEdge<string, double>>(false);
            graph.AddVertexRange(new List<string> { "A", "B", "C", "D" });
            graph.AddEdge(new TaggedEquatableEdge<string, double>("A", "B", 5));
            graph.AddEdge(new TaggedEquatableEdge<string, double>("A", "C", 6));
            graph.AddEdge(new TaggedEquatableEdge<string, double>("B", "C", 7));
            graph.AddEdge(new TaggedEquatableEdge<string, double>("B", "D", 8));
            graph.AddEdge(new TaggedEquatableEdge<string, double>("C", "D", 9));
            var yen = new YenShortestPathsAlgorithm<string>(graph, "A", "D", 5);
            // The three paths *should* be:
            // A -> B -> D (weight: 13 = 5 + 8)
            // A -> C -> D (weight: 15 = 6 + 9)
            // A -> B -> C -> D (weight: 21 = 5 + 7 + 9)
            var actualPaths = yen.Execute().ToList();
            foreach(var path in actualPaths)
            {
                var edges = path.ToList();
                Console.WriteLine();
                Console.Write(edges[0].Source);
                for(int i=0; i<edges.Count; i++) {
                    Console.Write(" -> " +edges[i].Target);
                }
            }
            // Output from above loops:
            //  A -> B -> D
            //  A -> C -> D
            // The last path is missing (i.e. A -> B -> C -> D)
            Assert.AreEqual(3, actualPaths.Count); // Failure: Expected: 3 But was:  2
        }
    }
KeRNeLith commented 4 years ago

Hello, I forked this QuickGraph repository (here) and made a fix to the Yen algorithm. And I made unit tests to assert such case will no longer be broken. Note that I also refactored a lot of the QuickGraph core library in the same time to make it .NET Core compliant.