Evaluate coverage of extract and assign

[mcmillan03]

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]

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

2. 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

3. V2 := V1, Seems like assignment operator, and copy assignment ctor

   • LG_CC_FastSV: assign used to copy a filled vector to another

4. 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

5. 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)

6. 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.

7. 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.

8. 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

9. 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

10. 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)