GraphBLAS/graphblas-api-cpp

Evaluate coverage of extract and assign

Opened this issue · 2 comments

BenBrock commented
Evaluate coverage of extract and assign
mcmillan03 commented

Below is a list of the uses for assign and extract. tldr, non-contiguous index sets are used a couple of times but there might be better ways to do things. Part of “let’s write some code” to find out.

Trends

  • many of the vector assigns use the complete sequence of indices: [0, n) and depend on a mask to filter what gets through to result (with optional accumulate)
  • another large portion of vector assigns use the complete sequence of indices to assign a constant; to either fill the result or use a mask to filter the assignment.

LAGraph (reorg branch)

  • LG_BreadthFirstSearch_vanilla.c: assign one whole vector to another with a mask and accumulation.
  • LAGr_PageRankGAP.c: assign to fill a vector with a constant.
  • LAGr_PageRankGAP.c: assign to accumulate a whole vector into the destination (basically v1 -= v0)
  • LAGr_PageRank.c: assign to fill a vector with a constant.
  • LAGr_PageRank.c: assign one whole vector to another with a mask (merge).
  • LAGr_PageRank.c: assign to accumulate a whole vector into the destination (basically v1 -= v0)
  • LAGr_Betweenness: assign to accumulate a whole vector into the destination (basically v1 += v0)
  • LAGr_Betweenness: assign to fill a matrix with 1’s
  • LAGr_Betweenness: assign to fill a vector with a constant
  • LAGr_TriangleCount.c: extract used to permute the full adj matrix to put vertices in degree order
  • LAGr_SingleSourceShortestPath.c: assign to fill a vector with INT##_MAX or INFINITY
  • LAGr_SingleSourceShortestPath.c: like BFS, assign one whole vector to another with a mask involved.
  • LAGr_SingleSourceShortestPath.c: assign to fill a vector with a constant only where mask allows
  • LG_CC_Boruvka.c: extract from a vector of grandparents (a permutation, full vector). Could have duplicates?
  • LG_CC_Boruvka.c: assign to a vector to rewrite parents (masked, full vector) REQUIRES FURTHER ANALYSIS
  • LG_CC_Boruvka.c: assign used to fill a vector with 0 (dense)
  • LG_CC_FastSV: extract from a vector of parents to get grandparents (full vector). Could have duplicates?
  • LG_CC_FastSV: assign used to fill a vector with 0 (dense)
  • LG_CC_FastSV: assign used to copy a filled vector to another

GBTL (develop branch)

  • BFS_appendixC1 – assign one whole vector to another with a mask
  • BC_appendixC4 – assign a whold vector to row of a matrix
  • BC_appendixC4 – assign to fill a vector with a constant
  • BC_appendixC4 - assign to fill a matrix with a constant
  • BC_appendixC4 – extract a row of a matrix into a vector (extract column of a transpose view)…a view might be better here.
  • BC_update_appendixC5 – extract a set of rows of a matrix into another matrix (not contiguous rows)
  • MIS_appendixC6 – assign to fill vector with a constant with a mask
  • APSP – extract a row or a column of a matrix into another matrix
  • BC – assign to fill a matrix with a constant
  • BC – assign to fill a vector with a constant
  • BC – extract a row of a matrix into vector (extract column of a transpose view)
  • BFS – assign to merge one whole vector with another using a mask
  • CC – assign to fill (merge) a vector with a constant filtered by a mask
  • CC – assign to fill (merge) a constant with a vector filtered by a mask
  • Cluster_louvain – assign to fill a mask vector
  • Cluster_louvain – assign a vector to a matrix row (complete overwrite)
  • Cluster_louvain – extract a matrix column as a vector (complete overwrite)…views might be better here
  • Cluster_louvain – extract a matrix row as a vector (extract a column of a transposed matrix)…views might be better here
  • K_truss – assign to fill a vector with a constant
  • K_truss – extract a set of rows (non-contiguous) of one matrix into another matrix (might be done with views)
  • Maxflow – extract a column of a matrix into a vector (view?)
  • Metrics – extract a column of a matrix
  • Metrics – extract a row of a matrix
  • MIS - assign to fill (merge) a vector with a constant filtered by a mask
  • MST - assign to fill a vector with a constant filtered by a mask
  • MST – extract a matrix row as a vector (extract a column of a transposed matrix)
  • Pagerank – assign to fill a vector
  • Pagerank – assign to accumulate a whole vector into the destination (basically v1 -= v0)
mcmillan03 commented

