Shortest Path

shortest_path([PathAlgorithm,]
              g::OSMGraph,
              origin::Union{Integer,Node},
              destination::Union{Integer,Node},
              [weights::AbstractMatrix=g.weights;
              cost_adjustment::Function=(u, v, parents) -> 0.0),
              max_distance::W=typemax(W)]

Calculates the shortest path between two OpenStreetMap node ids.

Arguments

• PathAlgorithm (optional): Path finding algorithm, possible values are:
  • Dijkstra: Same as DijkstraVector. This is the default algorithm.
  • DijkstraVector: Dijkstra's algorithm using the Vector implementation. Faster for small graphs and/or long paths.
  • DijkstraDict: Dijkstra's algorithm using the Dict implementation. Faster for large graphs and/or short paths.
  • AStar: Same as AStarVector.
  • AStarVector: A* algorithm using the Vector implementation. Faster for small graphs and/or long paths.
  • AStarDict: A* algorithm using the Dict implementation. Faster for large graphs and/or short paths.
• g::OSMGraph{U,T,W}: Graph container.
• origin::Union{Integer,Node}: Origin OpenStreetMap node or node id.
• destination::Union{Integer,Node},: Destination OpenStreetMap node or node id.
• weights: Optional matrix of node to node edge weights, defaults to g.weights. If a custom weights matrix is being used with algorithm set to AStar, make sure that a correct heuristic is being used.
• cost_adjustment::Function=(u,v,parents) -> 0.0: Option to pass in a function to adjust the cost between each pair of vetices u and v, normally the cost is just the weight between u and v, cost_adjustment takes in 3 arguments; u, v and parents; to apply an additive cost to the default weight. Defaults no adjustment. Use restriction_cost_adjustment to consider turn restrictions.
• heuristic::Function=distance_heuristic(g): Use custom heuristic with the AStar algorithms only. Defaults to a function h(u, v) -> haversine(u, v), i.e. returns the haversine distances between u, the current node, and v, the neighbouring node. If g.weight_type is :time or :lane_efficiency, use time_heuristic(g) instead.

Return

• Union{Nothing,Vector{T}}: Array of OpenStreetMap node ids making up the shortest path.

astar([::Type{<:AStar},]
      g::AbstractGraph{U},
      weights::AbstractMatrix{T},
      src::W,
      goal::W;
      heuristic::Function=(u, v) ->  0.0,
      cost_adjustment::Function=(u, v, parents) -> 0.0,
      max_distance::T=typemax(T)
      ) where {T <: Real, U <: Integer, W <: Integer}

A* shortest path algorithm. Implemented with a min heap. Using a min heap is faster than using a priority queue given the sparse nature of OpenStreetMap data, i.e. vertices far outnumber edges.

There are two implementations:

• AStarVector is faster for small graphs and/or long paths. This is default. It pre-allocates vectors at the start of the algorithm to store distances, parents and visited nodes. This speeds up graph traversal at the cost of large memory usage.
• AStarDict is faster for large graphs and/or short paths. It dynamically allocates memory during traversal to store distances, parents and visited nodes. This is faster compared to AStarVector when the graph contains a large number of nodes and/or not much traversal is required.

Compared to jl, this version improves runtime, memory usage, has a flexible heuristic function, and accounts for OpenStreetMap turn restrictions through the cost_adjustment function.

Note: A heuristic that does not accurately estimate the remaining cost to goal (i.e. overestimating heuristic) will result in a non-optimal path (i.e. not the shortest), dijkstra on the other hand guarantees the optimal path as the heuristic cost is zero.

Arguments

• ::Type{<:AStar}: Implementation to use, either AStarVector (default) or AStarDict.
• g::AbstractGraph{U}: Graphs abstract graph object.
• weights::AbstractMatrix{T}: Edge weights matrix.
• src::W: Source vertex.
• goal::W: Goal vertex.
• heuristic::Function=h(u, v) = 0.0: Heuristic cost function, takes a source and target vertex, default is 0.
• cost_adjustment:::Function=r(u, v, parents) = 0.0: Optional cost adjustment function for use cases such as turn restrictions, takes a source and target vertex, defaults to 0.
• max_distance::T=typemax(T): Maximum weight to traverse the graph, returns nothing if this is reached.

Return

• Union{Nothing,Vector{U}}: Array veritces represeting shortest path from src to goal.

dijkstra([::Type{<:Dijkstra},]
        g::AbstractGraph{U},
        weights::AbstractMatrix{T},
        src::W,
        goal::W;
        cost_adjustment::Function=(u, v, parents) -> 0.0,
        max_distance::T=typemax(T)
        ) where {T <: Real, U <: Integer, W <: Integer}

Dijkstra's shortest path algorithm with an early exit condition, is the same as astar with heuristic cost as 0.

There are two implementations:

• DijkstraVector is faster for small graphs and/or long paths. This is default. It pre-allocates vectors at the start of the algorithm to store distances, parents and visited nodes. This speeds up graph traversal at the cost of large memory usage.
• DijkstraDict is faster for large graphs and/or short paths. It dynamically allocates memory during traversal to store distances, parents and visited nodes. This is faster compared to AStarVector when the graph contains a large number of nodes and/or not much traversal is required.

Arguments

• ::Type{<:Dijkstra}: Implementation to use, either DijkstraVector (default) or DijkstraDict.
• g::AbstractGraph{U}: Graphs abstract graph object.
• weights::AbstractMatrix{T}: Edge weights matrix.
• src::W: Source vertex.
• goal::W: Goal vertex.
• cost_adjustment:::Function=r(u, v, parents) = 0.0: Optional cost adjustment function for use cases such as turn restrictions, takes a source and target vertex, defaults to 0.
• max_distance::T=typemax(T): Maximum weight to traverse the graph, returns nothing if this is reached.

