O'Reach is a fast, deterministic algorithm for answering reachability queries in a directed graph, i.e., it spends some time to preprocess a given directed (acyclic) graph and then quickly answers for arbitrary pairs of vertices s and t whether the graph has a directed path from s to t.
O'Reach can either be run standalone or use another algorithm as fallback in case that it cannot answer a reachability query in constant time.
This repository contains the source code accompanying our paper O'Reach: Even Faster Reachability in Large Graphs. Further information as well as instances are available on our paper website.
Before you can start you need to install the following software packages:
Both are also available as packages on many Linux distributions, e.g.:
- Debian/Ubuntu:
apt install cmake libboost-dev - Fedora:
dnf install cmake boost
Afterwards, in the main project directory, type ./compile_withcmake.sh. Once
you did that you can try to run the following command:
./build/reachability ./examples/arXiv.metis
We use code from the following projects (shipped in extern/):
Our code is licensed under MIT license. If you publish results using our algorithms, please acknowledge our work by citing the corresponding paper:
@inproceedings{hst-oreach-2021,
author = {Hanauer, Kathrin and Schulz, Christian and Trummer, Jonathan},
editor = {Coudert, David and Natale, Emanuele},
title = {O'Reach: Even Faster Reachability in Large Graphs},
booktitle = {19th International Symposium on Experimental Algorithms, {SEA} 2021,
June 7-9, 2021, Valrose, France},
series = {LIPIcs},
volume = {190},
pages = {13:1--13:24},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.SEA.2021.13},
doi = {10.4230/LIPIcs.SEA.2021.13},
}
- Kathrin Hanauer
- Christian Schulz
- Jonathan Trummer