Interface StrongConnectivityAlgorithm<V,​E>

Type Parameters:
V - the graph vertex type
E - the graph edge type
All Known Implementing Classes:
GabowStrongConnectivityInspector, KosarajuStrongConnectivityInspector

public interface StrongConnectivityAlgorithm<V,​E>
A strong connectivity inspector algorithm.
Author:
Sarah Komla-Ebri
  • Method Details

    • getGraph

      Graph<V,​E> getGraph()
      Return the underlying graph.
      Returns:
      the underlying graph
    • isStronglyConnected

      boolean isStronglyConnected()
      Returns true if the graph is strongly connected, false otherwise.
      Returns:
      true if the graph is strongly connected, false otherwise
    • stronglyConnectedSets

      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.
      Returns:
      List of Set s containing the strongly connected components
    • getStronglyConnectedComponents

      java.util.List<Graph<V,​E>> getStronglyConnectedComponents()
      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.
      Returns:
      a list of subgraphs representing the strongly connected components
    • getCondensation

      Graph<Graph<V,​E>,​DefaultEdge> getCondensation()
      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.
      Returns:
      the condensation of the given graph