org.jgrapht.alg

Class BiconnectivityInspector<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

public class BiconnectivityInspector<V,E>
extends Object

Inspects a graph for the biconnectivity property. See BlockCutpointGraph for more information. A biconnected graph has only one block (i.e. no cutpoints).

Since:

July 5, 2007

Author:

Guillaume Boulmier

Constructor Summary

Constructors

Constructor and Description
BiconnectivityInspector(UndirectedGraph<V,E> graph) Running time = O(m) where m is the number of edges.

Method Summary

Modifier and Type	Method and Description
Set<Set<V>>	getBiconnectedVertexComponents() Returns the biconnected vertex-components of the graph.
Set<Set<V>>	getBiconnectedVertexComponents(V vertex) Returns the biconnected vertex-components containing the vertex.
Set<V>	getCutpoints() Returns the cutpoints of the graph.
boolean	isBiconnected() Returns true if the graph is biconnected (no cutpoint), false otherwise.

Methods inherited from class java.lang.Object

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

Constructor Detail

BiconnectivityInspector

public BiconnectivityInspector(UndirectedGraph<V,E> graph)

Running time = O(m) where m is the number of edges.

Parameters:

graph - the input graph

Method Detail

getBiconnectedVertexComponents

public Set<Set<V>> getBiconnectedVertexComponents()

Returns the biconnected vertex-components of the graph.

Returns:

the biconnected vertec-components of the graph

getBiconnectedVertexComponents

public Set<Set<V>> getBiconnectedVertexComponents(V vertex)

Returns the biconnected vertex-components containing the vertex. A biconnected vertex-component contains all the vertices in the component. A vertex which is not a cutpoint is contained in exactly one component. A cutpoint is contained is at least 2 components.

Parameters:

vertex - the input vertex

Returns:

set of all biconnected vertex-components containing the vertex.

getCutpoints

public Set<V> getCutpoints()

Returns the cutpoints of the graph.

Returns:

the cutpoints

isBiconnected

public boolean isBiconnected()

Returns true if the graph is biconnected (no cutpoint), false otherwise.

Returns:

true if the graph is biconnected, false otherwise