|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--jdsl.graph.algo.IntegerDijkstraTemplate
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:
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 |
protected PriorityQueue pq_
protected InspectableGraph g_
protected Vertex source_
Constructor Detail |
public IntegerDijkstraTemplate()
Method Detail |
protected abstract int weight(Edge e)
e
- Edge for which the algorithm needs to know a weightprotected void shortestPathFound(Vertex v, int vDist)
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.
v
- Vertex that the algorithm just finishedvDist
- Distance of v from the sourceprotected void vertexNotReachable(Vertex v)
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.
v
- Vertex which the algorithm just found to be unreachable
from the sourceprotected void edgeRelaxed(Vertex u, int uDist, Edge uv, int uvWeight, Vertex v, int vDist)
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.
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 best-known-path to it
will be updated if the path via u and uv is bettervDist
- The present, possibly suboptimal, distance of v
from sprotected boolean shouldContinue()
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.protected boolean isFinished(Vertex v)
v
- a vertexprotected void setLocator(Vertex v, Locator vLoc)
v
- Vertex to decorate with a locatorvLoc
- the locator with which to decorate vgetLocator(Vertex)
,
Decorable.set(Object,Object)
protected Locator getLocator(Vertex v)
v
- Vertex previously decorated with a locatorsetLocator(Vertex,Locator)
,
Decorable.get(Object)
protected void setEdgeToParent(Vertex v, Edge vEdge)
v
- Vertex to decorate with an edgevEdge
- the with which to decorate vgetEdgeToParent(Vertex)
,
Decorable.set(Object,Object)
protected PriorityQueue newPQ()
protected void initMap()
protected EdgeIterator incidentEdges(Vertex v)
return G.incidentEdges(v, EdgeDirection.IN | EdgeDirection.OUT);
v
- Vertex soon to be finished by the algorithmprotected Vertex destination(Vertex origin, Edge e)
origin
and needs all its
adjacent vertices.origin
- Vertex soon to be finished by the algorithme
- Edge incident on origin
according to
incidentEdges(.)origin
along
e
protected VertexIterator vertices()
public final boolean isReachable(Vertex v)
v
- a vertexpublic final int distance(Vertex v) throws InvalidQueryException
v
- a vertexInvalidQueryException
- if v has not been reached yetpublic Edge getEdgeToParent(Vertex v) throws InvalidQueryException
v
- Vertex previously labeled with an edgeInvalidQueryException
- if v is the source or has not
been reached yetsetEdgeToParent(Vertex,Edge)
,
Decorable.get(Object)
public void init(InspectableGraph g, Vertex source)
Calls the following methods that can be overridden: newPQ(), initMap(), vertices(), setLocator(.).
g
- Graph on which to execute the algorithmsource
- Vertex at which to root the shortest-path treepublic void cleanup()
public final void doOneIteration() throws InvalidEdgeException
protected final void runUntil()
public final void execute(InspectableGraph g, Vertex source)
g
- Graph on which to execute the algorithmsource
- Vertex at which to root the shortest-path tree
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |