程式扎記: [ Java 代碼範本 ] JGraphT - Minimum Spanning Tree (MST)

標籤

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                                                                                                         
  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)
  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.     {  
  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:
  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) 

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!