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

[FEA] local bridges (similar to Nx) #1418

Open
Tracked by #3337
geoHeil opened this issue Feb 18, 2021 · 4 comments
Open
Tracked by #3337

[FEA] local bridges (similar to Nx) #1418

geoHeil opened this issue Feb 18, 2021 · 4 comments
Assignees

Comments

@geoHeil
Copy link

geoHeil commented Feb 18, 2021

Improve Networkx API compatibility: add support for local bridges:

https://networkx.org/documentation/stable//reference/algorithms/generated/networkx.algorithms.bridges.local_bridges.html#networkx.algorithms.bridges.local_bridges

@geoHeil geoHeil added the ? - Needs Triage Need team to review and classify label Feb 18, 2021
@geoHeil geoHeil changed the title [FEA] local bridges [FEA] NetworkX compatibility add local bridges Feb 18, 2021
@BradReesWork
Copy link
Member

@geoHeil thanks for the suggestion, we will investigate level of effort and work this request into the backlog

@BradReesWork BradReesWork added 0 - Backlog and removed ? - Needs Triage Need team to review and classify labels Feb 19, 2021
@geoHeil
Copy link
Author

geoHeil commented Feb 21, 2021

FYI: networkx works well when computing the local bridges without the shortest paths (with_span=False) https://stackoverflow.com/questions/66291151/how-to-consume-a-python-gneerator-in-parallel-using-multiprocessing/66302419#66302419

When trying to replace networkx with cugraph in a naive way i.e. only substituting the shortest path computation it still is really slow - as the whole loop is still running in python on a single core.

@BradReesWork
Copy link
Member

dropping the compatibility portion of this issues since that is captured in another issues and ties into the on-going work with NetworkX. The request for local bridges is still valid

@BradReesWork BradReesWork changed the title [FEA] NetworkX compatibility add local bridges [FEA] local bridges (similar to Nx) Apr 19, 2023
@ChuckHastings ChuckHastings self-assigned this Apr 29, 2024
@ChuckHastings
Copy link
Collaborator

local_bridges can be constructed using the technique from edge triangle counting, which is being added in 24.06. Instead of counting, we can remove any vertex pairs that are part of a triangle.

After #4382 is merged into the 24.06 release we should be able to schedule this work when we have someone to implement it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants