cppRouting

Vincent Larmet

2019-09-25

Package presentation

cppRouting is an R package which provide functions to calculate distances, shortest paths and isochrones/isodistances on non-negative weighted graphs. For now, cppRouting can implement :

All these functions are written in C++ and use std::priority_queue container from the Standard Template Library.
This package have been made with Rcpp and parallel packages.

Main functions

cppRouting package provide these functions :

Path algorithms

The choice between all the algorithms is available for one-to-one calculation like get_distance_pair and get_path_pair.
In these functions, uni-directional Dijkstra algorithm is stopped when the destination node is reached.
A* and NBA* are relevant if geographic coordinates of all nodes are provided. Note that coordinates should be expressed in a projection system.
To be accurate and efficient, A* and NBA* algorithms should use an admissible heuristic function (here the Euclidean distance), e.g cost and heuristic function must be expressed in the same unit.
In cppRouting, heuristic function h for a node (n) is defined such that :
h(n,d) = ED(n,d) / k with h the heuristic, ED the Euclidean distance, d the destination node and a constant k.

So in the case where coordinates are expressed in meters and cost is expressed in time, k is the maximum speed allowed on the road. By default, constant is 1 and is designed for graphs with cost expressed in the same unit than coordinates (for example in meters).

If coordinates cannot be provided, bi-directional Dijkstra algorithm can offer a good alternative to A* in terms of performance.

New algorithms cppRouting will provide in the future

Examples and applications using cppRouting

see : https://github.com/vlarmet/cppRouting/blob/master/README.md