Package 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 typeE
- the graph edge type
- All Implemented Interfaces:
java.io.Serializable
,java.lang.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
- See Also:
- Serialized Form
-
-
Field Summary
-
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 Instance Methods Concrete 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.java.util.Set<Graph<V,E>>
getBlocks()
Returns all blocks (biconnected components) in the graphjava.util.Set<V>
getCutpoints()
Returns 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, 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
-
-
-
-
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 java.util.Set<Graph<V,E>> getBlocks()
Returns all blocks (biconnected components) in the graph- Returns:
- all blocks (biconnected components) in the graph.
-
getCutpoints
public java.util.Set<V> getCutpoints()
Returns the cutpoints of the initial graph.- Returns:
- the cutpoints of the initial graph
-
isCutpoint
public boolean isCutpoint(V vertex)
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.
-
-