Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_check_coarsen: naive implementation of coarsening (edge by edge traversal), also checks
3 : // parent and mapping vectors for correctness
4 : //------------------------------------------------------------------------------
5 :
6 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
7 : // SPDX-License-Identifier: BSD-2-Clause
8 : //
9 : // For additional details (including references to third party source code and
10 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
11 : // Contributors.txt for a full list of contributors. Created, in part, with
12 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
13 : // DM22-0790
14 :
15 : // Contributed by Vidith Madhu, Texas A&M University
16 :
17 : //------------------------------------------------------------------------------
18 :
19 : // A naive coarsening implementation that individually traverses edges in the original graph
20 : // and updates the corresponding edge in the coarsened graph
21 : // In addition, verifies that the given parent and mapping vectors are correct for the general coarsening case.
22 : // there may be additional constraints that must be observed for specific types of coarsenings; for example,
23 : // the parent vector for a matching-based coarsening must come from a valid matching. Such properties should be checked
24 : // in the respective coarsening tests.
25 :
26 : // NOTE: The input adjacency matrix A must be from an undirected graph
27 :
28 : #include "LG_internal.h"
29 : #include "LG_test.h"
30 : #include "LG_test.h"
31 : #include "LG_Xtest.h"
32 :
33 : // #undef LG_FREE_ALL
34 : // #undef LG_FREE_WORK
35 :
36 48 : int LG_check_coarsen
37 : (
38 : // outputs:
39 : GrB_Matrix *coarsened, // coarsened adjacency
40 : // inputs:
41 : GrB_Matrix A, // input adjacency (for the purposes of testing, is FP64)
42 : GrB_Vector parent, // parent mapping. Must not be NULL.
43 : GrB_Vector newlabel, // new labels of nodes, used to populate resulting adjacency matrix, can be NULL if preserve_mapping = 1, else must be a valid result
44 : GrB_Vector inv_newlabel, // inverse of newlabel, can be NULL if preserve_mapping = 1, else must be a valid result
45 : int preserve_mapping, // whether to preserve the original namespace of nodes
46 : int combine_weights, // whether to combine the weights of edges that collapse together
47 : char *msg
48 : )
49 : {
50 48 : GrB_Matrix result = NULL ;
51 :
52 : GrB_Index n ;
53 : GrB_Index nvals ;
54 :
55 48 : GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
56 48 : GRB_TRY (GrB_Matrix_nvals (&nvals, A)) ;
57 :
58 48 : GrB_Index n_new = n ;
59 :
60 : // check that parent mapping is well-formed and is compressed (i.e. p[p[i]] = p[i] for all i)
61 : // also calculate n_new
62 12288 : for (GrB_Index i = 0 ; i < n ; i++) {
63 : uint64_t par ;
64 12240 : GrB_Info status = GrB_Vector_extractElement (&par, parent, i) ;
65 12240 : LG_ASSERT (status == GrB_SUCCESS, GrB_INVALID_VALUE) ;
66 12240 : LG_ASSERT (par >= 0 && par < n, GrB_INVALID_INDEX) ;
67 :
68 : uint64_t grandpa ;
69 12240 : GRB_TRY (GrB_Vector_extractElement (&grandpa, parent, par)) ;
70 12240 : LG_ASSERT (grandpa == par, GrB_INVALID_VALUE) ;
71 :
72 12240 : if (par != i && (!preserve_mapping)) {
73 : // make sure that there is no new label for nodes that get discarded
74 : uint64_t dummy ;
75 3031 : status = GrB_Vector_extractElement (&dummy, newlabel, i) ;
76 3031 : LG_ASSERT (status == GrB_NO_VALUE, GrB_INVALID_VALUE) ;
77 : // also update new number of nodes
78 3031 : n_new-- ;
79 : }
80 : }
81 :
82 48 : if (!preserve_mapping) {
83 : // if preserve_mapping = false, newlabel is not the identity and must be checked
84 : bool *occ ;
85 24 : GrB_Index num_entries = 0 ;
86 24 : LG_TRY (LAGraph_Malloc ((void**)(&occ), n, sizeof(bool), msg)) ;
87 24 : memset (occ, 0, n * sizeof(bool)) ;
88 :
89 : // check that newlabel vector is well-formed (entries must form a permutation of [0...(n_new - 1)])
90 6144 : for (GrB_Index i = 0 ; i < n ; i++) {
91 : uint64_t new_label ;
92 6120 : GrB_Info status = GrB_Vector_extractElement (&new_label, newlabel, i) ;
93 6120 : GRB_TRY (status) ; // check for errors
94 6120 : if (status == GrB_NO_VALUE) {
95 3031 : continue ;
96 : }
97 3089 : num_entries++ ;
98 3089 : GRB_TRY (GrB_Vector_extractElement (&new_label, newlabel, i)) ;
99 :
100 3089 : LG_ASSERT (new_label >= 0 && new_label < n_new, GrB_INVALID_INDEX) ;
101 3089 : LG_ASSERT (!occ[new_label], GrB_INVALID_VALUE) ;
102 3089 : occ[new_label] = 1 ;
103 : }
104 24 : LG_ASSERT (num_entries == n_new, GrB_INVALID_VALUE) ;
105 24 : LG_TRY (LAGraph_Free ((void**)(&occ), msg)) ;
106 :
107 : // check inv_newlabel
108 3113 : for (GrB_Index i = 0 ; i < n_new ; i++) {
109 : uint64_t old_label ;
110 3089 : GrB_Info status= GrB_Vector_extractElement (&old_label, inv_newlabel, i) ;
111 3089 : LG_ASSERT (status == GrB_SUCCESS, GrB_INVALID_VALUE) ;
112 :
113 : uint64_t new_label ; // entry in newlabel, check that it matches i
114 3089 : status = GrB_Vector_extractElement (&new_label, newlabel, old_label) ;
115 3089 : LG_ASSERT (status == GrB_SUCCESS, GrB_INVALID_VALUE) ;
116 :
117 3089 : LG_ASSERT (new_label == i, GrB_INVALID_VALUE) ;
118 : }
119 : }
120 :
121 48 : GRB_TRY (GrB_Matrix_new (&result, GrB_FP64, n_new, n_new)) ;
122 :
123 48 : GrB_Index *rows = NULL, *cols = NULL ;
124 48 : double *vals = NULL ;
125 :
126 48 : LG_TRY (LAGraph_Malloc ((void**)(&rows), nvals, sizeof(GrB_Index), msg)) ;
127 48 : LG_TRY (LAGraph_Malloc ((void**)(&cols), nvals, sizeof(GrB_Index), msg)) ;
128 48 : LG_TRY (LAGraph_Malloc ((void**)(&vals), nvals, sizeof(double), msg)) ;
129 :
130 48 : GRB_TRY (GrB_Matrix_extractTuples (rows, cols, vals, &nvals, A)) ;
131 :
132 1981872 : for (GrB_Index i = 0 ; i < nvals ; i++) {
133 1981824 : GrB_Index u = rows [i] ;
134 1981824 : GrB_Index v = cols [i] ;
135 :
136 1981824 : if (u > v) {
137 : // only consider upper-triangular entries (don't duplicate edges)
138 996979 : continue ;
139 : }
140 :
141 : uint64_t u_par, v_par ;
142 :
143 990912 : GRB_TRY (GrB_Vector_extractElement (&u_par, parent, u)) ;
144 990912 : GRB_TRY (GrB_Vector_extractElement (&v_par, parent, v)) ;
145 :
146 990912 : if (u_par == v_par) {
147 : // both nodes part of same coarsened component
148 6067 : continue ;
149 : }
150 : uint64_t u_par_newlabel, v_par_newlabel ;
151 984845 : if (preserve_mapping) {
152 : // new labels are the same as old labels
153 492408 : u_par_newlabel = u_par ;
154 492408 : v_par_newlabel = v_par ;
155 : } else {
156 : // find new labels
157 492437 : GRB_TRY (GrB_Vector_extractElement (&u_par_newlabel, newlabel, u_par)) ;
158 492437 : GRB_TRY (GrB_Vector_extractElement (&v_par_newlabel, newlabel, v_par)) ;
159 : }
160 984845 : double res_weight = 1 ;
161 :
162 984845 : if (combine_weights) {
163 : // current weight of edge between u_par and v_par
164 : double curr_weight ;
165 :
166 492401 : GrB_Info status = GrB_Matrix_extractElement (&curr_weight, result, u_par_newlabel, v_par_newlabel) ;
167 492401 : GRB_TRY (status) ; // check for errors
168 :
169 492401 : if (status == GrB_NO_VALUE) {
170 299296 : curr_weight = 0 ;
171 : }
172 :
173 : // weight of the current edge being added
174 492401 : double my_weight = vals [i] ;
175 492401 : res_weight = curr_weight + my_weight ;
176 : }
177 :
178 984845 : GRB_TRY (GrB_Matrix_setElement (result, res_weight, u_par_newlabel, v_par_newlabel)) ;
179 984845 : GRB_TRY (GrB_Matrix_setElement (result, res_weight, v_par_newlabel, u_par_newlabel)) ;
180 : }
181 48 : (*coarsened) = result ;
182 :
183 48 : LG_TRY (LAGraph_Free ((void**)(&rows), msg)) ;
184 48 : LG_TRY (LAGraph_Free ((void**)(&cols), msg)) ;
185 48 : LG_TRY (LAGraph_Free ((void**)(&vals), msg)) ;
186 :
187 48 : return (GrB_SUCCESS) ;
188 : }
|
