edu.uci.ics.jung.algorithms.shortestpath
Class DijkstraShortestPath

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
      extended by edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath
All Implemented Interfaces:
Distance, ShortestPath

public class DijkstraShortestPath
extends DijkstraDistance
implements ShortestPath

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.

Author:
Joshua O'Madadhain
See Also:
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
 
Field Summary
 
Fields inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
cached, dev, g, max_distance, max_targets, nev, sourceMap
 
Constructor Summary
DijkstraShortestPath(ArchetypeGraph g)
          Creates an instance of DijkstraShortestPath for the specified unweighted graph (that is, all weights 1) which caches results locally.
DijkstraShortestPath(ArchetypeGraph g, boolean cached)
          Creates an instance of DijkstraShortestPath for the specified unweighted graph (that is, all weights 1) which caches results locally.
DijkstraShortestPath(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.
DijkstraShortestPath(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
 Edge getIncomingEdge(Vertex source, Vertex target)
          Returns the last edge on a shortest path from source to target, or null if target is not reachable from source.
 Map getIncomingEdgeMap(Vertex 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 getIncomingEdgeMap(Vertex 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 getPath(Vertex source, Vertex 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(ArchetypeVertex source)
           
 
Methods inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
enableCaching, getDistance, getDistanceMap, getDistanceMap, getDistanceMap, getIncidentEdges, 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

DijkstraShortestPath

public DijkstraShortestPath(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

DijkstraShortestPath

public DijkstraShortestPath(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

DijkstraShortestPath

public DijkstraShortestPath(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

DijkstraShortestPath

public DijkstraShortestPath(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

getSourceData

protected DijkstraDistance.SourceData getSourceData(ArchetypeVertex source)
Overrides:
getSourceData in class DijkstraDistance

getIncomingEdge

public Edge getIncomingEdge(Vertex source,
                            Vertex 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.


getIncomingEdgeMap

public Map getIncomingEdgeMap(Vertex 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.

Specified by:
getIncomingEdgeMap in interface ShortestPath
Parameters:
source - the vertex from which distances are measured
See Also:
DijkstraDistance#getDistanceMap(Vertex,int), DijkstraDistance#getDistance(Vertex,Vertex)

getPath

public List getPath(Vertex source,
                    Vertex target)
Returns a 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.


getIncomingEdgeMap

public LinkedHashMap getIncomingEdgeMap(Vertex 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.

Parameters:
source - the vertex from which distances are measured
numDests - the number of vertics for which to measure distances
See Also:
getIncomingEdgeMap(Vertex), getPath(Vertex,Vertex)