Package graph

Class Pathfinding

java.lang.Object
graph.Pathfinding
public class Pathfinding extends Object

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    (package private) static final record 
    Pathfinding.PathEnd<E extends Edge<?>>
    Represents a path ending at `lastEdge.end()` along with its total weight (distance).

  • Constructor Summary

    Constructors
    Constructor
    Description
    Pathfinding()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    (package private) static <V extends Vertex<E>, E extends Edge<V>>
    Map<V,Pathfinding.PathEnd<E>>
    pathInfo(V src, E previousEdge)
    Returns a map that associates each vertex reachable from `src` along a non-backtracking path with a `PathEnd` object.
    (package private) static <V, E extends Edge<V>>
    List<E>
    pathTo(Map<V,Pathfinding.PathEnd<E>> pathInfo, V src, V dst)
    Return the list of edges in the shortest non-backtracking path from `src` to `dst`, as summarized by the given `pathInfo` map.
    static <V extends Vertex<E>, E extends Edge<V>>
    List<E>
    shortestNonBacktrackingPath(V src, V dst, E previousEdge)
    Returns a list of `E` edges comprising the shortest non-backtracking path from vertex `src` to vertex `dst`.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • Pathfinding

      public Pathfinding()

  • Method Details

    • shortestNonBacktrackingPath

      public static <V extends Vertex<E>, E extends Edge<V>> List<E> shortestNonBacktrackingPath(V src, V dst, E previousEdge)
      Returns a list of `E` edges comprising the shortest non-backtracking path from vertex `src` to vertex `dst`. A non-backtracking path never contains two consecutive edges between the same two vertices (e.g., v -> w -> v). As a part of this requirement, the first edge in the returned path cannot back-track `previousEdge` (when `previousEdge` is not null). If there is not a non-backtracking path from `src` to `dst`, then null is returned. Requires that if `E != null` then `previousEdge.dst().equals(src)`.

    • pathInfo

      static <V extends Vertex<E>, E extends Edge<V>> Map<V,Pathfinding.PathEnd<E>> pathInfo(V src, E previousEdge)
      Returns a map that associates each vertex reachable from `src` along a non-backtracking path with a `PathEnd` object. The `PathEnd` object summarizes relevant information about the shortest non-backtracking path from `src` to that vertex. A non-backtracking path never contains two consecutive edges between the same two vertices (e.g., v -> w -> v). As a part of this requirement, the first edge in the returned path cannot backtrack `previousEdge` (when `previousEdge` is not null). Requires that if `E != null` then `previousEdge.dst().equals(src)`.

    • pathTo

      static <V, E extends Edge<V>> List<E> pathTo(Map<V,Pathfinding.PathEnd<E>> pathInfo, V src, V dst)
      Return the list of edges in the shortest non-backtracking path from `src` to `dst`, as summarized by the given `pathInfo` map. Requires `pathInfo` conforms to the specification as documented by the `pathInfo` method; it must contain backpointers for the shortest non-backtracking paths from `src` to all reachable vertices.