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

Interface SpurShortestPathEngine<V,E>

Type Parameters:
V - graph vertex type
E - graph edge type
All Known Implementing Classes:
AStarSpurEngine, DijkstraSpurEngine
public interface SpurShortestPathEngine<V,E>
Abstract subroutine for the spur shortest-path computations performed by BoundedPrunedYenKShortestPath.

Implementations must return an exact non-negative-weight shortest path from source to sink on the input graph after temporarily removing the supplied bannedVertices and bannedEdges. Implementations may use the optional reverseDistancesToSink hint (computed once on the original graph by the caller) for admissible heuristic / pruning purposes.

This is a pluggable abstraction so that different shortest-path back-ends can be benchmarked inside the same Yen variant: classical Dijkstra and A* with reverse-distance heuristic. The engine API is intentionally narrow so swapping engines does not change Yen-level behaviour.

  • Method Summary

    Modifier and Type
    Method
    Description
    long
    expandedVertices()
    Number of vertices the engine has expanded (popped from its open set) since the last resetCounters() call.
    GraphPath<V,E>
    findPath(Graph<V,E> graph, V source, V sink, Set<V> bannedVertices, Set<E> bannedEdges, Map<V,Double> reverseDistancesToSink)
    Compute an exact shortest path from source to sink on graph ignoring vertices in bannedVertices and edges in bannedEdges.
    String
    name()
    Symbolic name of the engine, used in benchmark reports.
    long
    pathQueries()
    Number of shortest-path queries answered since the last resetCounters() call.
    void
    resetCounters()
    Reset internal counters.

  • Method Details

    • findPath

      GraphPath<V,E> findPath(Graph<V,E> graph, V source, V sink, Set<V> bannedVertices, Set<E> bannedEdges, Map<V,Double> reverseDistancesToSink)
      Compute an exact shortest path from source to sink on graph ignoring vertices in bannedVertices and edges in bannedEdges.
      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

      long expandedVertices()
      Number of vertices the engine has expanded (popped from its open set) since the last 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.
      Returns:
      number of vertices popped from the engine's open set since the last reset, or 0 when not tracked

    • pathQueries

      long pathQueries()
      Number of shortest-path queries answered since the last resetCounters() call.
      Returns:
      number of shortest-path queries answered since the last reset

    • resetCounters

      void resetCounters()
      Reset internal counters. Called by BoundedPrunedYenKShortestPath between independent runs so that counters report per-run statistics.

    • name

      String name()
      Symbolic name of the engine, used in benchmark reports.
      Returns:
      a short human-readable identifier for this engine