rust-graph: Dijkstra written in Rust

Graph algorithms implemented in Rust, available as a Python package. >10x faster than networkx.

So far, there is only one function implemented: all_pairs_dijkstra_path_length. It's a re-write of the networkx function with the same name and should return the same results.

🛠️ Installation

pip install rust-graph

🚦 Usage

from rust_graph import all_pairs_dijkstra_path_length

weighted_edges = [
    (0, 1, 1.0),
    (1, 2, 2.0),
    (2, 3, 3.0),
    (3, 0, 4.0),
    (0, 3, 5.0),
]

shortest_paths = all_pairs_dijkstra_path_length(weighted_edges, cutoff=3.0)

>>> shortest_paths
{3: {3: 0.0, 2: 3.0}, 2: {2: 0.0, 1: 2.0, 0: 3.0, 3: 3.0}, 1: {0: 1.0, 2: 2.0, 1: 0.0}, 0: {1: 1.0, 0: 0.0, 2: 3.0}}

📈 Benchmark

Tried a couple of options but failed for various reasons. Here are some notes on them:

• cugraph:
  • Slower than networkx for the test data.
  • Not available on PyPI, only supports python 3.10 (and not above) and some dependencies were broken, making it difficult to set up.
• rustworkx:
  • cutoff parameter is not implemented.
  • Extremely slow when the output is too large, because it returns lazy types rather than the actual values and converting it is probably not memory efficient.

Thus, we compare the performance of networkx and rust-graph for the all_pairs_dijkstra_path_length function.

MacBook Pro (M1)

23x as fast as networkx:

networkx Dijkstra took 4.45 s
rust-graph Dijkstra took 0.19 s

Personal laptop (AMD Ryzen R7 5800H (8 cores, 20MB total cache, 3.2 GHz, boost up to 4.4 GHz))

12x as fast as networkx:

networkx Dijkstra took 6.83 s
rust-graph Dijkstra took 0.57 s

If not using rayon parallelism, it's twice as slow:

networkx Dijkstra took 7.12 s
rust-graph Dijkstra took 1.04 s

Azure server (AMD EPYC 7V13 64-Core Processor)

CPU info:

    Model name:            AMD EPYC 7V13 64-Core Processor
    CPU family:          25
    Model:               1
    Thread(s) per core:  1
    Core(s) per socket:  48

15x as fast as networkx:

networkx Dijkstra took 6.14 s
rust-graph Dijkstra took 0.41 s

👨‍💻️ Maintenance Notes

Install from source

Install uv, rustup and maturin. Activate a virtual environment. Then,

bash scripts/install.sh
uv pip install -r deps/requirements_dev.in
python3 scripts/hf_download.py  # Download test data

Run benchmarks

python3 tools/benchmark.py

Compile requirements (generate lockfiles)

Use GitHub Actions: apply-pip-compile.yml. Manually launch the workflow and it will make a commit with the updated lockfiles.