nz.ac.waikato.jdsl.graph.algo
Class IntegerDijkstraTemplate

java.lang.Object
  nz.ac.waikato.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:

• 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 negative-weight 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 single-step 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:

JDSL 2.1.1

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 nz.ac.waikato.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 nz.ac.waikato.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.

Throws:

InvalidEdgeException

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