Package edu.uci.ics.jung.algorithms.shortestpath

Class DijkstraDistance<V,​E>

  • All Implemented Interfaces:
    Distance<V>
    Direct Known Subclasses:
    DijkstraShortestPath
    public class DijkstraDistance<V,​E>
extends java.lang.Object
implements Distance<V>

    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.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      protected class  DijkstraDistance.SourceData
      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.
      protected static class  DijkstraDistance.VertexComparator<V>
      Compares according to distances, so that the BinaryHeap knows how to order the tree.

    • Constructor Summary

      Constructors 
      Constructor Description
      DijkstraDistance​(edu.uci.ics.jung.graph.Graph<V,​E> g)
      Creates an instance of DijkstraShortestPath for the specified unweighted graph (that is, all weights 1) which caches results locally.
      DijkstraDistance​(edu.uci.ics.jung.graph.Graph<V,​E> g, boolean cached)
      Creates an instance of DijkstraShortestPath for the specified unweighted graph (that is, all weights 1) which caches results locally.
      DijkstraDistance​(edu.uci.ics.jung.graph.Hypergraph<V,​E> g, org.apache.commons.collections4.Transformer nev)
      Creates an instance of DijkstraShortestPath for the specified graph and the specified method of extracting weights from edges, which caches results locally.
      DijkstraDistance​(edu.uci.ics.jung.graph.Hypergraph<V,​E> g, org.apache.commons.collections4.Transformer nev, boolean cached)
      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.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void enableCaching​(boolean enable)
      Specifies whether or not this instance of DijkstraShortestPath should cache its results (final and partial) for future reference.
      java.lang.Number getDistance​(V source, V target)
      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.
      java.util.Map<V,​java.lang.Number> getDistanceMap​(V source)
      Returns a LinkedHashMap which maps each vertex in the graph (including the source vertex) to its distance from the source vertex.
      java.util.LinkedHashMap<V,​java.lang.Number> getDistanceMap​(V source, int numDests)
      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.
      java.util.Map<V,​java.lang.Number> getDistanceMap​(V source, java.util.Collection<V> targets)
      Returns a Map from each element t of targets to the shortest-path distance from source to t.
      protected java.util.Collection<E> getEdgesToCheck​(V v)
      Returns the set of edges incident to v that should be tested.
      protected DijkstraDistance.SourceData getSourceData​(V source)  
      void reset()
      Clears all stored distances for this instance.
      void reset​(V source)
      Clears all stored distances for the specified source vertex source.
      void setMaxDistance​(double max_dist)
      Allows the user to specify the maximum distance that this instance will calculate.
      void setMaxTargets​(int max_targets)
      Allows the user to specify the maximum number of target vertices per source vertex for which this instance will calculate distances.
      protected java.util.LinkedHashMap<V,​java.lang.Number> singleSourceShortestPath​(V source, java.util.Collection<V> targets, int numDests)
      Implements Dijkstra's single-source shortest-path algorithm for weighted graphs.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • g

        protected edu.uci.ics.jung.graph.Hypergraph<V,​E> g

      • nev

        protected org.apache.commons.collections4.Transformer nev

      • cached

        protected boolean cached

      • max_distance

        protected double max_distance

      • max_targets

        protected int max_targets

    • Constructor Detail

      • DijkstraDistance

        public DijkstraDistance​(edu.uci.ics.jung.graph.Hypergraph<V,​E> g,
                        org.apache.commons.collections4.Transformer nev,
                        boolean cached)

        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.

        Parameters:
        g - the graph on which distances will be calculated
        nev - the class responsible for returning weights for edges
        cached - specifies whether the results are to be cached

      • DijkstraDistance

        public DijkstraDistance​(edu.uci.ics.jung.graph.Hypergraph<V,​E> g,
                        org.apache.commons.collections4.Transformer nev)

        Creates an instance of DijkstraShortestPath for the specified graph and the specified method of extracting weights from edges, which caches results locally.

        Parameters:
        g - the graph on which distances will be calculated
        nev - the class responsible for returning weights for edges

      • DijkstraDistance

        public DijkstraDistance​(edu.uci.ics.jung.graph.Graph<V,​E> g)

        Creates an instance of DijkstraShortestPath for the specified unweighted graph (that is, all weights 1) which caches results locally.

        Parameters:
        g - the graph on which distances will be calculated

      • DijkstraDistance

        public DijkstraDistance​(edu.uci.ics.jung.graph.Graph<V,​E> g,
                        boolean cached)

        Creates an instance of DijkstraShortestPath for the specified unweighted graph (that is, all weights 1) which caches results locally.

        Parameters:
        g - the graph on which distances will be calculated
        cached - specifies whether the results are to be cached

    • Method Detail

      • singleSourceShortestPath

        protected java.util.LinkedHashMap<V,​java.lang.Number> singleSourceShortestPath​(V source,
                                                                                     java.util.Collection<V> targets,
                                                                                     int numDests)
        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
        Parameters:
        source - the vertex from which distances are to be measured
        numDests - the number of distances to measure
        targets - the set of vertices to which distances are to be measured

      • getEdgesToCheck

        protected java.util.Collection<E> getEdgesToCheck​(V v)
        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.

      • getDistance

        public java.lang.Number getDistance​(V source,
                                    V target)
        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.
        Specified by:
        getDistance in interface Distance<V>
        See Also:
        getDistanceMap(Object), getDistanceMap(Object,int)

      • getDistanceMap

        public java.util.Map<V,​java.lang.Number> getDistanceMap​(V source,
                                                              java.util.Collection<V> targets)
        Returns a Map from each element t of targets to the shortest-path distance from source to t.

      • getDistanceMap

        public java.util.Map<V,​java.lang.Number> getDistanceMap​(V source)

        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.

        Specified by:
        getDistanceMap in interface Distance<V>
        Parameters:
        source - the vertex from which distances are measured
        See Also:
        getDistanceMap(Object,int), getDistance(Object,Object)

      • getDistanceMap

        public java.util.LinkedHashMap<V,​java.lang.Number> getDistanceMap​(V source,
                                                                        int numDests)

        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.

        Parameters:
        source - the vertex from which distances are measured
        numDests - the number of vertices for which to measure distances
        See Also:
        getDistanceMap(Object), getDistance(Object,Object)

      • setMaxDistance

        public void setMaxDistance​(double max_dist)
        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 Also:
        setMaxTargets(int)

      • setMaxTargets

        public void setMaxTargets​(int 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 Also:
        setMaxDistance(double)

      • reset

        public void reset()
        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 Also:
        reset(Object)

      • enableCaching

        public void enableCaching​(boolean enable)
        Specifies whether or not this instance of DijkstraShortestPath should cache its results (final and partial) for future reference.
        Parameters:
        enable - true if the results are to be cached, and false otherwise

      • reset

        public void reset​(V source)
        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 Also:
        reset()