[ 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

[ Java 代碼範本 ] JGraphT - Bread First Search

Introduction 
先廣後深法 - BFS (Breadth-First Search, BFS) 走訪方式則是以佇列及遞迴技巧來走訪, 也是從圖形某一頂點開始走訪, 被拜訪過的頂點就做上已拜訪的記號. 接著走訪此頂點的所有相鄰且未拜訪過的頂點中的任一個頂點, 並且做上已拜訪的記號, 再以該頂點做為新的起點繼續進行先廣後深的搜尋. 底下我們以下圖來看看 BFS 的走訪過程 : 

 

步驟一 : 以頂點一為起點, 與頂點一相鄰且未拜訪過的頂點2 及頂點 5放入佇列 : 
 

步驟二 : 取出頂點2, 將與頂點2 相鄰且未拜訪過的頂點3 及頂點4 放入佇列 : 
 

步驟三 : 取出頂點5, 將與頂點5 相鄰且未拜訪過的頂點3 及頂點4 放入佇列 : 
 

步驟四 : 取出頂點3, 將與頂點3 相鄰且未拜訪過的頂點4 放入佇列 : 
 

步驟五 : 取出頂點4, 將與頂點4 相鄰且未拜訪過的頂點放入佇列中, 各位可以發現與頂點4 相鄰的頂點全部都被拜訪過, 所以無須再放入佇列中. 
 

步驟六 : 將佇列值取出並判斷是否已經走訪過, 直到佇列內無節點可走訪為止. 所以先廣後深走訪順序為 : 頂點1 > 頂點2 > 頂點5 > 頂點3 > 頂點4 

Sample Code 
底下範例代碼使用 JGrapthT 中的 BreadthFirstIterator 進行 BFS 訪問 Graph 的每個 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.UndirectedGraph  
7. import org.jgrapht.graph.SimpleGraph  
8. import org.jgrapht.traverse.BreadthFirstIterator  
9. import org.jgrapht.traverse.DepthFirstIterator  
10. import org.jgrapht.traverse.GraphIterator  
11.   
12. UndirectedGraph graph =  
13.         new SimpleGraph (DefaultEdge.class);  
14.   
15.           
16. // Graph          
17. // 1-----2-------+  
18. //   |           |             
19. //   +---5---3---+---4  
20. //       |           |  
21. //       +-----------+  
22.                                                                               
23. 5.times{  
24.     graph.addVertex(it+1);  
25. }                 
26.   
27. def edges = [:]  
28. edges[1]=[2,5]  
29. edges[2]=[3,4]  
30. edges[3]=[5,4]  
31. edges[4]=[5]  
32.   
33. edges.each{ k, v->     
34.     v.each{  
35.         graph.addEdge(k, it)  
36.     }  
37. }  
38.   
39. iterator =  
40.     new BreadthFirstIterator(graph, 1);  
41. while (iterator.hasNext()) {  
42. System.out.printf("%d ", iterator.next());  
43. }  
44. println()  

執行結果: 

1 2 5 3 4

Supplement 
* JGraphT - Depth First Search 
* Coursera - Algorithms, Part II - Breadth First Search 
* [ Intro Alg ] Elementary Graph Algorithms - Breadth-first search 
* [ 資料結構 小學堂 ] 圖形結構 : 圖形的追蹤 - 先廣後深法 (BFS) 
* [ 資料結構 小學堂 ] 佇列 : 認識佇列

[ Java 代碼範本 ] JGraphT - How to use the DepthFirstSearchIterator class to run a depth first search

Source From Here 
Question 
I am experimenting with JGraphT and have hit a brick wall trying to implement a depth first search using the JGraphT API. I have created a simple graph with nodes and vertices's as follows: 

view plaincopy to clipboardprint?

1. DirectedGraph graph = new   
2.     DefaultDirectedGraph (DefaultEdge.class);  
3.   
4. graph.addVertex(7);  
5. graph.addVertex(4);  
6. graph.addVertex(9);  
7. graph.addVertex(3);  
8. graph.addVertex(2);  
9. graph.addVertex(5);  
10.   
11.   
12. graph.addEdge(7, 4);  
13. graph.addEdge(7, 9);  
14. graph.addEdge(9, 3);  
15. graph.addEdge(3, 2);  
16. graph.addEdge(3, 5);  

How would I use the DepthFirstIterator to run DFS on this graph? 

How-To 
Just traverse the graph using DepthFirstIterator. Here is an example: 

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.UndirectedGraph  
7. import org.jgrapht.graph.SimpleGraph  
8. import org.jgrapht.traverse.DepthFirstIterator  
9. import org.jgrapht.traverse.GraphIterator  
10.   
11. UndirectedGraph graph =  
12.         new SimpleGraph (DefaultEdge.class);  
13.   
14.           
15. // Graph          
16. // 0-----1  
17. //   |  
18. //   +---2  
19. //   |  
20. //   +-------6---+  
21. //   |           |  
22. //   |   +---3   |  
23. //   +---5   +   |  
24. //       +---4---+                                                                    
25. 7.times{  
26.     graph.addVertex(it);  
27. }                 
28.   
29. def edges = [:]  
30. edges[0]=[1,2,5,6]  
31. edges[3]=[4,5]  
32. edges[4]=[6,5]  
33.   
34. edges.each{ k, v->     
35.     v.each{  
36.         graph.addEdge(k, it)  
37.     }  
38. }  
39.   
40. GraphIterator iterator =  
41.         new DepthFirstIterator(graph, 0);  
42. while (iterator.hasNext()) {  
43.     System.out.printf("%d ", iterator.next());  
44. }  
45. println()  

For more control, you can attach TraversalListener to the iterator using addTraversalListener(). Here is an example of a basic listener. 

Supplement 
* Coursera - Algorithms, Part II - Depth First Search 
* [ DS & Algorithm in C++ ] Section 9.6 : Applications of Depth-First Search 
* [ Algorithm ] Maze problem - Using Online DFS Search 
* [ Intro Alg ] Elementary Graph Algorithms - Depth-first search