search

GraphBLAS / LAGraph

This is a library plus a test harness for collecting algorithms that use the GraphBLAS. For test coverage reports, see https://graphblas.org/LAGraph/ . Documentation: https://lagraph.readthedocs.org
Other
229 stars 61 forks source link

Choosing a BFS algorithm #119

Closed jeffreylovitz closed 2 years ago

jeffreylovitz commented 2 years ago

RedisGraph is currently using LAGraph's older BFS push-pull algorithm - https://github.com/GraphBLAS/LAGraph/blob/6a07dc4b737bce1931c538826e68e177d5d57620/Source/Algorithm/LAGraph_bfs_pushpull.c .

We have seen a few issues, such as https://github.com/RedisGraph/RedisGraph/issues/1912 and https://github.com/RedisGraph/RedisGraph/issues/1695, which seem to indicate a bug in this algorithm. Using your latest work seems like a sensible solution, but there are now several BF variants, and we are unsure which to adopt.

In most cases we want the vector of parents to backtrack through, though this is not always true. We can adopt two algorithms to handle these two cases if that's a preferred solution.

Thanks for your guidance!

DrTimothyAldenDavis commented 2 years ago

Yes, that one is old and should be replaced by the LAGraph_BreadthFirstSearch.c in the reorg branch of LAGraph, in the src/algorithm folder. It has both the parent version and level-only variants.

jeffreylovitz commented 2 years ago

@DrTimothyAldenDavis Thanks for the help!

DrTimothyAldenDavis commented 2 years ago

The older BFS shouldn't have this problem, but you might be using it incorrectly. In that case, the new one would have the same problem.

The method ignores any edge weights. If you have an edge of zero, or infinite, weight to indicate "it's not really an edge", then the BFS will see it as an edge anyway, and follow it.

On Wed, Nov 3, 2021 at 1:13 PM Jeffrey Lovitz @.***> wrote:

@DrTimothyAldenDavis https://github.com/DrTimothyAldenDavis Thanks for the help!

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/GraphBLAS/LAGraph/issues/119#issuecomment-959796558, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEYIIOKFZBGOOSDJXMVPS5TUKGCXHANCNFSM5HJGV4HA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.