Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## edu.uci.ics.jung.algorithms.shortestpath
Class DijkstraDistance

    java.lang.Object
      edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance

All Implemented Interfaces:
  Distance

Direct Known Subclasses:
  DijkstraShortestPath

public class DijkstraDistance
extends Object
implements Distance

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

Nested Class Summary
`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 estimaed distance) of the vertices for which distances are unknown.
`protected class` | `DijkstraDistance.VertexComparator` Compares according to distances, so that the BinaryHeap knows how to order the tree.

Field Summary
`protected boolean` | `cached`
`protected static NumberEdgeValue` | `dev`
`protected ArchetypeGraph` | `g`
`protected double` | `max_distance`
`protected int` | `max_targets`
`protected NumberEdgeValue` | `nev`
`protected Map` | `sourceMap`

Constructor Summary
`DijkstraDistance(ArchetypeGraph g)` Creates an instance of `DijkstraShortestPath` for the specified unweighted graph (that is, all weights 1) which caches results locally.
`DijkstraDistance(ArchetypeGraph g, boolean cached)` Creates an instance of `DijkstraShortestPath` for the specified unweighted graph (that is, all weights 1) which caches results locally.
`DijkstraDistance(ArchetypeGraph g, NumberEdgeValue nev)` Creates an instance of `DijkstraShortestPath` for the specified graph and the specified method of extracting weights from edges, which caches results locally.
`DijkstraDistance(ArchetypeGraph g, NumberEdgeValue 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
`void` | `enableCaching(boolean enable)` Specifies whether or not this instance of `DijkstraShortestPath` should cache its results (final and partial) for future reference.
`Number` | `getDistance(ArchetypeVertex source, ArchetypeVertex 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.
`Map` | `getDistanceMap(ArchetypeVertex source)` Returns a `LinkedHashMap` which maps each vertex in the graph (including the `source` vertex) to its distance from the `source` vertex.
`LinkedHashMap` | `getDistanceMap(ArchetypeVertex 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.
`Map` | `getDistanceMap(ArchetypeVertex source, Set targets)`
`protected Set` | `getIncidentEdges(ArchetypeVertex v)` Returns the set of edges incident to `v` that should be tested.
`protected DijkstraDistance.SourceData` | `getSourceData(ArchetypeVertex source)`
`void` | `reset()` Clears all stored distances for this instance.
`void` | `reset(ArchetypeVertex 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 LinkedHashMap` | `singleSourceShortestPath(ArchetypeVertex source, Set 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 ArchetypeGraph g

### nev

    protected NumberEdgeValue nev

### sourceMap

    protected Map sourceMap

### cached

    protected boolean cached

### dev

    protected static final NumberEdgeValue dev

### max_distance

    protected double max_distance

### max_targets

    protected int max_targets

Constructor Detail

### DijkstraDistance

    public DijkstraDistance(ArchetypeGraph g,
                            NumberEdgeValue 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(ArchetypeGraph g,
                            NumberEdgeValue 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(ArchetypeGraph 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(ArchetypeGraph 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 LinkedHashMap singleSourceShortestPath(ArchetypeVertex source,
                                                     Set 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
  - 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

### getSourceData

    protected DijkstraDistance.SourceData getSourceData(ArchetypeVertex source)

### getIncidentEdges

    protected Set getIncidentEdges(ArchetypeVertex 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 `Vertex`, the set of incident edges for instances of `Hypervertex`, and is otherwise undefined.

### getDistance

    public Number getDistance(ArchetypeVertex source,
                              ArchetypeVertex 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`
  See Also:
    `getDistanceMap(ArchetypeVertex)`, `getDistanceMap(ArchetypeVertex,int)`

### getDistanceMap

    public Map getDistanceMap(ArchetypeVertex source,
                              Set targets)

### getDistanceMap

    public Map getDistanceMap(ArchetypeVertex 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`
  Parameters:
    `source` - the vertex from which distances are measured
  See Also:
    `getDistanceMap(ArchetypeVertex,int)`, `getDistance(ArchetypeVertex,ArchetypeVertex)`

### getDistanceMap

    public LinkedHashMap getDistanceMap(ArchetypeVertex 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(ArchetypeVertex)`, `getDistance(ArchetypeVertex,ArchetypeVertex)`

### 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(double)`

### 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(Vertex)` may be appropriate instead.

  See Also:
    `#reset(Vertex)`

### 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(ArchetypeVertex 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()`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD