Package org.jgrapht.alg.connectivity

Class KosarajuStrongConnectivityInspector<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    StrongConnectivityAlgorithm<V,​E>
    public class KosarajuStrongConnectivityInspector<V,​E>
extends Object
    Computes strongly connected components of a directed graph. The algorithm is implemented after "Cormen et al: Introduction to algorithms", Chapter 22.5. It has a running time of $O(V + E)$.

    Unlike ConnectivityInspector, this class does not implement incremental inspection. The full algorithm is executed at the first call of stronglyConnectedSets() or StrongConnectivityAlgorithm.isStronglyConnected().

    Author:
    Christian Soltenborn, Christian Hammer

    • Field Detail

      • graph

        protected final Graph<V,​E> graph

      • stronglyConnectedSets

        protected List<Set<V>> stronglyConnectedSets

      • stronglyConnectedSubgraphs

        protected List<Graph<V,​E>> stronglyConnectedSubgraphs

    • Constructor Detail

      • KosarajuStrongConnectivityInspector

        public KosarajuStrongConnectivityInspector​(Graph<V,​E> graph)
        Constructor
        Parameters:
        graph - the input graph
        Throws:
        NullPointerException - if the input graph is null

    • Method Detail

      • stronglyConnectedSets

        public List<Set<V>> stronglyConnectedSets()
        Description copied from interface: StrongConnectivityAlgorithm
        Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.
        Returns:
        List of Set s containing the strongly connected components

      • getStronglyConnectedComponents

        public List<Graph<V,​E>> getStronglyConnectedComponents()
        Description copied from interface: StrongConnectivityAlgorithm
        Computes a list of subgraphs of the given graph. Each subgraph will represent a strongly connected component and will contain all vertices of that component. The subgraph will have an edge $(u,v)$ iff $u$ and $v$ are contained in the strongly connected component.
        Specified by:
        getStronglyConnectedComponents in interface StrongConnectivityAlgorithm<V,​E>
        Returns:
        a list of subgraphs representing the strongly connected components

      • getCondensation

        public Graph<Graph<V,​E>,​DefaultEdge> getCondensation()
        Description copied from interface: StrongConnectivityAlgorithm
        Compute the condensation of the given graph. If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation of the graph.
        Specified by:
        getCondensation in interface StrongConnectivityAlgorithm<V,​E>
        Returns:
        the condensation of the given graph