|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance<V,E> edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath<V,E>
public class DijkstraShortestPath<V,E>
Calculates distances and shortest paths using Dijkstra's
single-source-shortest-path algorithm. This is a lightweight
extension of DijkstraDistance
that also stores
path information, so that the shortest paths can be reconstructed.
The elements in the maps returned by
getIncomingEdgeMap
are ordered (that is, returned
by the iterator) by nondecreasing distance from source
.
DijkstraDistance
Nested Class Summary | |
---|---|
protected class |
DijkstraShortestPath.SourcePathData
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. |
Nested classes/interfaces inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance |
---|
DijkstraDistance.SourceData, DijkstraDistance.VertexComparator<V> |
Field Summary |
---|
Fields inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance |
---|
cached, g, max_distance, max_targets, nev, sourceMap |
Constructor Summary | |
---|---|
DijkstraShortestPath(Graph<V,E> g)
Creates an instance of DijkstraShortestPath for
the specified unweighted graph (that is, all weights 1) which
caches results locally. |
|
DijkstraShortestPath(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. |
|
DijkstraShortestPath(Graph<V,E> g,
org.apache.commons.collections15.Transformer<E,Number> nev)
Creates an instance of DijkstraShortestPath for
the specified graph and the specified method of extracting weights
from edges, which caches results locally. |
|
DijkstraShortestPath(Graph<V,E> g,
org.apache.commons.collections15.Transformer<E,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 . |
Method Summary | |
---|---|
E |
getIncomingEdge(V source,
V target)
Returns the last edge on a shortest path from source
to target , or null if target is not
reachable from source . |
Map<V,E> |
getIncomingEdgeMap(V source)
Returns a LinkedHashMap which maps each vertex
in the graph (including the source vertex)
to the last edge on the shortest path from the
source vertex. |
LinkedHashMap<V,E> |
getIncomingEdgeMap(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 the incoming edge along the path from that vertex. |
List<E> |
getPath(V source,
V target)
Returns a List of the edges on the shortest path from
source to target , in order of their
occurrence on this path. |
protected DijkstraDistance.SourceData |
getSourceData(V source)
|
Methods inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance |
---|
enableCaching, getDistance, getDistanceMap, getDistanceMap, getDistanceMap, getEdgesToCheck, reset, reset, setMaxDistance, setMaxTargets, singleSourceShortestPath |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public DijkstraShortestPath(Graph<V,E> g, org.apache.commons.collections15.Transformer<E,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 DijkstraShortestPath(Graph<V,E> g, org.apache.commons.collections15.Transformer<E,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 DijkstraShortestPath(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 DijkstraShortestPath(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 cachedMethod Detail |
---|
protected DijkstraDistance.SourceData getSourceData(V source)
getSourceData
in class DijkstraDistance<V,E>
public E getIncomingEdge(V source, V target)
Returns the last edge on a shortest path from source
to target
, or null if target
is not
reachable from source
.
If either vertex is not in the graph for which this instance
was created, throws IllegalArgumentException
.
public Map<V,E> getIncomingEdgeMap(V source)
Returns a LinkedHashMap
which maps each vertex
in the graph (including the source
vertex)
to the last edge on the shortest path from the
source
vertex.
The map's iterator will return the elements in order of
increasing distance from source
.
getIncomingEdgeMap
in interface ShortestPath<V,E>
source
- the vertex from which distances are measuredDijkstraDistance.getDistanceMap(Object,int)
,
DijkstraDistance.getDistance(Object,Object)
public List<E> getPath(V source, V target)
List
of the edges on the shortest path from
source
to target
, in order of their
occurrence on this path.
If either vertex is not in the graph for which this instance
was created, throws IllegalArgumentException
.
public LinkedHashMap<V,E> getIncomingEdgeMap(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 the incoming edge along the path from that 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.
source
- the vertex from which distances are measurednumDests
- the number of vertics for which to measure distancesgetIncomingEdgeMap(Object)
,
getPath(Object,Object)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |