Search code examples
javagraphjgrapht

Identifying disjoined graphs in JgraphT

I have a use case as below. I need to construct a graph from a set of input as below -

SimpleDirectedGraph<String, DefaultEdge> g = new SimpleDirectedGraph<>(DefaultEdge.class);
g.addVertex("APP");
g.addVertex("CHROME");
g.addVertex("MOZILLA");
g.addVertex("LAPTOP");
g.addVertex("SERVER");
g.addVertex("CHROME_DEV");
g.addVertex("MOZILLA_DEV");
g.addVertex("APP_DEV");

Add edges for Server

g.addEdge("SERVER", "APP");
g.addEdge("SERVER", "CHROME");
g.addEdge("SERVER", "MOZILLA");

Add edges for Laptop

g.addEdge("LAPTOP", "APP_DEV");
g.addEdge("LAPTOP", "CHROME_DEV");
g.addEdge("LAPTOP", "MOZILLA_DEV");

Add Connecting edges between these 2 sets

g.addEdge("CHROME", "CHROME_DEV");
g.addEdge("MOZILLA", "MOZILLA_DEV");

Now i can construct a graph like this and the structure will looks something as below -

enter image description here

But my use starts here. Imagine i have removed the connecting edges from the graph above

g.removeEdge("CHROME", "CHROME_DEV");
g.removeEdge("MOZILLA", "MOZILLA_DEV");

Now my graph is essentially disjoint from each other. How do I find out it is disjoint graphs and how to get both the disjoint graphs. I will have to treat these two disjoint graphs separately here after.

Solution

  • What you are looking for is called 'connected components'. Have a look at the ConnectivityInspector.

    To test whether your graph is connected:

    Graph<String, DefaultEdge> g = new SimpleDirectedGraph<>(DefaultEdge.class);
ConnectivityInspector ci = new ConnectivityInspector(g);
//Test whether the graph is connected:
ci.isConnected();

    You can get the vertices of each of the connected components using: Set<String> vertexSets = ci.connectedSets(); For each of these sets, you can then create a graph induced on these vertices:

    Set<String> vertexSets = ci.connectedSets();
for(Set<String> vertexSet : vertexSets){
    Graph<String, DefaultEdge> subgraph = new AsSubGraph(g,vertexSet);
    //Do something with the subgraph
}

    More information on graph connectivity can be found here. For the purpose of your question you could also look into the difference between 'strongly' and 'weakly' connected components.