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

Non-deterministic CDLP algorithm #101

Open szarnyasg opened 4 years ago

szarnyasg commented 4 years ago

I had an interesting discussion with the [igraph authors]() at their forum. They highlighted that the non-deterministic CDLP algorithm isn't only faster but also better in some cases (as it tends to avoid the oscillation of labels). So when touching the CLDP codebase, I'll also add a boolean flag to set deterministic/non-deterministic behaviour.

szarnyasg commented 3 years ago

A correction to my earlier post: the nondeterminism (always picking the smallest label) is not the main cause of the oscillation - instead, the problem is the synchronous nature of the algorithm. An asynchronous algorithm does better for avoiding the problem.

A potential workaround is partitioning the work, then

  1. select k vertices and their incoming edges in the matrix randomly
  2. compute the new labels
  3. assign the labels to vector l
  4. if all vertices were processed, we're done, otherwise go to 1.