Package org.graph4j.connectivity

Interface BiconnectivityAlgorithm

All Known Implementing Classes:
TarjanBiconnectivity
public interface BiconnectivityAlgorithm
Author:
Cristian Frăsinaru

  • Method Summary

    Modifier and Type
    Method
    Description
    default Graph
    computeBlockCutTree()
    A block-cut tree (also known as BC-tree) is a tree that represents the blocks and articulation points (cut vertices) of a graph.
    default Graph
    computeBlockGraph()
    The block graph has one vertex for each block, and an edge between two vertices whenever their corresponding blocks share a vertex (an articulation point).
    List<Block>
    getBlocks()
    A block of a graph is a maximal 2-connected subgraph (it has no cut vertex).
    VertexSet
    getCutVertices()
    A cut vertex (cut point, articulation point, separating point) is any vertex whose removal increases the number of connected components.
    static BiconnectivityAlgorithm
    getInstance(Graph graph)
    Returns the default implementation of this interface.
    boolean
    isBiconnected()
    A graph is biconnected if it has no cut vertex.

  • Method Details

    • isBiconnected

      boolean isBiconnected()
      A graph is biconnected if it has no cut vertex.
      Returns:
      true if the graph is 2-connected.

    • getBlocks

      List<Block> getBlocks()
      A block of a graph is a maximal 2-connected subgraph (it has no cut vertex).
      Returns:
      the blocks of the graph.

    • getCutVertices

      VertexSet getCutVertices()
      A cut vertex (cut point, articulation point, separating point) is any vertex whose removal increases the number of connected components.
      Returns:
      the set of cut vertices.

    • computeBlockCutTree

      default Graph computeBlockCutTree()
      A block-cut tree (also known as BC-tree) is a tree that represents the blocks and articulation points (cut vertices) of a graph. The tree has a vertex for each block and for each articulation point of the given graph. There is an edge in the block-cut tree for each pair of a block and an articulation point that belongs to that block. The vertices of the returned tree are labeled either with the corresponding blocks or the vertex numbers of the articulation points.
      Returns:
      the block-cut tree.

    • computeBlockGraph

      default Graph computeBlockGraph()
      The block graph has one vertex for each block, and an edge between two vertices whenever their corresponding blocks share a vertex (an articulation point). The vertices of the returned graph are labeled with the corresponding blocks and their indices (and vertex numbers) are the same with the indices of the blocks int the list returned by the getBlocks() method.
      Returns:
      the block graph.

    • getInstance

      static BiconnectivityAlgorithm getInstance(Graph graph)
      Returns the default implementation of this interface.
      Parameters:
      graph - the input graph.
      Returns:
      the default implementation of this interface.