CP-22356: SourceFirstTopologicalSortAlgorithm throws NonAcyclicGraphException

[fubar-coder]

From unknown CodePlex user on Tuesday, 06 March 2012 13:38:19

The following code makes SourceFirstTopologicalSortAlgorithm throws a NonAcyclicGraphException for no apparent reason:   BidirectionalGraph<string, Edge> graph = new BidirectionalGraph<string, Edge>(); graph.AddVerticesAndEdge(new Edge("1", "2")); graph.SourceFirstTopologicalSort();   The TopologicalSortAlgorithm appears to work properly.   gabriel

[fubar-coder]

Form unknown CodePlex user on Monday, 12 March 2012 16:14:33

The following code throws the same exception:

        var test = new AdjacencyGraph<string, Edge<string>>();
        test.AddVerticesAndEdgeRange(new[] 
        {
            new Edge<string>("A", "B"),
            new Edge<string>("A", "C"),
        });
        test.SourceFirstTopologicalSort();

It's seems SourceFirstTopologicalSort works unpredictable.

Dmitry.

[fubar-coder]

Form unknown CodePlex user on Wednesday, 19 March 2014 11:24:17

I believe this bug can be fixed by changing SourceFirstTopologicalSortAlgorithm.InitializeInDegrees() to something like

        private void InitializeInDegrees()
        {
            foreach (var v in this.VisitedGraph.Vertices)
            {
                this.inDegrees.Add(v, 0);
            }

            foreach (var e in this.VisitedGraph.Edges)
            {
                if (e.Source.Equals(e.Target))
                    continue;
                this.inDegrees[e.Target]++;
            }

            foreach (var v in this.VisitedGraph.Vertices)
            {
                this.heap.Enqueue(v);
            }
        }

The important thing being that inDegrees is fully initialised before heap.Enqueue() is called otherwise the internal priority queue doesn't sort the vertices correctly.