Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_CoarsenMatching
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : //
8 : // For additional details (including references to third party source code and
9 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
10 : // Contributors.txt for a full list of contributors. Created, in part, with
11 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
12 : // DM22-0790
13 :
14 : // Contributed by Vidith Madhu, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : /*
19 : NOTE: Unlike the other tests, this does not use .mtx files, but rather generates the test
20 : matrices using specified configurations and seeds with LAGraph_Random_Matrix
21 : */
22 :
23 : #include <stdio.h>
24 : #include <acutest.h>
25 : #include "LAGraphX.h"
26 : #include "LAGraph_test.h"
27 : #include "LG_Xtest.h"
28 : #include "LG_internal.h"
29 :
30 : char msg [LAGRAPH_MSG_LEN] ;
31 :
32 : GrB_Matrix A = NULL, A_coarse_LAGraph = NULL, A_coarse_naive = NULL ;
33 : GrB_Vector parent = NULL, newlabel = NULL, inv_newlabel = NULL ; // outputs from the Coarsen_Matching function
34 : LAGraph_Graph G = NULL ;
35 :
36 : typedef struct
37 : {
38 : // options for building graph:
39 : GrB_Index n ; // number of nodes in the graph
40 : double density ; // density of the matrix
41 : uint64_t seed ; // seed used to generate the graph for this test
42 :
43 : // options for coarsening (see Coarsen_Matching function for details):
44 : LAGraph_Matching_kind matching_type ;
45 : int preserve_mapping ;
46 : int combine_weights ;
47 :
48 : const char *name ;
49 : }
50 : matrix_info ;
51 :
52 : const matrix_info tests [ ] = {
53 : // random, preserve, combine
54 : {10, 0.3, 55, LAGraph_Matching_unweighted, 1, 1, "small-random-preserve-combine"},
55 : {500, 0.4, 16, LAGraph_Matching_unweighted, 1, 1, "large-random-preserve-combine"},
56 : // random, preserve, nocombine
57 : {10, 0.3, 62, LAGraph_Matching_unweighted, 1, 0, "small-random-preserve-nocombine"},
58 : {500, 0.4, 21, LAGraph_Matching_unweighted, 1, 0, "large-random-preserve-nocombine"},
59 : // random, nopreserve, combine
60 : {10, 0.3, 23, LAGraph_Matching_unweighted, 0, 1, "small-random-nopreserve-combine"},
61 : {500, 0.4, 31, LAGraph_Matching_unweighted, 0, 1, "large-random-nopreserve-combine"},
62 : // random, nopreserve, nocombine
63 : {10, 0.3, 92, LAGraph_Matching_unweighted, 0, 0, "small-random-nopreserve-nocombine"},
64 : {500, 0.4, 44, LAGraph_Matching_unweighted, 0, 0, "large-random-nopreserve-nocombine"},
65 :
66 : // same as above except weighted matching (mix of light and heavy)
67 : // random, preserve, combine
68 : {10, 0.3, 55, LAGraph_Matching_heavy, 1, 1, "small-random-preserve-combine"},
69 : {500, 0.4, 16, LAGraph_Matching_light, 1, 1, "large-random-preserve-combine"},
70 : // random, preserve, nocombine
71 : {10, 0.3, 62, LAGraph_Matching_light, 1, 0, "small-random-preserve-nocombine"},
72 : {500, 0.4, 21, LAGraph_Matching_heavy, 1, 0, "large-random-preserve-nocombine"},
73 : // random, nopreserve, combine
74 : {10, 0.3, 23, LAGraph_Matching_light, 0, 1, "small-random-nopreserve-combine"},
75 : {500, 0.4, 31, LAGraph_Matching_heavy, 0, 1, "large-random-nopreserve-combine"},
76 : // random, nopreserve, nocombine
77 : {10, 0.3, 92, LAGraph_Matching_heavy, 0, 0, "small-random-nopreserve-nocombine"},
78 : {500, 0.4, 44, LAGraph_Matching_light, 0, 0, "large-random-nopreserve-nocombine"},
79 : {0, 0, 0, 0, 0, 0, ""}
80 : } ;
81 :
82 : #define LEN 512
83 : #define SEEDS_PER_TEST 3
84 :
85 : char filename [LEN+1] ;
86 : char msg [LAGRAPH_MSG_LEN] ;
87 :
88 1 : void test_Coarsen_Matching (void) {
89 : #if LAGRAPH_SUITESPARSE
90 :
91 1 : OK (LAGraph_Init (msg)) ;
92 : // OK (LG_SET_BURBLE (true)) ;
93 :
94 1 : for (int k = 0 ; ; k++)
95 16 : {
96 17 : const char *aname = tests [k].name ;
97 17 : if (strlen (aname) == 0) { break ; }
98 16 : TEST_CASE (aname) ;
99 :
100 : // ================= first generate graph (code from test_MaximalMatching) =================
101 16 : GrB_Index n = tests [k].n ;
102 :
103 16 : GrB_Matrix A_dup = NULL ;
104 16 : A = NULL ;
105 : GrB_Index nvals ;
106 : GrB_Index *rows, *cols ;
107 : double *vals ;
108 :
109 16 : OK (LAGraph_Random_Matrix (&A_dup, GrB_FP64, n, n, tests [k].density, tests [k].seed, msg)) ;
110 16 : OK (GrB_Matrix_new (&A, GrB_FP64, n, n)) ;
111 :
112 16 : OK (GrB_Matrix_nvals (&nvals, A_dup)) ;
113 :
114 16 : OK (LAGraph_Malloc ((void**)(&rows), nvals, sizeof(GrB_Index), msg)) ;
115 16 : OK (LAGraph_Malloc ((void**)(&cols), nvals, sizeof(GrB_Index), msg)) ;
116 16 : OK (LAGraph_Malloc ((void**)(&vals), nvals, sizeof(double), msg)) ;
117 :
118 16 : OK (GrB_Matrix_extractTuples (rows, cols, vals, &nvals, A_dup)) ;
119 :
120 659640 : for (GrB_Index i = 0; i < nvals; i++) {
121 659624 : GrB_Index row = rows [i];
122 659624 : GrB_Index col = cols [i];
123 659624 : double val = vals [i];
124 659624 : if (col < row){
125 : // use lower triangular entries for the entire matrix
126 330304 : OK (GrB_Matrix_setElement (A, val, col, row)) ;
127 330304 : OK (GrB_Matrix_setElement (A, val, row, col)) ;
128 : }
129 : }
130 :
131 16 : OK (GrB_free (&A_dup)) ;
132 16 : OK (LAGraph_Free ((void**)(&rows), msg)) ;
133 16 : OK (LAGraph_Free ((void**)(&cols), msg)) ;
134 16 : OK (LAGraph_Free ((void**)(&vals), msg)) ;
135 16 : OK (GrB_wait (A, GrB_MATERIALIZE)) ;
136 :
137 : // ================== graph generation done ======================================
138 :
139 16 : TEST_CHECK (A != NULL) ;
140 16 : TEST_MSG ("Building of adjacency matrix failed") ;
141 :
142 16 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
143 16 : TEST_CHECK (A == NULL) ;
144 16 : TEST_CHECK (G->A != NULL) ;
145 16 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
146 16 : OK (LAGraph_Cached_AT (G, msg)) ;
147 :
148 : // remove self-edges
149 16 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
150 16 : TEST_CHECK (G->nself_edges == 0) ;
151 :
152 16 : bool ok = 0;
153 16 : OK (LAGraph_Matrix_IsEqual (&ok, G->A, G->AT, msg)) ;
154 16 : TEST_CHECK (ok) ;
155 16 : TEST_MSG ("Input graph is not undirected") ;
156 16 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
157 :
158 16 : uint64_t matching_seed = 0 ;
159 64 : for (int i = 0; i < SEEDS_PER_TEST ; i++) {
160 :
161 48 : if (i == SEEDS_PER_TEST-1)
162 : {
163 : // convert graph to FP32 for the last test
164 16 : GrB_Matrix A_fp32 = NULL ;
165 16 : OK (GrB_Matrix_new (&A_fp32, GrB_FP32, n, n)) ;
166 16 : OK (GrB_assign (A_fp32, NULL, NULL, G->A, GrB_ALL, n, GrB_ALL, n, NULL)) ;
167 16 : OK (GrB_free (&(G->A))) ;
168 16 : OK (GrB_free (&(G->AT))) ;
169 16 : G->A = A_fp32 ;
170 16 : A_fp32 = NULL ;
171 : }
172 :
173 48 : OK (LAGraph_Coarsen_Matching (
174 : &A_coarse_LAGraph,
175 : &parent,
176 : &newlabel,
177 : &inv_newlabel,
178 : G,
179 : tests [k].matching_type,
180 : tests [k].preserve_mapping,
181 : tests [k].combine_weights,
182 : matching_seed,
183 : msg
184 : )) ;
185 48 : OK (LG_check_coarsen (
186 : &A_coarse_naive,
187 : G->A,
188 : parent,
189 : (newlabel == NULL ? NULL : newlabel),
190 : (inv_newlabel == NULL ? NULL : inv_newlabel),
191 : tests [k].preserve_mapping,
192 : tests [k].combine_weights,
193 : msg
194 : )) ;
195 :
196 48 : if (newlabel != NULL) {
197 24 : GrB_free (&newlabel) ;
198 24 : GrB_free (&inv_newlabel) ;
199 : }
200 : // Check parent vector for matching-specific correctness (must be derived from a valid matching)
201 : // requirements: no node is the parent of more than 2 nodes, and if p[i] != i, then A[i][p[i]] exists
202 : int8_t *freq ;
203 48 : OK (LAGraph_Malloc ((void**)(&freq), n, sizeof(int8_t), msg)) ;
204 48 : memset(freq, 0, n * sizeof(int8_t)) ;
205 :
206 12288 : for (GrB_Index i = 0 ; i < n ; i++) {
207 : uint64_t par ;
208 12240 : OK (GrB_Vector_extractElement (&par, parent, i)) ;
209 12240 : freq [par]++ ;
210 12240 : TEST_CHECK (freq [par] <= 2) ;
211 12240 : TEST_MSG ("Parent vector not from a valid matching for test: %s\n", tests [k].name) ;
212 :
213 12240 : if (par != i) {
214 : // make sure that (i, par) is a edge in the graph
215 6067 : TEST_CHECK (GxB_Matrix_isStoredElement (G->A, i, par) == GrB_SUCCESS) ;
216 6067 : TEST_MSG ("Parent vector not from a valid matching for test: %s\n", tests [k].name) ;
217 : }
218 : }
219 48 : GrB_free (&parent) ;
220 :
221 48 : OK (LAGraph_Free ((void**)(&freq), msg)) ;
222 :
223 : #if 0
224 : // OK (LAGraph_Matrix_Print (G->A, LAGraph_COMPLETE, stdout, msg)) ;
225 : OK (LAGraph_Matrix_Print (A_coarse_LAGraph, LAGraph_COMPLETE, stdout, msg)) ;
226 : OK (LAGraph_Matrix_Print (A_coarse_naive, LAGraph_COMPLETE, stdout, msg)) ;
227 : // OK (LAGraph_Vector_Print (parent[0], LAGraph_COMPLETE, stdout, msg)) ;
228 : // OK (LAGraph_Vector_Print (newlabels[0], LAGraph_COMPLETE, stdout, msg)) ;
229 : #endif
230 :
231 : GrB_Matrix Delta ;
232 : GrB_Index ncoarse ;
233 48 : GrB_Matrix_nrows (&ncoarse, A_coarse_LAGraph) ;
234 48 : GrB_Matrix_new (&Delta, GrB_FP64, ncoarse, ncoarse) ;
235 48 : GrB_eWiseAdd (Delta, NULL, NULL, GrB_MINUS_FP64, A_coarse_LAGraph, A_coarse_naive,
236 : NULL) ;
237 48 : GrB_apply (Delta, NULL, NULL, GrB_ABS_FP64, Delta, NULL) ;
238 : // OK (LAGraph_Matrix_Print (Delta, LAGraph_COMPLETE, stdout, msg)) ;
239 48 : double error = 0 ;
240 48 : GrB_reduce (&error, NULL, GrB_MAX_MONOID_FP64, Delta, NULL) ;
241 :
242 : // this test is wrong, it does not allow for floating point roundoff
243 : // OK (LAGraph_Matrix_IsEqual (&ok, A_coarse_LAGraph, A_coarse_naive, msg)) ;
244 : // TEST_CHECK (ok) ;
245 :
246 : // printf ("error: %g\n", error) ;
247 48 : TEST_CHECK (error < 1e-12) ;
248 48 : TEST_MSG ("Coarsened matrices do not match for test: %s", tests [k].name) ;
249 :
250 48 : OK (GrB_free (&Delta)) ;
251 48 : OK (GrB_free (&A_coarse_LAGraph)) ;
252 48 : OK (GrB_free (&A_coarse_naive)) ;
253 :
254 48 : matching_seed += tests [k].n ;
255 : }
256 16 : OK (LAGraph_Delete (&G, msg)) ;
257 : }
258 :
259 1 : OK (LAGraph_Finalize (msg)) ;
260 : #endif
261 1 : }
262 :
263 1 : void test_Coarsen_Matching_Errors(void) {
264 : #if LAGRAPH_SUITESPARSE
265 :
266 1 : OK (LAGraph_Init (msg)) ;
267 :
268 1 : GrB_Matrix C = NULL ;
269 1 : OK (GrB_Matrix_new (&A, GrB_FP64, 5, 5)) ;
270 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
271 :
272 1 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
273 :
274 1 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
275 1 : TEST_CHECK (G->nself_edges == 0) ;
276 :
277 : // directed graph
278 1 : GrB_Info result = LAGraph_Coarsen_Matching (&C, NULL, NULL, NULL, G, 0, 0, 0, 0, msg) ;
279 1 : printf ("\nresult: %d %s\n", result, msg) ;
280 1 : TEST_CHECK (result == LAGRAPH_INVALID_GRAPH) ;
281 1 : TEST_CHECK (C == NULL) ;
282 :
283 1 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
284 1 : G->nself_edges = 1 ;
285 :
286 : // non-zero self-loops
287 1 : result = LAGraph_Coarsen_Matching (&C, NULL, NULL, NULL, G, 0, 0, 0, 0, msg) ;
288 1 : printf ("\nresult: %d %s\n", result, msg) ;
289 1 : TEST_CHECK (result == LAGRAPH_NO_SELF_EDGES_ALLOWED) ;
290 1 : TEST_CHECK (C == NULL) ;
291 :
292 1 : G->nself_edges = 0;
293 :
294 : // output coarsened matrix pointer is NULL
295 1 : result = LAGraph_Coarsen_Matching (NULL, NULL, NULL, NULL, G, 0, 0, 0, 0, msg) ;
296 1 : printf ("\nresult: %d %s\n", result, msg) ;
297 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
298 :
299 1 : OK (LAGraph_Delete (&G, msg)) ;
300 1 : OK (LAGraph_Finalize (msg)) ;
301 : #endif
302 1 : }
303 :
304 :
305 1 : void test_Coarsen_Matching_NullInputs(void) {
306 : #if LAGRAPH_SUITESPARSE
307 :
308 1 : OK (LAGraph_Init (msg)) ;
309 :
310 :
311 1 : GrB_Matrix C = NULL ;
312 1 : OK (GrB_Matrix_new (&A, GrB_FP64, 5, 5)) ;
313 :
314 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
315 1 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
316 1 : OK (LAGraph_Cached_AT (G, msg) < 0) ; // warning is expected; check for error
317 :
318 : // do this to get full code coverage and catch any unexpected behavior
319 1 : OK (LAGraph_Coarsen_Matching (&C, NULL, NULL, NULL, G, 0, 0, 1, 42, msg)) ;
320 :
321 1 : OK (GrB_free (&C)) ;
322 : // do it with parent, inv_newlabels NULL but newlabels not NULL
323 1 : OK (LAGraph_Coarsen_Matching (&C, NULL, &newlabel, NULL, G, 0, 0, 1, 42, msg)) ;
324 :
325 1 : OK (GrB_free (&C)) ;
326 1 : OK (LAGraph_Delete (&G, msg)) ;
327 :
328 1 : TEST_CHECK (newlabel != NULL) ;
329 1 : TEST_MSG ("Null input check failed!\n") ;
330 :
331 1 : OK (GrB_free (&newlabel)) ;
332 1 : OK (LAGraph_Finalize (msg)) ;
333 : #endif
334 1 : }
335 :
336 : TEST_LIST = {
337 : {"Coarsen_Matching", test_Coarsen_Matching},
338 : {"Coarsen_Matching_Errors", test_Coarsen_Matching_Errors},
339 : {"Coarsen_Matching_NullInputs", test_Coarsen_Matching_NullInputs},
340 : {NULL, NULL}
341 : } ;
|
