Package com.jgalgo.alg.connect

Interface StronglyConnectedComponentsAlgo

  • All Known Implementing Classes:
    StronglyConnectedComponentsAlgoAbstract, StronglyConnectedComponentsPathBasedDfs, StronglyConnectedComponentsTarjan
    public interface StronglyConnectedComponentsAlgo
    Strongly Connected components algorithm.

    Given a graph \(G=(V,E)\), two vertices \(u,v \in V\) are strongly connected if there is a path from \(u\) to \(v\) and from \(v\) to \(u\). A strongly connected component is a maximal set of vertices that each pair in the set is strongly connected. This definition hold for both directed and undirected graphs. For undirected graphs, the strongly and weakly connected components are identical. The set of vertices \(V\) can be partitioned into disjoint strongly connected components.

    The blocks graph of a strongly connected components partition is a directed acyclic graph, where each vertex is a strongly connected component, and there is an edge from \(B_1\) to \(B_2\) if there is an edge \((u, v)\) in \(G\) such that \(u \in B_1\) and \(v \in B_2\). This blocks graph is sometimes called the condensation of \(G\).

    Use newInstance() to get a default implementation of this interface.

    Author:
    Barak Ugav
    See Also:
    WeaklyConnectedComponentsAlgo, BiConnectedComponentsAlgo, KVertexConnectedComponentsAlgo

    • Method Detail

      • findStronglyConnectedComponents

        <V,​E> VertexPartition<V,​E> findStronglyConnectedComponents​(Graph<V,​E> g)
        Find all strongly connected components in a graph.

        A strongly connected component is a maximal set of vertices for which for any pair of vertices \(u, v\) in the set there exist a path from \(u\) to \(v\) and from \(v\) to \(u\).

        If g is IntGraph, the returned object is IVertexPartition.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        Returns:
        a result object containing the partition of the vertices into strongly connected components

      • isStronglyConnected

        <V,​E> boolean isStronglyConnected​(Graph<V,​E> g)
        Check whether a graph is strongly connected.

        A graph is strongly connected if there is a path from any vertex to any other vertex. Namely if the the whole graph is a single strongly connected component.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        Returns:
        true if the graph is strongly connected, false otherwise