search

Qiskit / rustworkx

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

Add `shortest_simple_paths` #671

Open msurkovsky opened 2 years ago

msurkovsky commented 2 years ago

What is the expected enhancement?

Do you consider to add a function or is there any possibility to cover functionality of NetworkX shortest_simple_path?

I'd like to use this library to compute k shortest paths from source to target node. I need to work with different alternative paths. It would be great to have the same interface as NetworkX version, i.e. having a generator that gradually returns "the next" shortest path.

mattmcdermott commented 2 years ago

Until this is eventually added as a feature, it should be possible to write your own function in Python implementing Yen's Algorithm (k-shortest paths), since this is basically a wrapper that makes calls to rx.dijkstra_shortest_paths.

I was able to implement one based on the code gist here: https://gist.github.com/ALenfant/5491853

Let me know if you need more info or want to see my version (which is a bit more specific to the package I work on).

kevinhartman commented 2 years ago

I'd be interested in working on this one!