Class Algorithms<V>

java.lang.Object
com.github.yellowstonegames.path.Algorithms<V>
Type Parameters:
V - the vertex type; often Coord
Direct Known Subclasses:
DirectedGraphAlgorithms, UndirectedGraphAlgorithms
public class Algorithms<V> extends Object
Most of the algorithms that operate on a Graph are defined here, with some specific cases in subclasses. The most-frequently-used algorithm here is probably findShortestPath(Object, Object, ObjectDeque, Heuristic), or some overload of it; this is a standard A-Star algorithm backed by a priority queue that is very fast. Somewhat surprisingly, it doesn't need indices like gdx-ai's IndexedAStarPathFinder needs, and this makes the code easier to use. There's a good amount of other useful algorithms here, like containsCycle() and various non-A-Star search methods, like breadthFirstSearch(Object, int, int) and depthFirstSearch(Object, int, int).
This class is not meant to be extended from outside of this package, so it uses a package-private implementation.

  • Method Summary

    Modifier and Type
    Method
    Description
    Graph<V>
    breadthFirstSearch(V v)
    Perform a breadth first search starting from the specified vertex.
    Graph<V>
    breadthFirstSearch(V v, int maxVertices, int maxDepth)
    Perform a breadth first search starting from the specified vertex.
    boolean
    containsCycle()
    Checks whether there are any cycles in the graph using depth first searches.
    Graph<V>
    depthFirstSearch(V v)
    Perform a depth first search starting from the specified vertex.
    Graph<V>
    depthFirstSearch(V v, int maxVertices, int maxDepth)
    Perform a depth first search starting from the specified vertex.
    float
    findMinimumDistance(V start, V target)
    Find the length of the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
    float
    findMinimumDistance(V start, V target, Heuristic<V> heuristic)
    Find the length of the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
    com.github.tommyettinger.ds.ObjectDeque<V>
    findShortestPath(V start, V target)
    Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
    boolean
    findShortestPath(V start, V target, com.github.tommyettinger.ds.ObjectDeque<V> path, Heuristic<V> heuristic)
    Find the shortest path between the start and target vertices, using the A* search algorithm with the provided heuristic, and implemented with a priority queue.
    com.github.tommyettinger.ds.ObjectDeque<V>
    findShortestPath(V start, V target, Heuristic<V> heuristic)
    Find the shortest path between the start and target vertices, using the A* search algorithm with the provided heuristic, and implemented with a priority queue.
    boolean
    isConnected(V start, V target)
    Checks whether there exists a path from the start vertex to target vertex, using Dijkstra's algorithm implemented with a priority queue.
    int
    lastRunID()
    Gets the identifier for the last run of an algorithm; this should mostly be usable internally, but may be useful when different runs have affected a graph and a Node.lastRunID may need to be checked against this.
    void
    setRunID(int newID)
    Sets the identifier for the last run of an algorithm; this should mostly be usable internally, but may be useful when serializing and deserializing a Graph and you, for whatever reason, need to ensure previous runs of an algorithm on that Graph can be resumed.

    Methods inherited from class Object

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

  • Method Details

    • findShortestPath

      public com.github.tommyettinger.ds.ObjectDeque<V> findShortestPath(V start, V target)
      Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
      Parameters:
      start - the starting vertex
      target - the target vertex
      Returns:
      a list of vertices from start to target containing the ordered vertices of a shortest path, including both the start and target vertices

    • findShortestPath

      public com.github.tommyettinger.ds.ObjectDeque<V> findShortestPath(V start, V target, Heuristic<V> heuristic)
      Find the shortest path between the start and target vertices, using the A* search algorithm with the provided heuristic, and implemented with a priority queue.
      Parameters:
      start - the starting vertex
      target - the target vertex
      Returns:
      a list of vertices from start to target containing the ordered vertices of a shortest path, including both the start and target vertices

    • findShortestPath

      public boolean findShortestPath(V start, V target, com.github.tommyettinger.ds.ObjectDeque<V> path, Heuristic<V> heuristic)
      Find the shortest path between the start and target vertices, using the A* search algorithm with the provided heuristic, and implemented with a priority queue. Fills path with a list of vertices from start to target containing the ordered vertices of a shortest path, including both the start and target vertices.
      Parameters:
      start - the starting vertex
      target - the target vertex
      path - the list of vertices to which the path vertices should be added
      Returns:
      true if a path was found, or false if no path could be found

    • findMinimumDistance

      public float findMinimumDistance(V start, V target)
      Find the length of the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
      Parameters:
      start - the starting vertex
      target - the target vertex
      Returns:
      the sum of the weights in a shortest path from the starting vertex to the target vertex If there is no path from the start vertex to the target vertex, Float.MAX_VALUE is returned.

    • findMinimumDistance

      public float findMinimumDistance(V start, V target, Heuristic<V> heuristic)
      Find the length of the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
      Parameters:
      start - the starting vertex
      target - the target vertex
      Returns:
      the sum of the weights in a shortest path from the starting vertex to the target vertex If there is no path from the start vertex to the target vertex, Float.MAX_VALUE is returned.

    • isConnected

      public boolean isConnected(V start, V target)
      Checks whether there exists a path from the start vertex to target vertex, using Dijkstra's algorithm implemented with a priority queue.
      Parameters:
      start - the starting vertex
      target - the target vertex
      Returns:
      whether there exists a path from the start vertex to target vertex

    • breadthFirstSearch

      public Graph<V> breadthFirstSearch(V v, int maxVertices, int maxDepth)
      Perform a breadth first search starting from the specified vertex.
      Parameters:
      v - the vertex at which to start the search
      maxVertices - the maximum number of vertices to process before terminating the search
      maxDepth - the maximum edge distance (the number of edges in a shortest path between vertices) a vertex should have to be considered for processing. If a vertex has a distance larger than the maxDepth, it will not be added to the returned graph
      Returns:
      a Graph object containing all the processed vertices, and the edges from which each vertex was encountered. The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be reflected in the iteration order of the collections returned by Graph.getVertices() and Graph.getEdges().

    • breadthFirstSearch

      public Graph<V> breadthFirstSearch(V v)
      Perform a breadth first search starting from the specified vertex.
      Parameters:
      v - the vertex at which to start the search
      Returns:
      a Graph object containing all the processed vertices (all the vertices in this graph), and the edges from which each vertex was encountered. The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be reflected in the iteration order of the collections returned by Graph.getVertices() and Graph.getEdges().

    • depthFirstSearch

      public Graph<V> depthFirstSearch(V v, int maxVertices, int maxDepth)
      Perform a depth first search starting from the specified vertex.
      Parameters:
      v - the vertex at which to start the search
      maxVertices - the maximum number of vertices to process before terminating the search
      maxDepth - the maximum edge distance (the number of edges in a shortest path between vertices) a vertex should have to be considered for processing. If a vertex has a distance larger than the maxDepth, it will not be added to the returned graph
      Returns:
      a Graph object containing all the processed vertices, and the edges from which each vertex was encountered. The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be reflected in the iteration order of the collections returned by Graph.getVertices() and Graph.getEdges().

    • depthFirstSearch

      public Graph<V> depthFirstSearch(V v)
      Perform a depth first search starting from the specified vertex.
      Parameters:
      v - the vertex at which to start the search
      Returns:
      a Graph object containing all the processed vertices (all the vertices in this graph), and the edges from which each vertex was encountered. The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be reflected in the iteration order of the collections returned by Graph.getVertices() and Graph.getEdges().

    • containsCycle

      public boolean containsCycle()
      Checks whether there are any cycles in the graph using depth first searches.
      Returns:
      true if the graph contains a cycle, false otherwise

    • lastRunID

      public int lastRunID()
      Gets the identifier for the last run of an algorithm; this should mostly be usable internally, but may be useful when different runs have affected a graph and a Node.lastRunID may need to be checked against this.
      Returns:
      an identifier for which algorithm ran last, as a probably-unique int

    • setRunID

      public void setRunID(int newID)
      Sets the identifier for the last run of an algorithm; this should mostly be usable internally, but may be useful when serializing and deserializing a Graph and you, for whatever reason, need to ensure previous runs of an algorithm on that Graph can be resumed.
      Parameters:
      newID - an identifier for which algorithm ran last, as a probably-unique int