Main functions
cppRouting package provide these functions :
get_distance_matrix: compute distance matrix (between all combinations origin-destination nodes - one-to-many),
get_distance_pair: compute distances between origin and destination by pair (one-to-one),
get_path_pair: compute shortest paths between origin and destination by pair (one-to-one),
get_multi_paths: compute shortest paths between all origin nodes and all destination nodes (one-to-many),
get_isochrone: compute isochrones/isodistances with one or multiple breaks.
get_detour: return nodes that are reachable within a fixed additional cost around shortest paths. This function can be useful in producing accessibility indicators.
cpp_simplify: remove non-intersection nodes, duplicated edges and isolated loops in the graph. Graph topology is preserved so distance calculation is faster and remains true. This function can be applied to very large graphs (several millions of nodes).
cpp_contract: contract the graph by applying contraction hierarchies algorithm.
Path algorithms
Path algorithms proposed by the package are :
- 1 uni-directional Dijkstra algorithm,
- 2 bi-directional Dijkstra algorithm,
- 3 uni-directional A* algorithm
- 4 New bi-directional A* algorithm (Piljs & Post, 2009 : see http://repub.eur.nl/pub/16100/ei2009-10.pdf)
- 5 one-to-one bi-directional Dijkstra adapted to contraction hierarchies (Geisberger & al., 2008)
- 6 many-to-many bi-directional Dijkstra adapted to contraction hierarchies (Geisberger & al., 2008)
- 7 PHAST algorithm (Hardware-accelerated shortest path trees), one-to-all algorithm adapted to contraction hierarchies (Delling & al., 2011)
1, 2, 3 and 4 are available for one-to-one calculation in get_distance_pair and get_path_pair functions on a non-contracted graph. 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), i.e 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 is the best option in terms of performance.
5 is used for one-to-one calculation in get_distance_pair and get_path_pair functions on a contracted graph.
1 is used for one-to-many calculation in get_distance_matrix function on a non-contracted graph.
6 and 7 are available for one-to-many calculation in get_distance_matrix function on a contracted graph.