com.mhhe.clrs2e
Class SCC.SecondDFS

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

Enclosing class:

SCC

private class SCC.SecondDFS

extends DFS

Inner class to do the second DFS. It considers the vertices in order of decreasing finish times, which means that they are visited in the order in which they appear in the linked list. It also numbers them so that the vertices in each tree of the resulting depth-first forest get the same SCC number.

Field Summary

private int	currentSCC The number of the current SCC.
private static int	NO_SCC Value indicating that a vertex is not yet in an SCC.

Fields inherited from class com.mhhe.clrs2e.DFS

dfsInfo, time

Constructor Summary

SCC.SecondDFS()
Initializes currentSCC and all SCC numbers to NO_SCC.

Method Summary

protected void	finish(com.mhhe.clrs2e.AdjacencyListGraph g, com.mhhe.clrs2e.Vertex u) Overrides the DFS.finish(com.mhhe.clrs2e.AdjacencyListGraph, com.mhhe.clrs2e.Vertex) method to assign the current SCC number to the vertex.
void	search(com.mhhe.clrs2e.AdjacencyListGraph g) Performs the main loop of the second DFS.

Methods inherited from class com.mhhe.clrs2e.DFS

dfsVisit, discover, getDFSInfo, getDFSInfo

Methods inherited from class java.lang.Object

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

Field Detail

currentSCC

private int currentSCC

The number of the current SCC.

NO_SCC

private static final int NO_SCC

Value indicating that a vertex is not yet in an SCC.

See Also:

Constant Field Values

Constructor Detail

SCC.SecondDFS

public SCC.SecondDFS()

Initializes currentSCC and all SCC numbers to NO_SCC.

Method Detail

search

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

Performs the main loop of the second DFS. This DFS considers the vertices in order of decreasing finish times, based on their positions in the linked list, as created by the first DFS. This method calls DFS.dfsVisit(com.mhhe.clrs2e.AdjacencyListGraph, com.mhhe.clrs2e.Vertex), which in turn calls finish(com.mhhe.clrs2e.AdjacencyListGraph, com.mhhe.clrs2e.Vertex), which sets the SCC numbers in the sccNumber array.

Overrides:

search in class DFS

Parameters:

g - The directed graph.

finish

protected void finish(com.mhhe.clrs2e.AdjacencyListGraph g,
                      com.mhhe.clrs2e.Vertex u)

Overrides the DFS.finish(com.mhhe.clrs2e.AdjacencyListGraph, com.mhhe.clrs2e.Vertex) method to assign the current SCC number to the vertex.

Overrides:

finish in class DFS

Parameters:

g - The graph.

u - The vertex just finished.