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.

pip install rust-graph

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}}

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.

23x as fast as networkx:

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

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

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

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

python3 tools/benchmark.py

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