Package com.jgalgo.alg.connect

Interface BiConnectedComponentsAlgo

All Known Implementing Classes:

BiConnectedComponentsAlgoAbstract, BiConnectedComponentsAlgoHopcroftTarjan

public interface BiConnectedComponentsAlgo

An algorithm that compute the bi-connected components of a graph.

Given a graph \(G=(V,E)\) a bi-connected component \(B \subseteq V\) is a maximal set of connected vertices that remain connected even after removing any single vertex of \(B\). In particular, an isolated vertex is considered a bi-connected component, along with an isolated pair of vertices connected by a single edge. This algorithm compute all the maximal bi-connected components of the graph. Note that the bi-connected components are not disjoint, namely a single vertex can be included in multiple bi-connected components, differing from the regular connected components of a graph.

For a general k-vertex connected components, see KVertexConnectedComponentsAlgo.

Use newInstance() to get a default implementation of this interface.

Author:

Barak Ugav

See Also:

• Wikipedia
• StronglyConnectedComponentsAlgo
• KVertexConnectedComponentsAlgo
• WeaklyConnectedComponentsAlgo

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	BiConnectedComponentsAlgo.IResult	A result object of a BiConnectedComponentsAlgo computation for IntGraph.
static interface	BiConnectedComponentsAlgo.Result<V,E>	A result object of a BiConnectedComponentsAlgo computation.

Method Summary

Modifier and Type	Method	Description
<V, E> BiConnectedComponentsAlgo.Result<V,E>	findBiConnectedComponents(Graph<V,E> g)	Compute all maximal bi-connected components of a graph.
static BiConnectedComponentsAlgo	newInstance()	Create a new bi-connected components algorithm object.

Method Details

findBiConnectedComponents

<V,
E> BiConnectedComponentsAlgo.Result<V,E> findBiConnectedComponents(Graph<V,E> g)

Compute all maximal bi-connected components of a graph.

If an IntGraph is passed as an argument BiConnectedComponentsAlgo.IResult is returned.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

a result object containing the bi-connected components of the graph

newInstance

static BiConnectedComponentsAlgo newInstance()

Create a new bi-connected components algorithm object.

This is the recommended way to instantiate a new BiConnectedComponentsAlgo object.

Returns:

a default implementation of BiConnectedComponentsAlgo