[FEA]: shortest_path implementation in nx-cugraph

[lorenzobalzani]

Is this a new feature, an improvement, or a change to existing functionality?

New Feature

How would you describe the priority of this feature request

Critical (currently preventing usage)

Please provide a clear description of problem this feature solves

I would like nx-cugraph to implement the method shortest_path. Current algorithms implementation includes only path lengths, as you can see here.

Could an alternative be implementing single_source_shortest_path and access the path by looking up at the target node idx in the result? Maybe it's even easier since single_source_shortest_path_lengths is already there.

Are there any motivations why this feature hasn't been implemented yet?

Describe your ideal solution

A wrapper for shortest_path() that accepts a source and a target node in the graph and returns ONE of the possible shortest paths (if many).

Function signature to wrap:

def shortest_path(G, source=None, target=None, weight=None, method="dijkstra") -> Dict:

Describe any alternatives you have considered

I do not see any alternatives, as of today.

Additional context

No response

Code of Conduct

• I agree to follow cuGraph's Code of Conduct
• I have searched the open feature requests and have found no duplicates for this feature request

[rlratzel]

Thanks @lorenzobalzani for the feature request!

Are there any motivations why this feature hasn't been implemented yet?

We typically choose to implement algorithms for each release based on a combination of factors including requests for them, how much effort they are to add, and how much we think they'll be needed by community members and projects. Now that you've requested shortest_path, we'll be looking into implementing it sooner. cugraph has support for both sssp and bfs (bfs can be used to find the shortest path for an unweighted graph, and is already used in nx_cugraph.single_*_shortest_path_length), so I don't think the effort to add support for nx_cugraph.shortest_path should be too high. @eriknw should be able to comment further.

[ChuckHastings]

@eriknw - We can partially implement this today through the C API. There are several cases:

1. source and target both specified, run BFS for an unweighted graph and SSSP for a weighted graph to generate a predecessors array. Use the output from BFS/SSSP to call cugraph_extract_paths specifying both source and target, the result should be the desired list of paths. Note that we don't have a variant of BFS/SSSP that stops when we reach a target, so there's potentially some room for additional optimization here.
2. source specified, no target. As above, run BFS/SSSP and cugraph_extract_paths, don't specify the target
3. target specified, no source. If the graph is symmetric (undirected) just treat the target as the source and do option 2. At the end you need to reverse the paths.
4. target specified, no source, graph is not symmetric (directed). Transpose the graph and run option 2.
5. Neither source nor target specified... this is a function we do not have. I believe that @seunghwak did some work exploring this last year. The problem here is that the back pointers for the paths are large. If all of the vertices in your graph are connected you would need n^2 GPU Memory to compute this, which restricts the size graph you can handle. We could take source vertices in a batch of size b and then use n*b GPU Memory and run the extractions in parallel. But that's an algorithm we would need to work on.

[rlratzel]

Hi again, @lorenzobalzani
This PR was merged which adds shortest_path to nx-cugraph. The nightly 24.04 builds should have this, so please let us know what you think if you get a chance to try it.

I'll close this issue, but we can re-open it or create a new one if you find that there's still more to do. Currently, graphs with negative weights are not supported, but we should have an update in an upcoming release to remove that limitation (I created this issue for that)