[FEA]: GPU support for nx.minimum_spanning_tree

[yuxuan-z19]

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 wish to get a minimum spanning tree (MST) weight for a weighted NetworkX-generated classic graph (the edge weights are assigned after the graph generation). The MST routine nx.minimum_spanning_tree() is not supported yet.

Describe your ideal solution

ECL-MST (paper | code) is a working solution proposed in SC'23. Is it implementable on the existing framework?

Describe any alternatives you have considered

No response

Additional context

No response

Code of Conduct

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

[eriknw]

Thanks for the report and even providing reference paper and implementation @yuxuan-z19 !

It would be great to add this to nx-cugraph, and it should be very doable. cugraph already has it, and it appears to closely match networkx:

• https://docs.rapids.ai/api/cugraph/stable/api_docs/api/cugraph/cugraph.tree.minimum_spanning_tree.minimum_spanning_tree/
• https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tree.mst.minimum_spanning_tree.html

This is what we call a "legacy" API in cugraph, so we'll need to do a little more work on our end to first expose MST from pylibcugraph so it can then be used by both cugraph and nx-cugraph. This is totally doable and is already on our backlog, so we'll just bump it up to higher priority :)

CC @rlratzel @ChuckHastings

[yuxuan-z19]

Thanks, @eriknw @rlratzel @ChuckHastings, I just can't wait for it!!