org.jgrapht.alg

Class StrongConnectivityInspector<V,E>

java.lang.Object

org.jgrapht.alg.StrongConnectivityInspector<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

StrongConnectivityAlgorithm<V,E>

Deprecated.

Use KosarajuStrongConnectivityInspector instead.

@Deprecated
public class StrongConnectivityInspector<V,E>
extends Object
implements StrongConnectivityAlgorithm<V,E>

Complements the ConnectivityInspector class with the capability to compute the 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 isStronglyConnected().

Since:

Feb 2, 2005

Author:

Christian Soltenborn, Christian Hammer

Constructor Summary

Constructors

Constructor and Description
StrongConnectivityInspector(DirectedGraph<V,E> directedGraph) Deprecated. The constructor of the StrongConnectivityAlgorithm class.

Method Summary

Modifier and Type	Method and Description
DirectedGraph<V,E>	getGraph() Deprecated. Returns the graph inspected by the StrongConnectivityAlgorithm.
boolean	isStronglyConnected() Deprecated. Returns true if the graph of this StronglyConnectivityInspector instance is strongly connected.
List<Set<V>>	stronglyConnectedSets() Deprecated. Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.
List<DirectedSubgraph<V,E>>	stronglyConnectedSubgraphs() Deprecated. Computes a list of DirectedSubgraphs of the given graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

StrongConnectivityInspector

public StrongConnectivityInspector(DirectedGraph<V,E> directedGraph)

Deprecated.

The constructor of the StrongConnectivityAlgorithm class.

Parameters:

directedGraph - the graph to inspect

Throws:

IllegalArgumentException - if the input graph is null

Method Detail

getGraph

public DirectedGraph<V,E> getGraph()

Deprecated.

Returns the graph inspected by the StrongConnectivityAlgorithm.

Specified by:

getGraph in interface StrongConnectivityAlgorithm<V,E>

Returns:

the graph inspected by this StrongConnectivityAlgorithm

isStronglyConnected

public boolean isStronglyConnected()

Deprecated.

Returns true if the graph of this StronglyConnectivityInspector instance is strongly connected.

Specified by:

isStronglyConnected in interface StrongConnectivityAlgorithm<V,E>

Returns:

true if the graph is strongly connected, false otherwise

stronglyConnectedSets

public List<Set<V>> stronglyConnectedSets()

Deprecated.

Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.

Specified by:

stronglyConnectedSets in interface StrongConnectivityAlgorithm<V,E>

Returns:

List of Set s containing the strongly connected components

stronglyConnectedSubgraphs

public List<DirectedSubgraph<V,E>> stronglyConnectedSubgraphs()

Deprecated.

Computes a list of DirectedSubgraphs 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.

NOTE: Calling this method will first execute stronglyConnectedSets(). If you don't need subgraphs, use that method.

Specified by:

stronglyConnectedSubgraphs in interface StrongConnectivityAlgorithm<V,E>

Returns:

a list of subgraphs representing the strongly connected components