YaccConstructor / QuickGraph

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

CompressedSparseRow bug #169

Open AwesomeLemon opened 7 years ago

AwesomeLemon commented 7 years ago

While looking through sources in file https://github.com/YaccConstructor/QuickGraph/blob/master/src/QuickGraph/CompressedSparseRowGraph.cs I've noticed that the method FromGraph seems likely not to work due to the fact that start variable isn't updated after initialization.

I've confirmed my suspicions: I've run Topological sort on adjacency graph (it turned out OK), then converted that graph to CSR and run on that - it throws QuickGraph.NonAcyclicGraphException

Sample code:

            // a simple adjacency graph representation
            int[][] graph = new int[5][];
            graph[0] = new int[] {  };
            graph[1] = new int[] { 2, 3 };
            graph[2] = new int[] { 3, 0 };
            graph[3] = new int[] { 0 };
            graph[4] = new int[] { 1 };

            // interoping with quickgraph
            var g = GraphExtensions.ToDelegateVertexAndEdgeListGraph(
                Enumerable.Range(0, graph.Length),
                v => Array.ConvertAll(graph[v], w => new SEquatableEdge<int>(v, w))
            );

            // it's ready to use!
            foreach (var v in g.TopologicalSort())
                Console.WriteLine(v);

            var csr = CompressedSparseRowGraph<int>.FromGraph(g);
            foreach (var vertex in csr.TopologicalSort())
            {
                Console.WriteLine(vertex);
            }

P.S. It turned out that there's no sense for me in using QuickGraph's CSR anyway, so I just want to report this.

KeRNeLith commented 4 years ago

I made a fix for this (there) and also unit tests in this fork of the library (with also a lot of others fixes and .NET Core compliance).