org.jgrapht.alg.connectivity

Class BlockCutpointGraph<V,E>

java.lang.Object

org.jgrapht.graph.AbstractGraph<V,E>

org.jgrapht.graph.AbstractBaseGraph<V,E>

org.jgrapht.graph.SimpleGraph<Graph<V,E>,DefaultEdge>

org.jgrapht.alg.connectivity.BlockCutpointGraph<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

Serializable, Cloneable, Graph<Graph<V,E>,DefaultEdge>

public class BlockCutpointGraph<V,E>
extends SimpleGraph<Graph<V,E>,DefaultEdge>

A Block-Cutpoint graph (also known as a block-cut tree). If $G$ is a graph, the block-cutpoint graph of $G$, denoted $BC(G)$ is the simple bipartite graph with bipartition $(A, B)$ where $A$ is the set of cut-vertices (also known as articulation points) of $G$, and $B$ is the set of blocks of $G$. $BC(G)$ contains an edge $(a,b)$ for $a \in A$ and $b \in B$ if and only if block $b$ contains the cut-vertex $a$. A vertex in $G$ is a cut-vertex if removal of the vertex from $G$ (and all edges incident to this vertex) increases the number of connected components in the graph. A block of $G$ is a maximal connected subgraph $H \subseteq G$ so that $H$ does not have a cut-vertex. Note that if $H$ is a block, then either $H$ is 2-connected, or $|V(H)| \leq 2$. Each pair of blocks of $G$ share at most one vertex, and that vertex is a cut-point in $G$. $BC(G)$ is a tree in which each leaf node corresponds to a block of $G$.

Note: the block-cutpoint graph is not changed when the underlying graph is changed.

Since:

July 5, 2007

Author:

France Telecom S.A, Joris Kinable

See Also:

Serialized Form

Field Summary

Fields inherited from interface org.jgrapht.Graph

DEFAULT_EDGE_WEIGHT

Constructor Summary

Constructors

Constructor and Description
BlockCutpointGraph(Graph<V,E> graph) Constructs a Block-Cutpoint graph

Method Summary

Modifier and Type	Method and Description
Graph<V,E>	getBlock(V vertex) Returns the vertex if vertex is a cutpoint, and otherwise returns the block (biconnected component) containing the vertex.
Set<Graph<V,E>>	getBlocks() Returns all blocks (biconnected components) in the graph
Set<V>	getCutpoints() Returns the cutpoints of the initial graph.
boolean	isCutpoint(V vertex) Returns true if the vertex is a cutpoint, false otherwise.

Methods inherited from class org.jgrapht.graph.SimpleGraph

createBuilder, createBuilder, createBuilder

Methods inherited from class org.jgrapht.graph.AbstractBaseGraph

addEdge, addEdge, addVertex, addVertex, clone, containsEdge, containsVertex, createIntrusiveEdgesSpecifics, createSpecifics, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeSupplier, getEdgeTarget, getEdgeWeight, getType, getVertexSupplier, incomingEdgesOf, inDegreeOf, isAllowingLoops, isAllowingMultipleEdges, isDirected, isWeighted, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, setEdgeSupplier, setEdgeWeight, setVertexSupplier, vertexSet

Methods inherited from class org.jgrapht.graph.AbstractGraph

assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.jgrapht.Graph

containsEdge, removeAllEdges, removeAllEdges, removeAllVertices

Constructor Detail

BlockCutpointGraph

public BlockCutpointGraph(Graph<V,E> graph)

Constructs a Block-Cutpoint graph

Parameters:

graph - the input graph

Method Detail

getBlock

public Graph<V,E> getBlock(V vertex)

Returns the vertex if vertex is a cutpoint, and otherwise returns the block (biconnected component) containing the vertex.

Parameters:

vertex - vertex

Returns:

the biconnected component containing the vertex

getBlocks

public Set<Graph<V,E>> getBlocks()

Returns all blocks (biconnected components) in the graph

Returns:

all blocks (biconnected components) in the graph.

getCutpoints

public Set<V> getCutpoints()

Returns the cutpoints of the initial graph.

Returns:

the cutpoints of the initial graph

isCutpoint

public boolean isCutpoint(V vertex)

Returns true if the vertex is a cutpoint, false otherwise.

Parameters:

vertex - vertex in the initial graph.

Returns:

true if the vertex is a cutpoint, false otherwise.