Package com.inductiveautomation.ignition.designer.blockandconnector.routing

Class AStar<T>

  • public abstract class AStar<T>
extends java.lang.Object
    A* algorithm implementation using the method design pattern.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      class  AStar.Path  

    • Constructor Summary

      Constructors 
      Constructor Description
      AStar()
      Default c'tor.

    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.List<T> compute​(T start)
      Find the shortest path to a goal starting from start.
      protected java.lang.Double f​(AStar.Path p, T from, T to)
      Total cost function to reach the node to from from.
      protected abstract java.lang.Double g​(AStar.Path path, T from, T to)
      Cost for the operation to go to to from from.
      protected abstract java.util.List<T> generateSuccessors​(T node)
      Generate the successors for a given node.
      java.lang.Double getCost()
      Get the cost to reach the last node in the path.
      int getExpandedCounter()
      Check how many times a node was expanded.
      protected abstract java.lang.Double h​(T from, T to)
      Estimated cost to reach a goal node.
      protected abstract boolean isGoal​(T node)
      Check if the current node is a goal for the problem.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • AStar

        public AStar()
        Default c'tor.

    • Method Detail

      • isGoal

        protected abstract boolean isGoal​(T node)
        Check if the current node is a goal for the problem.
        Parameters:
        node - The node to check.
        Returns:
        true if it is a goal, false otherwise.

      • g

        protected abstract java.lang.Double g​(AStar.Path path,
                                      T from,
                                      T to)
        Cost for the operation to go to to from from.
        Parameters:
        from - The node we are leaving.
        to - The node we are reaching.
        Returns:
        The cost of the operation.

      • h

        protected abstract java.lang.Double h​(T from,
                                      T to)
        Estimated cost to reach a goal node. An admissible heuristic never gives a cost bigger than the real one. from.
        Parameters:
        from - The node we are leaving.
        to - The node we are reaching.
        Returns:
        The estimated cost to reach an object.

      • generateSuccessors

        protected abstract java.util.List<T> generateSuccessors​(T node)
        Generate the successors for a given node.
        Parameters:
        node - The node we want to expand.
        Returns:
        A list of possible next steps.

      • getExpandedCounter

        public int getExpandedCounter()
        Check how many times a node was expanded.
        Returns:
        A counter of how many times a node was expanded.

      • f

        protected java.lang.Double f​(AStar.Path p,
                             T from,
                             T to)
        Total cost function to reach the node to from from.

        The total cost is defined as: f(x) = g(x) + h(x).

        Parameters:
        from - The node we are leaving.
        to - The node we are reaching.
        Returns:
        The total cost.

      • getCost

        public java.lang.Double getCost()
        Get the cost to reach the last node in the path.
        Returns:
        The cost for the found path.

      • compute

        public java.util.List<T> compute​(T start)
        Find the shortest path to a goal starting from start.
        Parameters:
        start - The initial node.
        Returns:
        A list of nodes from the initial point to a goal, null if a path doesn't exist.