Tracking the Connected Components

Jan 26, 2009 at 4:14 PM
Hi,

I want to keep an eye on the connectivity of my graph when adding nodes and edges. So I call the method StronglyConnectedComponents many times. The code looks like this:

int

componentCount = _QRoadmap.StronglyConnectedComponents<RoadmapNode,TaggedEdge<RoadmapNode,double>>(out components);

Is there a way to do this more efficiently ?

Regards,
Stephan

 

 

Coordinator
Jan 27, 2009 at 5:12 PM
Is the graph growing, i.e. only edge added, or some edges are removed as well. This is an important details on which algorithm to use.

QuickGraph already has a disjointset datastructure, which is the building block of incremental connected components (http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/incremental_components.html).
Coordinator
Jan 27, 2009 at 7:30 PM
Added a (untested) incremental component algorithm. Use 

    // key = component count, value = vertex => component indexmap
    Func<KeyValuePair<int, IDictionary<TVertex,int>>> computeComponents = AlgorithmExtensions.IncrementalComponents(g);
    ...
    var components = computeComponents();
       
Jan 28, 2009 at 8:03 AM
Great I think this will suit my requirements very well.
Because I am only adding new Edges and myvbe some Vertices and I don't remove edges.
So I will try your incremental extension.

Jan 28, 2009 at 1:07 PM
I tried your incremental algorithm and I get not what I thought I should get.
I have a graph with 500 vertices and no edges. When I call the Compute()-Method it returns a key-value-pair with the key=499.
The value is a dictionary with my 500 vertices as the keys and all the values set to 0.
So it seems like the graph consists of on connected component instead of 500 connected components...
Coordinator
Jan 29, 2009 at 2:01 AM
Ooops. Forgot to update the index. Should work now, but still needs tests.