程式扎記: [ Alg info ] Topology sort using DFS

標籤

2013年6月16日 星期日

[ Alg info ] Topology sort using DFS

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

而我們的問題是要找出一種修課的順序可以滿足上面拓撲圖的要求, 而這類的問題稱之為 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 verticessuch that for every directed edge uv from vertex u to vertex vu 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 的位置. 底下是 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 的結果. 

Implementation: 
下面類別 TopologicalSort 實作了使用 DFS 的 Topology sort: (完整代碼
  1. package map.alg;  
  2.   
  3. import java.util.Stack;  
  4.   
  5. public class TopologicalSort {  
  6.       
  7.     public static void _DFS_Visit(Stack stack, Vertex v)  
  8.     {  
  9.         v.status = EStatus.Gray;  
  10.         // Discover       
  11.         for(Edge e:v.edgeSet)  
  12.         {  
  13.             if(e.to.status.equals(EStatus.White)) _DFS_Visit(stack, e.to);  
  14.         }  
  15.         // Finish  
  16.         v.status = EStatus.Black;  
  17.         stack.add(v);  
  18.     }  
  19.   
  20.     /** 
  21.      * Alg: 
  22.      *  1. Run DFS(G) 
  23.      *  2. v.f 越小說明其在 DFS 是處於較 deep 的位置 (相依性重). 因此它應該較後面處理. 
  24.      *     這邊我們使用 stack 來存放處理完畢的 vertex (依 finish 先後順序放入 stack) 
  25.      *  3. 從 Stack 取出的順序即是 Topological sort 的順序. 
  26.      *   
  27.      * Ref: 
  28.      *  - Wiki Topology sort  
  29.      *    http://en.wikipedia.org/wiki/Topological_sorting 
  30.      *     
  31.      * @param g 
  32.      * @return 
  33.      */  
  34.     public static Stack Go(Graph g)  
  35.     {  
  36.         // 0) Initialize  
  37.         Stack stack = new Stack();        
  38.         for(Vertex v:g.vtxMap.values())  
  39.         {  
  40.             v.pi = null;  
  41.             v.status = EStatus.White;  
  42.         }  
  43.           
  44.         // 1) Start DFS       
  45.         for (Vertex v : g.vtxMap.values()) {              
  46.             if (v.status.equals(EStatus.White)) {  
  47.                 _DFS_Visit(stack, v);                 
  48.             }  
  49.         }  
  50.         return stack;   
  51.     }  
  52. }  
Example: 
底下是使用上面類別來解決一開始的課程問題, 輸出為其中一個可能的修課順序: 
  1. public static void main(String args[])  
  2. {  
  3.     // 0) Prepare Graph  
  4.     Graph g = new Graph(true); // Directed graph  
  5.               
  6.     g.addVertex("微積分上"); g.addVertex("微積分下"); g.addVertex("機率");  
  7.     g.addVertex("計概"); g.addVertex("計組"); g.addVertex("作業系統");  
  8.     g.addVertex("計程"); g.addVertex("演算法上"); g.addVertex("演算法下");  
  9.     g.addVertex("計算機網路");  
  10.       
  11.     g.addEdge("微積分上""微積分下");  
  12.     g.addEdge("微積分下","機率");  
  13.     g.addEdge("機率""計算機網路");  
  14.     g.addEdge("計概""計組"); g.addEdge("計組""作業系統"); g.addEdge("作業系統""計算機網路");  
  15.     g.addEdge("計程""演算法上"); g.addEdge("演算法上""演算法下"); g.addEdge("演算法下""作業系統");  
  16.       
  17.     Stack stack = TopologicalSort.Go(g);  
  18.     System.out.printf("\t[Info] Topological Sort: %s", stack.pop());  
  19.     while (!stack.isEmpty()) {  
  20.         System.out.printf("->%s", stack.pop());  
  21.     }  
  22.     System.out.println();  
  23. }  
輸出如下: 
[Info] Topological Sort: 計程(Black)->計概(Black)->計組(Black)->演算法上(Black)->演算法下(Black)->微積分上(Black)->微積分下(Black)->機率(Black)->作業系統(Black)->計算機網路(Black)

Supplement: 
[CSIE 1212] Data Structure and Algorithm - 4/9 Graph2 
[ Intro Alg ] Elementary Graph Algorithms - Depth-first search

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!