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.

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

[BUG] SCC results for graph with loops seems incorrect and does not match Nx nor SciPy #1471

Closed
rlratzel opened this issue Mar 18, 2021 · 1 comment · Fixed by #1475
Closed
Assignees
Labels
? - Needs Triage Need team to review and classify bug Something isn't working

Comments

@rlratzel
Copy link
Contributor

rlratzel commented Mar 18, 2021

I recently observed behavior from cugraph.strongly_connected_components when handling directed graphs that have loops that appears to be a bug. The same input given to the SCC algos in SciPy and NetworkX both return identical results which match expectations (the input graph is trivially small and easy to predict results with, and is included in the test script attached below).

Other information:

  • This was initially discovered through using our C++ API from libcugraph directly, so that should eliminate the root cause of this issue as something in the python layer.
  • The handling of loops are assumed to be related, but only because the attached script uses them in the comparison and that may not be the root cause.
  • The attachments describe the issue best, but to summarize:
    For this input:
[[1., 1., 0., 0., 0.,],
 [1., 1., 0., 0., 0.,],
 [1., 0., 1., 0., 0.,],
 [0., 1., 0., 1., 0.,],
 [0., 0., 0., 0., 1.,],
]

this output is observed:

NUM LABELS: sp: 4, cu: 2, nx: 4
GROUPS: sp: [{0, 1}, {2}, {3}, {4}], cu: [{0, 1, 2, 3}, {4}], nx: [{0, 1}, {2}, {3}, {4}]

where sp is SciPy, cu is cuGraph, and nx is NetworkX. Each library's strongly connected components API was called using a directed graph created from the array above.

connected_components_example_py.txt

connected_components_example_output.txt

@rlratzel rlratzel added bug Something isn't working ? - Needs Triage Need team to review and classify labels Mar 18, 2021
@rlratzel
Copy link
Contributor Author

FYI: @anaruse

rapids-bot bot pushed a commit that referenced this issue Mar 23, 2021
This provides fixes for strongly connected components on graphs with self-loops: #1471.

closes #1471

Authors:
  - Andrei Schaffer (@aschaffer)

Approvers:
  - Brad Rees (@BradReesWork)
  - Rick Ratzel (@rlratzel)

URL: #1475
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
? - Needs Triage Need team to review and classify bug Something isn't working
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants