third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/MinimumSpanningForest.java

   1 package edu.uci.ics.jung.algorithms.shortestpath;
   2
   3 import java.util.Collection;
   4 import java.util.HashMap;
   5 import java.util.HashSet;
   6 import java.util.Map;
   7 import java.util.Set;
   8
   9 import org.apache.commons.collections15.Factory;
  10 import org.apache.commons.collections15.functors.ConstantTransformer;
  11 import org.apache.commons.collections15.map.LazyMap;
  12
  13 import edu.uci.ics.jung.graph.Forest;
  14 import edu.uci.ics.jung.graph.Graph;
  15 import edu.uci.ics.jung.graph.util.EdgeType;
  16 import edu.uci.ics.jung.graph.util.Pair;
  17
  18 /**
  19  * For the input Graph, creates a MinimumSpanningTree
  20  * using a variation of Prim's algorithm.
  21  *
  22  * @author Tom Nelson - tomnelson@dev.java.net
  23  *
  24  * @param <V>
  25  * @param <E>
  26  */
  27 public class MinimumSpanningForest<V,E> {
  28
  29         protected Graph<V,E> graph;
  30         protected Forest<V,E> forest;
  31         protected Map<E,Double> weights;
  32
  33         /**
  34          * Creates a Forest from the supplied Graph and supplied Factory, which
  35          * is used to create a new, empty Forest. If non-null, the supplied root
  36          * will be used as the root of the tree/forest. If the supplied root is
  37          * null, or not present in the Graph, then an arbitrary Graph vertex
  38          * will be selected as the root.
  39          * If the Minimum Spanning Tree does not include all vertices of the
  40          * Graph, then a leftover vertex is selected as a root, and another
  41          * tree is created.
  42          * @param graph the input graph
  43          * @param factory the factory to use to create the new forest
  44          * @param root the vertex of the graph to be used as the root of the forest
  45          * @param weights edge weights
  46          */
  47         public MinimumSpanningForest(Graph<V, E> graph, Factory<Forest<V,E>> factory,
  48                         V root, Map<E, Double> weights) {
  49                 this(graph, factory.create(), root, weights);
  50         }
  51
  52         /**
  53          * Creates a minimum spanning forest from the supplied graph, populating the
  54          * supplied Forest, which must be empty.
  55          * If the supplied root is null, or not present in the Graph,
  56          * then an arbitrary Graph vertex will be selected as the root.
  57          * If the Minimum Spanning Tree does not include all vertices of the
  58          * Graph, then a leftover vertex is selected as a root, and another
  59          * tree is created
  60          * @param graph the Graph to find MST in
  61          * @param forest the Forest to populate. Must be empty
  62          * @param root first Tree root, may be null
  63          * @param weights edge weights, may be null
  64          */
  65         public MinimumSpanningForest(Graph<V, E> graph, Forest<V,E> forest,
  66                         V root, Map<E, Double> weights) {
  67
  68                 if(forest.getVertexCount() != 0) {
  69                         throw new IllegalArgumentException("Supplied Forest must be empty");
  70                 }
  71                 this.graph = graph;
  72                 this.forest = forest;
  73                 if(weights != null) {
  74                         this.weights = weights;
  75                 }
  76                 Set<E> unfinishedEdges = new HashSet<E>(graph.getEdges());
  77                 if(graph.getVertices().contains(root)) {
  78                         this.forest.addVertex(root);
  79                 }
  80                 updateForest(forest.getVertices(), unfinishedEdges);
  81         }
  82
  83     /**
  84      * Creates a minimum spanning forest from the supplied graph, populating the
  85      * supplied Forest, which must be empty.
  86      * If the supplied root is null, or not present in the Graph,
  87      * then an arbitrary Graph vertex will be selected as the root.
  88      * If the Minimum Spanning Tree does not include all vertices of the
  89      * Graph, then a leftover vertex is selected as a root, and another
  90      * tree is created
  91      * @param graph the Graph to find MST in
  92      * @param forest the Forest to populate. Must be empty
  93      * @param root first Tree root, may be null
  94      */
  95     @SuppressWarnings("unchecked")
  96     public MinimumSpanningForest(Graph<V, E> graph, Forest<V,E> forest,
  97             V root) {
  98
  99         if(forest.getVertexCount() != 0) {
 100             throw new IllegalArgumentException("Supplied Forest must be empty");
 101         }
 102         this.graph = graph;
 103         this.forest = forest;
 104         this.weights = LazyMap.decorate(new HashMap<E,Double>(),
 105                 new ConstantTransformer(1.0));
 106         Set<E> unfinishedEdges = new HashSet<E>(graph.getEdges());
 107         if(graph.getVertices().contains(root)) {
 108             this.forest.addVertex(root);
 109         }
 110         updateForest(forest.getVertices(), unfinishedEdges);
 111     }
 112
 113         /**
 114          * Returns the generated forest.
 115          */
 116         public Forest<V,E> getForest() {
 117                 return forest;
 118         }
 119
 120         protected void updateForest(Collection<V> tv, Collection<E> unfinishedEdges) {
 121                 double minCost = Double.MAX_VALUE;
 122                 E nextEdge = null;
 123                 V nextVertex = null;
 124                 V currentVertex = null;
 125                 for(E e : unfinishedEdges) {
 126
 127                         if(forest.getEdges().contains(e)) continue;
 128                         // find the lowest cost edge, get its opposite endpoint,
 129                         // and then update forest from its Successors
 130                         Pair<V> endpoints = graph.getEndpoints(e);
 131                         V first = endpoints.getFirst();
 132                         V second = endpoints.getSecond();
 133                         if(tv.contains(first) == true && tv.contains(second) == false) {
 134                                 if(weights.get(e) < minCost) {
 135                                         minCost = weights.get(e);
 136                                         nextEdge = e;
 137                                         currentVertex = first;
 138                                         nextVertex = second;
 139                                 }
 140                         }
 141                         if(graph.getEdgeType(e) == EdgeType.UNDIRECTED &&
 142                                         tv.contains(second) == true && tv.contains(first) == false) {
 143                                 if(weights.get(e) < minCost) {
 144                                         minCost = weights.get(e);
 145                                         nextEdge = e;
 146                                         currentVertex = second;
 147                                         nextVertex = first;
 148                                 }
 149                         }
 150                 }
 151
 152                 if(nextVertex != null && nextEdge != null) {
 153                         unfinishedEdges.remove(nextEdge);
 154                         forest.addEdge(nextEdge, currentVertex, nextVertex);
 155                         updateForest(forest.getVertices(), unfinishedEdges);
 156                 }
 157                 Collection<V> leftovers = new HashSet<V>(graph.getVertices());
 158                 leftovers.removeAll(forest.getVertices());
 159                 if(leftovers.size() > 0) {
 160                         V anotherRoot = leftovers.iterator().next();
 161                         forest.addVertex(anotherRoot);
 162                         updateForest(forest.getVertices(), unfinishedEdges);
 163                 }
 164         }
 165 }