Class 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 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()