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%2FDijkstraDistance.java;fp=third-party%2Fnet.sf.jung2%2Fsrc%2Fmain%2Fjava%2Fedu%2Fuci%2Fics%2Fjung%2Falgorithms%2Fshortestpath%2FDijkstraDistance.java;h=0000000000000000000000000000000000000000;hp=3e99e16096ba8491b8f05ac6c0b84a97c3a1b67c;hb=e1c04c5af263a9604a765f1ab98be51dfc51d8cb;hpb=a935ffda7f26be29de879a47b426d0db7a28d588 diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DijkstraDistance.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DijkstraDistance.java deleted file mode 100644 index 3e99e16096..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DijkstraDistance.java +++ /dev/null @@ -1,582 +0,0 @@ -/* - * Created on Jul 9, 2005 - * - * Copyright (c) 2005, the JUNG Project and the Regents of the University - * of California - * All rights reserved. - * - * This software is open-source under the BSD license; see either - * "license.txt" or - * http://jung.sourceforge.net/license.txt for a description. - */ -package edu.uci.ics.jung.algorithms.shortestpath; - -import java.util.Collection; -import java.util.Comparator; -import java.util.HashMap; -import java.util.HashSet; -import java.util.LinkedHashMap; -import java.util.Map; -import java.util.Set; - -import org.apache.commons.collections15.Transformer; -import org.apache.commons.collections15.functors.ConstantTransformer; - -import edu.uci.ics.jung.algorithms.util.BasicMapEntry; -import edu.uci.ics.jung.algorithms.util.MapBinaryHeap; -import edu.uci.ics.jung.graph.Graph; -import edu.uci.ics.jung.graph.Hypergraph; - -/** - *

Calculates distances in a specified graph, using - * Dijkstra's single-source-shortest-path algorithm. All edge weights - * in the graph must be nonnegative; if any edge with negative weight is - * found in the course of calculating distances, an - * IllegalArgumentException will be thrown. - * (Note: this exception will only be thrown when such an edge would be - * used to update a given tentative distance; - * the algorithm does not check for negative-weight edges "up front".) - * - *

Distances and partial results are optionally cached (by this instance) - * for later reference. Thus, if the 10 closest vertices to a specified source - * vertex are known, calculating the 20 closest vertices does not require - * starting Dijkstra's algorithm over from scratch.

- * - *

Distances are stored as double-precision values. - * If a vertex is not reachable from the specified source vertex, no - * distance is stored. This is new behavior with version 1.4; - * the previous behavior was to store a value of - * Double.POSITIVE_INFINITY. This change gives the algorithm - * an approximate complexity of O(kD log k), where k is either the number of - * requested targets or the number of reachable vertices (whichever is smaller), - * and D is the average degree of a vertex.

- * - *

The elements in the maps returned by getDistanceMap - * are ordered (that is, returned - * by the iterator) by nondecreasing distance from source.

- * - *

Users are cautioned that distances calculated should be assumed to - * be invalidated by changes to the graph, and should invoke reset() - * when appropriate so that the distances can be recalculated.

- * - * @author Joshua O'Madadhain - * @author Tom Nelson converted to jung2 - */ -public class DijkstraDistance implements Distance -{ - protected Hypergraph g; - protected Transformer nev; - protected Map sourceMap; // a map of source vertices to an instance of SourceData - protected boolean cached; - protected double max_distance; - protected int max_targets; - - /** - *

Creates an instance of DijkstraShortestPath for - * the specified graph and the specified method of extracting weights - * from edges, which caches results locally if and only if - * cached is true. - * - * @param g the graph on which distances will be calculated - * @param nev the class responsible for returning weights for edges - * @param cached specifies whether the results are to be cached - */ - public DijkstraDistance(Hypergraph g, Transformer nev, boolean cached) { - this.g = g; - this.nev = nev; - this.sourceMap = new HashMap(); - this.cached = cached; - this.max_distance = Double.POSITIVE_INFINITY; - this.max_targets = Integer.MAX_VALUE; - } - - /** - *

Creates an instance of DijkstraShortestPath for - * the specified graph and the specified method of extracting weights - * from edges, which caches results locally. - * - * @param g the graph on which distances will be calculated - * @param nev the class responsible for returning weights for edges - */ - public DijkstraDistance(Hypergraph g, Transformer nev) { - this(g, nev, true); - } - - /** - *

Creates an instance of DijkstraShortestPath for - * the specified unweighted graph (that is, all weights 1) which - * caches results locally. - * - * @param g the graph on which distances will be calculated - */ - @SuppressWarnings("unchecked") - public DijkstraDistance(Hypergraph g) { - this(g, new ConstantTransformer(1), true); - } - - /** - *

Creates an instance of DijkstraShortestPath for - * the specified unweighted graph (that is, all weights 1) which - * caches results locally. - * - * @param g the graph on which distances will be calculated - * @param cached specifies whether the results are to be cached - */ - @SuppressWarnings("unchecked") - public DijkstraDistance(Hypergraph g, boolean cached) { - this(g, new ConstantTransformer(1), cached); - } - - /** - * Implements Dijkstra's single-source shortest-path algorithm for - * weighted graphs. Uses a MapBinaryHeap as the priority queue, - * which gives this algorithm a time complexity of O(m lg n) (m = # of edges, n = - * # of vertices). - * This algorithm will terminate when any of the following have occurred (in order - * of priority): - *

    - *
  • the distance to the specified target (if any) has been found - *
  • no more vertices are reachable - *
  • the specified # of distances have been found, or the maximum distance - * desired has been exceeded - *
  • all distances have been found - *
- * - * @param source the vertex from which distances are to be measured - * @param numDests the number of distances to measure - * @param targets the set of vertices to which distances are to be measured - * @param regular boolean is true if we want regular SP dijkstra. False for MT. - */ - private LinkedHashMap singleSourceShortestPath(V source, Collection targets, int numDests, boolean regular) - { - SourceData sd = getSourceData(source); - - Set to_get = new HashSet(); - if (targets != null) { - to_get.addAll(targets); - Set existing_dists = sd.distances.keySet(); - for(V o : targets) { - if (existing_dists.contains(o)) - to_get.remove(o); - } - } - - // if we've exceeded the max distance or max # of distances we're willing to calculate, or - // if we already have all the distances we need, - // terminate - if (sd.reached_max || - (targets != null && to_get.isEmpty()) || - (sd.distances.size() >= numDests)) - { - return sd.distances; - } - - while (!sd.unknownVertices.isEmpty() && (sd.distances.size() < numDests || !to_get.isEmpty())) - { - Map.Entry p = sd.getNextVertex(); - V v = p.getKey(); - double v_dist = p.getValue().doubleValue(); - to_get.remove(v); - if (v_dist > this.max_distance) - { - // we're done; put this vertex back in so that we're not including - // a distance beyond what we specified - sd.restoreVertex(v, v_dist); - sd.reached_max = true; - break; - } - sd.dist_reached = v_dist; - - if (sd.distances.size() >= this.max_targets) - { - sd.reached_max = true; - break; - } - - for (E e : getEdgesToCheck(v) ) - { - for (V w : g.getIncidentVertices(e)) - { - if (!sd.distances.containsKey(w)) - { - double edge_weight = nev.transform(e).doubleValue(); - if (edge_weight < 0) - throw new IllegalArgumentException("Edges weights must be non-negative"); - double new_dist; - if (regular == true) { - new_dist = v_dist + edge_weight; - } else { - if (v_dist <= edge_weight) { - new_dist = edge_weight; - } else { - new_dist = v_dist; - } - } - if (!sd.estimatedDistances.containsKey(w)) - { - sd.createRecord(w, e, new_dist); - } - else - { - double w_dist = ((Double)sd.estimatedDistances.get(w)).doubleValue(); - if (new_dist < w_dist) // update tentative distance & path for w - sd.update(w, e, new_dist); - } - } - } - } - } - return sd.distances; - } - - /** - * Implements Dijkstra's single-source shortest-path algorithm for - * weighted graphs. Uses a MapBinaryHeap as the priority queue, - * which gives this algorithm a time complexity of O(m lg n) (m = # of edges, n = - * # of vertices). - * This algorithm will terminate when any of the following have occurred (in order - * of priority): - *
    - *
  • the distance to the specified target (if any) has been found - *
  • no more vertices are reachable - *
  • the specified # of distances have been found, or the maximum distance - * desired has been exceeded - *
  • all distances have been found - *
- * - * @param source the vertex from which distances are to be measured - * @param numDests the number of distances to measure - * @param targets the set of vertices to which distances are to be measured - */ - protected LinkedHashMap singleSourceShortestPath(V source, Collection targets, int numDests) - { - return singleSourceShortestPath(source, targets, numDests, true); - } - - /** - * Implements Dijkstra's single-source shortest-path algorithm for - * weighted graphs. Uses a MapBinaryHeap as the priority queue, - * which gives this algorithm a time complexity of O(m lg n) (m = # of edges, n = - * # of vertices). - * This algorithm will terminate when any of the following have occurred (in order - * of priority): - *
    - *
  • the distance to the specified target (if any) has been found - *
  • no more vertices are reachable - *
  • the specified # of distances have been found, or the maximum distance - * desired has been exceeded - *
  • all distances have been found - *
- * - * @param source the vertex from which distances are to be measured - * @param numDests the number of distances to measure - * @param targets the set of vertices to which distances are to be measured - */ - protected LinkedHashMap singleSourceMaxThroughputPath(V source, Collection targets, int numDests) - { - return singleSourceShortestPath(source, targets, numDests, false); - } - - protected SourceData getSourceData(V source) - { - SourceData sd = sourceMap.get(source); - if (sd == null) - sd = new SourceData(source); - return sd; - } - - /** - * Returns the set of edges incident to v that should be tested. - * By default, this is the set of outgoing edges for instances of Graph, - * the set of incident edges for instances of Hypergraph, - * and is otherwise undefined. - */ - protected Collection getEdgesToCheck(V v) - { - if (g instanceof Graph) - return ((Graph)g).getOutEdges(v); - else - return g.getIncidentEdges(v); - - } - - - /** - * Returns the length of a shortest path from the source to the target vertex, - * or null if the target is not reachable from the source. - * If either vertex is not in the graph for which this instance - * was created, throws IllegalArgumentException. - * - * @see #getDistanceMap(Object) - * @see #getDistanceMap(Object,int) - */ - public Number getDistance(V source, V target) - { - if (g.containsVertex(target) == false) - throw new IllegalArgumentException("Specified target vertex " + - target + " is not part of graph " + g); - if (g.containsVertex(source) == false) - throw new IllegalArgumentException("Specified source vertex " + - source + " is not part of graph " + g); - - Set targets = new HashSet(); - targets.add(target); - Map distanceMap = getDistanceMap(source, targets); - return distanceMap.get(target); - } - - - /** - * Returns a {@code Map} from each element {@code t} of {@code targets} to the - * shortest-path distance from {@code source} to {@code t}. - */ - public Map getDistanceMap(V source, Collection targets) - { - if (g.containsVertex(source) == false) - throw new IllegalArgumentException("Specified source vertex " + - source + " is not part of graph " + g); - if (targets.size() > max_targets) - throw new IllegalArgumentException("size of target set exceeds maximum " + - "number of targets allowed: " + this.max_targets); - - Map distanceMap = - singleSourceShortestPath(source, targets, - Math.min(g.getVertexCount(), max_targets)); - if (!cached) - reset(source); - - return distanceMap; - } - - /** - *

Returns a LinkedHashMap which maps each vertex - * in the graph (including the source vertex) - * to its distance from the source vertex. - * The map's iterator will return the elements in order of - * increasing distance from source.

- * - *

The size of the map returned will be the number of - * vertices reachable from source.

- * - * @see #getDistanceMap(Object,int) - * @see #getDistance(Object,Object) - * @param source the vertex from which distances are measured - */ - public Map getDistanceMap(V source) - { - return getDistanceMap(source, Math.min(g.getVertexCount(), max_targets)); - } - - - - /** - *

Returns a LinkedHashMap which maps each of the closest - * numDist vertices to the source vertex - * in the graph (including the source vertex) - * to its distance from the source vertex. Throws - * an IllegalArgumentException if source - * is not in this instance's graph, or if numDests is - * either less than 1 or greater than the number of vertices in the - * graph.

- * - *

The size of the map returned will be the smaller of - * numDests and the number of vertices reachable from - * source. - * - * @see #getDistanceMap(Object) - * @see #getDistance(Object,Object) - * @param source the vertex from which distances are measured - * @param numDests the number of vertices for which to measure distances - */ - public LinkedHashMap getDistanceMap(V source, int numDests) - { - - if(g.getVertices().contains(source) == false) { - throw new IllegalArgumentException("Specified source vertex " + - source + " is not part of graph " + g); - - } - if (numDests < 1 || numDests > g.getVertexCount()) - throw new IllegalArgumentException("numDests must be >= 1 " + - "and <= g.numVertices()"); - - if (numDests > max_targets) - throw new IllegalArgumentException("numDests must be <= the maximum " + - "number of targets allowed: " + this.max_targets); - - LinkedHashMap distanceMap = - singleSourceShortestPath(source, null, numDests); - - if (!cached) - reset(source); - - return distanceMap; - } - - /** - * Allows the user to specify the maximum distance that this instance will calculate. - * Any vertices past this distance will effectively be unreachable from the source, in - * the sense that the algorithm will not calculate the distance to any vertices which - * are farther away than this distance. A negative value for max_dist - * will ensure that no further distances are calculated. - * - *

This can be useful for limiting the amount of time and space used by this algorithm - * if the graph is very large.

- * - *

Note: if this instance has already calculated distances greater than max_dist, - * and the results are cached, those results will still be valid and available; this limit - * applies only to subsequent distance calculations.

- * @see #setMaxTargets(int) - */ - public void setMaxDistance(double max_dist) - { - this.max_distance = max_dist; - for (V v : sourceMap.keySet()) - { - SourceData sd = sourceMap.get(v); - sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets); - } - } - - /** - * Allows the user to specify the maximum number of target vertices per source vertex - * for which this instance will calculate distances. Once this threshold is reached, - * any further vertices will effectively be unreachable from the source, in - * the sense that the algorithm will not calculate the distance to any more vertices. - * A negative value for max_targets will ensure that no further distances are calculated. - * - *

This can be useful for limiting the amount of time and space used by this algorithm - * if the graph is very large.

- * - *

Note: if this instance has already calculated distances to a greater number of - * targets than max_targets, and the results are cached, those results - * will still be valid and available; this limit applies only to subsequent distance - * calculations.

- * @see #setMaxDistance(double) - */ - public void setMaxTargets(int max_targets) - { - this.max_targets = max_targets; - for (V v : sourceMap.keySet()) - { - SourceData sd = sourceMap.get(v); - sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets); - } - } - - /** - * Clears all stored distances for this instance. - * Should be called whenever the graph is modified (edge weights - * changed or edges added/removed). If the user knows that - * some currently calculated distances are unaffected by a - * change, reset(V) may be appropriate instead. - * - * @see #reset(Object) - */ - public void reset() - { - sourceMap = new HashMap(); - } - - /** - * Specifies whether or not this instance of DijkstraShortestPath - * should cache its results (final and partial) for future reference. - * - * @param enable true if the results are to be cached, and - * false otherwise - */ - public void enableCaching(boolean enable) - { - this.cached = enable; - } - - /** - * Clears all stored distances for the specified source vertex - * source. Should be called whenever the stored distances - * from this vertex are invalidated by changes to the graph. - * - * @see #reset() - */ - public void reset(V source) - { - sourceMap.put(source, null); - } - - /** - * Compares according to distances, so that the BinaryHeap knows how to - * order the tree. - */ - protected static class VertexComparator implements Comparator - { - private Map distances; - - protected VertexComparator(Map distances) - { - this.distances = distances; - } - - public int compare(V o1, V o2) - { - return ((Double) distances.get(o1)).compareTo((Double) distances.get(o2)); - } - } - - /** - * For a given source vertex, holds the estimated and final distances, - * tentative and final assignments of incoming edges on the shortest path from - * the source vertex, and a priority queue (ordered by estimated distance) - * of the vertices for which distances are unknown. - * - * @author Joshua O'Madadhain - */ - protected class SourceData - { - protected LinkedHashMap distances; - protected Map estimatedDistances; - protected MapBinaryHeap unknownVertices; - protected boolean reached_max = false; - protected double dist_reached = 0; - - protected SourceData(V source) - { - distances = new LinkedHashMap(); - estimatedDistances = new HashMap(); - unknownVertices = new MapBinaryHeap(new VertexComparator(estimatedDistances)); - - sourceMap.put(source, this); - - // initialize priority queue - estimatedDistances.put(source, new Double(0)); // distance from source to itself is 0 - unknownVertices.add(source); - reached_max = false; - dist_reached = 0; - } - - protected Map.Entry getNextVertex() - { - V v = unknownVertices.remove(); - Double dist = (Double)estimatedDistances.remove(v); - distances.put(v, dist); - return new BasicMapEntry(v, dist); - } - - protected void update(V dest, E tentative_edge, double new_dist) - { - estimatedDistances.put(dest, new_dist); - unknownVertices.update(dest); - } - - protected void createRecord(V w, E e, double new_dist) - { - estimatedDistances.put(w, new_dist); - unknownVertices.add(w); - } - - protected void restoreVertex(V v, double dist) - { - estimatedDistances.put(v, dist); - unknownVertices.add(v); - distances.remove(v); - } - } -}