org.geotools.graph.traverse.standard
Class AStarIterator

Object
  extended by AbstractGraphIterator
      extended by SourceGraphIterator
          extended by AStarIterator
All Implemented Interfaces:
GraphIterator

public class AStarIterator
extends SourceGraphIterator

A Star : It uses a function (usually denoted f(x)) to determine the order in which the algorithm visits nodes, f(x) is a sum of two functions: - The path-cost function (usually denoted g(x), which may or may not be a heuristic) and - An admissible "heuristic estimate" (usually denoted h(x)). the itaration oparates as follows: // COST(n,n') : the real cost to go from n to n' OPEN = [Source] CLOSE = [] while ( |OPEN| > 0 ) n = a node in OPEN with less f remove n from OPEN add n to CLOSE if ( n == target ) { return // path find // if n != target for each node n' that relates to n do if n' in OPEN if (g(n) + COST(n,n')) < g(n') g(n') = g(n) + COST(n,n') parent(n') = n else g(n') = g(n) + COST(n,n') parent(n') = n add n' to OPEN // end while (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)
Module:
modules/extension/graph (gt-graph.jar)

Nested Class Summary
static class AStarIterator.AStarFunctions
          Defines the functions needed by A Star.
static class AStarIterator.AStarNode
          Internal data structure used to track node costs, and parent nodes.
 
Constructor Summary
AStarIterator(Node source, AStarIterator.AStarFunctions afuncs)
           
 
Method Summary
 void cont(Graphable current, GraphTraversal traversal)
          Makes a step of the A* algorithm.
 Node getParent(Node n)
           
 void init(Graph graph, GraphTraversal traversal)
          Does Nothing.
 void killBranch(Graphable current, GraphTraversal traversal)
          Kills the branch of the traversal
 Graphable next(GraphTraversal traversal)
          Returns the next node in the priority queue. if the queue is empty then there is no path from the source to the destiny in this graph.
 
Methods inherited from class SourceGraphIterator
getSource, setSource
 
Methods inherited from class AbstractGraphIterator
getGraph, getTraversal, getWalker, setTraversal
 
Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

AStarIterator

public AStarIterator(Node source,
                     AStarIterator.AStarFunctions afuncs)
Method Detail

init

public void init(Graph graph,
                 GraphTraversal traversal)
Does Nothing. All the work was already done by the constructor.

Parameters:
graph - The graph being whose components are being iterated over.

next

public Graphable next(GraphTraversal traversal)
Returns the next node in the priority queue. if the queue is empty then there is no path from the source to the destiny in this graph.

Returns:
The next component in the iteration, or null if iteration is complete.
See Also:
org.geotools.graph.traverse.GraphIterator#next()

cont

public void cont(Graphable current,
                 GraphTraversal traversal)
Makes a step of the A* algorithm. Takes the current node, looks for its neighbours. The ones which are closed are discarted. The ones "in" the opened queue are checked to see if its necessary to update them. The rest of the nodes are initialized as AStarNodes and inserted in the opened queue.

Parameters:
current - The current component of the traversal.
See Also:
org.geotools.graph.traverse.GraphIterator#cont(Graphable)

killBranch

public void killBranch(Graphable current,
                       GraphTraversal traversal)
Kills the branch of the traversal

Parameters:
current - The current component of the traversal.
See Also:
org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)

getParent

public Node getParent(Node n)


Copyright © 1996-2010 Geotools. All Rights Reserved.