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.