README.md
[![SWH](https://archive.softwareheritage.org/badge/origin/https://github.com/o-reach/O-Reach/)](https://archive.softwareheritage.org/browse/origin/?origin_url=https://github.com/o-reach/O-Reach)
[![SWH](https://archive.softwareheritage.org/badge/swh:1:dir:f3b335103fbc2a0d161f573a2ffc64f4599a2a66/)](https://archive.softwareheritage.org/swh:1:dir:f3b335103fbc2a0d161f573a2ffc64f4599a2a66)
O'Reach
=====
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](https://doi.org/10.4230/LIPIcs.SEA.2021.13).
Further information as well as instances are available on our [paper website](https://oreach.taa.univie.ac.at/).
Installation Notes
=====
Before you can start you need to install the following software packages:
- [CMake](https://cmake.org/) (at least version 3.10)
- [Boost](https://www.boost.org/) (at least version 1.61)
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
```
External Projects
======
We use code from the following projects (shipped in extern/):
- [KaHIP v3.10](https://github.com/KaHIP/KaHIP/)
- [argtable3](https://github.com/argtable/argtable3)
- [MurmurHash3](https://github.com/aappleby/smhasher/blob/92cf3702fcfaadc84eb7bef59825a23e0cd84f56/src/MurmurHash3.cpp)
- [ska flat hashmap](https://github.com/skarupke/flat_hash_map/blob/2c4687431f978f02a3780e24b8b701d22aa32d9c/flat_hash_map.hpp)
License
=====
Our code is licensed under MIT license.
If you publish results using our algorithms, please acknowledge our work by
citing the [corresponding paper](https://doi.org/10.4230/LIPIcs.SEA.2021.13):
```
@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},
}
```
Project Contributors (sorted by last name)
=====
- Kathrin Hanauer
- Christian Schulz
- Jonathan Trummer