Simple and fast graph operations written in Rust

Navigation

Verified details

These details have been verified by PyPI
Project links
GitHub Statistics
Maintainers
Avatar for Deargen from gravatar.com Deargen

Unverified details

These details have not been verified by PyPI
Meta
  • License: Apache Software License (Apache-2.0)
  • Author: Kiyoon Kim
  • Requires: Python <4, >=3.8
Classifiers
Report project as malware

Project description

rust-graph: Dijkstra written in Rust

image PyPI - Downloads image image
Ruff rustfmt Actions status
Ruff Clippy Actions status
pytest cargo test Actions status
uv Actions status

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.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page