org.geotools.graph.path
Class AStarShortestPathFinder

Object
  extended by 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
Module:
modules/extension/graph (gt-graph.jar)

Constructor Summary
AStarShortestPathFinder(Graph graph, Node source, Node target, AStarIterator.AStarFunctions afuncs)
          Constructs a new path finder
 
Method Summary
 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.
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 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()


Copyright © 1996-2009 Geotools. All Rights Reserved.