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

   1 package edu.uci.ics.jung.algorithms.shortestpath;
   2
   3 import java.util.Collection;
   4 import java.util.Set;
   5
   6 import org.apache.commons.collections15.Factory;
   7 import org.apache.commons.collections15.Transformer;
   8 import org.apache.commons.collections15.functors.ConstantTransformer;
   9
  10 import edu.uci.ics.jung.algorithms.cluster.WeakComponentClusterer;
  11 import edu.uci.ics.jung.algorithms.filters.FilterUtils;
  12 import edu.uci.ics.jung.graph.Forest;
  13 import edu.uci.ics.jung.graph.Graph;
  14 import edu.uci.ics.jung.graph.Tree;
  15 import edu.uci.ics.jung.graph.util.TreeUtils;
  16
  17 /**
  18  * For the input Graph, creates a MinimumSpanningTree
  19  * using a variation of Prim's algorithm.
  20  *
  21  * @author Tom Nelson - tomnelson@dev.java.net
  22  *
  23  * @param <V>
  24  * @param <E>
  25  */
  26 @SuppressWarnings("unchecked")
  27 public class MinimumSpanningForest2<V,E> {
  28
  29         protected Graph<V,E> graph;
  30         protected Forest<V,E> forest;
  31         protected Transformer<E,Double> weights =
  32                 (Transformer<E,Double>)new ConstantTransformer<Double>(1.0);
  33
  34         /**
  35          * create a Forest from the supplied Graph and supplied Factory, which
  36          * is used to create a new, empty Forest. If non-null, the supplied root
  37          * will be used as the root of the tree/forest. If the supplied root is
  38          * null, or not present in the Graph, then an arbitary Graph vertex
  39          * will be selected as the root.
  40          * If the Minimum Spanning Tree does not include all vertices of the
  41          * Graph, then a leftover vertex is selected as a root, and another
  42          * tree is created
  43          * @param graph
  44          * @param factory
  45          * @param weights
  46          */
  47         public MinimumSpanningForest2(Graph<V, E> graph,
  48                         Factory<Forest<V,E>> factory,
  49                         Factory<? extends Graph<V,E>> treeFactory,
  50                         Transformer<E, Double> weights) {
  51                 this(graph, factory.create(),
  52                                 treeFactory,
  53                                 weights);
  54         }
  55
  56         /**
  57          * create a forest from the supplied graph, populating the
  58          * supplied Forest, which must be empty.
  59          * If the supplied root is null, or not present in the Graph,
  60          * then an arbitary Graph vertex will be selected as the root.
  61          * If the Minimum Spanning Tree does not include all vertices of the
  62          * Graph, then a leftover vertex is selected as a root, and another
  63          * tree is created
  64          * @param graph the Graph to find MST in
  65          * @param forest the Forest to populate. Must be empty
  66          * @param weights edge weights, may be null
  67          */
  68         public MinimumSpanningForest2(Graph<V, E> graph,
  69                         Forest<V,E> forest,
  70                         Factory<? extends Graph<V,E>> treeFactory,
  71                         Transformer<E, Double> weights) {
  72
  73                 if(forest.getVertexCount() != 0) {
  74                         throw new IllegalArgumentException("Supplied Forest must be empty");
  75                 }
  76                 this.graph = graph;
  77                 this.forest = forest;
  78                 if(weights != null) {
  79                         this.weights = weights;
  80                 }
  81
  82                 WeakComponentClusterer<V,E> wcc =
  83                         new WeakComponentClusterer<V,E>();
  84                 Set<Set<V>> component_vertices = wcc.transform(graph);
  85                 Collection<Graph<V,E>> components =
  86                         FilterUtils.createAllInducedSubgraphs(component_vertices, graph);
  87
  88                 for(Graph<V,E> component : components) {
  89                         PrimMinimumSpanningTree<V,E> mst =
  90                                 new PrimMinimumSpanningTree<V,E>(treeFactory, this.weights);
  91                         Graph<V,E> subTree = mst.transform(component);
  92                         if(subTree instanceof Tree) {
  93                                 TreeUtils.addSubTree(forest, (Tree<V,E>)subTree, null, null);
  94                         }
  95                 }
  96         }
  97
  98         /**
  99          * Returns the generated forest.
 100          */
 101         public Forest<V,E> getForest() {
 102                 return forest;
 103         }
 104 }