## 2015年11月7日 星期六

### [ 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 helphere.

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:
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
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)
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)
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:
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.     {
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.             }
42.
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.                 {
55.                     minimumSpanningTreeTotalWeight+=edge.getWeight()
56.                     printf("\t[Test] MST Edge=%s\n", edge)
58.                     {
59.                         for(E se:g.edgesOf(s))
60.                         {
61.                             if(!spanned.contains(se.getSource())||!spanned.contains(se.getTarget()))
62.                             {
65.                             }
66.                         }
67.                     }
69.                     {
70.                         for(E se:g.edgesOf(t))
71.                         {
72.                             if(!spanned.contains(se.getSource())||!spanned.contains(se.getTarget()))
73.                             {
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:
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)
[Test] MST Edge=(B : C)
[Test] MST Edge=(B : D)
[Test] MST Edge=(B : 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)

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

## 關於我自己

Where there is a will, there is a way!