Find k shortest paths using Yen's Algorithm

[nitsatiisc]

This pull request provides the function get_k_shortest_paths_yen which finds k shortest paths between a source vertex and a target vertex in a graph. If less than k paths exist between source and target, then all the paths are returned. We require edge-weights to be positive.

• [ * ] I ran rustfmt locally
• [ * ] I have added the tests to cover my changes.
• [ ] I have updated the documentation accordingly.
• [ ] I have read the CONTRIBUTING document.

[CLAassistant]

All committers have signed the CLA.

[CLAassistant]

Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you sign our Contributor License Agreement before we can accept your contribution.

---

Nitin seems not to be a GitHub user. You need a GitHub account to be able to sign the CLA. If you have already a GitHub account, please add the email address used for this commit to your account.
_{You have signed the CLA already but the status is still pending? Let us recheck it.}

[ranjana-mishra]

This pull request provides the function get_k_shortest_paths_yen which finds k shortest paths between a source vertex and a target vertex in a graph. If less than k paths exist between source and target, then all the paths are returned. We require edge-weights to be positive.

• [ * ] I ran rustfmt locally
• [ * ] I have added the tests to cover my changes.
• [ ] I have updated the documentation accordingly.
• [ ] I have read the CONTRIBUTING document.

closing PR https://github.com/Qiskit/rustworkx/pull/1284 , as it is duplicate. ( both worked by Nitin )

[kaldag]

Yen's algorithm was used to get the k-shortest path. This builds on top of an existing shortest path algorithm, like the Dijkstra's algorithm, etc. More on Yen's algorithm - https://people.csail.mit.edu/minilek/yen_kth_shortest.pdf

[ranjana-mishra]

Thanks for opening a PR adding this feature. I haven't looked at the code in any detail yet, before I did I saw some small administrative details:

1. Can you remove the .idea directory from the commit. Not everyone uses jetbrains ides and the config is often specific to a local environment anyway. I'd suggest setting up a global git ignore so .idea/ is always ignored by git by default.
2. Could you sign the CLA following the bot's comments in: Find k shortest paths using Yen's Algorithm #1363 (comment) this is a requirement before we can accept any code contributions to the repository.
3. Can you run cargo fmt and fix anything lint, formatting, tests, etc flag. We document how to run these things locally in: https://github.com/Qiskit/rustworkx/blob/main/CONTRIBUTING.md

@mtreinish can you verify now, we all have submitted CLA. removed .idea folder and rust fmt was executed for it.

[giobus75]

Hi,

I'm currently working on vehicle traffic networks and found this function quite interesting. While reviewing the code, I noticed that the costs of the shortest paths are sent to standard output.

I believe it would be helpful if the function returned the costs along with the shortest path list. This would allow users to filter the paths based on a cost cutoff directly.

Alternatively, adding a cutoff parameter to the function interface could also be useful. This would enable the function to return only the shortest paths with costs smaller than the specified cutoff.

Thank you for considering this suggestion!

[ranjana-mishra]

Hi,

I'm currently working on vehicle traffic networks and found this function quite interesting. While reviewing the code, I noticed that the costs of the shortest paths are sent to standard output.

I believe it would be helpful if the function returned the costs along with the shortest path list. This would allow users to filter the paths based on a cost cutoff directly.

Alternatively, adding a cutoff parameter to the function interface could also be useful. This would enable the function to return only the shortest paths with costs smaller than the specified cutoff.

Thank you for considering this suggestion!

Thankyou for your suggestion. We will consider this if this can add value. Here as we are always returning the paths in increasing cost order its not needed to give cost info. But yes there could be many paths with same cost, and user can choose between them.

[giobus75]

Hi, I'm currently working on vehicle traffic networks and found this function quite interesting. While reviewing the code, I noticed that the costs of the shortest paths are sent to standard output. I believe it would be helpful if the function returned the costs along with the shortest path list. This would allow users to filter the paths based on a cost cutoff directly. Alternatively, adding a cutoff parameter to the function interface could also be useful. This would enable the function to return only the shortest paths with costs smaller than the specified cutoff. Thank you for considering this suggestion!

Thankyou for your suggestion. We will consider this if this can add value. Here as we are always returning the paths in increasing cost order its not needed to give cost info. But yes there could be many paths with same cost, and user can choose between them.

I understand, thank you for the clarification. My question is related to the application I'm working on. Specifically, I need to find all shortest paths between a given source and target, with a total cost less than or equal to a parameter that I can pass to the function. I was wondering if adding this as a feature to the current function would be straightforward.

Additionally, since the function already has access to this information, it could be useful for various applications to return the costs along with the paths. This would allow for easier post-processing in different use cases avoiding to recompute the cost for each path.

[nitsatiisc]

Hi, I'm currently working on vehicle traffic networks and found this function quite interesting. While reviewing the code, I noticed that the costs of the shortest paths are sent to standard output. I believe it would be helpful if the function returned the costs along with the shortest path list. This would allow users to filter the paths based on a cost cutoff directly. Alternatively, adding a cutoff parameter to the function interface could also be useful. This would enable the function to return only the shortest paths with costs smaller than the specified cutoff. Thank you for considering this suggestion!

Thankyou for your suggestion. We will consider this if this can add value. Here as we are always returning the paths in increasing cost order its not needed to give cost info. But yes there could be many paths with same cost, and user can choose between them.

I understand, thank you for the clarification. My question is related to the application I'm working on. Specifically, I need to find all shortest paths between a given source and target, with a total cost less than or equal to a parameter that I can pass to the function. I was wondering if adding this as a feature to the current function would be straightforward.

Additionally, since the function already has access to this information, it could be useful for various applications to return the costs along with the paths. This would allow for easier post-processing in different use cases avoiding to recompute the cost for each path.

Thank you for your interest. Agreed, this is a small modification. We can update the pull request with the required changes. Just wanted to know stylistically what is preferred: the function returning a tuple containing a vector of paths and a corresponding vector of costs, or a vector of tuples containing the path and the cost.

[giobus75]

Thank you for your interest. Agreed, this is a small modification. We can update the pull request with the required changes. Just wanted to know stylistically what is preferred: the function returning a tuple containing a vector of paths and a corresponding vector of costs, or a vector of tuples containing the path and the cost.

Hi,

Thank you for your quick response! I believe a tuple containing a vector of paths and a corresponding vector of costs would be the best option. This structure makes it simple to extract all paths when costs are not needed while also allowing for straightforward association of paths with their respective costs when required.

[giobus75]

Hi, I see that the pull request check process fails because there are two white lines (259, 260) in the file rustworkx-core/src/shortest_path/simple_shortest_paths.rs . Removing just one of them solves the issue. Even doing this and installing the code with pip install ., the Python binding for the get_smallest_k_paths_yen function looks missing. Is it possibile to add it? Thank you