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

• ### Fields inherited from interface org.jgrapht.Graph

DEFAULT_EDGE_WEIGHT
• ### Constructor Summary

Constructors
Constructor Description
BlockCutpointGraph​(Graph<V,​E> graph)
Constructs a Block-Cutpoint graph
• ### Method Summary

All Methods
Modifier and Type Method 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
• ### Methods inherited from class org.jgrapht.graph.AbstractBaseGraph

addEdge, addEdge, addVertex, addVertex, clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getEdgeWeight, getType, getVertexSupplier, incomingEdgesOf, inDegreeOf, 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, setEdgeWeight
• ### 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.