2
Vote

Finding Disconnected Subgraphs or Components

description

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<T>> from myGraph which is BidirectionalGraph<T>.

comments

bobby751 wrote Oct 29, 2014 at 10:14 PM

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<T>>


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

bobby751 wrote Oct 29, 2014 at 11:07 PM

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.