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 limitation of one connected component within input Graph from nx_cugraph.k_truss #3963

Closed
rlratzel opened this issue Oct 30, 2023 · 0 comments · Fixed by #3965
Closed

Add limitation of one connected component within input Graph from nx_cugraph.k_truss #3963

rlratzel opened this issue Oct 30, 2023 · 0 comments · Fixed by #3965
Assignees
@eriknw
Labels
improvement Improvement / enhancement to an existing function non-breaking Non-breaking change

Comments

@rlratzel
Copy link
Contributor

The current cugraph k_truss algo is not supported for input graphs with >1 connected component (separate issue needed).

In order to prevent nx-cugraph users from receiving bad results/crashes, nx_cugraph.k_truss() should raise an informative exception if the input graph has >1 connected component.

One proposal is to simply call the PLC WCC algo and check the number of components, then raise NotImplementedError if >1. This check and exception can be removed when a future version of PLC k_truss that supports >1 connected component is available (24.02 at the earliest?).

cc @ChuckHastings
@rlratzel rlratzel added improvement Improvement / enhancement to an existing function non-breaking Non-breaking change labels Oct 30, 2023
@eriknw eriknw mentioned this issue Oct 31, 2023
Merged
rapids-bot bot pushed a commit that referenced this issue Oct 31, 2023
@eriknw
nx-cugraph: add CC for undirected graphs to fix k-truss (#3965)
eb1e515 
Fixes #3963 and add `connected_components`, `is_connected`, `node_connected_component`, and `number_connected_components`.

Also updated `_groupby` to handle groups that are not consecutive integers starting with 0.

Also, `plc.weakly_connected_components` does not handle isolated nodes well, and I needed to handle this at the Python layer as was done in #3897

Authors:
  - Erik Welch (https://github.com/eriknw)

Approvers:
  - Rick Ratzel (https://github.com/rlratzel)

URL: #3965
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@eriknw eriknw

Labels
improvement Improvement / enhancement to an existing function non-breaking Non-breaking change
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

nx-cugraph: add CC for undirected graphs to fix k-truss eriknw/cugraph
2 participants
@eriknw @rlratzel