1 package edu.uci.ics.jung.algorithms.shortestpath;
3 import java.util.Collection;
4 import java.util.HashMap;
5 import java.util.HashSet;
9 import org.apache.commons.collections15.Factory;
10 import org.apache.commons.collections15.functors.ConstantTransformer;
11 import org.apache.commons.collections15.map.LazyMap;
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;
19 * For the input Graph, creates a MinimumSpanningTree
20 * using a variation of Prim's algorithm.
22 * @author Tom Nelson - tomnelson@dev.java.net
27 public class MinimumSpanningForest<V,E> {
29 protected Graph<V,E> graph;
30 protected Forest<V,E> forest;
31 protected Map<E,Double> weights;
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
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
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);
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
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
65 public MinimumSpanningForest(Graph<V, E> graph, Forest<V,E> forest,
66 V root, Map<E, Double> weights) {
68 if(forest.getVertexCount() != 0) {
69 throw new IllegalArgumentException("Supplied Forest must be empty");
74 this.weights = weights;
76 Set<E> unfinishedEdges = new HashSet<E>(graph.getEdges());
77 if(graph.getVertices().contains(root)) {
78 this.forest.addVertex(root);
80 updateForest(forest.getVertices(), unfinishedEdges);
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
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
95 @SuppressWarnings("unchecked")
96 public MinimumSpanningForest(Graph<V, E> graph, Forest<V,E> forest,
99 if(forest.getVertexCount() != 0) {
100 throw new IllegalArgumentException("Supplied Forest must be empty");
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);
110 updateForest(forest.getVertices(), unfinishedEdges);
114 * Returns the generated forest.
116 public Forest<V,E> getForest() {
120 protected void updateForest(Collection<V> tv, Collection<E> unfinishedEdges) {
121 double minCost = Double.MAX_VALUE;
124 V currentVertex = null;
125 for(E e : unfinishedEdges) {
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);
137 currentVertex = first;
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);
146 currentVertex = second;
152 if(nextVertex != null && nextEdge != null) {
153 unfinishedEdges.remove(nextEdge);
154 forest.addEdge(nextEdge, currentVertex, nextVertex);
155 updateForest(forest.getVertices(), unfinishedEdges);
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);