Package org.geotools.graph.traverse.standard

Class AStarIterator

  • All Implemented Interfaces:
    GraphIterator
    public class AStarIterator
extends SourceGraphIterator
    A path iterator that 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)
    • An admissible "heuristic estimate" (usually denoted h(x)).
    The iterator proceeds as follows (pseudo-code): 
     
     // 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 more details see http://en.wikipedia.org/wiki/A_star
    Author:
    Germán E. Trouillet, Francisco G. Malbrán. Universidad Nacional de Córdoba (UNC)

    • 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)

      • getRelated

        protected Iterator<?> getRelated​(Graphable current)