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 templatemethod
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:
 A method you must override to make the compiler happy: You must
override weight(Edge) to supply the algorithm with a weight for
every edge in the graph. Note that Dijkstra's algorithm cannot
handle negativeweight edges.
 "Hook" methods that may be overridden to specialize the
algorithm to the application at hand: shortestPathFound(.),
edgeRelaxed(.), and vertexNotReachable(.). For every vertex in the
graph (or every vertex you allow the algorithm to consider), either
shortestPathFound(.) or vertexNotReachable(.) will be called, and
will be called exactly once. When that has occurred, the vertex is
considered to be "finished"; it will not be considered again by the
algorithm. Finally, edgeRelaxed(.) will be called every time an
edge to an unfinished vertex is explored.
 Overridable methods that will need to be overridden more
rarely: See the comments for shouldContinue(), isFinished(.),
setLocator(.), getLocator(.), setEdgeToParent(.), newPQ(),
initMap(), incidentEdges(.), destination(.), vertices(), and
init(.) (which has a split role between this category of methods
and the next).
 "Output" methods through which the user can test, after the
execution of the algorithm, whether a vertex is reachable from the
source, and retrieve the decorations of the vertices: See the
comments for isReachable(.), distance(.), and getEdgeToParent(.).
 Methods composing the core of the algorithm, which cannot be
overridden (or, in the case of init(.), should rarely be
overridden): You can run the algorithm in either of two ways. If
you want to run the whole algorithm at once, use either version of
executeAll(.). It will call doOneIteration() multiple times, and
doOneIteration() will call your overridden output methods as it
encounters vertices. Instead of using executeAll(.), you can
singlestep the algorithm by calling init(.) to initialize, then
calling doOneIteration() repeatedly.
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
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 singlestep 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 shortestpath 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 finergrained
control of the algorithm is needed. 
protected void 
initMap()
Can be overridden to initialize a locatorlookup 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 shortestpath
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 
pq_
protected PriorityQueue pq_
g_
protected InspectableGraph g_
source_
protected Vertex source_
IntegerDijkstraTemplate
public IntegerDijkstraTemplate()
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 zeroweight edges,
some of the methods of this class make guarantees based on
assuming positive weights that they cannot make if there are
zeroweight 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 getmethod; 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 finishedvDist
 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 getmethod; 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 shortestpath 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
getmethod; 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 exploreduDist
 The final distance to u (will soon be passed as
svDist to shortestPathFound(.))uv
 Edge being exploreduvWeight
 Weight of uvv
 Vertex being investigated: the bestknownpath to it
will be updated if the path via u and uv is bettervDist
 The present, possibly suboptimal, distance of v
from s
shouldContinue
protected boolean shouldContinue()
 Can be overridden in any application where the full shortestpath
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
shortestpath 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 locatorvLoc
 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 edgevEdge
 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 locatorlookup 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 shortestpath 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 algorithme
 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 singlestep 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 finergrained
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 algorithmsource
 Vertex at which to root the shortestpath 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 singlestep 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 shortestpath 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 algorithmsource
 Vertex at which to root the shortestpath tree