org.jgrapht.alg

## Class KosarajuStrongConnectivityInspector<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
StrongConnectivityAlgorithm<V,E>

Deprecated.
Moved to package org.jgrapht.connectivity

@Deprecated
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 AbstractStrongConnectivityInspector.isStronglyConnected().

Since:
Feb 2, 2005
Author:
Christian Soltenborn, Christian Hammer
• ### Field Detail

• #### graph

protected final Graph<V,E> graph
Deprecated.
• #### stronglyConnectedSets

protected List<Set<V>> stronglyConnectedSets
Deprecated.
• #### stronglyConnectedSubgraphs

protected List<Graph<V,E>> stronglyConnectedSubgraphs
Deprecated.
• ### Constructor Detail

• #### KosarajuStrongConnectivityInspector

public KosarajuStrongConnectivityInspector(Graph<V,E> graph)
Deprecated.
Constructor
Parameters:
graph - the input graph
Throws:
NullPointerException - if the input graph is null
• ### Method Detail

• #### stronglyConnectedSets

public List<Set<V>> stronglyConnectedSets()
Deprecated.
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
• #### isStronglyConnected

public boolean isStronglyConnected()
Deprecated.
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()
Deprecated.
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()
Deprecated.
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