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 typeE
 the graph edge type
 All Implemented Interfaces:
Serializable
,Cloneable
,Graph<Graph<V,
E>, DefaultEdge>
A BlockCutpoint graph (also known as a blockcut tree). If $G$ is a graph, the blockcutpoint
graph of $G$, denoted $BC(G)$ is the simple bipartite graph with bipartition $(A, B)$ where $A$
is the set of cutvertices
(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 cutvertex $a$. A
vertex in $G$ is a cutvertex 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 cutvertex. Note that if $H$ is a
block, then either $H$ is 2connected, or $V(H) \leq 2$. Each pair of blocks of $G$ share at
most one vertex, and that vertex is a cutpoint in $G$. $BC(G)$ is a tree in which each leaf node
corresponds to a block of $G$.
Note: the blockcutpoint graph is not changed when the underlying graph is changed.
 Author:
 France Telecom S.A, Joris Kinable
 See Also:

Field Summary
Fields inherited from interface org.jgrapht.Graph
DEFAULT_EDGE_WEIGHT

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionReturns the vertex if vertex is a cutpoint, and otherwise returns the block (biconnected component) containing the vertex.Returns all blocks (biconnected components) in the graphReturns the cutpoints of the initial graph.boolean
isCutpoint
(V vertex) Returnstrue
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, iterables, 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 Details

BlockCutpointGraph
Constructs a BlockCutpoint graph Parameters:
graph
 the input graph


Method Details

getBlock
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
Returns all blocks (biconnected components) in the graph Returns:
 all blocks (biconnected components) in the graph.

getCutpoints
Returns the cutpoints of the initial graph. Returns:
 the cutpoints of the initial graph

isCutpoint
Returnstrue
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.
