Parallel-SSSP

This repository includes the implmentation of $\rho$-stepping, $\Delta$*-stepping, and Bellman-Ford.

Developing

Prerequisites

• g++ >= 7 with support for Cilk Plus and C++17 (It is tested with g++ 7.5.0)

Setting up

Clone the library with submodule

git clone --recurse-submodules https://github.com/ucrparlay/Parallel-SSSP.git 
cd Parallel-SSSP/ 

Alternatively, you can first clone it and add the submodule

git clone https://github.com/ucrparlay/Parallel-SSSP.git 
git submodule update --init --recursive 
cd Parallel-SSSP/ 

Building

A makefile is given in the repository, you can compile the code by:

make 

Usage

./sssp [-i input_file] [-p parameter] [-w] [-s] [-v] [-a algorithm] 

Options:

• -i input file path
• -p parameter(e.g. delta, rho)
• -w weighted input graph
• -s symmetrized input graph
• -v verify result
• -a algorithm: [rho-stepping] [delta-stepping] [bellman-ford]

For example, if you want to run $\rho$-stepping on a symmetrized weighted graph INPUT_NAME, set $\rho$=2000000, and use Dijkstra's algorithm to verify the result after the test, you can run:

./sssp -i INPUT_NAME -p 2000000 -w -s -v -a rho-stepping

Graph Formats

The application can auto-detect the format of the input graph based on the suffix of the filename. Here is a list of supported graph formats:

• .bin The binary graph format from GBBS.
• .adj The adjacency graph format from Problem Based Benchmark suite.
• .wsg The weighted serialized pre-built graph format from GAPBS.
• .gr The galois graph file from Galois.

Some unweighted binary graphs can be found in our Google Drive. For storage limit, we don't provide the large graphs used in our paper. They can be found in Stanford Network Analysis Project and Web Data Commons.

Reference

Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang. Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 184-197, 2021.

Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang. Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths. arXiv preprint 2105.06145, 2021.

If you use our code, please cite our paper:

@inproceedings{dong2021efficient,
  title     = {Efficient stepping algorithms and implementations for parallel shortest paths},
  author    = {Dong, Xiaojun and Gu, Yan and Sun, Yihan and Zhang, Yunming},
  booktitle = {Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures},
  pages     = {184--197},
  year      = {2021}
}