Module org.jgrapht.core
Package org.jgrapht.alg.connectivity

Class KosarajuStrongConnectivityInspector<V,E>

java.lang.Object
org.jgrapht.alg.connectivity.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 Details

    • graph

      protected final Graph<V,E> graph

    • stronglyConnectedSets

      protected List<Set<V>> stronglyConnectedSets

    • stronglyConnectedSubgraphs

      protected List<Graph<V,E>> stronglyConnectedSubgraphs

  • Constructor Details

    • KosarajuStrongConnectivityInspector

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

  • Method Details

    • 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

    • getGraph

      public Graph<V,E> getGraph()
      Description copied from interface: StrongConnectivityAlgorithm
      Return the underlying graph.
      Specified by:
      getGraph in interface StrongConnectivityAlgorithm<V,E>
      Returns:
      the underlying graph

    • isStronglyConnected

      public boolean isStronglyConnected()
      Description copied from interface: StrongConnectivityAlgorithm
      Returns true if the graph is strongly connected, false otherwise.
      Specified by:
      isStronglyConnected in interface StrongConnectivityAlgorithm<V,E>
      Returns:
      true if the graph is strongly connected, false otherwise

    • 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