cugraph icon indicating copy to clipboard operation
cugraph copied to clipboard

[FEA] local bridges (similar to Nx)

Open geoHeil opened this issue 4 years ago • 4 comments

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 avatar Feb 18 '21 18:02 geoHeil

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

BradReesWork avatar Feb 19 '21 14:02 BradReesWork

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.

geoHeil avatar Feb 21 '21 17:02 geoHeil

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 avatar Apr 19 '23 15:04 BradReesWork

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.

ChuckHastings avatar May 22 '24 23:05 ChuckHastings