Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Add shortest path function #151

Closed
mtreinish opened this issue Sep 30, 2020 · 0 comments · Fixed by #162
Closed

Add shortest path function #151

mtreinish opened this issue Sep 30, 2020 · 0 comments · Fixed by #162
Assignees
@mtreinish
Labels
enhancement New feature or request good first issue Good for newcomers
Milestone
0.6.0

Comments

@mtreinish
Copy link
Member

What is the expected enhancement?

Right now retworkx doesn't have a shortest_path function to return the shortest path between 2 nodes in a graph. There a several shortest path length functions that return the shortest path length between nodes. We should add a retworkx.graph_shortest_path and retworkx.digraph_shortest_path functions that will return the path as node indices from a source to the target node. One thing to mention here is that for the directed graph function there should be an option to treat edges as undirected/bidirectional so that a user can find the undirected shortest path between nodes.
@mtreinish mtreinish added enhancement New feature or request good first issue Good for newcomers labels Sep 30, 2020
@mtreinish mtreinish mentioned this issue Sep 30, 2020
Closed
7 tasks
mtreinish added a commit to mtreinish/retworkx that referenced this issue Oct 5, 2020
@mtreinish
Add Dijkstra shortest path functions
a0de080 
This commit adds 2 new functions, digraph_dijkstra_shortest_paths() and
graph_dijkstra_shortest_path(), which is a function to get the shortest
path from a node in a graph. It leverages the same dijkstra's algorithm
module which has been modified to get a path in addition to the path
length.

Depends on Qiskit#161
Fixes Qiskit#151
@mtreinish mtreinish mentioned this issue Oct 5, 2020
Merged
@mtreinish mtreinish added this to the 0.6.0 milestone Oct 6, 2020
@mtreinish mtreinish self-assigned this Oct 15, 2020
mtreinish added a commit that referenced this issue Nov 9, 2020
@mtreinish @lcapelluto
Add Dijkstra shortest path functions (#162)
0ef76fe 
* Add to_undirected method for PyDiGraph

This commit adds a new method to the PyDiGraph class, to_undirected(),
which will generate an undirected PyGraph object from the PyDiGraph
object.

Fixes #153

* Fix lint

* Add Dijkstra shortest path functions

This commit adds 2 new functions, digraph_dijkstra_shortest_paths() and
graph_dijkstra_shortest_path(), which is a function to get the shortest
path from a node in a graph. It leverages the same dijkstra's algorithm
module which has been modified to get a path in addition to the path
length.

Depends on #161
Fixes #151

* Fix lint

* Fix duplicate weight_callable functions from rebase

This commit fixes an issue with duplicate weight_callable functions that
happened because one was added in this PR's branch and another was
added in a different PR. The functions were mostly identical so this
just consolidates the 2.

* Apply suggestions from code review

Co-authored-by: Lauren Capelluto <laurencapelluto@gmail.com>

* Add docs for paths parameter in dijkstra::dijkstra

* Use setUp() to build common test graphs

* Move path HashMap initialization into dijkstra::dijkstra()

Co-authored-by: Lauren Capelluto <laurencapelluto@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@mtreinish mtreinish

Labels
enhancement New feature or request good first issue Good for newcomers
Projects
None yet
Milestone
0.6.0
Development

Successfully merging a pull request may close this issue.

Add Dijkstra shortest path functions mtreinish/retworkx
1 participant
@mtreinish