CP-23392: CondensationAlgorithm throws KeyNotFoundException

[fubar-coder]

From unknown CodePlex user on Wednesday, 19 September 2012 02:13:22

QuickGraph.Algorithms.Condensation.CondensationGraphAlgorithm fails on Compute() for weaklyconnected components if input is a graph containing Vertices without edges   [Test] public void TestWeaklyConnectedComponents() { var graph = new BidirectionalGraph<int, Edge>(); graph.AddVerticesAndEdge(new Edge(1, 2)); graph.AddVerticesAndEdge(new Edge(2, 3)); graph.AddVerticesAndEdge(new Edge(4, 5)); graph.AddVerticesAndEdge(new Edge(4, 6)); graph.AddVerticesAndEdge(new Edge(7, 1)); //graph.AddVertex(8); // uncomment me to reproduce error   var condensed = new QuickGraph.Algorithms.Condensation.CondensationGraphAlgorithm<int, Edge, BidirectionalGraph<int, Edge>>(graph); condensed.StronglyConnected = false; condensed.Compute(); // Throws KeyNotFoundException if edgeless vertex is added }

[fubar-coder]

Form unknown CodePlex user on Thursday, 09 January 2014 07:11:58

I have resolved this issue. WeaklyConnectedComponentsAlgorithm returns components.Values in series not in all cases. The update may cause the values ​​will not in series.

            // updating component numbers
            foreach (var v in this.VisitedGraph.Vertices)
            {
                int component = this.components[v];
                int equivalent = this.GetComponentEquivalence(component);
                if (component != equivalent)
                    this.components[v] = equivalent;
            }

Replace this code in the file CondensationGraphAlgorithm.cs

            for (int i = 0; i < componentCount; ++i)
            {
                TGraph v = new TGraph();
                condensatedVertices.Add(i, v);
                this.condensedGraph.AddVertex(v);
            }

to

            var componentsNumbers = components.Values.Distinct();
            foreach (var componentsNumber in componentsNumbers)
            {
                TGraph v = new TGraph();
                condensatedVertices.Add(componentsNumber, v);
                this.condensedGraph.AddVertex(v);
            }