cppRouting

Vincent Larmet

2019-06-21

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 :

The choice between all the algorithms is available for 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 is defined such that : h(xi,yi,xdestination,ydestination)/k, with 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 (e.g 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