[request for feature] hierarchical contraction
In this Issue we discuss the implementation of hierarchical contraction.
Motivation
As per Wikipedia "the method of contraction hierarchies is a technique to speed up shortest-path routing by first creating precomputed "contracted" versions of the connection graph."
Overview
More precisely, as per Robert Geisberger "[...] the nodes of a weighted directed graph G = (V, E) are ordered by “importance” given a total node order <. Let u < v, then the node v is more important than u. We now construct a hierarchy by contracting the nodes in this order. A node u is contracted by removing it from the network in such a way that shortest paths in the remaining overlay graph are preserved. This property is achieved by replacing paths of the form ⟨hv, u, wi⟩ by a shortcut edge ⟨hv, wi⟩. Note that the shortcut ⟨hv, wi⟩ is only required if ⟨hv, u, wi⟩ is the only shortest path from v to w. We shall view the contraction process as a way to add all discovered shortcuts to the edge set E. We obtain a contraction hierarchy (CH)."
Existing implementations
(1) Graphhopper (JAVA) [https://github.com/graphhopper/graphhopper]
(2) OSMR (CPP) [https://github.com/Project-OSRM/osrm-backend]
Bibliography (extracted from wikipedia)
(1) Robert Geisberger [http://algo2.iti.kit.edu/schultes/hwy/contract.pdf]
(2) Rice and Tsotras [http://www.vldb.org/pvldb/vol4/p69-rice.pdf]
(3) Prof. Dr. Hannah Bast's lectures https://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012