ArrayBidirectionalGraph fails with ShortestPathsDijkstra

Topics: algorithm, bug
Oct 1, 2010 at 9:58 AM

Hi,

Please consider this example :

 

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

public class MyEdge : IEdge<int>
{
    public int ID { get; set; }
    public int Source { get; set; }
    public int Target { get; set; }
    public MyEdge(int id, int source, int target)
    {
        Source = source;
        Target = target;
        ID = id;
    }
}

public class Test
{
    public void test()
    {
        IEnumerable<MyEdge> resPath1 = null;
        IEnumerable<MyEdge> resPath2 = null;

        BidirectionalGraph<int, MyEdge> g = new BidirectionalGraph<int, MyEdge>();
        g.AddVertex(1);
        g.AddVertex(2);
        g.AddVertex(3);
        g.AddEdge(new MyEdge(89, 1, 2));
        g.AddEdge(new MyEdge(90, 2, 3));
        int vSource = 1;
        int vTarget = 3;

        var tryGetPath1 = AlgorithmExtensions.ShortestPathsDijkstra(g.ToArrayBidirectionalGraph(), e => 1, vSource);
        tryGetPath1(vTarget, out resPath1);

        var tryGetPath2 = AlgorithmExtensions.ShortestPathsDijkstra(g, e => 1, vSource);
        tryGetPath2(vTarget, out resPath2);

        bool ko = (resPath1 == null && resPath2 != null) || (resPath1 != null && resPath2 == null);

        System.Diagnostics.Debugger.Break();
    }
}

resPath1 and resPath2 should represent the same path but it's not the case : ShortestPathsDijkstra always return a null path when using ArrayBidirectionalGraph.

Any idea ?
Thanks