[ Data Structures with Java ] Section 25.1 : Topological Sort

Preface : 
In Section 24.3, we developed the depth-first method dfs(), which searches all of the vertices in a graph by using a series of calls to dfsVisit(). Method dfs() returns a list, called dfsList, that sequences the vertices in the reverse order of their finishing times. The order of vertices in dfsList depends on the selection of starting vertices for the calls to dfsVisit(). When the graph is acyclic, we will show that dfsList has a topological order implying that if P(v, w) is a path from v to w, then v must occur before w in the list. We say that dfs() produces a topological sort of the vertices. 
A topological sort has important applications for graphs that define a precedence order in the scheduling of activities. For instance, a department at a university uses a graph to lay out the courses for its major. Edges in the graph define course prerequisites. Below figure is a graph of courses for a religious studies major. A student can elect courses R51 and R37 in any order, but R63 can be taken only after the student completes these two courses because they are prerequisites. 
 
The previous examples are clearly acyclic graphs. A topological sort of the vertices provides the student a possible four-year schedule of courses or the contractor a schedule for the subconstractors. 

Why It Works : 
Assume a depth-first search returns a list that describes an order of visits to all of the vertices in an acyclic graph. We must show that for any pair of vertices v and w in the graph that are connected by a path P(v, w), v must appear before w in the list. We do this in two stages. We first establish that both v and w are visited by one of the dfsVisit() calls that were used by dfs() to create the list. Then we establish that within the sublist created by dfsVisit(), v must occur before w. 
The dfs() algorithm builds the list of visits to vertices by making repeated calls to dfsVisit(). For some starting vertex vs, dfsVisit(vs) recursively scans down a path of neighbors and discovers v; that is, v is reachable from vs. Because there is a path P(v,w), we know that w is reachable from vs and thus is in the sublist of vertices returns by dfsVisit(vs) (Below Figure-a). Establishing that v must before w in the sublist relies on the fact the path is acyclic. Assume that v occurs after w in the list. This implies that dfsVisit(vs) discovers w before v. Equivalently, there is a path P(w, v) connecting w to v. By appending the path P(v, w), we have a cycle of length 2 or more connecting vertex w to itself, contrary to the fact that the graph is acyclic (Below Figure-b). 
 

Implementing the topologicalSort() Method : 
The static method topologicalSort() implements the topological sort algorithm. The output is dfsList from the depth-first search algorithm discussed in Chapter 24, so we use the code structure of that algorithm, with one modification: A topological sort requires an acyclic graph, so topologicalSort() checks for a cycle when calling dfsVisit(). This simply means setting the argument checkForCycle to true and including the call in a try block. The catch block catches an exception from dfsVisit() and throws a second IllegalPathStateException : 

- Method topologicalSort() :

view plaincopy to clipboardprint?

1. public static void topologicalSort(JGraph g, LinkedList tlist) {  
2.     HashMap verticesColor = new HashMap();  
3.     Iterator iter = g.vertexSet().iterator();  
4.     while(iter.hasNext()) verticesColor.put(iter.next(), VertexColor.WHITE);  
5.     iter = g.vertexSet().iterator();  
6.     try{  
7.         while(iter.hasNext()) {  
8.             T vertex = iter.next();  
9.             if(verticesColor.get(vertex).equals(VertexColor.WHITE)) {                     
10.                 dfsVisit(g, vertex, tlist, verticesColor, true);  
11.                 //System.out.println("dfs on Vertex("+vertex+")\n\t"+tlist);  
12.             }  
13.         }  
14.         Collections.reverse(tlist);  
15.     }catch(Exception e){throw new IllegalPathStateException("topologicalSort(): graph has a cycle");}  
16. }  

- Running Time for the Topological Sort : 
The topological sort uses the algorithm for dfs(), so its running time is also O(V+E), where V is the number of vertices in the graph and E is the number of edges.