Package org.jgrapht.alg.connectivity
Class BiconnectivityInspector<V,E>
 java.lang.Object

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

 Type Parameters:
V
 the graph vertex typeE
 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, useKosarajuStrongConnectivityInspector
instead. This class offers an alternative implementation of some of the functionality encountered inConnectivityInspector
. It is likely to perform somewhat slower thanConnectivityInspector
, 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 depthfirst 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 Depthfirst search.
 Author:
 Joris Kinable


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

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.



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 noncutpoint 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.

