[ Java 代碼範本 ] JGraphT - Minimum Spanning Tree (MST)

Source From Here
Question
I have a problem that can essentially be viewed as a graph. I'm considering using JGraphT to implement it instead of rolling my own. What would be the best way to get a minimum spanning tree out of a graph using JGraphT?

How-To
The list of algorithms included with jgrapht is here, and you can also find graph traversals implemented as iterators (if that is any help) here.

Below are some algorithm sample code related to MST. First of all, we create a SimpleWeightedGraph object as target graph for follow up sample code:

view plaincopy to clipboardprint?

1. package graph.alg  
2.   
3. import org.jgrapht.alg.PrimMinimumSpanningTree  
4. import org.jgrapht.graph.DefaultWeightedEdge  
5. import org.jgrapht.graph.SimpleWeightedGraph  
6.   
7. // 0) Initialize Graph    
8. SimpleWeightedGraph g =    
9.             new SimpleWeightedGraph(DefaultWeightedEdge.class)  
10.               
11.   
12. // 1) Build Graph                                                                                                         
13. g.addVertex("A")   
14. g.addVertex("B")  
15. g.addVertex("C")  
16. g.addVertex("D")  
17. g.addVertex("E")  
18. g.addVertex("F")  
19.   
20. def edges = [:]  
21. edges["A"]=["B": 6, "F":12, "E":10]  
22. edges["B"]=["A": 6, "C": 3, "D": 5, "F": 8]  
23. edges["C"]=["B": 3, "D": 7]  
24. edges["D"]=["B": 5, "C": 7, "E": 9, "F":11]  
25. edges["E"]=["A":10, "D": 9, "F":16]  
26. edges["F"]=["A":12, "B": 8, "D":11, "E":16]  
27.   
28. edges.each{ k, v->  
29.     v.each{ n, w->  
30.         DefaultWeightedEdge e = g.addEdge(k, n)  
31.         if(e!=null)  
32.         {             
33.             g.setEdgeWeight(e, w)  
34.         }  
35.     }  
36. }  

The graph which looks like:


- Prim Algorithm (PrimMinimumSpanningTree)

view plaincopy to clipboardprint?

1. printf("\t[Info] Prim's MST:\n")  
2. PrimMinimumSpanningTree pMST = new PrimMinimumSpanningTree(g)  
3. for(DefaultWeightedEdge e:pMST.getMinimumSpanningTreeEdgeSet())  
4. {  
5.     printf("\t%s (%.01f)\n", e, e.getWeight())  
6. }  

Output:

[Info] Prim's MST:
(B : F) (8.0)
(A : B) (6.0)
(D : E) (9.0)
(B : D) (5.0)
(B : C) (3.0)

- Kruskal Algorithm (KruskalMinimumSpanningTree)

view plaincopy to clipboardprint?

1. KruskalMinimumSpanningTree kMST = new KruskalMinimumSpanningTree(g)  
2. printf("\t[Info] Kruskal's MST (%.01f):\n", kMST.getMinimumSpanningTreeTotalWeight())  
3. for(DefaultWeightedEdge e:kMST.getMinimumSpanningTreeEdgeSet())  
4. {  
5.     printf("\t%s (%.01f)\n", e, e.getWeight())  
6. }  

Output:

[Info] Kruskal's MST (31.0):
(A : B) (6.0)
(B : D) (5.0)
(D : E) (9.0)
(B : C) (3.0)
(B : F) (8.0)

Or you can implement your own MST by extends MinimumSpanningTree class. For example:

view plaincopy to clipboardprint?

