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

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

Introduction

Sample Code

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
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{
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{
36.     }
37. }
38.
39. iterator =
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-ﬁrst 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:
1. DirectedGraph graph = new
2.     DefaultDirectedGraph (DefaultEdge.class);
3.
10.
11.
How would I use the DepthFirstIterator to run DFS on this graph?

How-To
Just traverse the graph using DepthFirstIterator. Here is an example:
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{
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{
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-ﬁrst search

### [ Python 常見問題 ] How to get symbolic link target in Python?

Source From  Here Question How do I extract the target path from a  symbolic link ? HowTo The problem with  os .readlink()  is it will onl...