V
 the graph vertex typeE
 the graph edge typepublic class BiconnectivityInspector<V,E> extends Object
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 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.
Constructor and Description 

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

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.

public Set<V> getCutpoints()
public Set<E> getBridges()
public Set<Graph<V,E>> getBlocks(V vertex)
vertex
 vertex in the initial graph.public Set<Graph<V,E>> getBlocks()
public Set<Graph<V,E>> getConnectedComponents()
public Graph<V,E> getConnectedComponent(V vertex)
vertex
 vertexpublic boolean isBiconnected()
public boolean isConnected()
true
if and only if inspected graph is connected.Copyright © 2019. All rights reserved.