Package com.jgalgo.alg.connect

Interface BiConnectedComponentsAlgo.Result<V,E>

Type Parameters:
V - the vertices type
E - the edges type
All Known Subinterfaces:
BiConnectedComponentsAlgo.IResult
Enclosing interface:
BiConnectedComponentsAlgo
public static interface BiConnectedComponentsAlgo.Result<V,E>
A result object of a BiConnectedComponentsAlgo computation.

Each bi-connected components is labeled by an integer in range [0, getNumberOfBiCcs()).

Note that the bi-connected components are not disjoint, namely a single vertex can be included in multiple bi-connected components, differing from the regular connected components of a graph.

Author:
Barak Ugav

  • Method Summary

    Modifier and Type
    Method
    Description
    Set<E>
    getBiCcEdges(int biccIdx)
    Get the edges contained in a single bi-connected component.
    Set<V>
    getBiCcVertices(int biccIdx)
    Get the vertices contained in a single bi-connected component.
    IntGraph
    getBlockGraph()
    Get the graph of the bi-connected components.
    Set<V>
    getCutVertices()
    Get all the cut vertices in the graph.
    int
    getNumberOfBiCcs()
    Get the number of bi-connected components computed in the graph.
    IntSet
    getVertexBiCcs(V vertex)
    Get the bi-connected components a vertex is contained in.
    boolean
    isCutVertex(V vertex)
    Check whether a vertex is a cut-vertex.

  • Method Details

    • getVertexBiCcs

      IntSet getVertexBiCcs(V vertex)
      Get the bi-connected components a vertex is contained in.
      Parameters:
      vertex - a vertex in the graph
      Returns:
      the labels of the bi-connected components containing the vertex
      Throws:
      NoSuchVertexException - if vertex is not a valid vertex identifier in the graph

    • getNumberOfBiCcs

      int getNumberOfBiCcs()
      Get the number of bi-connected components computed in the graph.

      Each bi-connected component is labeled by an integer in range [0, getNumberOfBiCcs()).

      Returns:
      the number of bi-connected components

    • getBiCcVertices

      Set<V> getBiCcVertices(int biccIdx)
      Get the vertices contained in a single bi-connected component.
      Parameters:
      biccIdx - an index of a bi-connected component
      Returns:
      all the vertices that are contained in the bi-connected component
      Throws:
      IndexOutOfBoundsException - if biccIdx is not in range [0, getNumberOfBiCcs())

    • getBiCcEdges

      Set<E> getBiCcEdges(int biccIdx)
      Get the edges contained in a single bi-connected component.

      An edge \((u,v)\) is said to be contained in a bi-connected component \(B\) if both \(u\) and \(v\) are in \(B\).

      Parameters:
      biccIdx - an index of a bi-connected component
      Returns:
      all the edges that are contained in the bi-connected component
      Throws:
      IndexOutOfBoundsException - if biccIdx is not in range [0, getNumberOfBiCcs())

    • isCutVertex

      boolean isCutVertex(V vertex)
      Check whether a vertex is a cut-vertex.

      A cut vertex is a vertex whose removal disconnects the graph. In the context of bi-connected components, a cut vertex is also a vertex that belongs to more than one bi-connected component. These vertices are also called articulation points, or separating vertices.

      Parameters:
      vertex - a vertex in the graph
      Returns:
      true if vertex is a cut-vertex, false otherwise

    • getCutVertices

      Set<V> getCutVertices()
      Get all the cut vertices in the graph.

      A cut vertex is a vertex whose removal disconnects the graph. In the context of bi-connected components, a cut vertex is also a vertex that belongs to more than one bi-connected component. These vertices are also called articulation points, or separating vertices.

      Returns:
      all the cut vertices in the graph

    • getBlockGraph

      IntGraph getBlockGraph()
      Get the graph of the bi-connected components.

      The vertices of the graph are the bi-connected components, and there is an edge between two bi-connected components if they share a (cut) vertex. There are no cycles in the graph, namely its a forest.

      The vertex of each bi-connected component is assigned the index of the bi-connected component. The edges are assigned arbitrary unique integers identifiers.

      Returns:
      the graph of the bi-connected components