org.geotools.graph.path
Class DijkstraShortestPathFinder

java.lang.Object
  extended byorg.geotools.graph.path.DijkstraShortestPathFinder
All Implemented Interfaces:
GraphWalker

public class DijkstraShortestPathFinder
extends java.lang.Object
implements GraphWalker

Calculates node paths in a graph using Dijkstra's Shortest Path Algorithm. Dijsktras algorithm calculates a shortest path from a specefied node (the source node of the underlying dijkstra iteration) to every other node in the graph.

Author:
Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
See Also:
DijsktraIterator

Constructor Summary
DijkstraShortestPathFinder(Graph graph, DijkstraIterator iterator)
          Constructs a new path finder.
DijkstraShortestPathFinder(Graph graph, Graphable source, DijkstraIterator.EdgeWeighter weighter)
          Constructs a new path finder.
 
Method Summary
 void calculate()
          Performs the graph traversal and calculates the shortest path from the source node to every other node in the graph.
 void finish()
          Does nothing.
 double getCost(Graphable g)
          Returns the cost associated with a node calculated during the graph traversal.
 DijkstraIterator getIterator()
           
 Path getPath(Graphable g)
          Returns a path from g to the source.
 GraphTraversal getTraversal()
           
 int visit(Graphable element, GraphTraversal traversal)
          Does nothing except signal the traversal to continue.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

DijkstraShortestPathFinder

public DijkstraShortestPathFinder(Graph graph,
                                  DijkstraIterator iterator)
Constructs a new path finder.

Parameters:
graph - The graph to calculate paths for.
iterator - The dijsktra iterator to used to calculate shortest paths.

DijkstraShortestPathFinder

public DijkstraShortestPathFinder(Graph graph,
                                  Graphable source,
                                  DijkstraIterator.EdgeWeighter weighter)
Constructs a new path finder.

Parameters:
graph - Graph to calculate paths for.
source - Node to calculate paths from.
weighter - Associates weights with edges in the graph.
Method Detail

calculate

public void calculate()
Performs the graph traversal and calculates the shortest path from the source node to every other node in the graph.


getPath

public Path getPath(Graphable g)
Returns a path from g to the source. If the desired path is the opposite (from the source to g) can be used.

Parameters:
g - The start node of the path to be calculated.
Returns:
A path from g to the source.
See Also:
Walk.riterator()

getCost

public double getCost(Graphable g)
Returns the cost associated with a node calculated during the graph traversal.

Parameters:
g - The node whose cost is desired.
Returns:
The cost associated with the node.

getIterator

public DijkstraIterator getIterator()

getTraversal

public GraphTraversal getTraversal()

visit

public int visit(Graphable element,
                 GraphTraversal traversal)
Does nothing except signal the traversal to continue.

Specified by:
visit in interface GraphWalker
Parameters:
element - The component being visited.
traversal - The traversal controlling the sequence of graph component visits.
Returns:
GraphTraversal#CONTINUE to signal that the traversal should continue.
GraphTraversal#CONTINUE to signal that the traversal should suspend.
GraphTraversal#KILL_BRANCH to signal that the traversal should kill its current branch.
GraphTraversal#STOP to signal that the traversal should stop.
See Also:
GraphWalker.visit(Graphable, GraphTraversal)

finish

public void finish()
Does nothing.

Specified by:
finish in interface GraphWalker
See Also:
GraphWalker.finish()


Copyright © GeoTools. All Rights Reserved.