--- /dev/null
+package edu.uci.ics.jung.algorithms.shortestpath;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.commons.collections15.Factory;
+import org.apache.commons.collections15.functors.ConstantTransformer;
+import org.apache.commons.collections15.map.LazyMap;
+
+import edu.uci.ics.jung.graph.Forest;
+import edu.uci.ics.jung.graph.Graph;
+import edu.uci.ics.jung.graph.util.EdgeType;
+import edu.uci.ics.jung.graph.util.Pair;
+
+/**
+ * For the input Graph, creates a MinimumSpanningTree
+ * using a variation of Prim's algorithm.
+ *
+ * @author Tom Nelson - tomnelson@dev.java.net
+ *
+ * @param <V>
+ * @param <E>
+ */
+public class MinimumSpanningForest<V,E> {
+
+ protected Graph<V,E> graph;
+ protected Forest<V,E> forest;
+ protected Map<E,Double> weights;
+
+ /**
+ * Creates a Forest from the supplied Graph and supplied Factory, which
+ * is used to create a new, empty Forest. If non-null, the supplied root
+ * will be used as the root of the tree/forest. If the supplied root is
+ * null, or not present in the Graph, then an arbitrary Graph vertex
+ * will be selected as the root.
+ * If the Minimum Spanning Tree does not include all vertices of the
+ * Graph, then a leftover vertex is selected as a root, and another
+ * tree is created.
+ * @param graph the input graph
+ * @param factory the factory to use to create the new forest
+ * @param root the vertex of the graph to be used as the root of the forest
+ * @param weights edge weights
+ */
+ public MinimumSpanningForest(Graph<V, E> graph, Factory<Forest<V,E>> factory,
+ V root, Map<E, Double> weights) {
+ this(graph, factory.create(), root, weights);
+ }
+
+ /**
+ * Creates a minimum spanning forest from the supplied graph, populating the
+ * supplied Forest, which must be empty.
+ * If the supplied root is null, or not present in the Graph,
+ * then an arbitrary Graph vertex will be selected as the root.
+ * If the Minimum Spanning Tree does not include all vertices of the
+ * Graph, then a leftover vertex is selected as a root, and another
+ * tree is created
+ * @param graph the Graph to find MST in
+ * @param forest the Forest to populate. Must be empty
+ * @param root first Tree root, may be null
+ * @param weights edge weights, may be null
+ */
+ public MinimumSpanningForest(Graph<V, E> graph, Forest<V,E> forest,
+ V root, Map<E, Double> weights) {
+
+ if(forest.getVertexCount() != 0) {
+ throw new IllegalArgumentException("Supplied Forest must be empty");
+ }
+ this.graph = graph;
+ this.forest = forest;
+ if(weights != null) {
+ this.weights = weights;
+ }
+ Set<E> unfinishedEdges = new HashSet<E>(graph.getEdges());
+ if(graph.getVertices().contains(root)) {
+ this.forest.addVertex(root);
+ }
+ updateForest(forest.getVertices(), unfinishedEdges);
+ }
+
+ /**
+ * Creates a minimum spanning forest from the supplied graph, populating the
+ * supplied Forest, which must be empty.
+ * If the supplied root is null, or not present in the Graph,
+ * then an arbitrary Graph vertex will be selected as the root.
+ * If the Minimum Spanning Tree does not include all vertices of the
+ * Graph, then a leftover vertex is selected as a root, and another
+ * tree is created
+ * @param graph the Graph to find MST in
+ * @param forest the Forest to populate. Must be empty
+ * @param root first Tree root, may be null
+ */
+ @SuppressWarnings("unchecked")
+ public MinimumSpanningForest(Graph<V, E> graph, Forest<V,E> forest,
+ V root) {
+
+ if(forest.getVertexCount() != 0) {
+ throw new IllegalArgumentException("Supplied Forest must be empty");
+ }
+ this.graph = graph;
+ this.forest = forest;
+ this.weights = LazyMap.decorate(new HashMap<E,Double>(),
+ new ConstantTransformer(1.0));
+ Set<E> unfinishedEdges = new HashSet<E>(graph.getEdges());
+ if(graph.getVertices().contains(root)) {
+ this.forest.addVertex(root);
+ }
+ updateForest(forest.getVertices(), unfinishedEdges);
+ }
+
+ /**
+ * Returns the generated forest.
+ */
+ public Forest<V,E> getForest() {
+ return forest;
+ }
+
+ protected void updateForest(Collection<V> tv, Collection<E> unfinishedEdges) {
+ double minCost = Double.MAX_VALUE;
+ E nextEdge = null;
+ V nextVertex = null;
+ V currentVertex = null;
+ for(E e : unfinishedEdges) {
+
+ if(forest.getEdges().contains(e)) continue;
+ // find the lowest cost edge, get its opposite endpoint,
+ // and then update forest from its Successors
+ Pair<V> endpoints = graph.getEndpoints(e);
+ V first = endpoints.getFirst();
+ V second = endpoints.getSecond();
+ if(tv.contains(first) == true && tv.contains(second) == false) {
+ if(weights.get(e) < minCost) {
+ minCost = weights.get(e);
+ nextEdge = e;
+ currentVertex = first;
+ nextVertex = second;
+ }
+ }
+ if(graph.getEdgeType(e) == EdgeType.UNDIRECTED &&
+ tv.contains(second) == true && tv.contains(first) == false) {
+ if(weights.get(e) < minCost) {
+ minCost = weights.get(e);
+ nextEdge = e;
+ currentVertex = second;
+ nextVertex = first;
+ }
+ }
+ }
+
+ if(nextVertex != null && nextEdge != null) {
+ unfinishedEdges.remove(nextEdge);
+ forest.addEdge(nextEdge, currentVertex, nextVertex);
+ updateForest(forest.getVertices(), unfinishedEdges);
+ }
+ Collection<V> leftovers = new HashSet<V>(graph.getVertices());
+ leftovers.removeAll(forest.getVertices());
+ if(leftovers.size() > 0) {
+ V anotherRoot = leftovers.iterator().next();
+ forest.addVertex(anotherRoot);
+ updateForest(forest.getVertices(), unfinishedEdges);
+ }
+ }
+}
Code Review / controller.git / blobdiff