org.jgrapht.alg.connectivity

## Class 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.

Author:
France Telecom S.A, Joris Kinable
Serialized Form
• ### 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.