Class KosarajuSharirSCC

java.lang.Object

KosarajuSharirSCC

public class KosarajuSharirSCC
extends java.lang.Object

The KosarajuSharirSCC class represents a data type for determining the strong components in a digraph. The id operation determines in which strong component a given vertex lies; the areStronglyConnected operation determines whether two vertices are in the same strong component; and the count operation determines the number of strong components. The component identifier of a component is one of the vertices in the strong component: two vertices have the same component identifier if and only if they are in the same strong component.

This implementation uses the Kosaraju-Sharir algorithm. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the id, count, and areStronglyConnected operations take constant time. For alternate implementations of the same API, see TarjanSCC and GabowSCC.

For additional documentation, see Section 4.2 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
KosarajuSharirSCC(Digraph G) Computes the strong components of the digraph G.

Method Summary

Methods

Modifier and Type	Method and Description
int	count() Returns the number of strong components.
int	id(int v) Returns the component id of the strong component containing vertex v.
static void	main(java.lang.String[] args) Unit tests the KosarajuSharirSCC data type.
boolean	stronglyConnected(int v, int w) Are vertices v and w in the same strong component?

Methods inherited from class java.lang.Object

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

Constructor Detail

KosarajuSharirSCC

public KosarajuSharirSCC(Digraph G)

Computes the strong components of the digraph G.

Parameters:

G - the digraph

Method Detail

count

public int count()

Returns the number of strong components.

Returns:

the number of strong components

stronglyConnected

public boolean stronglyConnected(int v,
                        int w)

Are vertices v and w in the same strong component?

Parameters:

v - one vertex

w - the other vertex

Returns:

true if vertices v and w are in the same strong component, and false otherwise

id

public int id(int v)

Returns the component id of the strong component containing vertex v.

Parameters:

v - the vertex

Returns:

the component id of the strong component containing vertex v

main

public static void main(java.lang.String[] args)

Unit tests the KosarajuSharirSCC data type.