search

rapidsai / cugraph

cuGraph - RAPIDS Graph Analytics Library
https://docs.rapids.ai/api/cugraph/stable/
Apache License 2.0
1.75k stars 303 forks source link

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

Open geoHeil opened 3 years ago

geoHeil commented 3 years ago

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

BradReesWork commented 3 years ago

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

geoHeil commented 3 years ago

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 commented 1 year ago

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

ChuckHastings commented 5 months ago

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.