Version 2008/06/24 Revision 447

Please contact me ([email protected]) if you are using the source code as I am very interested in the possible applications that arise from using it.

This program allows to create and test contraction hierarchies (CH), a hierarchical, shortcut-based speedup technique for fast and simple routing in road networks. The code was created as part of a diploma thesis at Universitaet Karlsruhe (TH), Institute for Algorithmics II.

Papers: - R. Geisberger, P. Sanders, D. Schultes, D. Delling. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In 7th International Workshop on Efficient and Experimental Algorithms (WEA), 2008.

• STL
• Boost IO-streams & regular expressions (only for input/output)

git submodule init
git submodule update
./make-release.txt
./run-node-order.sh docu/example.ddsg
./run-contraction.sh docu/example.ddsg

To clean the temporary generated files:

./clean.sh docu/example.ddsg

You can create a development project in Xcode:

mkdir build
cd build
cmake -G Xcode ..
cd ..
open contraction-hierarchies.xcodeproj

In docs/index.html, there are some examples what command-line arguments can be used to create a CH and perform tests.

Robert Geisberger ([email protected])

In the subfolder many/ is a test program for fast many-to-many distance table computations. However, the source code and the command-line arguments are well not documented well. It is an implementation of the algorithm desribed in the paper

S. Knopp, P. Sanders, D. Schultes, F. Schulz, and D. Wagner. Computing many-to-many shortest paths using highway hierarchies. In Workshop on Algorithm Engineering and Experiments (ALENEX), 2007.

but using contraction hierarchies.