BFS

Problem Specification

Input

$G=(V, E)$, an unweighted graph, and a source, $s \in V$. The input graph can either be undirected or directed.

Output

$P$, a mapping where $P[v]$ is the parent of $v$ in the output BFS-tree rooted at $s$, and $P[s] = s$.

Algorithm Implementations

We implement a non-deterministic parallel breadth-first search as our BFS implementation in GBBS. The implementation is based on the one from Ligra. More details about our implementation can be found in Section 6.1 of [1].

We provide a tutorial on how to implement this BFS example in our tutorial.

The code for our implemenation is available here.

Cost Bounds

The algorithm runs in $O(n + m)$ work and $O(\mathsf{D}(G) \log n)$ depth, which follows from our bounds on the edgeMap primitive.

Compiling and Running

The benchmark can be compiled by running:

bazel build -c opt //benchmarks/BFS/NonDeterministicBFS:BFS

It can then be run on a test input graph in the uncompressed format as follows:

numactl -i all ./bazel-bin/benchmarks/BFS/NonDeterministicBFS/BFS_main -s -m -src 1 inputs/rMatGraph_J_5_100

It can then be run on a test input graph in the compressed format as follows:

numactl -i all ./bazel-bin/benchmarks/BFS/NonDeterministicBFS/BFS_main -s -c -m -src 1 inputs/rMatGraph_J_5_100.bytepda

References

[1] Laxman Dhulipala, Guy Blelloch, and Julian Shun
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 393-404, 2018.