Parallel-SSSP

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

Developing

Prerequisites

• clang++ from the OpenSilk project https://www.opencilk.org/doc/users-guide/install/

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]
• -r number of rounds per source
• -n number of different sources per graph

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

X. Dong, Y. Gu, Y. Sun, and Y. Zhang. Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021.

X. Dong, Y. Gu, Y. Sun, and Y. Zhang. Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths. arXiv preprint 2105.06145, 2021.