Package org.geotools.graph.path

Class AStarShortestPathFinder

Object

AStarShortestPathFinder

All Implemented Interfaces:

GraphWalker

public class AStarShortestPathFinder
extends Object
implements GraphWalker

Calculates the shortest path between two nodes using the A Star algorithm (for details see http://en.wikipedia.org/wiki/A_star)

Author:

Germán E. Trouillet, Francisco G. Malbrán. Universidad Nacional de Córdoba (UNC)

See Also:

AStarIterator

Constructor Summary

Constructors

Constructor	Description
AStarShortestPathFinder(Graph graph, Node source, Node target, AStarIterator.AStarFunctions afuncs)	Constructs a new path finder

Method Summary

Modifier and Type	Method	Description
void	calculate()	Performs the graph traversal and calculates the shortest path from the source node to destiny node in the graph.
void	finish()	Does nothing.
Path	getPath()	Returns a path from the target to the source.
int	visit(Graphable element, GraphTraversal traversal)	Visits a graph component.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AStarShortestPathFinder

public AStarShortestPathFinder(Graph graph,
                               Node source,
                               Node target,
                               AStarIterator.AStarFunctions afuncs)

Constructs a new path finder

Parameters:

graph - Graph where we will perform the search.

source - Node to calculate path from.

target - Node to calculate path to.

Method Detail

calculate

public void calculate()

Performs the graph traversal and calculates the shortest path from the source node to destiny node in the graph.

visit

public int visit(Graphable element,
                 GraphTraversal traversal)

Description copied from interface: GraphWalker

Visits a graph component.

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)

getPath

public Path getPath()
             throws WrongPathException

Returns a path from the target to the source. If the desired path is the opposite (from the source to the target), the reverse or the riterator methods from the Path class can be used.

Returns:

A path from the target to the source.

Throws:

WrongPathException

See Also:

Walk.riterator(), Walk.reverse()

finish

public void finish()

Does nothing.

Specified by:

finish in interface GraphWalker

See Also:

GraphWalker.finish()