Author: Patrick Steil

This repository implements a hub labeling algorithm for reachability queries on directed acyclic graphs (DAGs). It does not compute or store shortest path distances.

I wrote a small paper describing the new parallelism approach, see ArXiv. Please cite my work when using the code:

@misc{steil2025parallelplldags,
      title={Parallel PLL on DAGs}, 
      author={Patrick Steil},
      year={2025},
      eprint={2507.21204},
      archivePrefix={arXiv},
      primaryClass={cs.DS},
      url={https://arxiv.org/abs/2507.21204}, 
}

To build the project, run the provided build.sh script:

./build.sh

Alternatively, to build only the release version:

mkdir -p build-release
cd build-release
cmake -DCMAKE_BUILD_TYPE=Release ..
make

The project supports three build configurations:

• Release: Optimized for performance.
• Debug: Includes debug symbols and error checks.
• Sanitize: Uses sanitizers for runtime error detection.

To build and run the release version:

cd build-release
cmake -DCMAKE_BUILD_TYPE=Release ..
make
./DAGHL -h

The output file contains hub labels for all vertices in the graph. Each vertex has exactly two lines:

• o line – outgoing hubs (forward labels).
• i line – incoming hubs (backward labels).

1. First line contains V followed by the number of vertices.
2. Outgoing Hubs (o line)
   • Starts with o.
   • Followed by the vertex ID.
   • Followed by hubs reachable in the forward direction.
   • Example: o 0 1 3 → Vertex 0 has outgoing hubs 1 and 3.
3. Incoming Hubs (i line)
   • Starts with i.
   • Followed by the vertex ID.
   • Followed by hubs reachable in the backward direction.
   • Example: i 0 2 4 → Vertex 0 has incoming hubs 2 and 4.
4. Each vertex contributes exactly two lines to the file (o and i).
5. The total number of lines is 2 × number of vertices + 1.

For a graph with the following labels:

• Vertex 0: Outgoing: [1, 3], Incoming: [2, 4]
• Vertex 1: Outgoing: [2], Incoming: [0, 3]

The output file:

V 5
o 0 1 3
i 0 2 4
o 1 2
i 1 0 3

Using the bitset scheme and tail parallelism with 4 threads:

./DAGHL -s -i ../data/kvv.dimacs -t 4 -c -b

Example Output:

Reading graph from DIMACS ... done [2627ms]
Forward Graph Statistics:
  Number of vertices: 2527390
  Number of edges:    7955735
  Min degree:         0
  Max degree:         15
  Average degree:     3.14781
Reversing Graph ... done [103ms]
Initializing data structures ... done [191ms]
Computing HLs ... done [39661ms]
Computing hub permutation ... done [2450ms]
Sorting labels ... done [592ms]
Forward Labels:
  Min Size:     1
  Max Size:     240
  Avg Size:     78.5583
Backward Labels:
  Min Size:     1
  Max Size:     227
  Avg Size:     69.6271
FWD # count:    198547362
BWD # count:    175974860
Both # count:   374522222
Total memory usage: 2188.12 MB
10000 random queries: total time 180436 ms, avg time 18.0436 ns

./PLL -s -i ../data/kvv.dimacs -c -b

Example Output:

Reading graph from DIMACS ... done [2627ms]
Forward Graph Statistics:
  Number of vertices: 2527390
  Number of edges:    7955735
  Min degree:         0
  Max degree:         15
  Average degree:     3.14781
Reversing Graph ... done [106ms]
Computing HLs ... done [105986ms]
Computing hub permutation ... done [2444ms]
Sorting labels ... done [407ms]
Forward Labels:
  Min Size:     1
  Max Size:     240
  Avg Size:     78.5563
Backward Labels:
  Min Size:     1
  Max Size:     227
  Avg Size:     69.6233
FWD # count:    198542389
BWD # count:    175965342
Both # count:   374507731
Total memory usage: 2149.45 MB
10000 random queries: total time 180408 ms, avg time 18.0408 ns

This project is based on:

• "Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling" – Akiba et al. ArXiv
• "Robust Exact Distance Queries on Massive Networks" – Delling et al. Microsoft