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

• Duplicate shortcuts (source target and cost vector) are delete after every contraction round.

• Augmented LP:

  The original paper proposes the following LP for finding a configuration the certifies the need for a shortcut. When checking path p~, for all paths p found form s to t which are not p~ introduce a constraint:

  alpha^T * (c(p) - c(p~)) <= 0
  

  This does not work when alpha^T * c(p) == alpha^T * c(p~). Therefore the following LP is used

  max delta
  alpha^T * (c(p) - c(p~)) + delta  <= 0
  

• More than one path with minimal cost:

  When delta = 0 after the LP runs and more than one path has the same cost as the shortcut a heuristic search is done to find if one of the paths has no node that is contracted in this route inside. If one such path is found, it certifies that no shortcut is needed.