- Type Parameters:
V- the graph vertex type
E- the graph edge type
- All Implemented Interfaces:
public class KosarajuStrongConnectivityInspector<V,E> extends ObjectComputes 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)$.
ConnectivityInspector, this class does not implement incremental inspection. The full algorithm is executed at the first call of
- Christian Soltenborn, Christian Hammer
All Methods Instance Methods Concrete Methods Modifier and Type Method Description
getCondensation()Compute the condensation of the given graph.
getGraph()Return the underlying graph.
getStronglyConnectedComponents()Computes a list of subgraphs of the given graph.
isStronglyConnected()Returns true if the graph is strongly connected, false otherwise.
Sets, where each set contains vertices which together form a strongly connected component within the given graph.
Sets containing the strongly connected components
public Graph<V,E> getGraph()Return the underlying graph.
public boolean isStronglyConnected()Returns true if the graph is strongly connected, false otherwise.
getStronglyConnectedComponentsComputes 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.
public 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.