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 Detail

      • 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