public class DijkstraDistance<V,E> extends 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.
Modifier and Type | Class and 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.
|
Modifier and Type | Field and Description |
---|---|
protected boolean |
cached |
protected Hypergraph<V,E> |
g |
protected double |
max_distance |
protected int |
max_targets |
protected com.google.common.base.Function<? super E,? extends Number> |
nev |
protected Map<V,DijkstraDistance.SourceData> |
sourceMap |
Constructor and Description |
---|
DijkstraDistance(Graph<V,E> g)
Creates an instance of
DijkstraShortestPath for
the specified unweighted graph (that is, all weights 1) which
caches results locally. |
DijkstraDistance(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(Hypergraph<V,E> g,
com.google.common.base.Function<? super E,? extends Number> nev)
Creates an instance of
DijkstraShortestPath for
the specified graph and the specified method of extracting weights
from edges, which caches results locally. |
DijkstraDistance(Hypergraph<V,E> g,
com.google.common.base.Function<? super E,? extends Number> 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 . |
Modifier and Type | Method and Description |
---|---|
void |
enableCaching(boolean enable)
Specifies whether or not this instance of
DijkstraShortestPath
should cache its results (final and partial) for future reference. |
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.
|
Map<V,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. |
Map<V,Number> |
getDistanceMap(V source,
Collection<V> targets)
Returns a
Map from each element t of targets to the
shortest-path distance from source to t . |
LinkedHashMap<V,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. |
protected 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 LinkedHashMap<V,Number> |
singleSourceShortestPath(V source,
Collection<V> targets,
int numDests)
Implements Dijkstra's single-source shortest-path algorithm for
weighted graphs.
|
protected Hypergraph<V,E> g
protected Map<V,DijkstraDistance.SourceData> sourceMap
protected boolean cached
protected double max_distance
protected int max_targets
public DijkstraDistance(Hypergraph<V,E> g, com.google.common.base.Function<? super E,? extends Number> 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
.
g
- the graph on which distances will be calculatednev
- the class responsible for returning weights for edgescached
- specifies whether the results are to be cachedpublic DijkstraDistance(Hypergraph<V,E> g, com.google.common.base.Function<? super E,? extends Number> nev)
Creates an instance of DijkstraShortestPath
for
the specified graph and the specified method of extracting weights
from edges, which caches results locally.
g
- the graph on which distances will be calculatednev
- the class responsible for returning weights for edgespublic DijkstraDistance(Graph<V,E> g)
Creates an instance of DijkstraShortestPath
for
the specified unweighted graph (that is, all weights 1) which
caches results locally.
g
- the graph on which distances will be calculatedpublic DijkstraDistance(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.
g
- the graph on which distances will be calculatedcached
- specifies whether the results are to be cachedprotected LinkedHashMap<V,Number> singleSourceShortestPath(V source, Collection<V> targets, int numDests)
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):
source
- the vertex from which distances are to be measurednumDests
- the number of distances to measuretargets
- the set of vertices to which distances are to be measuredprotected DijkstraDistance.SourceData getSourceData(V source)
protected Collection<E> getEdgesToCheck(V v)
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.v
- the vertex whose edges are to be checkedv
that should be testedpublic Number getDistance(V source, V target)
IllegalArgumentException
.getDistance
in interface Distance<V>
source
- the vertex from which the distance to target
is to be measuredtarget
- the vertex to which the distance from source
is to be measuredsource
and target
getDistanceMap(Object)
,
getDistanceMap(Object,int)
public Map<V,Number> getDistanceMap(V source, Collection<V> targets)
Map
from each element t
of targets
to the
shortest-path distance from source
to t
.source
- the vertex from which the distance to each target is to be measuredtargets
- the vertices to which the distance from the source is to be measuredMap
from each element of targets
to its distance from source
public Map<V,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
.
getDistanceMap
in interface Distance<V>
source
- the vertex from which distances are measuredsource
getDistanceMap(Object,int)
,
getDistance(Object,Object)
public LinkedHashMap<V,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
.
source
- the vertex from which distances are measurednumDests
- the number of vertices for which to measure distancesnumDests
vertices in the graph
closest to source
, to their distance from source
getDistanceMap(Object)
,
getDistance(Object,Object)
public void setMaxDistance(double max_dist)
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.
max_dist
- the maximum distance that this instance will calculatesetMaxTargets(int)
public void setMaxTargets(int max_targets)
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.
max_targets
- the maximum number of targets for which this instance will calculate
distancessetMaxDistance(double)
public void reset()
reset(V)
may be appropriate instead.reset(Object)
public void enableCaching(boolean enable)
DijkstraShortestPath
should cache its results (final and partial) for future reference.enable
- true
if the results are to be cached, and
false
otherwisepublic void reset(V source)
source
. Should be called whenever the stored distances
from this vertex are invalidated by changes to the graph.source
- the vertex for which stored distances should be clearedreset()
Copyright © 2015. All rights reserved.