org.geotools.graph.path

Class DijkstraShortestPathFinder

Object

DijkstraShortestPathFinder

All Implemented Interfaces:

GraphWalker

public class DijkstraShortestPathFinder
extends 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

Constructors

Constructor and Description
DijkstraShortestPathFinder(Graph graph, DijkstraIterator iterator) Constructs a new path finder.
DijkstraShortestPathFinder(Graph graph, Graphable source, DijkstraIterator.EdgeWeighter weighter) Constructs a new path finder.
DijkstraShortestPathFinder(Graph graph, Graphable source, DijkstraIterator.EdgeWeighter weighter, DijkstraIterator.NodeWeighter nweighter) Constructs a new path finder.

Method Summary

Modifier and Type	Method and Description
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 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.

DijkstraShortestPathFinder

public DijkstraShortestPathFinder(Graph graph,
                                  Graphable source,
                                  DijkstraIterator.EdgeWeighter weighter,
                                  DijkstraIterator.NodeWeighter nweighter)

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.

nweighter - Associates weights with nodes 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()