org.jgrapht.alg.connectivity

Class BiconnectivityInspector<V,E>

java.lang.Object

org.jgrapht.alg.connectivity.BiconnectivityInspector<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

public class BiconnectivityInspector<V,E>
extends Object

Allows obtaining various connectivity aspects of a graph. The inspected graph is specified at construction time and cannot be modified. No restrictions are imposed on the input graph. Multigraphs and pseudographs are also supported. The inspector traverses connected components (undirected graphs) or weakly connected components (directed graphs). To find strongly connected components, use KosarajuStrongConnectivityInspector instead. This class offers an alternative implementation of some of the functionality encountered in ConnectivityInspector. It is likely to perform somewhat slower than ConnectivityInspector, but offers more functionality in return.

The algorithm implemented in this class is Hopcroft and Tarjan's biconnected components algorithm, described in: Hopcroft, J. Tarjan, R. Algorithm 447: efficient algorithms for graph manipulation, 1973. Communications of the ACM. 16 (6): 372–378. This implementation runs in linear time $O(|V|+|E|)$ and is based on a recursive depth-first search. More information about this subject be be found in this wikipedia article.

The inspector methods work in a lazy fashion: no computations are performed unless immediately necessary. Computation are done once and results are cached within this class for future need. The core of this class is built around a recursive Depth-first search.

Author:

Joris Kinable

Constructor Summary

Constructors

Constructor and Description
BiconnectivityInspector(Graph<V,E> graph) Constructs a new BiconnectivityInspector

Method Summary

Modifier and Type	Method and Description
Set<Graph<V,E>>	getBlocks() Returns all blocks (biconnected components) in the graph.
Set<Graph<V,E>>	getBlocks(V vertex) Returns a set of blocks (biconnected components) containing the specified vertex.
Set<E>	getBridges() Returns the graph's bridges.
Graph<V,E>	getConnectedComponent(V vertex) Returns the connected component containing the given vertex.
Set<Graph<V,E>>	getConnectedComponents() Returns all connected components in the graph.
Set<V>	getCutpoints() Returns the cutpoints (articulation points) of the graph.
boolean	isBiconnected() Tests if the inspected graph is biconnected.
boolean	isConnected() Test if the inspected graph is connected.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BiconnectivityInspector

public BiconnectivityInspector(Graph<V,E> graph)

Constructs a new BiconnectivityInspector

Parameters:

graph - the input graph

Method Detail

getCutpoints

public Set<V> getCutpoints()

Returns the cutpoints (articulation points) of the graph. A vertex is a cutpoint if removal of that vertex (and all edges incident to that vertex) would increase the number of (weakly) connected components in the graph.

Returns:

the cutpoints of the graph

getBridges

public Set<E> getBridges()

Returns the graph's bridges. An edge is a bridge if removal of that edge would increase the number of (weakly) connected components in the graph. Note that this definition remains applicable in case of multigraphs or pseudographs.

Returns:

the graph's bridges

getBlocks

public Set<Graph<V,E>> getBlocks(V vertex)

Returns a set of blocks (biconnected components) containing the specified vertex. A block is a maximal biconnected subgraph. Each non-cutpoint resides in at most one block. Each cutpoint resides in at least two blocks.

Parameters:

vertex - vertex in the initial graph.

Returns:

the blocks containing the given vertex

getBlocks

public Set<Graph<V,E>> getBlocks()

Returns all blocks (biconnected components) in the graph. A block is a maximal biconnected subgraph.

Returns:

all blocks (biconnected components) in the graph.

getConnectedComponents

public Set<Graph<V,E>> getConnectedComponents()

Returns all connected components in the graph. In case the graph is directed, this method returns all weakly connected components.

Returns:

all connected components in the graph if the graph is undirected, or all weakly connected components if the graph is directed.

getConnectedComponent

public Graph<V,E> getConnectedComponent(V vertex)

Returns the connected component containing the given vertex. If the underlying graph is directed, this method returns a weakly connected component.

Parameters:

vertex - vertex

Returns:

the connected component containing the given vertex, or a weakly connected component if the underlying graph is directed.

isBiconnected

public boolean isBiconnected()

Tests if the inspected graph is biconnected. A biconnected graph is a connected graph on two or more vertices having no cutpoints.

Returns:

true if the graph is biconnected, false otherwise

isConnected

public boolean isConnected()

Test if the inspected graph is connected. A graph is connected when, while ignoring edge directionality, there exists a path between every pair of vertices. In a connected graph, there are no unreachable vertices. When the inspected graph is a directed graph, this method returns true if and only if the inspected graph is weakly connected. An empty graph is not considered connected.

Returns:

true if and only if inspected graph is connected.