Connectivity

Algorithms

Testing connectivity and finding connected components are classic tasks when working with graphs. Recall that depending on whether the graph is directed or not, we have two different notions of connectivity, i.e. strong and weak connectivity.

jgrapht.algorithms.connectivity.is_connected(graph)

Compute connected components of a graph.

For directed graphs this method computed strongly connected components.

Parameters

graph – the graph. Must be directed

Returns

a tuple containing a boolean value on whether the graph is connected and an iterator over all connected components. Each component is represented as a vertex set

jgrapht.algorithms.connectivity.is_strongly_connected_gabow(graph)

Computes strongly connected components in a directed graph.

This is Cheriyan-Mehlhorn/Gabow’s algorithm and can be found at:

• Gabow, Harold N. “Path-Based Depth-First Search for Strong and Biconnected Components; CU-CS-890-99.” (1999).

Running time \(\mathcal{O}(n+m)\).

Parameters

graph – the graph. Must be directed

Returns

a tuple containing a boolean value on whether the graph is strongly connected and an iterator over all connected components. Each component is represented as a vertex set

jgrapht.algorithms.connectivity.is_strongly_connected_kosaraju(graph)

Computes strongly connected components in a directed graph.

This is an implementation based on:

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.

Running time \(\mathcal{O}(n+m)\).

Parameters

graph – the graph. Must be directed

Returns

a tuple containing a boolean value on whether the graph is strongly connected and an iterator over all connected components. Each component is represented as a vertex set

jgrapht.algorithms.connectivity.is_weakly_connected(graph)

Computes weakly connected components in a directed graph or

connected components in an undirected graph.

This is a simple BFS based implementation.

Running time \(\mathcal{O}(n+m)\).

Parameters

graph – the graph.

Returns

a tuple containing a boolean value on whether the graph is connected and an iterator over all connected components. Each component is represented as a vertex set