## 2013年6月16日 星期日

### [ Alg info ] Topology sort using DFS

Preface:

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.

Using DFS as Solution:

Implementation:

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;
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.
10.
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-ﬁrst search

### [NodeJS 文章收集] NodeJS accessing file with relative path

Source From  Here Question It seemed like a straight forward problem. But I am not able to crack this. Within  helper1.js  I would like to a...