Class Dijkstra<E>

java.lang.Object
rgu.transport.algorithms.search.Dijkstra<E>
All Implemented Interfaces:
ReachabilityAlgorithm<E>, RoutingAlgorithm<E>, SpatialTemporalReachabilityAlgorithm<E>, SpatialTemporalRoutingAlgorithm<E>
public final class Dijkstra<E> extends Object implements RoutingAlgorithm<E>, ReachabilityAlgorithm<E>, SpatialTemporalRoutingAlgorithm<E>, SpatialTemporalReachabilityAlgorithm<E>
A thread-safe and generic implementation of Dijkstra's shortest path algorithm. Instances are typically obtained by calling ofInt(), ofLong(), ofDouble(), ofDuration(), etc. depending on the desired edge type. The generic constructor Dijkstra(Object, BinaryOperator, BiPredicate) method enables use of Dijkstra on other types not listed. Dijkstra uses the BinaryMinHeap class.
Author:
Lee A. Christie

  • Constructor Details

    • Dijkstra

      public Dijkstra(E zero, BinaryOperator<E> add, BiPredicate<E,E> lessThan)
      Creates an instance of Dijkstra which works on the specified generic type of edges. Operators must be pure and the zero immutable for a valid thread-safe instance to be returned.
      Parameters:
      zero - an immutable instance of E which represents the constant zero, not null
      add - a pure binary operator which returns a + b, not null
      lessThan - a pure predicate which tests whether a < b, not null

  • Method Details

    • ofLong

      public static Dijkstra<Long> ofLong()
      Returns an instance of Dijkstra which works on long edges.
      Returns:
      a Dijkstra instance

    • ofDouble

      public static Dijkstra<Double> ofDouble()
      Returns an instance of Dijkstra which works on double edges.
      Returns:
      a Dijkstra instance

    • ofInt

      public static Dijkstra<Integer> ofInt()
      Returns an instance of Dijkstra which works on integer edges.
      Returns:
      a Dijkstra instance

    • ofDuration

      public static Dijkstra<Duration> ofDuration()
      Returns an instance of Dijkstra which works on duration edges.
      Returns:
      a Dijkstra instance

    • ofNegativeDuration

      public static Dijkstra<Duration> ofNegativeDuration()
      Returns an instance of Dijkstra which works on duration edges where edges are all negative but treated as positive.
      Returns:
      a Dijkstra instance

    • ofDistance

      public static Dijkstra<Distance> ofDistance()
      Returns an instance of Dijkstra which works on distance edges.
      Returns:
      a Dijkstra instance

    • cost

      public <V> E cost(Explorable<V,E> graph, List<V> path)
      Reconstructs the total cost of a given path.
      Specified by:
      cost in interface RoutingAlgorithm<E>
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      path - a list of vertices describing each step in the path, no null
      Returns:
      the total cost of the path

    • path

      public <V> List<V> path(Explorable<V,E> graph, V source, V target) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target.
      Specified by:
      path in interface RoutingAlgorithm<E>
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the target vertex, in graph, not null
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted

    • path

      public <V> List<V> path(Explorable<V,E> graph, V source, V target, E maxCost) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target within a given maximum cost.
      Specified by:
      path in interface RoutingAlgorithm<E>
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the target vertex, in graph, not null
      maxCost - the maximum cost, considered unlimited if null
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted

    • path

      public <V> List<V> path(Explorable<V,E> graph, V source, Predicate<V> target) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target(s) by predicate which returns true if a given vertex is a target.
      Specified by:
      path in interface RoutingAlgorithm<E>
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the criteria to identify a target vertex, in graph, not null
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted

    • path

      public <V> List<V> path(Explorable<V,E> graph, V source, Predicate<V> target, E maxCost) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target(s) by predicate which returns true if a given vertex is a target, within a given maximum cost.
      Specified by:
      path in interface RoutingAlgorithm<E>
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the target vertex, in graph, not null
      maxCost - the maximum cost, considered unlimited if null
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted

    • stPath

      public <ST,S> List<ST> stPath(Explorable<ST,E> graph, ST source, ST target, SpatialTemporalMapping<S,E,ST> stMapping) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target.
      Specified by:
      stPath in interface SpatialTemporalRoutingAlgorithm<E>
      Type Parameters:
      ST - the type of the spatial-temporal vertex
      S - the type of the spatial component of the vertex
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the target vertex, in graph, not null
      stMapping - a spatial-temporal mapping
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted

    • stPath

      public <ST,S> List<ST> stPath(Explorable<ST,E> graph, ST source, ST target, E maxCost, SpatialTemporalMapping<S,E,ST> stMapping) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target within a given maximum cost.
      Specified by:
      stPath in interface SpatialTemporalRoutingAlgorithm<E>
      Type Parameters:
      ST - the type of the spatial-temporal vertex
      S - the type of the spatial component of the vertex
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the target vertex, in graph, not null
      maxCost - the maximum cost, considered unlimited if null
      stMapping - a spatial-temporal mapping
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted

    • stPath

      public <ST,S> List<ST> stPath(Explorable<ST,E> graph, ST source, Predicate<ST> target, SpatialTemporalMapping<S,E,ST> stMapping) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target(s) by predicate which returns true if a given vertex is a target.
      Specified by:
      stPath in interface SpatialTemporalRoutingAlgorithm<E>
      Type Parameters:
      ST - the type of the spatial-temporal vertex
      S - the type of the spatial component of the vertex
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the criteria to identify a target vertex, in graph, not null
      stMapping - a spatial-temporal mapping
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted

    • stPath

      public <ST,S> List<ST> stPath(Explorable<ST,E> graph, ST source, Predicate<ST> target, E maxCost, SpatialTemporalMapping<S,E,ST> stMapping) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target(s) by predicate which returns true if a given vertex is a target, within a given maximum cost.
      Specified by:
      stPath in interface SpatialTemporalRoutingAlgorithm<E>
      Type Parameters:
      ST - the type of the spatial-temporal vertex
      S - the type of the spatial component of the vertex
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the target vertex, in graph, not null
      maxCost - the maximum cost, considered unlimited if null
      stMapping - a spatial-temporal mapping
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted

    • reachable

      public <V> Map<V,E> reachable(Explorable<V,E> graph, V source) throws InterruptedException
      Returns the set of reachable vertices and the corresponding cost of each vertex's shortest path.
      Specified by:
      reachable in interface ReachabilityAlgorithm<E>
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      Returns:
      a map of reachable vertices, with associated costs
      Throws:
      InterruptedException - if the thread is interrupted

    • reachable

      public <V> Map<V,E> reachable(Explorable<V,E> graph, V source, E maxCost) throws InterruptedException
      Returns the set of vertices reachable within a given maximum cost, and the corresponding cost of each vertex's shortest path.
      Specified by:
      reachable in interface ReachabilityAlgorithm<E>
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      maxCost - the maximum cost, considered unlimited if null
      Returns:
      a map of reachable vertices, with associated costs
      Throws:
      InterruptedException - if the thread is interrupted

    • reachable

      public <V> void reachable(Explorable<V,E> graph, V source, ReachabilityCallback<V,E> callback) throws InterruptedException
      Streams to a callback function the set of reachable vertices and the corresponding cost of each vertex's shortest path.
      Specified by:
      reachable in interface ReachabilityAlgorithm<E>
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      callback - a callback which acts as a consumer of reachable vertices, with associated costs, but returns ReachabilityCallback.Action.BREAK if the algorithm should abandon the search or ReachabilityCallback.Action.CONTINUE otherwise, not null
      Throws:
      InterruptedException - if the thread is interrupted

    • reachable

      public <V> void reachable(Explorable<V,E> graph, V source, E maxCost, ReachabilityCallback<V,E> callback) throws InterruptedException
      Streams to a callback function the set of vertices reachable within a given maximum cost, and the corresponding cost of each vertex's shortest path.
      Specified by:
      reachable in interface ReachabilityAlgorithm<E>
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      maxCost - the maximum cost, considered unlimited if null
      callback - a callback which acts as a consumer of reachable vertices, with associated costs, but returns ReachabilityCallback.Action.BREAK if the algorithm should abandon the search or ReachabilityCallback.Action.CONTINUE otherwise, not null
      Throws:
      InterruptedException - if the thread is interrupted

    • stReachable

      public <ST,S> Map<ST,E> stReachable(Explorable<ST,E> graph, ST source, SpatialTemporalMapping<S,E,ST> stMapping) throws InterruptedException
      Returns the set of reachable vertices and the corresponding cost of each vertex's shortest path.
      Specified by:
      stReachable in interface SpatialTemporalReachabilityAlgorithm<E>
      Type Parameters:
      ST - the type of the spatial-temporal vertex
      S - the type of the spatial component of the vertex
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      stMapping - a spatial-temporal mapping
      Returns:
      a map of reachable vertices, with associated costs
      Throws:
      InterruptedException - if the thread is interrupted

    • stReachable

      public <ST,S> Map<ST,E> stReachable(Explorable<ST,E> graph, ST source, E maxCost, SpatialTemporalMapping<S,E,ST> stMapping) throws InterruptedException
      Returns the set of vertices reachable within a given maximum cost, and the corresponding cost of each vertex's shortest path.
      Specified by:
      stReachable in interface SpatialTemporalReachabilityAlgorithm<E>
      Type Parameters:
      ST - the type of the spatial-temporal vertex
      S - the type of the spatial component of the vertex
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      maxCost - the maximum cost, considered unlimited if null
      stMapping - a spatial-temporal mapping
      Returns:
      a map of reachable vertices, with associated costs
      Throws:
      InterruptedException - if the thread is interrupted

    • stReachable

      public <ST,S> void stReachable(Explorable<ST,E> graph, ST source, ReachabilityCallback<ST,E> callback, SpatialTemporalMapping<S,E,ST> stMapping) throws InterruptedException
      Streams to a callback function the set of reachable vertices and the corresponding cost of each vertex's shortest path.
      Specified by:
      stReachable in interface SpatialTemporalReachabilityAlgorithm<E>
      Type Parameters:
      ST - the type of the spatial-temporal vertex
      S - the type of the spatial component of the vertex
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      callback - a callback which acts as a consumer of reachable vertices, with associated costs, but returns ReachabilityCallback.Action.BREAK if the algorithm should abandon the search or ReachabilityCallback.Action.CONTINUE otherwise, not null
      stMapping - a spatial-temporal mapping
      Throws:
      InterruptedException - if the thread is interrupted

    • stReachable

      public <ST,S> void stReachable(Explorable<ST,E> graph, ST source, E maxCost, ReachabilityCallback<ST,E> callback, SpatialTemporalMapping<S,E,ST> stMapping) throws InterruptedException
      Streams to a callback function the set of vertices reachable within a given maximum cost, and the corresponding cost of each vertex's shortest path.
      Specified by:
      stReachable in interface SpatialTemporalReachabilityAlgorithm<E>
      Type Parameters:
      ST - the type of the spatial-temporal vertex
      S - the type of the spatial component of the vertex
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      maxCost - the maximum cost, considered unlimited if null
      callback - a callback which acts as a consumer of reachable vertices, with associated costs, but returns ReachabilityCallback.Action.BREAK if the algorithm should abandon the search or ReachabilityCallback.Action.CONTINUE otherwise, not null
      stMapping - a spatial-temporal mapping
      Throws:
      InterruptedException - if the thread is interrupted