Home

Awesome

Multi-CH-Constructor

A multi-threaded multi-criteria contraction hierarchy graph creator. The general approach follows this paper. But a few improvements have been made to ensure that less shortcuts are generated. Less shortcuts lead to faster contraction time and higher speed-up of Dijkstra runs.

Build

To Build Multi-CH-Constructor first clone it and change into its directory:

git clone --recursive https://github.com/lesstat/multi-ch-constructor
cd multi-ch-constructor

Initialize submodules

git submodule update --init --recursive

Then create a build directory for cmake and run cmake and make.

cmake -Bbuild -D GRAPH_DIM=4 # only 'cmake -Bbuild' for default graph-dim
cmake --build build

Usage

The main executable of Multi-CH-Constructor is multi-ch. It has the following CLI options:

$ ./build/multi-ch -h
  -h [ --help ]               Prints help message

loading options:
  -t [ --text ] arg           Load graph from text file
  -m [ --multi ] arg          Load graph from multiple files

contraction options:
  -p [ --percent ] arg (=98)  How far the graph should be contracted
  --stats                     Print statistics while contracting
  --threads arg               Maximal number of threads used

saving:
  -w [ --write ] arg          File to save graph to

It needs exactly one parameter of the loading category to load a graph. The text format is described in detail here. The Dimension of the graph must match the DIMENSION constant in the graph.hpp file. The application must be recompiled to contract graphs of other dimensions.

The -p option specifies how much of the graph will be contracted. This option can and should be given as decimal value aka -p 99.85.

The --stats options prints per thread per round information of the contraction.

With the --threads option the number of threads is specified. If left out the number of threads is determined by std::thread::hardware_concurrency()

-w specifies where to save the graph. The format is the same as the text format.

Shortcut Reducing Improvements