Package org.jgrapht.alg
Class BiconnectivityInspector<V,E>
- java.lang.Object
-
- org.jgrapht.alg.BiconnectivityInspector<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
public class BiconnectivityInspector<V,E> extends java.lang.Object
Inspects a graph for the biconnectivity property. SeeBlockCutpointGraph
for more information. A biconnected graph has only one block (i.e. no cutpoints).- Since:
- July 5, 2007
-
-
Field Summary
Fields Modifier and Type Field Description private BlockCutpointGraph<V,E>
blockCutpointGraph
-
Constructor Summary
Constructors Constructor Description BiconnectivityInspector(UndirectedGraph<V,E> graph)
Running time = O(m) where m is the number of edges.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description java.util.Set<java.util.Set<V>>
getBiconnectedVertexComponents()
Returns the biconnected vertex-components of the graph.java.util.Set<java.util.Set<V>>
getBiconnectedVertexComponents(V vertex)
Returns the biconnected vertex-components containing the vertex.java.util.Set<V>
getCutpoints()
Returns the cutpoints of the graph.boolean
isBiconnected()
Returnstrue
if the graph is biconnected (no cutpoint),false
otherwise.
-
-
-
Field Detail
-
blockCutpointGraph
private BlockCutpointGraph<V,E> blockCutpointGraph
-
-
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 java.util.Set<java.util.Set<V>> getBiconnectedVertexComponents()
Returns the biconnected vertex-components of the graph.- Returns:
- the biconnected vertec-components of the graph
-
getBiconnectedVertexComponents
public java.util.Set<java.util.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 java.util.Set<V> getCutpoints()
Returns the cutpoints of the graph.- Returns:
- the cutpoints
-
isBiconnected
public boolean isBiconnected()
Returnstrue
if the graph is biconnected (no cutpoint),false
otherwise.- Returns:
- true if the graph is biconnected, false otherwise
-
-