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

[FEA] target to source shortest path #806

Closed
aerdem4 opened this issue Apr 6, 2020 · 6 comments · Fixed by #1278
Closed

[FEA] target to source shortest path #806

aerdem4 opened this issue Apr 6, 2020 · 6 comments · Fixed by #1278
Labels
feature request New feature or request
Milestone
0.18

Comments

@aerdem4
Copy link

aerdem4 commented Apr 6, 2020

Is your feature request related to a problem? Please describe.
cugraph sssp implementation only takes source as input and calculates shortest path to all other nodes. I only need shortest path to a target node.

Describe the solution you'd like
I would like to have shortest_path_length(g, source=a, target=b) functionality similar to networkx.
@aerdem4 aerdem4 added the ? - Needs Triage Need team to review and classify label Apr 6, 2020
@BradReesWork
Copy link
Member

@aerdem4 getting the shortest path to just a single target vertex is just a matter of filtering the returned results down to the single path you want.

There is a utility function to do that: get_traversed_path(df, id):

df = cugraph.sssp(G, start_id)
path = cugraph.util.get_traversed_path(df, target):

@aerdem4
Copy link
Author

aerdem4 commented Apr 7, 2020

@BradReesWork but doesn't it do a redundant work then? Or did you suggest it as a work around?

@BradReesWork
Copy link
Member

@aerdem4 The amount of time to do an all path SSSP is the same of a directed Source to Destination. We could just make an API that hides that fact

@BradReesWork BradReesWork added question Further information is requested 2 - In Progress feature request New feature or request and removed 2 - In Progress question Further information is requested ? - Needs Triage Need team to review and classify labels Apr 7, 2020
@BradReesWork
Copy link
Member

Adding the creation of a new function to the roadmap

@BradReesWork BradReesWork added this to the 0.16 milestone Apr 8, 2020
@BradReesWork BradReesWork modified the milestones: 0.16, 0.17 Sep 10, 2020
@jsnns
Copy link

jsnns commented Oct 23, 2020

I want to start working on this. @BradReesWork, can you assign it to me?

@jpurviance
Copy link
Contributor

I've been playing around with this.

From looking at the networkx docs, the api for this supports more than what was requested. How important is it for the api to match exactly. Is the goal to support duck typing as much as possible?

@jpurviance jpurviance mentioned this issue Nov 23, 2020
Merged
@BradReesWork BradReesWork modified the milestones: 0.17, 0.18 Nov 23, 2020
@rapids-bot rapids-bot bot closed this as completed in #1278 Dec 3, 2020
rapids-bot bot pushed a commit that referenced this issue Dec 3, 2020
@jpurviance
Add support for shortest_path_length and fix graph vertex checks(#1278)
6b92349 
Adds the ability to get the length/cost of path from source to destination(s). Closely follows [`networkx.shortest_path_length`](https://networkx.org/documentation/latest/reference/algorithms/generated/networkx.algorithms.shortest_paths.generic.shortest_path_length.html#networkx.algorithms.shortest_paths.generic.shortest_path_length). 


Similarities:
1) Takes an optional target vertex
2) If only source is provided, a `cudf` dataframe is returned with columns: `[vertex, distance]` (similar to `networkx` dictionary return)
3) If source and target are specified the exact length is returned or `sys.float_info.max` if the vertex is not reachable. 


Differences:
1) Requires that source be provided, as apposed to `networkx`
2) Nethod of graph traversal is not an option. 

Fixes:
1) Fixes #806 
2) `sssp` and `cugraph.Graph.has_node` vertex checks. Added support for checking for vertexes that are not apart of the graph. in the past, `TypeError` was raised when doing a comparison check (as apposed to `ValueError`)

Authors:
  - John Purviance <[email protected]>
  - BradReesWork <[email protected]>

Approvers:
  - Alex Fender

URL: #1278
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
feature request New feature or request
Projects
None yet
Milestone
0.18
Development

Successfully merging a pull request may close this issue.

[REVIEW] Add support for shortest_path_length and fix graph vertex checks jpurviance/cugraph
4 participants
@jpurviance @jsnns @aerdem4 @BradReesWork