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:

  • Method Details

    • 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

    • newInstance

      static StronglyConnectedComponentsAlgo newInstance()
      Create a new strongly connected components algorithm object.

      This is the recommended way to instantiate a new StronglyConnectedComponentsAlgo object.

      Returns:
      a default implementation of StronglyConnectedComponentsAlgo