Contraction hierarchies
Also known as: Contraction hierarchies · CH · node contraction · shortcuts · witness search
How a navigator answers in fractions of a millisecond: once, in advance, it “contracts” crossroads from unimportant to important, replacing paths through them with shortcuts, and then finds a path with two waves that only climb up the tiers. On the streets of Almaty such a search looks at 119 crossroads instead of Dijkstra's 4263 and answers just as exactly.
To lay out a random route across Almaty, Dijkstra looks at 4263 crossroads of 7909 on average. A navigator with the roads of a whole continent at hand cannot afford that: millions of crossroads per query. So real navigators process the graph once, in advance, and then answer in fractions of a millisecond. Below, one such processing, a contraction hierarchy, is built right in your browser on the real streets of Almaty. Crossroads disappear one at a time, the least important first, and paths through them are replaced by shortcuts. Move the slider: towards the end only a skeleton of main streets is left of the city. Then switch to “Query” and choose A and B, and “Tiers” shows how the search climbs the hierarchy.
In “Tiers” each crossroads is raised to the height of its tier: the later it was contracted, the higher. The waves from A and from B go only up, towards more important crossroads, and meet at the top. Neither descends into the neighbourhoods: the way through the neighbourhoods near the finish is hidden in shortcuts, and the shortcuts are unfolded back into streets when the answer is given.
The idea
Order the crossroads by importance and throw them out of the graph one at a time, from unimportant to important. Throwing out a crossroads v, look at each pair of its neighbours u and w: if the shortest path between them went through v, add a shortcut between u and w, an edge with the length of u–v–w. The distances between the remaining crossroads do not change. When everything has been thrown out, the graph with shortcuts has, between any two points, a shortest path that first only climbs to more important crossroads and then only descends. So a query is two Dijkstra waves going up, from the start and from the finish.
“Importance” here has nothing to do with the size of a street. The algorithm knows nothing about avenues; it looks only at the graph and counts: if this crossroads is contracted now, how many shortcuts must be added? A crossroads in a dead end can be thrown out for free, one in the middle of a straight street for one shortcut, and a node that paths go through in all directions only at the cost of many shortcuts. Those are the ones that stay on the upper tiers. The algorithm finds the main roads by itself, from how the shortest paths are laid out.
Contraction step by step
Take 21 crossroads of the central grid around the corner of Shevchenko and Tchaikovsky and contract them with the same algorithm that builds the hierarchy for the whole city. For each pair of neighbours of the crossroads being contracted, a witness is sought, a detour no longer than the path through the crossroads. If one is found, no shortcut is needed. If not, a shortcut is added.
A witness often turns out to be just the neighbouring block: from E to J you can drive through F in 334 m, or round through I in 333 m, and no shortcut is needed. In a grid of blocks there is almost always a second path of the same length, and contraction manages without shortcuts. Shortcuts are needed where there is no way round: at the edge of the grid, in dead ends, on long streets without crossings.
The order is chosen on the fly. Each crossroads has a priority: how many shortcuts its contraction would give minus how many edges would leave with it, the edge difference, plus how many of its neighbours have already been contracted. The second term prevents contracting crossroads of one area in a row: the hierarchy comes out more even when contractions are scattered over the whole graph. The priorities are kept in a heap, but recomputing them for everyone after each contraction is too expensive. So the recomputation is lazy: take the crossroads with the smallest priority from the heap, recompute it, and if it is still no greater than the next in the heap, contract it, and if it has grown, put it back. The scene shows such returns too.
The witness search is an ordinary Dijkstra from the neighbour u in the graph without v, but with two limits. It stops when the distance exceeds the length of the path through v: there will be no witness beyond that. And it gives up after looking at 50 crossroads. If because of this limit no witness was found, a superfluous shortcut is added. A superfluous shortcut breaks nothing, as it is an edge with the length of a real path; it only makes the graph slightly heavier. A missing shortcut would break everything, so mistakes are allowed only in this direction.
The order decides everything
Contraction can be done in any order: the hierarchy will be correct with any. But its size depends on the order very strongly. Below, a piece of the city around Republic Square is contracted three ways: by edge difference, as above; by the number of streets at a crossroads at the start; and in random order. The colour of a shortcut is the tier of the crossroads it bypasses.
A random order on a two-kilometre piece gives four times as many shortcuts and almost four times as many tiers, and a query looks at two and a half times as many crossroads. As the piece grows, the gap grows: switch to three kilometres. The reason is clear: if a crossroads that paths go through in all directions is contracted early, its neighbours have to be joined pairwise by shortcuts. They become even more tightly connected, and contracting any of them needs even more shortcuts. A good order postpones such nodes to the very top, where they are few and no longer in anyone's way.
Why the answer is exact
Let G* be the original graph together with all shortcuts, and let the rank be a crossroads' number in the contraction order: the later it was contracted, the higher the rank. Three statements are needed: contraction does not change distances, G* has an “up, then down” shortest path, and the query finds it.
Contracting one vertex v does not change the distances between the remaining vertices.
A shortcut is an edge with the length of a real path u–v–w, so distances do not get shorter. Nor longer: take a shortest path between remaining vertices that went through v. All lengths are positive, so v occurs on it once, and the path enters it from a neighbour u and leaves to a neighbour w. The piece u–v–w is a shortest path between u and w, and the contraction checked the pair (u, w): it either added a shortcut of the same length or found a witness, a path without v that is no longer. Replace the piece with the shortcut or the witness, and you get a path of the same length without v.
For any connected vertices s and t, G* has a shortest path whose vertex ranks first only increase and then only decrease.
Call a valley an inner vertex of a path whose rank is smaller than the ranks of both its neighbours on the path. A path without valleys is exactly “up, then down”: it has no vertex where the ranks turn from going down to going up.
Let a shortest path P contain a valley v with neighbours u and w. The edges (u, v) and (v, w) are in G*, and both appeared no later than the contraction of v: shortcuts are added only between vertices not yet contracted, and after its contraction v gets no new edges. When v was contracted, u and w were still in the graph, as their ranks are higher. So the pair (u, w) was checked: the graph then had either a shortcut u–w of the same length as u–v–w or a witness no longer. Both lie in G*, and all their inner vertices had not yet been contracted, that is, their ranks are higher than the rank of v. Replace u–v–w with the shortcut or the witness: the path stays shortest.
It remains to make sure the replacements end. Give a vertex of rank r the weight (n + 1)−r, where n is the number of vertices, and call the weight of a path the sum of the weights of its inner vertices. A replacement removes a vertex of weight (n + 1)−r and adds at most n − 1 vertices, each of weight at most (n + 1)−r−1, less than what was removed in total. The weight of the path strictly decreases. There are finitely many shortest paths (they are simple, as lengths are positive), so the replacements end, on a path without valleys.
The query, two Dijkstras along upward edges from s and from t, where a wave ends when its smallest key is no less than the best path found so far, best, and best is updated when a wave takes a vertex with a label of the other wave, finds δ(s, t).
best is always the length of a real path, so best ≥ δ(s, t). Take the “up, then down” shortest path from the theorem, its top vertex x, the length of the climb from s to x, a, and from t to x, b; a + b = δ(s, t). Dijkstra from s along upward edges finds a path to x no longer than a, but no shorter either: otherwise, together with the climb from t, it would give a path shorter than δ. So x is taken by the wave from s with key exactly a, and likewise by the wave from t with key b.
Suppose that at the end best > δ. Then the wave from s ended when its smallest key became no less than best > δ ≥ a, and Dijkstra takes vertices in order of keys, so by then x had been taken. Likewise for the wave from t. When the second of the waves took x, x already had a label of the first, and best became at most a + b = δ. A contradiction.
Note the stopping rule: each wave ends by itself when its key has grown to best. The rule of bidirectional Dijkstra, stopping when the sum of the two smallest keys reaches best, will not do here. Its proof relied on a wave having looked at everything within its radius. An upward wave does not do that: it may use only upward edges, and a vertex two steps from the start may be arbitrarily far for it or not reachable at all. The listing below checks this on the same 40 routes: with that rule the query would answer wrongly 19 times out of 40.
Code
Precomputation and query on the whole city. The remaining graph is kept as dictionaries “neighbour → length”, so that shortcuts are added and edges removed in O(1). For each crossroads the edges to neighbours that remained in the graph at the moment of its contraction are recorded: these are the upward edges. A shortcut records the crossroads it bypasses, and from these records the function unpack recursively unfolds a shortcut into streets.
hierarchy: 12545 shortcuts, 22934 upward edges, 50 levels Republic Square -> Green Bazaar: 3786 m (Dijkstra: 3786 m) settled: Dijkstra 1422, hierarchy 114 route: 7 edges of the hierarchy, 4 of them shortcuts, 39 street pieces 40 random routes, all distances equal: Dijkstra settles 4263 on average, the hierarchy 119 the stop of bidirectional Dijkstra would answer wrongly on 19 of 40
The route from Republic Square to the Green Bazaar is just 7 edges in the hierarchy, 4 of them shortcuts, and they unfold into 39 real pieces of street. Streets are treated as two-way, as in all of the catalogue's articles on the streets of Almaty. With one-way streets two graphs of upward edges are needed: the wave from the start goes along upward edges in their direction, and the wave from the finish along edges leading into it from above, backwards, as in bidirectional search.
What it costs
Contraction hierarchies have no worst-case guarantees: in the worst case a query is the same Dijkstra, only on a graph with shortcuts, and there may turn out to be many shortcuts. Their good performance on roads has been established by experiment, so only measurements can honestly speak about speed.
Precomputation. For Almaty: 12,545 shortcuts on top of 10,389 streets, so the graph slightly more than doubles, and 50 tiers. The hierarchy is built in a fraction of a second: in the browser the scene above shows the time on your machine, and in Python the listing takes about 0.7 s. In the 2008 paper the creators of the method built a hierarchy for a road graph of 18 million crossroads and 42 million directed segments, and their main variant took about ten minutes of precomputation: 545 s to choose the order and 57 s for the contraction itself.
Query. Let us compare all the methods from the neighbouring articles on the same 40 random routes. The numbers are averages over the routes, from those articles' listings.
| Method | Crossroads looked at | Precomputation |
|---|---|---|
| Dijkstra | 4263 | none |
| two Dijkstra waves | 2614 | none |
| A* with the straight-line hint | 1009 | none |
| contraction hierarchy | 119 | 12,545 shortcuts |
36 times fewer than Dijkstra and 8.5 times fewer than A*. But the main thing shows on the chart: the query time barely grows with distance. Dijkstra, as befits a wave on a plane, grows as the square of the distance, while the hierarchy levels off after four or five kilometres: long routes climb to the upper tiers anyway, and there are few of them.
At eight kilometres the hierarchy is 17 times faster than Dijkstra in Python and 15 times in Go, and on half-kilometre routes the gain in Python disappears: Dijkstra has little work there too. On large graphs the difference is enormous. On the same graph of 18 million crossroads a hierarchy query in the 2008 paper looked at 459 vertices on average and took 0.22 ms. Dijkstra to a random finish looks at half the graph on average, millions of vertices.
Why roads have so few shortcuts was explained in 2010 by Ittai Abraham, Amos Fiat, Andrew Goldberg and Renato Werneck. They introduced highway dimension: how few crossroads are enough to “intercept” all long shortest paths in a neighbourhood. They proved that with a small highway dimension there is a contraction order for which queries look at few vertices. That real roads have a small highway dimension is supported by experiments, not by a proof.
Where the hierarchy does not help
- Weights change. A hierarchy is built for particular lengths. A traffic jam on an avenue invalidates the shortcuts that bypass it or run along it, and rebuilding everything takes long. That is why the OSRM router recommends another method, multi-level Dijkstra, for data that are updated often, traffic for example, and keeps contraction hierarchies for cases where query speed matters most. There is also a variant of the hierarchies themselves: in 2014–2016 Julian Dibbelt, Ben Strasser and Dorothea Wagner split the precomputation into a long part that depends only on the layout of the roads and a short one that recomputes the lengths, customizable contraction hierarchies (CCH).
- Networks without a hierarchy. In a road network most crossroads have detours, and contraction gets off lightly. In “small-world” networks where everything is connected to everything through hub nodes, like the air network from the article on bidirectional search, contraction quickly produces a dense core of shortcuts, precomputation takes tens of times longer, and the query gain melts away. Other techniques work better there.
- Turns and time. A ban on a left turn or its cost is a property of a pair of streets, not of a crossroads, and for them the graph is rebuilt so that street segments become the vertices. Travel time that depends on the hour is a big separate story: there are time-dependent hierarchies for it, where a shortcut keeps a function of time rather than a number.
The query can be sped up further. An upward wave sometimes takes a vertex along a path that is clearly not shortest: an edge from above leads into it from a vertex already taken, and it is shorter through that edge. Such a vertex can be “stalled”, that is, the search does not continue from it, and the answer is not spoiled. The technique is called stall-on-demand and was in the hierarchies from the very beginning.
Where it is used
- OSRM, the open router on OpenStreetMap data. The command
osrm-contractbuilds a contraction hierarchy. The documentation recommends it where query speed matters most, especially for large distance tables, and multi-level Dijkstra for live traffic and by default. - GraphHopper, another open router. Its documentation calls the speed mode, that is, contraction hierarchies, the fastest of three; the hybrid mode is A* with landmarks from the article on A*, slower but more flexible.
- As the basis of other methods. A hierarchy sets an order of “importance”, and customizable hierarchies rest on it, as do “many-to-many” distance tables needed in logistics: dispatching hundreds of couriers to thousands of addresses.
History
By the mid-2000s route researchers had learned to answer queries on the roads of a continent in milliseconds, but at the cost of complex multi-level constructions. Peter Sanders and Dominik Schultes proposed highway hierarchies in 2005, road levels found from the graph itself, and a year later, at the DIMACS challenge on shortest paths, such methods showed how far one could get from Dijkstra.
In 2008 Robert Geisberger, in a diploma thesis supervised by Sanders and Schultes, took the idea to the limit of simplicity: no levels, just an order of crossroads, one contraction per step. The same year saw the paper by Geisberger, Sanders, Schultes and Daniel Delling, “Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks”, and “faster and simpler” is no exaggeration: the query itself is bidirectional Dijkstra with one condition on edges. Its simplicity made the method the basis for a dozen more: mobile hierarchies for weak devices, time-dependent ones, customizable ones.
Problems
In the problem the hierarchy has already been built, on the streets of Almaty by the same precomputation as in the listing, and you have to answer thousands of queries. The main trap is the stopping rule: what is right for two Dijkstra waves answers wrongly here.
Queries over the tiersData: Almaty roads © OpenStreetMap contributors, ODbL