## 2015年10月31日 星期六

### [ Java 代碼範本 ] JGraphT - Topological Sort

Introduction

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 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:

Sample Code

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
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.
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{
35. }
36.
42.
43. // 1) Start DFS and store finished vertex into stack in order
44. GraphIterator iterator = new DepthFirstIterator(g)
45. MyListener listener = new MyListener()
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

### [ Python 常見問題 ] python generator “send” function purpose?

Source From  Here   Question   Can someone give me an example of why the "send" function associated with Python generator function...