Efficient Customizable Contraction Hierarchies for shortest path queries in directed graphs

This repository contains a compact, modular C++ library for Customizable Contraction Hierarchies (CCH), inspired by and complementing the original authors' publication and RoutingKit. Designed for flexibility, it allows for the seamless integration of any query algorithm or priority queue, making it highly adaptable for shortest path computation in a variety of settings. It's suited for use in large-scale road networks, accounting for turn costs and restrictions, and can also accommodate different graph structures such as graph databases. The library includes efficient implementations of priority queues, query algorithms, and graph data structures. For comprehensive details on Customizable Contraction Hierarchies, please refer to the original publication or RoutingKit.

Project Structure

.
├── external                                                      # External libraries      
├── LICENSE
├── optimizedkit
│   ├── CMakeLists.txt
│   ├── include                                                   # Header files                 
│   │   ├── customizable_contraction_hierarchy        
│   │   ├── graph
│   │   ├── graph_order_algorithms
│   │   ├── map
│   │   ├── path_finding_algorithms
│   │   ├── priority_queues
│   │   └── utils
│   ├── src                                                       # Source files             
│   │   ├── customizable_contraction_hierarchy
│   │   ├── graph
│   │   ├── graph_order_algorithms
│   │   ├── map
│   │   ├── path_finding_algorithms
│   │   ├── priority_queues
│   │   └── utils
│   └── tests                                                     # Test files               
└── README.md

Dependencies

The library depends on the following libraries for testing purposes only, that should be cloned into the external folder automatically:

Development Guide

Prerequisites

Install CMake (version 3.14 or higher) and a C++ compiler on your system.

Clone the repository:

git clone https://github.com/OliverKlukas/customizable-contraction-hierarchies.git
cd customizable-contraction-hierarchies/optimizedkit

Build instructions

Create a build directory and navigate into it:

cd customizable-contraction-hierarchies/optimizedkit
mkdir build
cd build

Build with -DCMAKE_BUILD_TYPE=Debug or -DCMAKE_BUILD_TYPE=Release depending on environment:
1. Build library with all tests & examples:
```
cmake -DCMAKE_BUILD_TYPE=Release .. && cmake --build .
```
2. Build library with all tests:
```
cmake -DCMAKE_BUILD_TYPE=Release .. && cmake --build .
```
3. Build library with only RoutingKit independent tests:
```
cmake -DCMAKE_BUILD_TYPE=Release -DTEST_AGAINST_ROUTING_KIT=OFF .. && cmake --build .
```

Test instructions

After having followed the build instructions, test the code via:
```
cd build
./tests/all_unit_tests
```

License

This project is licensed under the BSD 2-Clause License. Parts of the code that are directly derived from external libraries are marked accordingly.