Welcome

This is a supplementary website to our paper O’Reach: Even Faster Reachability in Large Graphs and provides the source code as well as all instances. Please cite our work if you use materials provided here.

Abstract

One of the most fundamental problems in computer science is the reachability problem: Given a directed graph and two vertices s and t, can s reach t via a path? We revisit existing techniques and combine them with new approaches to support a large portion of reachability queries in constant time using a linear-sized reachability index. Our new algorithm O’Reach can be easily combined with previously developed solutions for the problem or run standalone.

In a detailed experimental study, we compare a variety of algorithms with respect to their index- building and query times as well as their memory footprint on a diverse set of instances. Our experiments indicate that the query performance often depends strongly not only on the type of graph, but also on the result, i.e., reachable or unreachable. Furthermore, we show that previous algorithms are significantly sped up when combined with our new approach in almost all scenarios. Surprisingly, due to cache effects, a higher investment in space doesn’t necessarily pay off: Reachability queries can often be answered even faster than single memory accesses in a precomputed full reachability matrix.

Software

We implemented all algorithms in C++. The source code as well as instructions on how to build and run are publicly available on Github (MIT license).

Instances

We used the following seven collections of acyclic instances for our experiments. Each instance comes with four query files, containing random, only positive (“true”), only negative (“false”), and 50:50 positive and negative queries (“mixed”).

Kronecker

Generated with the RMAT generator for the Graph500 benchmark in different sizes. Instance kron_logni has 2ⁱ vertices. Edges were oriented according to vertex ID from smaller to larger.

Random

Generated according to the Erdős-Renyí model G(n, m). Instance randni-j has 2ⁱ vertices and 2^j edges. Edges were oriented according to vertex ID from smaller to larger.

Delaunay

Delaunay instances adapted from the 10th DIMACS Implementation Challenge. delaunay_ni: Delaunay triangulation of 2ⁱ random points in the unit square.

Large Real

Different kinds of networks, adapted from the GRAIL Code Repository.

Small Real Dense

Different kinds of networks, adapted from the GRAIL Code Repository.

Small Real Sparse

Different kinds of networks, adapted from the GRAIL Code Repository.

SNAP

Different kinds of networks, adapted from the Stanford Large Network Dataset Collection.

License and Bibliography

Our implementation of the algorithms is available under the MIT license.

If you publish results using our algorithms, instances, or implementation, please acknowledge our work by citing our paper as follows:

@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},
}

For the full version:

@article{hst-oreachfull-2021,
  author        = {Hanauer, Kathrin and Schulz, Christian and Trummer, Jonathan},
  title         = {O'Reach: Even Faster Reachability in Large Graphs},
  journal       = {CoRR},
  volume        = {abs/2008.10932},
  year          = {2021},
  url           = {https://arxiv.org/abs/2008.10932},
  archivePrefix = {arXiv},
  eprint        = {2008.10932},
  primaryClass  = {cs.DS},
}