jdsl.graph.algo
Class IntegerDijkstraTemplate

java.lang.Object
  |
  +--jdsl.graph.algo.IntegerDijkstraTemplate
Direct Known Subclasses:
IntegerDijkstraPathfinder

public abstract class IntegerDijkstraTemplate
extends java.lang.Object

Implementation of Dijkstra's algorithm using the template-method pattern: the core functionality is coded in a few final methods that call overridable methods to do some of the work. The methods of this class are in five categories:

Note that it is possible to confuse the algorithm by doing things like modifying the graph, messing with the priority queue, or changing edge weights while it is running.

Version:
$Id: IntegerDijkstraTemplate.java,v 1.24 2001/01/24 22:03:37 lv Exp $
Author:
Mark Handy, Galina Shubina, Luca Vismara

Field Summary
protected  InspectableGraph g_
           
protected  PriorityQueue pq_
           
protected  Vertex source_
           
 
Constructor Summary
IntegerDijkstraTemplate()
           
 
Method Summary
 void cleanup()
          Removes the decorations from the vertices.
protected  Vertex destination(Vertex origin, Edge e)
          Can be overridden to supply the destination of an edge, although I can't think of any reason to do so.
 int distance(Vertex v)
          Returns the distance of a vertex from the source.
 void doOneIteration()
          Can be called manually to single-step the algorithm, but you must call init(.) before the first call to this method.
protected  void edgeRelaxed(Vertex u, int uDist, Edge uv, int uvWeight, Vertex v, int vDist)
          Can be overridden in any application where the edges considered for the shortest-path tree matter.
 void execute(InspectableGraph g, Vertex source)
          The easiest way to use the algorithm is to use this method.
 Edge getEdgeToParent(Vertex v)
          Can be overridden to supply a way of storing and retrieving one edge per vertex.
protected  Locator getLocator(Vertex v)
          Can be overridden to supply a way of storing and retrieving one locator per vertex.
protected  EdgeIterator incidentEdges(Vertex v)
          Can be overridden in any application where the default choice of edges to consider at any vertex is not satisfactory.
 void init(InspectableGraph g, Vertex source)
          Called automatically by executeAll(); must be called by the client prior to the first call to doOneIteration() if finer-grained control of the algorithm is needed.
protected  void initMap()
          Can be overridden to initialize a locator-lookup data structure of your choosing, but the default implementation, which decorates each vertex with its locator, is probably sufficient for most purposes.
protected  boolean isFinished(Vertex v)
          Tests whether a vertex has been reached.
 boolean isReachable(Vertex v)
          Tests whether a vertex is reachable from the source.
protected  PriorityQueue newPQ()
          Can be overridden to supply a priority queue of your choosing, but the default implementation, which gives an empty jdsl.core.ref.ArrayHeap, is probably sufficient for most purposes.
protected  void runUntil()
          Repeatedly calls method doOneIteration() until either the priority queue is empty or method shouldContinue() returns false.
protected  void setEdgeToParent(Vertex v, Edge vEdge)
          Can be overridden to supply a way of storing and retrieving one edge per vertex.
protected  void setLocator(Vertex v, Locator vLoc)
          Can be overridden to supply a way of storing and retrieving one locator per vertex.
protected  void shortestPathFound(Vertex v, int vDist)
          Can be overridden to give you a notification when the shortest path to a vertex is determined.
protected  boolean shouldContinue()
          Can be overridden in any application where the full shortest-path tree is not needed and the algorithm should terminate early.
protected  void vertexNotReachable(Vertex v)
          Can be overridden in any application that involves unreachable vertices.
protected  VertexIterator vertices()
          Can be overridden to consider a subset of the vertices in the graph, although I can't think of any reason to do so.
protected abstract  int weight(Edge e)
          Must be overridden to supply a way of getting a positive weight for every edge in the graph.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

pq_

protected PriorityQueue pq_

g_

protected InspectableGraph g_

source_

protected Vertex source_
Constructor Detail

IntegerDijkstraTemplate

public IntegerDijkstraTemplate()
Method Detail

weight

protected abstract int weight(Edge e)
Must be overridden to supply a way of getting a positive weight for every edge in the graph. This method gets called by the algorithm when the algorithm needs to know the weight of an edge. Dijkstra's algorithm cannot handle negative weights. Furthermore, although it works correctly with zero-weight edges, some of the methods of this class make guarantees based on assuming positive weights that they cannot make if there are zero-weight edges.
Parameters:
e - Edge for which the algorithm needs to know a weight
Returns:
Your application's weight for e

