CP-25751: Finding Disconnected Subgraphs or Components

[fubar-coder]

From unknown CodePlex user on Monday, 29 September 2014 06:04:04

In my graphs, I generally have at least two completely disconnected subgraphs or components. These components may be of 1 or N vertices. I can easily detect orphans, but not components.

Orphans are easy:

myGraph.Vertices.Where(v => myGraph.InDegree(v) == 0)

I have no idea how to get the disconnected components. Ideally, I'd like to return an IEnumerable<BidirectionalGraph> from myGraph which is BidirectionalGraph.

[fubar-coder]

Form unknown CodePlex user on Wednesday, 29 October 2014 14:14:18

I would be very interested by this feature, and I did not find how to do it yet.

It seems like the function does part of the job:
Func<KeyValuePair<int, IDictionary<DataVertex, int>>> components = AlgorithmExtensions.IncrementalConnectedComponents(graph);
var current = components();

By examining current, you see vertices that share the same branches (see value index).
But it does not give directly the list of sub-graphs: IEnumerable<BidirectionalGraph>

Maybe the weaklyConnectedComponents, and condensateWeaklyConnected extensions can do the job.
I haven't been able to implement any of them.

The following code casts an error.
var weaklyCondensated= g.CondensateWeaklyConnected<Vertex,Edge,GraphType>();

I would be very interested to have a solution for this.
Thanks a lot

[fubar-coder]

Form unknown CodePlex user on Wednesday, 29 October 2014 15:07:31

Actually for those interested there is a solution given in another post.
-> Solution given in the comments to solve the bug in "CondensationGraphAlgorithm".

One it is solved (I tried by adding a CondensationGraphAlgorithm2 in a new class, with the corrected code), you can get what you want like this (it is basically the code of "g.CondensateWeaklyConnected" actually!)

var condensator = new QuickGraph.Algorithms.Condensation.CondensationGraphAlgorithm2<DataVertex, DataEdge, CalculationEngineGraph>(this.CalculationEngineGraph);
condensator.StronglyConnected = false;
condensator.Compute(); // Throws KeyNotFoundException if edgeless vertex is added
var condensed = condensator.CondensedGraph;

It should be simple to correct the code. I don't know if only the owner of the project can change it.