I took some time to categorize the list into common operations per our last conversation. The last three groups require further study and discussion to see if a simpler extract/assign or view can accomplish the computation.

  1. V = fill(c): Things that can be done with a simple fill constructor for matrix and vector:
  • LAGr_PageRankGAP.c: assign to fill a vector with a constant.
  • LAGr_PageRank.c: assign to fill a vector with a constant.
  • LAGr_Betweenness: assign to fill a matrix with 1’s
  • LAGr_Betweenness: assign to fill a vector with a constant
  • LAGr_SingleSourceShortestPath.c: assign to fill a vector with INT##_MAX or INFINITY
  • LG_CC_Boruvka.c: assign used to fill a vector with 0 (dense)
  • LG_CC_FastSV: assign used to fill a vector with 0 (dense)
  • GBTL:BC_appendixC4 – assign to fill a vector with a constant
  • GBTL:BC_appendixC4 - assign to fill a matrix with a constant
  • GBTL:BC – assign to fill a matrix with a constant
  • GBTL:BC – assign to fill a vector with a constant
  • GBTL:Cluster_louvain – assign to fill a mask vector
  • GBTL:Pagerank – assign to fill a vector
  • GBTL:K_truss – assign to fill a vector with a constant
  1. V := c, assign a constant to a vector, but since a mask is involved this is a different operation than the previous if merge semantics are included this is not another constructor
  • LAGr_SingleSourceShortestPath.c: assign to fill a vector with a constant only where mask allows
  • GBTL:CC – assign to fill (merge) a vector with a constant filtered by a mask
  • GBTL:MIS - assign to fill (merge) a vector with a constant filtered by a mask
  • GBTL:MST - assign to fill a vector with a constant filtered by a mask
  • GBTL:MIS_appendixC6 – assign to fill vector with a constant with a mask
  • GBTL:CC – assign to fill (merge) a constant with a vector filtered by a mask
  1. V2 := V1, Seems like assignment operator, and copy assignment ctor
  • LG_CC_FastSV: assign used to copy a filled vector to another
  1. V2 := V1, because a mask is involved this is NOT copy assignment/ctor
  • GBTL:BFS_appendixC1 – assign one whole vector to another with a mask
  • LAGr_SingleSourceShortestPath.c: like BFS, assign one whole vector to another with a mask involved.
  • LAGr_PageRank.c: assign one whole vector to another with a mask (merge).
  • GBTL:BFS – assign to merge one whole vector with another using a mask
  1. V2 += V1, because accumulation is involved this is NOT copy assignment/ctor, because other operators are involved I don’t think operator+() should be used either
  • LAGr_PageRankGAP.c: assign to accumulate a whole vector into the destination (basically v1 -= v0)
  • LAGr_PageRank.c: assign to accumulate a whole vector into the destination (basically v1 -= v0)
  • LAGr_Betweenness: assign to accumulate a whole vector into the destination (basically v1 += v0)
  • GBTL:Pagerank – assign to accumulate a whole vector into the destination (basically v1 -= v0)
  1. V2 += V1, could be combined with previous set to create a simpler assign operator that does not include index sets, but supports optional mask and accumulate.
  • LG_BreadthFirstSearch_vanilla.c: assign one whole vector to another with a mask and accumulation.
  1. Mapping between vectors and whole rows/cols of a matrix…mutable views would be nice
  • GBTL:BC_appendixC4 – assign a whole vector to row of a matrix
  • GBTL:Cluster_louvain – assign a vector to a matrix row (complete overwrite)
  • GBTL:BC – extract a row of a matrix into vector (extract column of a transpose view)
  • GBTL:Metrics – extract a column of a matrix
  • GBTL:Metrics – extract a row of a matrix
  • GBTL:Maxflow – extract a column of a matrix into a vector (view?)
  • GBTL:MST – extract a matrix row as a vector (extract a column of a transposed matrix)
  • GBTL:Cluster_louvain – extract a matrix row as a vector (extract a column of a transposed matrix)…views might be better here
  • GBTL:Cluster_louvain – extract a matrix column as a vector (complete overwrite)…views might be better here
  • GBTL:BC_appendixC4 – extract a row of a matrix into a vector (extract column of a transpose view)…a view might be better here.
  1. I don’t know if this belongs with the previous set.
  • GBTL:APSP – extract a row or a column of a matrix into another matrix
  1. Complete permutation of a matrix, could be specified with a single index array
  • LAGr_TriangleCount.c: extract used to permute the full adj matrix to put vertices in degree order
  1. All of these require further study
  • LG_CC_Boruvka.c: extract from a vector of grandparents (a permutation, full vector). Could have duplicates?
  • LG_CC_Boruvka.c: assign to a vector to rewrite parents (masked, full vector) REQUIRES FURTHER ANALYSIS
  • LG_CC_FastSV: extract from a vector of parents to get grandparents (full vector). Could have duplicates?
  • GBTL:K_truss – extract a set of rows (non-contiguous) of one matrix into another matrix (might be done with views)
  • GBTL:BC_update_appendixC5 – extract a set of rows of a matrix into another matrix (not contiguous rows)