Orionet

Orionet is a parallel graph library to process point to point shortest path queries.

Developing

Prerequisites

• g++ or clang with C++17 features support (tested with g++ 13.2.1 and clang 14.0.6) on Linux machines.
• We use ParlayLib to support fork-join parallelism and some parallel primitives. It is provided as a submodule in our repository.

Setting up

Clone the library with submodule

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

Alternatively, you can first clone it and add the submodule

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

Building

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

make 

Usage

Single Source Shortest Path

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

Options:

• -i input graph 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

Point to Point Shortest Path

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

Options:

• Same as above
• -b use bidirectional search

A*

./astar [-i input_file] [-c coordinates] [-p parameter] [-w] [-s] [-v] [-a algorithm] [-b]

Options:

• Same as above
• -c coordinate file path

Multiple Point to Point Shortest Path Queries

./multi_ppsp [-i input_file] [-p parameter] [-q query_file] [-w] [-s] [-v] [-a algorithm]

Options:

• Same as above
• -q query graph file path

The application will map the nodes of the query graph to random nodes in the input file, and run a PPSP query for every edge in the query graph.

Supported Formats

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.

Coordinate Formats

The application supports Problem Based Benchmark Suite geometry file format for coordinates in any dimension.

• .pbbs The geometry file format from PBBS.

By default the application will use euclidean distance. To use spherical coordinates, compile using

make astar -DOSM=1