Return

• Union{Nothing,Vector{U}}: Array veritces represeting shortest path between src to goal.

dijkstra(g::AbstractGraph{U},
         weights::AbstractMatrix{T},
         src::W;
         cost_adjustment::Function=(u, v, parents) -> 0.0
         ) where {T <: Real, U <: Integer, W <: Integer}

Dijkstra's shortest path algorithm, implemented with a min heap. Using a min heap is faster than using a priority queue given the sparse nature of OpenStreetMap data, i.e. vertices far outnumber edges.

This dispatch returns full set of parents or the dijkstra state given a source vertex, i.e. without and early exit condition of goal.

Arguments

• g::AbstractGraph{U}: Graphs abstract graph object.
• weights::AbstractMatrix{T}: Edge weights matrix.
• src::W: Source vertex.
• cost_adjustment:::Function=r(u, v, parents) = 0.0: Optional cost adjustment function for use cases such as turn restrictions, takes a source and target vertex, defaults to 0.

Return

• Vector{U}: Array parent veritces from which the shortest path can be extracted.

shortest_path_from_dijkstra_state(g::OSMGraph, origin::Integer, destination::Integer)

Extract shortest path from precomputed dijkstra state, from origin to detination node id.

Note, function will raise UndefRefError: access to undefined reference if the dijkstra state of the origin node is not precomputed.

Arguments

• g::OSMGraph: Graph container.
• origin::Integer: Origin OpenStreetMap node or node id.
• destination::Integer: Destination OpenStreetMap node or node id.

Return

• Union{Nothing,Vector{T}}: Array of OpenStreetMap node ids making up the shortest path.

set_dijkstra_state!(g::OSMGraph, src::Union{Integer,Vecotr{<:Integer}, weights::AbstractMatrix; cost_adjustment::Function=(u, v, parents) -> 0.0)

Compute and set the dijkstra parent states for one or multiple src vertices. Threads are used for multiple srcs. Note, computing dijkstra states for all vertices is a O(V² + ElogV) operation, use on large graphs with caution.

restriction_cost_adjustment(g::OSMGraph)

Returns the cost adjustment function (user in dijkstra and astar) for restrictions. The return function takes 3 arguments, u being the current node, v being the neighbour node, parents being the array of parent dijkstra states. By default g.indexed_restrictions is used to check whether the path from u to v is restricted given all previous nodes in parents.

distance_heuristic(g::OSMGraph)

Returns the heuristic function used in astar shortest path calculation, should be used with a graph with weight_type=:distance. The heuristic function takes in 2 arguments, u being the current node and v being the neighbour node, and returns the haversine distance between them.

time_heuristic(g::OSMGraph)

Returns the heuristic function used in astar shortest path calculation, should be used with a graph with weight_type=:time or weight_type=:lane_efficiency. The heuristic function takes in 2 arguments, u being the current node and v being the neighbour node, and returns the estimated travel time between them. Calculated by dividing the harversine distance by a fixed maxspeed of 100. Remember to achieve an optimal path, it is important to pick an underestimating heuristic that best estimates the cost remaining to the goal, hence we pick the largest maxspeed across all ways.

weights_from_path(g::OSMGraph{U,T,W}, path::Vector{T}; weights=g.weights)::Vector{W} where {U <: DEFAULT_OSM_INDEX_TYPE,T <: DEFAULT_OSM_ID_TYPE,W <: Real}

Extracts edge weights from a path using the weight matrix stored in g.weights unless a different matrix is passed to the weights kwarg.

Arguments

• g::OSMGraph: Graph container.
• path::Vector{T}: Array of OpenStreetMap node ids.
• weights=g.weights: the matrix that the edge weights are extracted from. Defaults to g.weights.

Return

• Vector{W}: Array of edge weights, distances are in km, time is in hours.

total_path_weight(g::OSMGraph{U,T,W}, path::Vector{T}; weights=g.weights)::W where {U <: Integer,T <: DEFAULT_OSM_ID_TYPE,W <: Real}

Extract total edge weight along a path.

Arguments

• g::OSMGraph: Graph container.
• path::Vector{T}: Array of OpenStreetMap node ids.
• weights=g.weights: the matrix that the edge weights are extracted from. Defaults to g.weights.

Return

• sum::W: Total path edge weight, distances are in km, time is in hours.

path_from_parents(parents::P, goal::V) where {P <: Union{<:AbstractVector{<:U}, <:AbstractDict{<:U, <:U}}} where {U <: Integer, V <: Integer}

Extracts shortest path given dijkstra parents of a given source.

Arguments

• parents::Union{<:AbstractVector{<:U}, <:AbstractDict{<:U, <:U}}: Mapping of dijkstra parent states.
• goal::V: Goal vertex.

Return

• Union{Nothing,Vector{U}}: Array veritces represeting shortest path to goal.

path_from_parents(parents::P, goal::V, path_length::N) where {P <: Union{<:AbstractVector{<:U}, <:AbstractDict{<:U, <:U}}} where {U <: Integer, V <: Integer, N <: Integer}

Extracts shortest path given dijkstra parents of a given source, providing path_length allows preallocation of the array and avoids the need to reverse the path.

Arguments

• parents::Union{<:AbstractVector{<:U}, <:AbstractDict{<:U, <:U}}: Mapping of dijkstra parent states.
• goal::V: Goal vertex.
• path_kength::N: Known length of the return path, allows preallocation of final path array.

Return

• Union{Nothing,Vector{U}}: Array veritces represeting shortest path to goal.