Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/src/test/test_RichClubCoefficient.c: test cases for
3 : // LAGraph_RichClubCoefficient
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 : //-----------------------------------------------------------------------------
16 :
17 : // This program tests Rich Club Coefficient by comparing it to know values.
18 :
19 : #include <stdio.h>
20 : #include <acutest.h>
21 : #include <LAGraphX.h>
22 : #include <LAGraph_test.h>
23 : #include <LG_Xtest.h>
24 : #include <LG_test.h>
25 :
26 : char msg [LAGRAPH_MSG_LEN] ;
27 :
28 : GrB_Matrix A = NULL, C = NULL;
29 : GrB_Vector rcc = NULL, check_rcc = NULL ;
30 : LAGraph_Graph G = NULL ;
31 :
32 : #define LEN 512
33 : char filename [LEN+1] ;
34 : typedef struct
35 : {
36 : double *rcc ; // for unweighted matchings, the size of the matching. For weighted, sum of edge weights
37 : uint64_t n;
38 : const char *name ; // matrix file name
39 : }
40 : matrix_info ;
41 :
42 : double rcc1[] = {0.08489795918367347, 0.09042553191489362, 0.11806543385490754,
43 : 0.15270935960591134, 0.17543859649122806, 0.18681318681318682,
44 : 0.3333333333333333, 0.3333333333333333};
45 :
46 : double rcc2[] = {0.048040201005025124, 0.048040201005025124,
47 : 0.04842393787117405, 0.04945054945054945, 0.05129490392648287,
48 : 0.052702702702702706, 0.05523809523809524, 0.0613164184592756,
49 : 0.06755555555555555, 0.07603960396039604, 0.08637747336377473,
50 : 0.09183673469387756, 0.09090909090909091, 0.11578947368421053,
51 : 0.15555555555555556, 0.16666666666666666, 0.0};
52 :
53 : double rcc3[] = {0.020418922066450775, 0.020418922066450775,
54 : 0.020418922066450775, 0.020418922066450775, 0.020683173955750592,
55 : 0.02150664338158559, 0.02150664338158559, 0.02150664338158559,
56 : 0.02150664338158559, 0.021543516982986302, 0.02175414105479627,
57 : 0.02177185436416472, 0.0218052051134787, 0.021857560922981484,
58 : 0.02201878369318151, 0.022188402920223206, 0.022804582640104137,
59 : 0.02498473901586159, 0.025249731948717845, 0.02596385205080857,
60 : 0.027247042660294644, 0.027751420992800303, 0.028748882924051613,
61 : 0.030170594138205473, 0.031102722135686933, 0.03269071555292726,
62 : 0.03991334958028703, 0.04169452474008947, 0.04259653806582863,
63 : 0.044304609453855226, 0.04526841567726286, 0.04650692548781721,
64 : 0.049532888465204955, 0.05002586270597798, 0.05063092496587295,
65 : 0.05300441583096034, 0.054629398879867785, 0.05653826181371855,
66 : 0.059291297964366496, 0.06080825884426539, 0.06422637670884515,
67 : 0.06768885564697083, 0.06889041561605802, 0.0701751819478477,
68 : 0.07607985994153141, 0.07831153079788616, 0.07894806048652203,
69 : 0.08038113301271196, 0.08207037795568796, 0.0836966039974926,
70 : 0.08430976691170078, 0.08589112981595826, 0.08725832508207827,
71 : 0.10235720633666719, 0.10276089969086451, 0.10358862936809705,
72 : 0.10741510741510742, 0.1110049401354954, 0.11278770872986284,
73 : 0.11678584477269169, 0.11817043607981033, 0.12116372726010276,
74 : 0.1218450408924313, 0.12440239209741634, 0.12798272259582463,
75 : 0.13977635782747605, 0.14573643410852713, 0.14652869744786873,
76 : 0.1486150774302895, 0.15837726930369062, 0.158866930171278,
77 : 0.16537043438184124, 0.16662279547249276, 0.1688366106970758,
78 : 0.17170333945410973, 0.17634190936398067, 0.17711727724564694,
79 : 0.17787300615583443, 0.1779243342906783, 0.17813492063492065,
80 : 0.16556371804990588, 0.16556371804990588, 0.16556371804990588,
81 : 0.16556371804990588, 0.16729064039408867, 0.1701346389228886,
82 : 0.1989280560709132, 0.20149602618045817, 0.20475808607324245,
83 : 0.16666666666666666, 0.16840882694541232, 0.17894736842105263,
84 : 0.16666666666666666, 1.0} ;
85 : double rcc4[] = {0.0016506547800326698, 0.0017226315730560155,
86 : 0.0034201182512489416, 0.0037033309852068028, 0.05405405405405406};
87 : const matrix_info tests [ ] =
88 : {
89 : {rcc1, sizeof(rcc1) / sizeof(rcc1[0]), "random_unweighted_general1.mtx"},
90 : {rcc2, sizeof(rcc2) / sizeof(rcc2[0]), "random_unweighted_general2.mtx"},
91 : {rcc3, sizeof(rcc3) / sizeof(rcc3[0]), "bcsstk13.mtx"},
92 : {rcc4, sizeof(rcc4) / sizeof(rcc4[0]), "test_FW_2500.mtx"},
93 : {NULL, 0, ""}
94 : } ;
95 :
96 : const char *tests2 [ ] =
97 : {
98 : "random_unweighted_general1.mtx",
99 : "random_unweighted_general2.mtx",
100 : "bcsstk13.mtx",
101 : "bcsstk13_celeb.mtx",
102 : "test_FW_1000.mtx",
103 : "test_FW_2003.mtx",
104 : "test_FW_2500.mtx",
105 : ""
106 : } ;
107 :
108 1 : void test_RichClubCoefficient (void)
109 : {
110 : //--------------------------------------------------------------------------
111 : // start LAGraph
112 : //--------------------------------------------------------------------------
113 1 : OK (LAGraph_Init (msg)) ;
114 :
115 :
116 1 : for (int k = 0 ; ; k++)
117 4 : {
118 : //The following code taken from MIS tester
119 : // load the matrix as A
120 5 : const char *aname = tests [k].name;
121 5 : if (strlen (aname) == 0) break;
122 4 : TEST_CASE (aname) ;
123 4 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
124 4 : FILE *f = fopen (filename, "r") ;
125 4 : TEST_CHECK (f != NULL) ;
126 4 : OK (LAGraph_MMRead (&A, f, msg)) ;
127 4 : OK (fclose (f)) ;
128 4 : TEST_MSG ("Loading of valued matrix failed") ;
129 4 : printf ("\nMatrix: %s\n", aname) ;
130 4 : const double *ans = tests [k].rcc;
131 4 : const uint64_t n_ans = tests [k].n;
132 :
133 : // C = structure of A
134 4 : OK (LAGraph_Matrix_Structure (&C, A, msg)) ;
135 4 : OK (GrB_free (&A)) ;
136 :
137 : // construct a directed graph G with adjacency matrix C
138 4 : OK (LAGraph_New (&G, &C, LAGraph_ADJACENCY_DIRECTED, msg)) ;
139 4 : TEST_CHECK (C == NULL) ;
140 :
141 : // check if the pattern is symmetric
142 4 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
143 :
144 4 : if (G->is_symmetric_structure == LAGraph_FALSE)
145 : {
146 : // make the adjacency matrix symmetric
147 1 : OK (LAGraph_Cached_AT (G, msg)) ;
148 1 : OK (GrB_eWiseAdd (G->A, NULL, NULL, GrB_LOR, G->A, G->AT, NULL)) ;
149 1 : G->is_symmetric_structure = LAGraph_TRUE ;
150 : }
151 4 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
152 :
153 : // check for self-edges
154 4 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
155 4 : if (G->nself_edges != 0)
156 : {
157 : // remove self-edges
158 2 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
159 2 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
160 2 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
161 2 : TEST_CHECK (G->nself_edges == 0) ;
162 : }
163 :
164 : // compute the row degree
165 4 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
166 :
167 : //----------------------------------------------------------------------
168 : // test the algorithm
169 : //----------------------------------------------------------------------
170 :
171 4 : printf ("RCC computation begins:\n") ;
172 4 : GrB_set (GrB_GLOBAL, (int32_t) (true), GxB_BURBLE) ;
173 4 : OK(LAGraph_RichClubCoefficient ( &rcc, G, msg));
174 4 : printf("%s\n", msg);
175 4 : GrB_set (GrB_GLOBAL, (int32_t) (false), GxB_BURBLE) ;
176 4 : printf ("RCC computation ends:\n") ;
177 :
178 : //----------------------------------------------------------------------
179 : // check results
180 : //----------------------------------------------------------------------
181 4 : double comp_val = 0;
182 128 : for(int64_t i = n_ans - 1; i >= 0; --i)
183 : {
184 124 : GrB_Vector_extractElement(&comp_val, rcc, i) ;
185 124 : TEST_CHECK (
186 : comp_val - ans[i] <= 1e-10 && ans[i] - comp_val <= 1e-10) ;
187 : }
188 4 : GxB_Vector_fprint (rcc, "rcc", GxB_SHORT, stdout);
189 4 : OK (GrB_free (&rcc)) ;
190 4 : OK (LAGraph_Delete (&G, msg)) ;
191 : }
192 :
193 : //--------------------------------------------------------------------------
194 : // free everything and finalize LAGraph
195 : //--------------------------------------------------------------------------
196 1 : OK (LAGraph_Finalize (msg)) ;
197 1 : }
198 :
199 1997 : void iseq(bool *z, const double *x, const double *y)
200 : {
201 1997 : (*z) = (isnan(*x) && isnan(*y)) ||*x == *y ;
202 1997 : }
203 : //------------------------------------------------------------------------------
204 : // test RichClubCoefficient vs C code
205 : //------------------------------------------------------------------------------
206 1 : void test_RCC_Check (void)
207 : {
208 : //--------------------------------------------------------------------------
209 : // start LAGraph
210 : //--------------------------------------------------------------------------
211 1 : OK (LAGraph_Init (msg)) ;
212 1 : GrB_BinaryOp iseqFP = NULL ;
213 1 : OK (GrB_BinaryOp_new (
214 : &iseqFP, (GxB_binary_function) iseq, GrB_BOOL, GrB_FP64, GrB_FP64)) ;
215 : // OK (GxB_BinaryOp_new (
216 : // &iseqFP, (GxB_binary_function) iseq,
217 : // GrB_BOOL, GrB_FP64, GrB_FP64, "iseq", ISEQ)) ;
218 1 : for (int k = 0 ; ; k++)
219 7 : {
220 : //The following code taken from MIS tester
221 : // load the matrix as A
222 8 : const char *aname = tests2 [k];
223 8 : if (strlen (aname) == 0) break;
224 7 : TEST_CASE (aname) ;
225 7 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
226 7 : FILE *f = fopen (filename, "r") ;
227 7 : TEST_CHECK (f != NULL) ;
228 7 : OK (LAGraph_MMRead (&A, f, msg)) ;
229 7 : OK (fclose (f)) ;
230 7 : TEST_MSG ("Loading of valued matrix failed") ;
231 7 : printf ("\nMatrix: %s\n", aname) ;
232 :
233 : // C = structure of A
234 7 : OK (LAGraph_Matrix_Structure (&C, A, msg)) ;
235 7 : OK (GrB_free (&A)) ;
236 :
237 : // construct a directed graph G with adjacency matrix C
238 7 : OK (LAGraph_New (&G, &C, LAGraph_ADJACENCY_DIRECTED, msg)) ;
239 7 : TEST_CHECK (C == NULL) ;
240 :
241 : // check if the pattern is symmetric
242 7 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
243 :
244 7 : if (G->is_symmetric_structure == LAGraph_FALSE)
245 : {
246 : // make the adjacency matrix symmetric
247 2 : OK (LAGraph_Cached_AT (G, msg)) ;
248 2 : OK (GrB_eWiseAdd (G->A, NULL, NULL, GrB_LOR, G->A, G->AT, NULL)) ;
249 2 : G->is_symmetric_structure = LAGraph_TRUE ;
250 : }
251 7 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
252 :
253 : // check for self-edges
254 7 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
255 7 : if (G->nself_edges != 0)
256 : {
257 : // remove self-edges
258 5 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
259 5 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
260 5 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
261 5 : TEST_CHECK (G->nself_edges == 0) ;
262 : }
263 :
264 : // compute the row degree
265 7 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
266 :
267 : //----------------------------------------------------------------------
268 : // test the algorithm
269 : //----------------------------------------------------------------------
270 :
271 : // GrB_set (GrB_GLOBAL, (int32_t) (true), GxB_BURBLE) ;
272 7 : OK(LAGraph_RichClubCoefficient ( &rcc, G, msg));
273 : // GrB_set (GrB_GLOBAL, (int32_t) (false), GxB_BURBLE) ;
274 :
275 7 : OK(LG_check_rcc(&check_rcc, G, msg));
276 : //----------------------------------------------------------------------
277 : // check results
278 : //----------------------------------------------------------------------
279 7 : bool flag = false;
280 7 : OK (LAGraph_Vector_IsEqualOp(&flag, rcc, check_rcc, iseqFP, msg)) ;
281 7 : TEST_CHECK (flag) ;
282 7 : GxB_Vector_fprint (rcc, "rcc", GxB_SHORT, stdout);
283 7 : GxB_Vector_fprint (check_rcc, "check_rcc", GxB_SHORT, stdout);
284 7 : OK (GrB_free (&rcc)) ;
285 7 : OK (GrB_free (&check_rcc)) ;
286 7 : OK (LAGraph_Delete (&G, msg)) ;
287 : }
288 :
289 : //--------------------------------------------------------------------------
290 : // free everything and finalize LAGraph
291 : //--------------------------------------------------------------------------
292 1 : OK (GrB_free (&iseqFP)) ;
293 1 : OK (LAGraph_Finalize (msg)) ;
294 1 : }
295 : //------------------------------------------------------------------------------
296 : // test_RCC_brutal:
297 : //------------------------------------------------------------------------------
298 :
299 : #if LAGRAPH_SUITESPARSE
300 1 : void test_rcc_brutal (void)
301 : {
302 : //--------------------------------------------------------------------------
303 : // start LAGraph
304 : //--------------------------------------------------------------------------
305 1 : OK (LG_brutal_setup (msg)) ;
306 :
307 :
308 1 : for (int k = 0 ; ; k++)
309 4 : {
310 : // load the matrix as A
311 5 : const char *aname = tests [k].name;
312 5 : if (strlen (aname) == 0) break;
313 4 : TEST_CASE (aname) ;
314 4 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
315 4 : FILE *f = fopen (filename, "r") ;
316 4 : TEST_CHECK (f != NULL) ;
317 4 : OK (LAGraph_MMRead (&A, f, msg)) ;
318 4 : OK (fclose (f)) ;
319 4 : TEST_MSG ("Loading of valued matrix failed") ;
320 4 : printf ("\nMatrix: %s\n", aname) ;
321 4 : const double *ans = tests [k].rcc;
322 4 : const uint64_t n_ans = tests [k].n;
323 :
324 : // C = structure of A
325 4 : OK (LAGraph_Matrix_Structure (&C, A, msg)) ;
326 4 : OK (GrB_free (&A)) ;
327 :
328 : // construct a directed graph G with adjacency matrix C
329 4 : OK (LAGraph_New (&G, &C, LAGraph_ADJACENCY_DIRECTED, msg)) ;
330 4 : TEST_CHECK (C == NULL) ;
331 :
332 : // check if the pattern is symmetric
333 4 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
334 :
335 4 : if (G->is_symmetric_structure == LAGraph_FALSE)
336 : {
337 : // make the adjacency matrix symmetric
338 1 : OK (LAGraph_Cached_AT (G, msg)) ;
339 1 : OK (GrB_eWiseAdd (G->A, NULL, NULL, GrB_LOR, G->A, G->AT, NULL)) ;
340 1 : G->is_symmetric_structure = LAGraph_TRUE ;
341 : }
342 4 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
343 :
344 : // check for self-edges
345 4 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
346 4 : if (G->nself_edges != 0)
347 : {
348 : // remove self-edges
349 2 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
350 2 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
351 2 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
352 2 : TEST_CHECK (G->nself_edges == 0) ;
353 : }
354 :
355 : // compute the row degree
356 4 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
357 :
358 4 : LG_BRUTAL_BURBLE (LAGraph_CheckGraph (G, msg)) ;
359 : //----------------------------------------------------------------------
360 : // test the algorithm
361 : //----------------------------------------------------------------------
362 :
363 4 : printf ("RCC computation begins:\n") ;
364 : // GrB_set (GrB_GLOBAL, (int32_t) (true), GxB_BURBLE) ;
365 391 : LG_BRUTAL_BURBLE (LAGraph_RichClubCoefficient( &rcc, G, msg));
366 4 : printf("%s\n", msg);
367 : // GrB_set (GrB_GLOBAL, (int32_t) (false), GxB_BURBLE) ;
368 4 : printf ("RCC computation ends:\n") ;
369 :
370 : //----------------------------------------------------------------------
371 : // check results
372 : //----------------------------------------------------------------------
373 4 : double comp_val = 0;
374 128 : for(int64_t i = n_ans - 1; i >= 0; --i)
375 : {
376 124 : OK (GrB_Vector_extractElement(&comp_val, rcc, i)) ;
377 124 : TEST_CHECK (fabs(comp_val - ans[i]) <= 1e-15) ;
378 : }
379 4 : OK (GrB_free (&rcc)) ;
380 4 : OK (LAGraph_Delete (&G, msg)) ;
381 : }
382 :
383 : //--------------------------------------------------------------------------
384 : // free everything and finalize LAGraph
385 : //--------------------------------------------------------------------------
386 1 : OK(LG_brutal_teardown(msg)) ;
387 1 : }
388 : #endif
389 :
390 : //----------------------------------------------------------------------------
391 : // the make program is created by acutest, and it runs a list of tests:
392 : //----------------------------------------------------------------------------
393 :
394 : TEST_LIST =
395 : {
396 : {"RichClubCoefficient", test_RichClubCoefficient},
397 : #if LG_SUITESPARSE_GRAPHBLAS_V10
398 : {"RichClubCoefficient_Check", test_RCC_Check},
399 : #endif
400 : #if LAGRAPH_SUITESPARSE
401 : {"rcc_brutal", test_rcc_brutal},
402 : #endif
403 : {NULL, NULL}
404 : } ;
|
