🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more
Socket
Book a DemoInstallSign in
Socket

rust-graph

Package Overview
Dependencies
Maintainers
1
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

rust-graph

Simple and fast graph operations written in Rust

0.1.1
PyPI
Maintainers
1

rust-graph: Dijkstra written in Rust

image PyPI - Downloads image image

Ruff rustfmtActions status
Ruff ClippyActions status
pytest cargo testActions status
uvActions 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.

FAQs

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts