Package megamek.common.pathfinder

Class AbstractPathFinder<N,C,E>

java.lang.Object
megamek.common.pathfinder.AbstractPathFinder<N,C,E>
Type Parameters:
N - the type of nodes in the graph.
C - the type of computed lowest cost for a node. If needed this type can contain information for recreating the path.
E - the type of directed edges used by the graph.
Direct Known Subclasses:
MovePathFinder, SBFMovePathFinder
public class AbstractPathFinder<N,C,E> extends Object
This class provides a skeletal implementation of pathfinder algorithm in a given directed graph.

It uses a generalisation of Dijkstra algorithm. User must provide methods that allow traversing the graph and evaluating paths. All needed methods have been encapsulated and separated in classes:

  • DestinationNodeFactory and EdgeNeighborsFactory - responsible for representing graph
  • Filter - Filters edges that are produced by EdgeNeighborsFactory. It allows EdgeNeighborsFactory to be a general use class.
  • Comparator - compares paths according to generated cost.
  • EdgeRelaxer - relaxes node cost.
  • StopCondition - responsible for halting if user does not want to traverse whole graph.

  • Constructor Details

    • AbstractPathFinder

      public AbstractPathFinder(DestinationMap<N,E> edgeDestinationMap, EdgeRelaxer<C,E> edgeRelaxer, AdjacencyMap<E> edgeAdjacencyMap, Comparator<E> edgeComparator)
      Parameters:
      edgeDestinationMap - functional interface for retrieving destination node of an edge.
      edgeRelaxer - functional interface for calculating relaxed cost.
      edgeAdjacencyMap - functional interface for retrieving neighbouring edges.
      edgeComparator - implementation of path comparator. Each path is defined by its last edge. (path:= edge concatenated with the best path to the source of the edge)

  • Method Details

    • addFilter

      public void addFilter(Filter<E> edgeFilter)
      Adds an EdgeFilter. If this method is invoked multiple times: an edge is removed from the graph iff at least one filter removes it.
      See Also:

    • removeAllFilters

      @Deprecated(since="0.51.0", forRemoval=true) public void removeAllFilters()
      Deprecated, for removal: This API element is subject to removal in a future version.

    • addStopCondition

      public void addStopCondition(StopCondition<E> stopCondition)
      See Also:

    • run

      public void run(Collection<E> startingEdges)
      Computes shortest paths to nodes in the graph.
      Parameters:
      startingEdges - a collection of possible starting edges.

    • run

      public void run(E start)
      Computes shortest paths to nodes in the graph.
      Parameters:
      start - a starting edge.

    • getComparator

      public Comparator<E> getComparator()
      Returns:
      edge comparator used by this AbstractPathFinder

    • getCostOf

      protected C getCostOf(N node)
      Returns:
      calculated cost for this node or null if this node has not been reached.

    • getPathCostMap

      protected Map<N,C> getPathCostMap()
      Returns the cost map. Important: Neither the returned map, nor its elements, should be modified.
      Returns:
      map Node to LowestCost

    • setAdjacencyMap

      @Deprecated(since="0.51.0", forRemoval=true) public void setAdjacencyMap(AdjacencyMap<E> edgeNeighborsFactory)
      Deprecated, for removal: This API element is subject to removal in a future version.
      See Also:

    • getAdjacencyMap

      @Deprecated(since="0.51.0", forRemoval=true) public AdjacencyMap<E> getAdjacencyMap()
      Deprecated, for removal: This API element is subject to removal in a future version.

    • setComparator

      public void setComparator(Comparator<E> comparator)
      Sets comparator.
      Parameters:
      comparator - implementation of path comparator. Each path is uniquely defined by its last edge. (path:= an edge concatenated with the best path to the source of the edge)

    • setDestinationMap

      @Deprecated(since="0.51.0", forRemoval=true) public void setDestinationMap(DestinationMap<N,E> nodeFactory)
      Deprecated, for removal: This API element is subject to removal in a future version.
      See Also:

    • getDestinationMap

      @Deprecated(since="0.51.0", forRemoval=true) protected DestinationMap<N,E> getDestinationMap()
      Deprecated, for removal: This API element is subject to removal in a future version.

    • setEdgeRelaxer

      @Deprecated(since="0.51.0", forRemoval=true) public void setEdgeRelaxer(EdgeRelaxer<C,E> costRelaxer)
      Deprecated, for removal: This API element is subject to removal in a future version.
      See Also: