Development of Contraction Hierarchy algorithm for shortest path computation

oslandia · September 27, 2024, 8:21am

I forward the issue we posted on GitHub a few months ago

Support for contraction hierarchies

opened 03:05PM - 28 Jul 23 UTC

Functionality Request

Hello the pgRouting team, I recently worked with pgRouting on a graph that co…ntained around 31 millions of edges and got nice results in terms of computation time (a few seconds). You're doing a really nice job for those who want to compute routes in a database context! Anyway, in a lot of routing situations, we want to get results in less than one second, and I was wondering if some optimization could be possible for pgRouting. ## TL;DR I read on the [GsoC 2022 program](https://github.com/pgRouting/pgrouting/wiki/GSoC-Ideas%3A-2022#details-of-idea-14) that implementing Contraction Hierarchies is still a valid idea. Hence comes my question: are you interested in a contribution on that topic? Do you still consider the Contraction Hierarchies algorithm has an added value for pgRouting? ## Contraction in pgRouting Knowing that Contraction Hierarchies are a game changer for fast routing purpose, I was wondering if they were implemented in pgRouting. Then I read the [pgRouting documentation](https://docs.pgrouting.org/latest/en/contraction-family.html), digged into the [pgRouting mailing list archive](https://lists.osgeo.org/pipermail/pgrouting-dev/2015-December/001607.html) and read #440 (which confuses me a bit). By cross-referencing information from the [GsoC 2016 contraction report](https://github.com/pgRouting/pgrouting/wiki/GSoC-2016-Contraction), I understand that the implemented features are dead end and linear contractions, and that Contraction Hierarchies are not implemented. Is it correct? Another confusing point for me is that there are [CH vertices](https://github.com/pgRouting/pgrouting/blob/main/include/cpp_common/ch_vertex.h), [CH edges](https://github.com/pgRouting/pgrouting/blob/main/include/cpp_common/ch_edge.h) and [CH graphs](https://github.com/pgRouting/pgrouting/blob/main/include/contraction/ch_graphs.hpp) in the pgRouting API: in this context I hypothesize that "CH" means "Contraction Hierarchies", but I may be wrong? ## Improvement As far as I understand the different contraction algorithms, there is a seminal difference between the pgRouting contractions and the Contraction Hierarchies. While the formers act on the graph topology, the latter considers the edge weights and evaluates every vertex in the graph in order to build a node ordering (the higher the node is in the hierarchy, the less likely its contraction is). Of course, it means that the contracted graph is valid as long as the weights are static. In order to implement Contraction Hierarchies, one should first implement this node ordering procedure, whose outputs are a set of shortcuts (as in other contraction algorithms) and a rank in the hierarchy for each vertex (this is the big difference). This preprocessing could be another contraction referenced in [include/contraction/pgr_contract.hpp](https://github.com/pgRouting/pgrouting/blob/main/include/contraction/pgr_contract.hpp). Then comes the routing query itself, that has to be run in the ordered graph (with shortcuts). This query algorithm is closed to a bidirectional Dijkstra, but highly depends on the vertex ordering. I do not know where could be the best place for such a querying algorithm; could a brand new `chquery` subfolder do the job? ## External resources The Contraction Hierarchies is mainly described by the following papers: - [Geisberger, 2008](http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf) - [Geisberger et al., 2008](http://algo2.iti.kit.edu/schultes/hwy/contract.pdf) - [Geisberger et al., 2012](https://publikationen.bibliothek.kit.edu/1000028701) As a side note, there is a [Github repo](https://github.com/RoutingKit/RoutingKit) handled by the research team, with (amongst other things) a [C++ implementation of Contraction Hierarchies](https://github.com/RoutingKit/RoutingKit/blob/master/src/contraction_hierarchy.cpp). Considering this could help to design a proof of concept within the pgRouting API.