-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