jdsl.graph.algo
Class IntegerDijkstraPathfinder

java.lang.Object
  |
  +--jdsl.graph.algo.IntegerDijkstraTemplate
        |
        +--jdsl.graph.algo.IntegerDijkstraPathfinder

public abstract class IntegerDijkstraPathfinder
extends IntegerDijkstraTemplate

Class that allows finding a path between two vertices of a graph, using Dijkstra's algorithm. You must extend this class and implement the weight(Edge) method. As always, Dijkstra's algorithm cannot handle negative-weight edges.

If necessary, you also have access to all the customization methods of IntegerDijkstraTemplate, although using some of them without the knowledge of this class could give incorrect results.

Version:
$Id: IntegerDijkstraPathfinder.java,v 1.13 2001/04/26 09:29:35 lv Exp $
Author:
Mark Handy, Luca Vismara

Fields inherited from class jdsl.graph.algo.IntegerDijkstraTemplate
g_, pq_, source_
 
Constructor Summary
IntegerDijkstraPathfinder()
           
 
Method Summary
 void execute(InspectableGraph g, Vertex source, Vertex dest)
           
 boolean pathExists()
          Returns whether a path between the source and the destination exists
 EdgeIterator reportPath()
           
protected  boolean shouldContinue()
          Can be overridden in any application where the full shortest-path tree is not needed and the algorithm should terminate early.
 
Methods inherited from class jdsl.graph.algo.IntegerDijkstraTemplate
cleanup, destination, distance, doOneIteration, edgeRelaxed, execute, getEdgeToParent, getLocator, incidentEdges, init, initMap, isFinished, isReachable, newPQ, runUntil, setEdgeToParent, setLocator, shortestPathFound, vertexNotReachable, vertices, weight
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

IntegerDijkstraPathfinder

public IntegerDijkstraPathfinder()
Method Detail

shouldContinue

protected boolean shouldContinue()
Description copied from class: IntegerDijkstraTemplate
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.
Overrides:
shouldContinue in class IntegerDijkstraTemplate
Following copied from class: jdsl.graph.algo.IntegerDijkstraTemplate
Returns:
Whether to continue running the algorithm

pathExists

public boolean pathExists()
Returns whether a path between the source and the destination exists
Returns:
whether there is a path from source to destination

reportPath

public EdgeIterator reportPath()
                        throws InvalidQueryException
Returns:
Iterator over the edges, in order, of a shortest path from source to destination

execute

public final void execute(InspectableGraph g,
                          Vertex source,
                          Vertex dest)
                   throws InvalidVertexException
Parameters:
g - the graph on which to execute the algorithm
source - the source vertex
dest - the destination vertex
Throws:
InvalidVertexException - if source or dest are not contained in g