Module org.jgrapht.core
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 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
See Also:

  • Constructor Details

    • BlockCutpointGraph

      public BlockCutpointGraph(Graph<V,E> graph)
      Constructs a Block-Cutpoint graph
      Parameters:
      graph - the input graph

  • Method Details

    • 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.