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

### [Git 文章收集] Differences between git merge and git rebase

Source From  Here Preface Merging and rebasing are the two most popular way to applying changes from one branch into another one. They bot...