Package org.graph4j.connectivity

Class TarjanBiconnectivity

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.connectivity.TarjanBiconnectivity

All Implemented Interfaces:

BiconnectivityAlgorithm

public class TarjanBiconnectivity
extends SimpleGraphAlgorithm
implements BiconnectivityAlgorithm

The algorithm for computing biconnected components in a connected undirected graph is due to John Hopcroft and Robert Tarjan (1973). It runs in linear time, and is based on depth-first search. A block is a maximal 2-connected subgraph.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.SimpleGraphAlgorithm

graph

Constructor Summary

Constructors

Constructor	Description
TarjanBiconnectivity(Graph graph)

Method Summary

Modifier and Type	Method	Description
List<Block>	getBlocks()	A block of a graph is a maximal 2-connected subgraph (it has no cut vertex).
VertexSet	getCutVertices()	A cut vertex (cut point, articulation point, separating point) is any vertex whose removal increases the number of connected components.
boolean	isBiconnected()	A graph is biconnected if it has no cut vertex.

Methods inherited from class org.graph4j.SimpleGraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.graph4j.connectivity.BiconnectivityAlgorithm

computeBlockCutTree, computeBlockGraph

Constructor Details

TarjanBiconnectivity

public TarjanBiconnectivity(Graph graph)

Method Details

isBiconnected

public boolean isBiconnected()

Description copied from interface: BiconnectivityAlgorithm

A graph is biconnected if it has no cut vertex.

Specified by:

isBiconnected in interface BiconnectivityAlgorithm

Returns:

true if the graph is 2-connected.

getCutVertices

public VertexSet getCutVertices()

Description copied from interface: BiconnectivityAlgorithm

A cut vertex (cut point, articulation point, separating point) is any vertex whose removal increases the number of connected components.

Specified by:

getCutVertices in interface BiconnectivityAlgorithm

Returns:

the set of cut vertices.

getBlocks

public List<Block> getBlocks()

Description copied from interface: BiconnectivityAlgorithm

A block of a graph is a maximal 2-connected subgraph (it has no cut vertex).

Specified by:

getBlocks in interface BiconnectivityAlgorithm

Returns:

the blocks of the graph.