1. package graph.alg.cust  
2.   
3. import org.jgrapht.Graph  
4. import org.jgrapht.alg.interfaces.MinimumSpanningTree  
5.   
6. class JPrimMinimumSpanningTree  implements MinimumSpanningTree{  
7.   
8.     /** 
9.      * Minimum Spanning-Tree/Forest edge set 
10.      */  
11.     private final List minimumSpanningTreeEdgeList;  
12.   
13.     /** 
14.      * Minimum Spanning-Tree/Forest edge set overall weight 
15.      */  
16.     private final double minimumSpanningTreeTotalWeight;  
17.   
18.     public JPrimMinimumSpanningTree(final Graph g, V sv = null)  
19.     {  
20.         minimumSpanningTreeEdgeList = new LinkedList()   
21.         Set unspanned = new HashSet(g.vertexSet())  
22.         Set spanned = new HashSet()  
23.           
24.         while (!unspanned.isEmpty())   
25.         {  
26.             PriorityQueue dangling =  
27.             new PriorityQueue(  
28.                 g.edgeSet().size(),  
29.                 new Comparator() {  
30.                     @Override public int compare(E lop, E rop)  
31.                     {  
32.                         return Double.valueOf(g.getEdgeWeight(lop))  
33.                             .compareTo(g.getEdgeWeight(rop));  
34.                     }  
35.                 });  
36.             if(sv==null)  
37.             {  
38.                 sv = unspanned.iterator().next()  
39.                 unspanned.remove(sv)  
40.             }  
41.             spanned.add(sv)  
42.               
43.             dangling.addAll(g.edgesOf(sv))  
44.             sv = null  
45.             while(dangling.size()>0)  
46.             {  
47.                 E edge = dangling.poll()  
48.                 V s = edge.getSource(); V t = edge.getTarget()  
49.                 boolean hit=false  
50.                 if(unspanned.remove(s)) hit=true  
51.                 if(unspanned.remove(t)) hit=true                  
52.                 if(hit)  
53.                 {  
54.                     minimumSpanningTreeEdgeList.add(edge)  
55.                     minimumSpanningTreeTotalWeight+=edge.getWeight()  
56.                     printf("\t[Test] MST Edge=%s\n", edge)  
57.                     if(spanned.add(s))  
58.                     {  
59.                         for(E se:g.edgesOf(s))  
60.                         {  
61.                             if(!spanned.contains(se.getSource())||!spanned.contains(se.getTarget()))  
62.                             {  
63.                                 dangling.add(se)  
64.                                 printf("\t\tAdd Edge=%s\n", se)  
65.                             }  
66.                         }  
67.                     }                     
68.                     if(spanned.add(t))  
69.                     {  
70.                         for(E se:g.edgesOf(t))  
71.                         {  
72.                             if(!spanned.contains(se.getSource())||!spanned.contains(se.getTarget()))  
73.                             {  
74.                                 dangling.add(se)  
75.                                 printf("\t\tAdd Edge=%s\n", se)  
76.                             }  
77.                         }  
78.                     }                                         
79.                 }                 
80.             }  
81.         }  
82.     }  
83.       
84.     public List getMinimumSpanningTreeEdgeList(){return Collections.unmodifiableList(minimumSpanningTreeEdgeList)}  
85.       
86.     @Override public Set getMinimumSpanningTreeEdgeSet()  
87.     {  
88.         Set set = new HashSet(); set.addAll(minimumSpanningTreeEdgeList)  
89.         return Collections.unmodifiableSet(set);  
90.     }  
91.   
92.     @Override public double getMinimumSpanningTreeTotalWeight()  
93.     {  
94.         return minimumSpanningTreeTotalWeight;  
95.     }  
96. }  

Testing Code:

view plaincopy to clipboardprint?

1. printf("\t[Info] JPrim's MST:\n")  
2. JPrimMinimumSpanningTree pMST = new JPrimMinimumSpanningTree(g, "A")  
3. for(DefaultWeightedEdge e:pMST.getMinimumSpanningTreeEdgeList())  
4. {  
5.     printf("\t%s (%.01f)\n", e, e.getWeight())  
6. }  

Output:

[Info] JPrim's MST:
[Test] MST Edge=(A : B)
Add Edge=(B : C)
Add Edge=(B : D)
Add Edge=(B : F)
[Test] MST Edge=(B : C)
Add Edge=(C : D)
[Test] MST Edge=(B : D)
Add Edge=(D : E)
Add Edge=(D : F)
[Test] MST Edge=(B : F)
Add Edge=(E : F)
[Test] MST Edge=(D : E)
(A : B) (6.0)
(B : C) (3.0)
(B : D) (5.0)
(B : F) (8.0)
(D : E) (9.0)

Supplement
* [ Alg info ] Borůvka's algorithm (MST) 

* [ Alg info ] Kruskal’s algorithm (MST) 
* Coursera - Algorithm2 - Prim's Algorithm
* [ 資料結構 小學堂 ] 圖形結構 : 擴張樹 - 求最小成本擴張樹 (Kruskal 演算法)

This message was edited 15 times. Last update was at 07/11/2015 22:11:59