How to Run STRATA

1. Installation

Clone the Repository

git clone https://github.com/dknife/STRATA.git
cd STRATA

Install Dependencies

pip install numpy scipy networkx tqdm

GPU Methods (optional)

pip install cupy-cuda12x

If CuPy cannot find CUDA, install the runtime packages:

pip install nvidia-cuda-runtime-cu12 nvidia-cuda-nvrtc-cu12 nvidia-cublas-cu12 nvidia-cusparse-cu12 nvidia-nvjitlink-cu12

The common/cuda_env.py module automatically detects CUDA_PATH from pip-installed nvidia packages.

GraphBLAS Methods (optional)

pip install suitesparse-graphblas

2. Running Benchmarks

Full Benchmark (11 methods × 6 graphs)

cd 02_Implementations
python run_full_benchmark.py

This benchmarks 10 methods (BC1–BC5, TC1–TC2, BG1, TG1–TG2) across 6 graph topologies. Results are saved to full_benchmark_results.json.

TC3 (GraphBLAS) Standalone

TC3 must run in a separate process to avoid GrB_init conflict with BC5:

python run_tc3_standalone.py

Results are saved to tc3_benchmark_results.json.

Benchmark Graphs

Benchmark Protocol

• Runs: 3 runs per method, minimum time reported
• GPU warmup: 1 warmup run before measurement
• Correctness: All distance matrices compared element-wise (int32)

3. Python API

Each method in 02_Implementations/<ID>/apsp.py exposes the same interface:

def run_apsp(A_csr, k=-1, verbose=True):
    """
    Args:
        A_csr: Adjacency matrix (scipy.sparse or numpy array)
        k: Hop constraint (-1 for full APSP)
        verbose: Show progress
    Returns:
        D: Distance matrix as numpy int32 array
    """

Example Usage

import sys
sys.path.insert(0, '02_Implementations')

import scipy.sparse as sp
from common.loader import load_graph, make_undirected

# Load graph
A, n, m = load_graph('04_Datasets/real-world/facebook_combined.txt',
                      fmt='edgelist', directed=True)
A = make_undirected(A)

# Run any method
from TC1_STRATA_SpMM_Cython.apsp import run_apsp
D = run_apsp(A, verbose=True)
print(f"Distance matrix: {D.shape}, max distance: {D.max()}")

# GPU method
from TG2_STRATA_CUDA.apsp import run_apsp as run_gpu
D_gpu = run_gpu(A, verbose=True)

Available Methods

4. Supported Graph Formats