X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=controller.git;a=blobdiff_plain;f=third-party%2Fnet.sf.jung2%2Fsrc%2Fmain%2Fjava%2Fedu%2Fuci%2Fics%2Fjung%2Falgorithms%2Fshortestpath%2FMinimumSpanningForest.java;fp=third-party%2Fnet.sf.jung2%2Fsrc%2Fmain%2Fjava%2Fedu%2Fuci%2Fics%2Fjung%2Falgorithms%2Fshortestpath%2FMinimumSpanningForest.java;h=0000000000000000000000000000000000000000;hp=18cb0fe0269f30746b8a5584d7dcd94e23854eec;hb=e1c04c5af263a9604a765f1ab98be51dfc51d8cb;hpb=a935ffda7f26be29de879a47b426d0db7a28d588 diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/MinimumSpanningForest.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/MinimumSpanningForest.java deleted file mode 100644 index 18cb0fe026..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/MinimumSpanningForest.java +++ /dev/null @@ -1,165 +0,0 @@ -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 - * @param - */ -public class MinimumSpanningForest { - - protected Graph graph; - protected Forest forest; - protected Map 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 graph, Factory> factory, - V root, Map 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 graph, Forest forest, - V root, Map 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 unfinishedEdges = new HashSet(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 graph, Forest 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(), - new ConstantTransformer(1.0)); - Set unfinishedEdges = new HashSet(graph.getEdges()); - if(graph.getVertices().contains(root)) { - this.forest.addVertex(root); - } - updateForest(forest.getVertices(), unfinishedEdges); - } - - /** - * Returns the generated forest. - */ - public Forest getForest() { - return forest; - } - - protected void updateForest(Collection tv, Collection 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 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 leftovers = new HashSet(graph.getVertices()); - leftovers.removeAll(forest.getVertices()); - if(leftovers.size() > 0) { - V anotherRoot = leftovers.iterator().next(); - forest.addVertex(anotherRoot); - updateForest(forest.getVertices(), unfinishedEdges); - } - } -}