Package com.jgalgo.alg.connect

Class BiConnectedComponentsAlgoHopcroftTarjan

java.lang.Object

com.jgalgo.alg.connect.BiConnectedComponentsAlgoAbstract

com.jgalgo.alg.connect.BiConnectedComponentsAlgoHopcroftTarjan

All Implemented Interfaces:

BiConnectedComponentsAlgo

public class BiConnectedComponentsAlgoHopcroftTarjan
extends BiConnectedComponentsAlgoAbstract

Hopcroft-Tarjan algorithm for bi-connected components.

The algorithm performs a DFS and look for edges from vertices with greater depth to vertices with lower depth. Each such edge indicate there are two separates paths between the edge endpoints: one using the DFS tree, and the other using the edge itself. If there are two disjoint paths between a pair of vertices, they must be in the same bi-connected component, as the removal of any single vertex will not disconnect them.

The algorithm runs in linear time and space.

Based on 'Algorithm 447: efficient algorithms for graph manipulation' by Hopcroft, J. and Tarjan, R. 1973.

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.connect.BiConnectedComponentsAlgo

BiConnectedComponentsAlgo.IResult, BiConnectedComponentsAlgo.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
BiConnectedComponentsAlgoHopcroftTarjan()	Create a new instance of the algorithm.

Method Summary

Methods inherited from class com.jgalgo.alg.connect.BiConnectedComponentsAlgoAbstract

findBiConnectedComponents

Methods inherited from class java.lang.Object

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

Constructor Details

BiConnectedComponentsAlgoHopcroftTarjan

public BiConnectedComponentsAlgoHopcroftTarjan()

Create a new instance of the algorithm.

Please prefer using BiConnectedComponentsAlgo.newInstance() to get a default implementation for the BiConnectedComponentsAlgo interface.