Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath

Class AStarSpurEngine<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.AStarSpurEngine<V,E>
Type Parameters:
V - graph vertex type
E - graph edge type
All Implemented Interfaces:
SpurShortestPathEngine<V,E>
public class AStarSpurEngine<V,E> extends Object implements SpurShortestPathEngine<V,E>
Spur shortest-path engine that delegates to JGraphT's AStarShortestPath, using the reverseDistancesToSink hint as an admissible heuristic. Bans are applied by wrapping the input graph in a MaskSubgraph so we do not duplicate or modify the underlying A* implementation.

Correctness: distances on the original graph are a valid lower bound for distances on any subgraph obtained by removing vertices/edges (Dijkstra never gets shorter when the graph shrinks). So h(v) = reverseDistancesToSink[v] is admissible for the spur subproblem on the masked graph. If the heuristic map is null or missing for some vertex, the engine falls back to 0.0 for that vertex (still admissible, equivalent to running A* with a trivial heuristic, i.e. Dijkstra).

Edge weights must be non-negative.

  • Constructor Details

    • AStarSpurEngine

      public AStarSpurEngine()

  • Method Details

    • findPath

      public GraphPath<V,E> findPath(Graph<V,E> graph, V source, V sink, Set<V> bannedVertices, Set<E> bannedEdges, Map<V,Double> reverseDistancesToSink)
      Description copied from interface: SpurShortestPathEngine
      Compute an exact shortest path from source to sink on graph ignoring vertices in bannedVertices and edges in bannedEdges.
      Specified by:
      findPath in interface SpurShortestPathEngine<V,E>
      Parameters:
      graph - original graph (engines should not mutate it)
      source - source vertex of the spur query
      sink - target vertex of the spur query
      bannedVertices - vertices to ignore (must not include source or sink)
      bannedEdges - edges to ignore
      reverseDistancesToSink - optional hint, lower-bound distances from each vertex to sink computed on the original graph; may be null for engines that do not need it
      Returns:
      the shortest path or null if no path exists in the masked graph

    • expandedVertices

      public long expandedVertices()
      Description copied from interface: SpurShortestPathEngine
      Number of vertices the engine has expanded (popped from its open set) since the last SpurShortestPathEngine.resetCounters() call. Best-effort metric used by benchmarks; engines that do not track expansion (e.g. those delegating to a back-end without a public expansion counter) may return 0.
      Specified by:
      expandedVertices in interface SpurShortestPathEngine<V,E>
      Returns:
      number of vertices popped from the engine's open set since the last reset, or 0 when not tracked

    • pathQueries

      public long pathQueries()
      Description copied from interface: SpurShortestPathEngine
      Number of shortest-path queries answered since the last SpurShortestPathEngine.resetCounters() call.
      Specified by:
      pathQueries in interface SpurShortestPathEngine<V,E>
      Returns:
      number of shortest-path queries answered since the last reset

    • resetCounters

      public void resetCounters()
      Description copied from interface: SpurShortestPathEngine
      Reset internal counters. Called by BoundedPrunedYenKShortestPath between independent runs so that counters report per-run statistics.
      Specified by:
      resetCounters in interface SpurShortestPathEngine<V,E>

    • name

      public String name()
      Description copied from interface: SpurShortestPathEngine
      Symbolic name of the engine, used in benchmark reports.
      Specified by:
      name in interface SpurShortestPathEngine<V,E>
      Returns:
      a short human-readable identifier for this engine