Is there an open source implementation of shortest path algorithm with distance labeling a la Gavoille et al.?

Question

If you are allowed to precompute linear in |V| amount of data on graph then there are a family of algorithms which have sublinear query times for shortest paths in a graph.

1. Gavoille et al. Distance labeling in graphs.
2. Cohen et al. Reachability and distance queries via 2-hop labels
3. Abraham, Goldberg et al. Hierarchical Hub Labellings for Shortest Paths

Some of them are used in Bing Maps for extremely fast shortest routes calculations.

The basic idea is to precompute for each vertex forward labels L_f(v) and backward labels L_b(v) which poses a cover property. Each label is a pair of a vertex and the distance to it, e.g. L_f(v) = { (u, dist(v, u)) } and L_r(v) = { (u, dist(u, v)) }. And the cover property asserts that for any vertices s and t L_f(s) 'Union' L_r(t) contains at least one vertex on the shortest path from s to t.

Is there an open source implementation of one of those algorithms (C++, C#, F#, D, Go, Java)?

Answer 1

I have not found any code that implements those algorithms but you could look at the Karlsruhe homepage where you can find code for Contraction Hierarchies, which form the basis of the (original) Hub Labeling. You could use that to create your own implementation of HL but you should know they filed a patent for it.