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

Graphalytics PageRank variant #163

Closed szarnyasg closed 1 year ago

szarnyasg commented 1 year ago

Initial implementation of the Graphalytics PageRank variant.

It's been a while since I contributed to LAGraph so my knowledge is a bit rusty. So I'm grateful for any feedback – please let me know if there are any changes to be made.

I have two questions:

  1. Should this implementation go into the stable or the experimental algorithms?

  2. Is accessing G->A in

    GRB_TRY (GrB_reduce (nondangling_mask, NULL, NULL, GxB_LOR_BOOL_MONOID,
        G->A, NULL)) ;

    allowed without any further checks?

mcmillan03 commented 1 year ago

Regarding question 1 (stable or experimental): I don't think we have established the process for promoting algorithms but I would imagine the following.

  1. establish a dev branch that stages the changes for the next commit (all work should be done on branches off of dev.
  2. as algorithms are chosen for the next release they move to stable on the dev branch.
  3. Mods could be done to the algorithms on experimental before this move, but I can see where mods would also be done in stable after the move.
szarnyasg commented 1 year ago

Got it. I think creating the initial implementation of this algorithm as an experimental would be the way to go. I also changed the target of my pull request to the dev branch.

DrTimothyAldenDavis commented 1 year ago

Yes, it should be fine to do that call to reduce on G->A.

DrTimothyAldenDavis commented 1 year ago

With this update, LAGraph passes all of its tests (including the new PageRankX) with my draft v8.0.0 and the JIT, with no changes. When I turn on the compact mode (GBCUDA_DEV enabled), SS:GrB doesn't use any of its built-in kernels. In v7.4.3 it would call all my generic methods. In my draft v8.0.0 (on the master branch of SS:GrB), it compiles 27 kernels. I think all of them would be covered by my built-in kernels if I turned of GBCUDA_DEV.