com.mhhe.clrs2e
Class SCC

java.lang.Object
  |
  +--com.mhhe.clrs2e.SCC

public class SCC

extends java.lang.Object

Class to perform the Strongly-Connected-Components procedure on page 554 of Introduction to Algorithms, Second edition.

Nested Class Summary

private class	SCC.FirstDFS Inner class to do the first DFS.
private class	SCC.SecondDFS Inner class to do the second DFS.

Field Summary

private com.mhhe.clrs2e.SentinelDLL	list A list of vertices.
private int[]	sccNumber The SCC number of each vertex.

Constructor Summary

SCC()

Method Summary

int	getSCCNumber(int v) Returns the SCC number for a given vertex.
int	getSCCNumber(com.mhhe.clrs2e.Vertex v) Returns the SCC number for a given vertex.
void	stronglyConnectedComponents(com.mhhe.clrs2e.AdjacencyListGraph g) Computes the strongly connected components of a directed graph, filling in SCC numbers in the sccNumber array so that sccNumber[i] is the SCC number of the vertex whose index is i.
private com.mhhe.clrs2e.AdjacencyListGraph	transpose(com.mhhe.clrs2e.AdjacencyListGraph g) Transposes a graph.

Methods inherited from class java.lang.Object

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

Field Detail

list

private com.mhhe.clrs2e.SentinelDLL list

A list of vertices.

sccNumber

private int[] sccNumber

The SCC number of each vertex. sccNumber[i] is the SCC number of the vertex whose index is i. Valid SCC numbers start at 0.

Constructor Detail

SCC

public SCC()

Method Detail

stronglyConnectedComponents

public void stronglyConnectedComponents(com.mhhe.clrs2e.AdjacencyListGraph g)

Computes the strongly connected components of a directed graph, filling in SCC numbers in the sccNumber array so that sccNumber[i] is the SCC number of the vertex whose index is i.

Parameters:

g - The directed graph.

transpose

private com.mhhe.clrs2e.AdjacencyListGraph transpose(com.mhhe.clrs2e.AdjacencyListGraph g)

Transposes a graph. The transpose has the same Vertex objects as the input graph but different edges.

Parameters:

g - The directed graph to transpose.

Returns:

The transpose of g.

getSCCNumber

public int getSCCNumber(com.mhhe.clrs2e.Vertex v)

Returns the SCC number for a given vertex.

Parameters:

v - The vertex for which the corresponding SCC number is returned.

getSCCNumber

public int getSCCNumber(int v)

Returns the SCC number for a given vertex.

Parameters:

v - The index of the vertex for which the corresponding SCC number is returned.