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.
Creates an instance of Creates an instance of Creates an instance of Creates an instance of Returns a The size of the map returned will be the number of
- * vertices reachable from Returns a The size of the map returned will be the smaller of
- * 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 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 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(HypergraphDijkstraShortestPath
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(HypergraphDijkstraShortestPath
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(HypergraphDijkstraShortestPath
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(HypergraphMapBinaryHeap
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):
- *
- *
- *
- * @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 LinkedHashMapMapBinaryHeap
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):
- *
- *
- *
- * @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 LinkedHashMapMapBinaryHeap
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):
- *
- *
- *
- * @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 LinkedHashMapv
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 CollectionIllegalArgumentException
.
- *
- * @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);
-
- SetLinkedHashMap
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
.source
.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.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 LinkedHashMapmax_dist
- * will ensure that no further distances are calculated.
- *
- * max_dist
,
- * and the results are cached, those results will still be valid and available; this limit
- * applies only to subsequent distance calculations.max_targets
will ensure that no further distances are calculated.
- *
- * max_targets
, and the results are cached, those results
- * will still be valid and available; this limit applies only to subsequent distance
- * calculations.reset(V)
may be appropriate instead.
- *
- * @see #reset(Object)
- */
- public void reset()
- {
- sourceMap = new HashMapDijkstraShortestPath
- * 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