Package 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
    See Also:
    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.