search

Qiskit / rustworkx

A high performance Python graph library implemented in Rust.
https://www.rustworkx.org
Apache License 2.0
1.11k stars 151 forks source link

Contraction Hierarchies #1018

Open sourabhlal-ds opened 1 year ago

sourabhlal-ds commented 1 year ago

What is the expected enhancement?

In order to perform shortest path searches on massive graphs, it would be quite useful to have some implementation of contraction hierarchies. https://en.wikipedia.org/wiki/Contraction_hierarchies

Is there any plan to implement this feature? Thank you!

Lucianod28 commented 1 year ago

I'm also looking for this or a hub-labeling algorithm such as the one described in Abraham et al. It seems these algorithms are widely used for large graphs, but the only implementation I've found is this C++ one: https://github.com/savrus/hl. I'm curious if this might be implemented here or alternatively if anyone knows of a Rust or Python implementation that we could adapt to use with this library?

Edit: Just found out about this Rust graph library for contraction hierarchies: https://github.com/easbar/fast_paths though I'm not sure how it could be integrated.