shortestPathFound

protected void shortestPathFound(Vertex v,
                                 int vDist)
Can be overridden to give you a notification when the shortest path to a vertex is determined. The algorithm calls this method at most once per vertex, after the vertex has been "finished" (i.e., when the path from s to the vertex is known). The vertex will never again be touched or considered by the algorithm.

Note that there is no corresponding get-method; the algorithm does not need this information again, so the only constraints on what you do with the information are those imposed by your application.

Parameters:
v - Vertex that the algorithm just finished
vDist - Distance of v from the source

vertexNotReachable

protected void vertexNotReachable(Vertex v)
Can be overridden in any application that involves unreachable vertices. Called every time a vertex with distance INFINITY comes off the priority queue. When it has been called once, it should subsequently be called for all remaining vertices, until the priority queue is empty.

Note that there is no corresponding get-method; the algorithm does not need this information again, so the only constraints on what you do with the information are those imposed by your application.

Parameters:
v - Vertex which the algorithm just found to be unreachable from the source

edgeRelaxed

protected void edgeRelaxed(Vertex u,
                           int uDist,
                           Edge uv,
                           int uvWeight,
                           Vertex v,
                           int vDist)
Can be overridden in any application where the edges considered for the shortest-path tree matter. Called every time an edge leading to a vertex is examined (relaxed); this can happen many times per vertex. If udist + uvweight is less than vDist, there is a shorter path to v, via u and uv, than the shortest path to v previously known, so v is updated in the priority queue. This method notifies you before such a calculation is made, whether the calculation results in an update or not.

For every vertex reachable from the source, except the source, this method will be called at least once before the vertex is finished. Once a vertex has been finished, this method will never be called for that vertex again.

Note that there is no corresponding get-method; the algorithm does not need this information again, so the only constraints on what you do with the information are those imposed by your application.

Parameters:
u - Vertex about to be finished, from which an edge to v is being explored
uDist - The final distance to u (will soon be passed as svDist to shortestPathFound(.))
uv - Edge being explored
uvWeight - Weight of uv
v - Vertex being investigated: the best-known-path to it will be updated if the path via u and uv is better
vDist - The present, possibly suboptimal, distance of v from s

shouldContinue

protected boolean shouldContinue()
Can be overridden in any application where the full shortest-path tree is not needed and the algorithm should terminate early. executeAll(.) checks the return from this method before each call to doOneIteration(). The default implementation just returns true, so executeAll(.) continues until the full shortest-path tree is built. Notice that if you are calling doOneIteration() manually, this method is irrelevant; only executeAll(.) calls this method.
Returns:
Whether to continue running the algorithm

isFinished

protected boolean isFinished(Vertex v)
Tests whether a vertex has been reached.
Parameters:
v - a vertex
Returns:
Whether v has been marked as finished

setLocator

protected void setLocator(Vertex v,
                          Locator vLoc)
Can be overridden to supply a way of storing and retrieving one locator per vertex. Will be called only once per vertex, during initialization. The default implementation decorates each vertex with its locator.
Parameters:
v - Vertex to decorate with a locator
vLoc - the locator with which to decorate v
See Also:
getLocator(Vertex), Decorable.set(Object,Object)

getLocator

protected Locator getLocator(Vertex v)
Can be overridden to supply a way of storing and retrieving one locator per vertex. This is the counterpart to setLocator(.) but may be called many times. The default implementation uses the decoration of each vertex. The algorithm calls this method whenever it needs to update the best distance it knows for a vertex, which requires updating the priority queue.
Parameters:
v - Vertex previously decorated with a locator
Returns:
Locator associated with v in the earlier setLocator(.) call
See Also:
setLocator(Vertex,Locator), Decorable.get(Object)

setEdgeToParent

protected void setEdgeToParent(Vertex v,
                               Edge vEdge)
Can be overridden to supply a way of storing and retrieving one edge per vertex. The default implementation decorates each vertex with its edge.
Parameters:
v - Vertex to decorate with an edge
vEdge - the with which to decorate v
See Also:
getEdgeToParent(Vertex), Decorable.set(Object,Object)

newPQ

protected PriorityQueue newPQ()
Can be overridden to supply a priority queue of your choosing, but the default implementation, which gives an empty jdsl.core.ref.ArrayHeap, is probably sufficient for most purposes. The priority queue must be able to accept keys of type Integer. If you choose to override the method, for typical applications you should return an empty priority queue. If necessary, it can be preinitialized, although you will need to accommodate that fact in other methods.
Returns:
PriorityQueue to be used by the algorithm

initMap

protected void initMap()
Can be overridden to initialize a locator-lookup data structure of your choosing, but the default implementation, which decorates each vertex with its locator, is probably sufficient for most purposes. This method is called by the algorithm before any call to setLocator(.). The best reason to override this method is that you have some other way to implement set/getLocator(.). In that case, override this method to do any necessary initialization of your data structure.


incidentEdges

protected EdgeIterator incidentEdges(Vertex v)
Can be overridden in any application where the default choice of edges to consider at any vertex is not satisfactory. The default is to consider all outgoing and all undirected edges from a given vertex. Example: if you have a directed graph but want to view it as undirected for purposes of building a shortest-path tree, you should override this method to read
return G.incidentEdges(v, EdgeDirection.IN | EdgeDirection.OUT);
Parameters:
v - Vertex soon to be finished by the algorithm
Returns:
All the interesting edges of v -- i.e., all edges whose weights you want the algorithm to inspect in considering alternative routes to vertices adjacent to v

destination

protected Vertex destination(Vertex origin,
                             Edge e)
Can be overridden to supply the destination of an edge, although I can't think of any reason to do so. Presently implemented with opposite(.), so it works even if the edge is incoming to v (see the example under incidentEdges(.)). Called by the core algorithm when it is about to finish origin and needs all its adjacent vertices.
Parameters:
origin - Vertex soon to be finished by the algorithm
e - Edge incident on origin according to incidentEdges(.)
Returns:
the vertex opposite origin along e

vertices

protected VertexIterator vertices()
Can be overridden to consider a subset of the vertices in the graph, although I can't think of any reason to do so. Note that overriding this method will probably also require overriding incidentEdges(.), in order to avoid edges leading to vertices not in the subset.
Returns:
Iterator over all vertices to be initially put in the priority queue and eventually finished by the algorithm

isReachable

public final boolean isReachable(Vertex v)
Tests whether a vertex is reachable from the source. The method can be invoked at any time during the single-step execution of the algorithm.
Parameters:
v - a vertex
Returns:
whether v is reachable from the source

distance

public final int distance(Vertex v)
                   throws InvalidQueryException
Returns the distance of a vertex from the source.
Parameters:
v - a vertex
Returns:
the distance of v from the source
Throws:
InvalidQueryException - if v has not been reached yet

getEdgeToParent

public Edge getEdgeToParent(Vertex v)
                     throws InvalidQueryException
Can be overridden to supply a way of storing and retrieving one edge per vertex. This is the counterpart to setEdgeToParent(.) but may be called many times. The default implementation uses the decoration of each vertex. The algorithm calls this method whenever it needs to update the best distance it knows for a vertex, which requires updating the edge to parent.
Parameters:
v - Vertex previously labeled with an edge
Returns:
Edge associated with v in the earlier setEdgeToParent(.) call
Throws:
InvalidQueryException - if v is the source or has not been reached yet
See Also:
setEdgeToParent(Vertex,Edge), Decorable.get(Object)

init

public void init(InspectableGraph g,
                 Vertex source)
Called automatically by executeAll(); must be called by the client prior to the first call to doOneIteration() if finer-grained control of the algorithm is needed. The method initializes instance variables and then puts all vertices in the PQ with initial distances, and records their respective locators. Can be overridden, although I can't think of any reason to do so.

Calls the following methods that can be overridden: newPQ(), initMap(), vertices(), setLocator(.).

Parameters:
g - Graph on which to execute the algorithm
source - Vertex at which to root the shortest-path tree

cleanup

public void cleanup()
Removes the decorations from the vertices. Its invocation is the user's responsibility.

doOneIteration

public final void doOneIteration()
                          throws InvalidEdgeException
Can be called manually to single-step the algorithm, but you must call init(.) before the first call to this method. Finishes one vertex and updates all adjacent vertices. If the vertex that gets finished was reachable from the source, this method expands the shortest-path tree by one vertex.

runUntil

protected final void runUntil()
Repeatedly calls method doOneIteration() until either the priority queue is empty or method shouldContinue() returns false.

execute

public final void execute(InspectableGraph g,
                          Vertex source)
The easiest way to use the algorithm is to use this method. Calls init(.) once, then doOneIteration() repeatedly until either the PQ is empty or shouldContinue() returns false.
Parameters:
g - Graph on which to execute the algorithm
source - Vertex at which to root the shortest-path tree