[ Java 代碼範本 ] JGraphT - Topological Sort

Introduction 
考慮你有修課的順序如下, 箭頭說明該課程有相依性. 如 計概->計組 指 "計概" 要先修完後才能修 "計組": 
 

而我們的問題是要找出一種修課的順序可以滿足上面拓撲圖的要求, 而這類的問題稱之為 Topology sort. 底下是 wiki 上面較詳細的說明: 

In computer science, a topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

上面說明的 vertex 就可以看成課程, 而 edge 說明課程間的相依性. 而這樣的 Graph 必須滿足 DAG (directed acyclic grapn) 而這類問題的圖形也稱為 AOV (activity on vertex). 

Using DFS as Solution: 
要解決這個問題一個常見的解法是使用 DFS (Deep First Search). 在跑 DFS 的過程中每個 vertex 都會產生所謂的 discover time 與 finish time. 而 finish time 較小的 vertex 相對 finish time 較大的 vertex 在圖形中較 deep 的位置. 以下圖來說, Vertex 7 的 finish time 會比 Vertex 0 小: 

底下是 DFS 的 pseudo code: 
 

上面的 u.f 指的即是 finish time. 因此直覺的可以將 vertex 依其 finish time 以 decreasing order 排列後, 取出的的順序便是其中一個可能的解法. (finish time 較大的先取出來, 即由 root 依序往其 leaf 移動). 而其實 finish time 大的先取; 小的後取 的概念類似於 ADT Stack 的想法 (FILO - First in Last out 或是 LIFO - Last in First out), 因此下面的實作中當每個 vertex 狀態由 Gray->Black (finish), 便將之加入 stack, 最後將該 stack 返回並依序取出 vertex 便是 Topology sort 的結果. 

Sample Code 
底下範例代碼使用 JGraphT 套件並使用上面說明的演算法實作 Topological Sort. 主要透過實作一個課製的 TraversalListenerAdapter 來監聽 Vertex finished 的時候, 並將之加入到 Stack 中, 方便後續使用 finished time 以 descending 的順序取出對應的 Vertex: 

view plaincopy to clipboardprint?

1. package lab  
2.   
3. import static org.junit.Assert.*  
4.   
5. import org.jgraph.graph.DefaultEdge  
6. import org.jgrapht.DirectedGraph  
7. import org.jgrapht.event.ConnectedComponentTraversalEvent  
8. import org.jgrapht.event.EdgeTraversalEvent  
9. import org.jgrapht.event.TraversalListenerAdapter  
10. import org.jgrapht.event.VertexTraversalEvent  
11. import org.jgrapht.graph.DefaultDirectedGraph  
12. import org.jgrapht.traverse.DepthFirstIterator  
13. import org.jgrapht.traverse.GraphIterator  
14.   
15. class MyListener extends TraversalListenerAdapter  
16. {  
17.     Stack stack = new Stack()  
18.       
19.     @Override  
20.     public void vertexFinished(VertexTraversalEvent e) {  
21.         printf("V=%s finished.\n", e.getVertex())  
22.         stack.push(e.getVertex())         
23.     }  
24. }  
25.   
26. // 0) Initialize Graph  
27. DirectedGraph g =  
28.             new DefaultDirectedGraph(DefaultEdge.class)  
29.   
30.               
31. def vertex = ["微積分上", "微積分下", "機率", "計概", "計組",  
32.               "作業系統", "計程", "演算法上", "演算法下", "計算機網路"]              
33. vertex.each{  
34.     g.addVertex(it)  
35. }  
36.   
37. g.addEdge("微積分上", "微積分下")    
38. g.addEdge("微積分下","機率")   
39. g.addEdge("機率", "計算機網路")  
40. g.addEdge("計概", "計組"); g.addEdge("計組", "作業系統"); g.addEdge("作業系統", "計算機網路")  
41. g.addEdge("計程", "演算法上"); g.addEdge("演算法上", "演算法下"); g.addEdge("演算法下", "作業系統")  
42.   
43. // 1) Start DFS and store finished vertex into stack in order   
44. GraphIterator iterator = new DepthFirstIterator(g)  
45. MyListener listener = new MyListener()  
46. iterator.addTraversalListener(listener)  
47. while(iterator.hasNext()) iterator.next()  
48.   
49. // 2) Pop out the stack with finished vertex  
50. while(!listener.stack.isEmpty()) printf("%s ", listener.stack.pop())  
51. println()  

執行結果: 

V=計算機網路 finished.
V=機率 finished.
V=微積分下 finished.
V=微積分上 finished.
V=作業系統 finished.
V=計組 finished.
V=計概 finished.
V=演算法下 finished.
V=演算法上 finished.
V=計程 finished.
計程 演算法上 演算法下 計概 計組 作業系統 微積分上 微積分下 機率 計算機網路

Supplement 
* Coursera - Topological Sort 
* [ Alg info ] Topology sort using DFS 
* JGraphT - DFS 
* Topological Ordering