Using JUNG to find disconnected sub graph in a graph

Question

I have created a graph using JUNG in java

Graph<Integer, String> g;
public SimpleGraphView2() {
    // Graph<V, E> where V is the type of the vertices and E is the type of the edges

    g = new SparseGraph<Integer, String>();
    // Add some vertices. From above we defined these to be type Integer.
    g.addVertex((Integer)1);
    g.addVertex((Integer)2);
    g.addVertex((Integer)3); 
    g.addVertex((Integer)4); 
    g.addVertex((Integer)5); 
    g.addVertex((Integer)6); 
    g.addVertex((Integer)7);
    g.addVertex((Integer)8); 

    g.addEdge("A", 1, 2);
    g.addEdge("B", 2, 3);  
    g.addEdge("C", 2, 4); 
    g.addEdge("D", 4, 5); 
    g.addEdge("E", 1, 3); 
    g.addEdge("F", 6, 7); 
    g.addEdge("G", 7, 8); 
}

I want to find the number of disconnected graphs in my created graph g . So in my case , I want an output of 2 (the 1st graph contain:1,2,3,4,5. The 2nd contain:6,7,8). Any help would be appreciated

Answer 1

Joshua gave you the correct answer. An example would be:

Transformer<Graph<V,E>, Set<Set<V>>> trns = new WeakComponentClusterer<V,E>();
Set<Set<V>> clusters = trns.transform(graph);

This will give you clusters which is a Set (collection) of Sets of vertices. Basically, it will look like:

{                                                    <---+
   {1,2,3},{4,5},       <--- a set of vertices           |
   {1,2},{3},{5},                                        |- a set of sets
   {1},{2,3,4},                                          |
   ...                                                   |
}                                                    <---+

As an aside, the speed of this algorithm will depend on the number of vertices you have (as you correctly stated) as well as the number of edges. But 100,000 vertices shouldn't be a limiting factor.

Answer 2

You want WeakComponentClusterer: http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/cluster/WeakComponentClusterer.html

Answer 3

Simple BFS will give you the answer...start your BFS from any node you will find all the nodes reachable from it..then again start BFS from another another node which has not been visited and so on...