Package org._3pq.jgrapht.alg

Class StrongConnectivityInspector

  • public class StrongConnectivityInspector
extends java.lang.Object

    Complements the ConnectivityInspector class with the capability to compute the strongly connected components of a directed graph. The algorithm is implemented after "Corman et al: Introduction to agorithms", Chapter 25.2. 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
    Author:
    Christian Soltenborn

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      DirectedGraph getGraph()
      Returns the graph inspected by the StrongConnectivityInspector.
      boolean isStronglyConnected()
      Returns true if the graph of this StronglyConnectivityInspector instance is strongly connected.
      java.util.List stronglyConnectedSets()
      Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.
      java.util.List stronglyConnectedSubgraphs()
      Computes a list of DirectedSubgraphs of the given graph.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • StrongConnectivityInspector

        public StrongConnectivityInspector​(DirectedGraph directedGraph)
        The constructor of the StrongConnectivityInspector class.
        Parameters:
        directedGraph - the graph to inspect
        Throws:
        java.lang.IllegalArgumentException

    • Method Detail

      • getGraph

        public DirectedGraph getGraph()
        Returns the graph inspected by the StrongConnectivityInspector.
        Returns:
        the graph inspected by this StrongConnectivityInspector

      • isStronglyConnected

        public boolean isStronglyConnected()
        Returns true if the graph of this StronglyConnectivityInspector instance is strongly connected.
        Returns:
        true if the graph is strongly connected, false otherwise

      • stronglyConnectedSets

        public java.util.List stronglyConnectedSets()
        Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.
        Returns:
        List of Sets containing the strongly connected components

      • stronglyConnectedSubgraphs

        public java.util.List 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.

        Returns:
        a list of subgraphs representing the strongly connected components