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 java.lang.Object
    implements StrongConnectivityAlgorithm<V,​E>

    Complements the ConnectivityInspector class with the capability to compute the strongly connected components of a directed graph. The algorithm is implemented after "Cormen et al: Introduction to agorithms", 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 isStronglyConnected().

    Since:
    Feb 2, 2005
    • Constructor Detail

      • KosarajuStrongConnectivityInspector

        public KosarajuStrongConnectivityInspector​(DirectedGraph<V,​E> directedGraph)
        The constructor of the StrongConnectivityAlgorithm class.
        Parameters:
        directedGraph - the graph to inspect
        Throws:
        java.lang.IllegalArgumentException - if the input graph is null
    • Method Detail

      • isStronglyConnected

        public boolean isStronglyConnected()
        Returns true if the graph of this StronglyConnectivityInspector instance is strongly connected.
        Specified by:
        isStronglyConnected in interface StrongConnectivityAlgorithm<V,​E>
        Returns:
        true if the graph is strongly connected, false otherwise
      • stronglyConnectedSets

        public java.util.List<java.util.Set<V>> stronglyConnectedSets()
        Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.
        Specified by:
        stronglyConnectedSets in interface StrongConnectivityAlgorithm<V,​E>
        Returns:
        List of Set s containing the strongly connected components
      • stronglyConnectedSubgraphs

        public java.util.List<DirectedSubgraph<V,​E>> stronglyConnectedSubgraphs()

        Computes a list of DirectedSubgraphs 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.

        NOTE: Calling this method will first execute stronglyConnectedSets(). If you don't need subgraphs, use that method.

        Specified by:
        stronglyConnectedSubgraphs in interface StrongConnectivityAlgorithm<V,​E>
        Returns:
        a list of subgraphs representing the strongly connected components
      • createVertexData

        private void createVertexData()
      • resetVertexData

        private void resetVertexData()