Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/src/test/test_TriangleCount.c: test cases for triangle
3 : // counting algorithms
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 Scott McMillan, SEI, and Timothy A. Davis, Texas A&M
16 : // University
17 :
18 : //-----------------------------------------------------------------------------
19 :
20 : #include <stdio.h>
21 : #include <acutest.h>
22 :
23 : #include <LAGraph_test.h>
24 : #include <graph_zachary_karate.h>
25 :
26 : char msg[LAGRAPH_MSG_LEN];
27 : LAGraph_Graph G = NULL;
28 :
29 : #define LEN 512
30 : char filename [LEN+1] ;
31 :
32 : typedef struct
33 : {
34 : uint64_t ntriangles ; // # triangles in original matrix
35 : const char *name ; // matrix filename
36 : }
37 : matrix_info ;
38 :
39 : const matrix_info files [ ] =
40 : {
41 : { 45, "karate.mtx" },
42 : { 11, "A.mtx" },
43 : { 2016, "jagmesh7.mtx" },
44 : { 6, "ldbc-cdlp-undirected-example.mtx" },
45 : { 4, "ldbc-undirected-example.mtx" },
46 : { 5, "ldbc-wcc-example.mtx" },
47 : { 0, "LFAT5.mtx" },
48 : { 342300, "bcsstk13.mtx" },
49 : { 0, "tree-example.mtx" },
50 : { 0, "" },
51 : } ;
52 :
53 : //****************************************************************************
54 7 : void setup(void)
55 : {
56 7 : LAGraph_Init(msg);
57 : int retval;
58 :
59 7 : GrB_Matrix A = NULL;
60 :
61 7 : GrB_Matrix_new(&A, GrB_UINT32, ZACHARY_NUM_NODES, ZACHARY_NUM_NODES);
62 7 : GrB_Matrix_build(A, ZACHARY_I, ZACHARY_J, ZACHARY_V, ZACHARY_NUM_EDGES,
63 : GrB_LOR);
64 :
65 7 : retval = LAGraph_New(&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg);
66 7 : TEST_CHECK(retval == 0);
67 7 : TEST_MSG("retval = %d (%s)", retval, msg);
68 :
69 7 : retval = LAGraph_Cached_NSelfEdges(G, msg);
70 7 : TEST_CHECK(retval == 0);
71 7 : TEST_MSG("retval = %d (%s)", retval, msg);
72 :
73 7 : TEST_CHECK(G->nself_edges == 0);
74 7 : }
75 :
76 : //****************************************************************************
77 7 : void teardown(void)
78 : {
79 7 : int retval = LAGraph_Delete(&G, msg);
80 7 : TEST_CHECK(retval == 0);
81 7 : TEST_MSG("retval = %d (%s)", retval, msg);
82 :
83 7 : G = NULL;
84 7 : LAGraph_Finalize(msg);
85 7 : }
86 :
87 : //****************************************************************************
88 : //****************************************************************************
89 1 : void test_TriangleCount_Methods1(void)
90 : {
91 1 : setup();
92 : int retval;
93 1 : uint64_t ntriangles = 0UL;
94 :
95 : // with presort
96 1 : LAGr_TriangleCount_Presort presort = LAGr_TriangleCount_AutoSort ;
97 1 : LAGr_TriangleCount_Method method = LAGr_TriangleCount_Burkhardt ;
98 1 : ntriangles = 0UL;
99 : // LAGr_TriangleCount_Burkhardt: sum (sum ((A^2) .* A)) / 6
100 1 : retval = LAGr_TriangleCount(&ntriangles, G, &method, &presort, msg);
101 :
102 1 : TEST_CHECK(retval == 0);
103 1 : TEST_MSG("retval = %d (%s)", retval, msg);
104 :
105 1 : TEST_CHECK( ntriangles == 45 );
106 1 : TEST_MSG("numtri = %g", (double) ntriangles);
107 :
108 1 : teardown();
109 1 : }
110 :
111 : //****************************************************************************
112 1 : void test_TriangleCount_Methods2(void)
113 : {
114 1 : setup();
115 : int retval;
116 1 : uint64_t ntriangles = 0UL;
117 :
118 1 : LAGr_TriangleCount_Presort presort = LAGr_TriangleCount_AutoSort ;
119 1 : LAGr_TriangleCount_Method method = LAGr_TriangleCount_Cohen ;
120 1 : ntriangles = 0UL;
121 : // LAGr_TriangleCount_Cohen: sum (sum ((L * U) .* A)) / 2
122 1 : retval = LAGr_TriangleCount(&ntriangles, G, &method, &presort, msg);
123 1 : TEST_CHECK(retval == 0);
124 1 : TEST_MSG("retval = %d (%s)", retval, msg);
125 :
126 1 : TEST_CHECK( ntriangles == 45 );
127 1 : TEST_MSG("numtri = %g", (double) ntriangles);
128 :
129 1 : teardown();
130 1 : }
131 :
132 : //****************************************************************************
133 1 : void test_TriangleCount_Methods3(void)
134 : {
135 1 : setup();
136 : int retval;
137 1 : uint64_t ntriangles = 0UL;
138 :
139 1 : LAGr_TriangleCount_Presort presort = LAGr_TriangleCount_AutoSort ;
140 1 : LAGr_TriangleCount_Method method = LAGr_TriangleCount_Sandia_LL ;
141 1 : ntriangles = 0UL;
142 : // LAGr_TriangleCount_Sandia_LL: sum (sum ((L * L) .* L))
143 1 : retval = LAGr_TriangleCount (&ntriangles, G, &method, &presort, msg) ;
144 : // should fail (out_degrees needs to be defined)
145 1 : TEST_CHECK(retval == LAGRAPH_NOT_CACHED);
146 1 : TEST_MSG("retval = %d (%s)", retval, msg);
147 :
148 1 : retval = LAGraph_Cached_OutDegree(G, msg);
149 1 : TEST_CHECK(retval == 0);
150 1 : TEST_MSG("retval = %d (%s)", retval, msg);
151 :
152 1 : presort = LAGr_TriangleCount_AutoSort ;
153 1 : method = LAGr_TriangleCount_Sandia_LL ;
154 1 : retval = LAGr_TriangleCount(&ntriangles, G, &method, &presort, msg);
155 1 : TEST_CHECK(retval == 0);
156 1 : TEST_MSG("retval = %d (%s)", retval, msg);
157 :
158 1 : TEST_CHECK( ntriangles == 45 );
159 1 : TEST_MSG("numtri = %g", (double) ntriangles);
160 :
161 1 : teardown();
162 1 : }
163 :
164 : //****************************************************************************
165 1 : void test_TriangleCount_Methods4(void)
166 : {
167 1 : setup();
168 : int retval;
169 1 : uint64_t ntriangles = 0UL;
170 :
171 1 : LAGr_TriangleCount_Presort presort = LAGr_TriangleCount_AutoSort ;
172 1 : LAGr_TriangleCount_Method method = LAGr_TriangleCount_Sandia_UU ;
173 1 : ntriangles = 0UL;
174 : // LAGr_TriangleCount_Sandia_UU: sum (sum ((U * U) .* U))
175 1 : retval = LAGr_TriangleCount(&ntriangles, G, &method, &presort, msg);
176 : // should fail (out_degrees needs to be defined)
177 1 : TEST_CHECK(retval == LAGRAPH_NOT_CACHED);
178 1 : TEST_MSG("retval = %d (%s)", retval, msg);
179 :
180 1 : retval = LAGraph_Cached_OutDegree(G, msg);
181 1 : TEST_CHECK(retval == 0);
182 1 : TEST_MSG("retval = %d (%s)", retval, msg);
183 :
184 1 : presort = LAGr_TriangleCount_AutoSort ;
185 1 : method = LAGr_TriangleCount_Sandia_UU ;
186 1 : retval = LAGr_TriangleCount(&ntriangles, G, &method, &presort, msg);
187 1 : TEST_CHECK(retval == 0);
188 1 : TEST_MSG("retval = %d (%s)", retval, msg);
189 :
190 1 : TEST_CHECK( ntriangles == 45 );
191 1 : TEST_MSG("numtri = %g", (double) ntriangles) ;
192 :
193 1 : teardown();
194 1 : }
195 :
196 : //****************************************************************************
197 1 : void test_TriangleCount_Methods5(void)
198 : {
199 1 : setup();
200 : int retval;
201 1 : uint64_t ntriangles = 0UL;
202 :
203 1 : LAGr_TriangleCount_Presort presort = LAGr_TriangleCount_AutoSort ;
204 1 : LAGr_TriangleCount_Method method = LAGr_TriangleCount_Sandia_LUT ;
205 1 : ntriangles = 0UL;
206 : // LAGr_TriangleCount_Sandia_LUT: sum (sum ((L * U') .* L))
207 1 : retval = LAGr_TriangleCount(&ntriangles, G, &method, &presort, msg);
208 : // should fail (out_degrees needs to be defined)
209 1 : TEST_CHECK(retval == LAGRAPH_NOT_CACHED);
210 1 : TEST_MSG("retval = %d (%s)", retval, msg);
211 :
212 1 : retval = LAGraph_Cached_OutDegree(G, msg);
213 1 : TEST_CHECK(retval == 0);
214 1 : TEST_MSG("retval = %d (%s)", retval, msg);
215 :
216 1 : presort = LAGr_TriangleCount_AutoSort ;
217 1 : method = LAGr_TriangleCount_Sandia_LUT ;
218 1 : retval = LAGr_TriangleCount(&ntriangles, G, &method, &presort, msg);
219 1 : TEST_CHECK(retval == 0);
220 1 : TEST_MSG("retval = %d (%s)", retval, msg);
221 :
222 1 : TEST_CHECK( ntriangles == 45 );
223 1 : TEST_MSG("numtri = %g", (double) ntriangles) ;
224 :
225 1 : teardown();
226 1 : }
227 :
228 : //****************************************************************************
229 1 : void test_TriangleCount_Methods6(void)
230 : {
231 1 : setup();
232 : int retval;
233 1 : uint64_t ntriangles = 0UL;
234 :
235 1 : LAGr_TriangleCount_Presort presort = LAGr_TriangleCount_AutoSort ;
236 1 : LAGr_TriangleCount_Method method = LAGr_TriangleCount_Sandia_ULT ;
237 1 : ntriangles = 0UL;
238 : // LAGr_TriangleCount_Sandia_ULT: sum (sum ((U * L') .* U))
239 1 : retval = LAGr_TriangleCount(&ntriangles, G, &method, &presort, msg);
240 : // should fail (out_degrees needs to be defined)
241 1 : TEST_CHECK(retval == LAGRAPH_NOT_CACHED) ;
242 1 : TEST_MSG("retval = %d (%s)", retval, msg);
243 :
244 1 : retval = LAGraph_Cached_OutDegree(G, msg);
245 1 : TEST_CHECK(retval == 0);
246 1 : TEST_MSG("retval = %d (%s)", retval, msg);
247 :
248 1 : presort = LAGr_TriangleCount_AutoSort ;
249 1 : method = LAGr_TriangleCount_Sandia_ULT ;
250 1 : retval = LAGr_TriangleCount(&ntriangles, G, &method, &presort, msg);
251 1 : TEST_CHECK(retval == 0);
252 1 : TEST_MSG("retval = %d (%s)", retval, msg);
253 :
254 1 : TEST_CHECK( ntriangles == 45 );
255 1 : TEST_MSG("numtri = %g", (double) ntriangles) ;
256 :
257 1 : teardown();
258 1 : }
259 :
260 : //****************************************************************************
261 1 : void test_TriangleCount(void)
262 : {
263 1 : setup();
264 :
265 1 : uint64_t ntriangles = 0UL;
266 1 : int retval = LAGraph_TriangleCount(&ntriangles, G, msg);
267 : // should not fail (out_degrees will be calculated)
268 1 : TEST_CHECK(retval == 0);
269 1 : TEST_MSG("retval = %d (%s)", retval, msg);
270 :
271 1 : TEST_CHECK( ntriangles == 45 );
272 1 : TEST_MSG("numtri = %g", (double) ntriangles) ;
273 :
274 1 : OK (LG_check_tri (&ntriangles, G, msg)) ;
275 1 : TEST_CHECK( ntriangles == 45 );
276 :
277 1 : teardown();
278 1 : }
279 :
280 : //****************************************************************************
281 1 : void test_TriangleCount_many (void)
282 : {
283 1 : LAGraph_Init(msg);
284 1 : GrB_Matrix A = NULL ;
285 1 : printf ("\n") ;
286 :
287 1 : for (int k = 0 ; ; k++)
288 9 : {
289 :
290 : // load the adjacency matrix as A
291 10 : const char *aname = files [k].name ;
292 10 : uint64_t ntriangles = files [k].ntriangles ;
293 10 : if (strlen (aname) == 0) break;
294 9 : TEST_CASE (aname) ;
295 9 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
296 9 : FILE *f = fopen (filename, "r") ;
297 9 : TEST_CHECK (f != NULL) ;
298 9 : OK (LAGraph_MMRead (&A, f, msg)) ;
299 9 : OK (fclose (f)) ;
300 9 : TEST_MSG ("Loading of adjacency matrix failed") ;
301 :
302 : // create the graph
303 9 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
304 9 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
305 :
306 : // delete any diagonal entries
307 9 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
308 9 : TEST_CHECK (G->nself_edges == 0) ;
309 9 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
310 9 : TEST_CHECK (G->nself_edges == 0) ;
311 :
312 : // get the # of triangles
313 : uint64_t nt0, nt1 ;
314 9 : OK (LAGraph_TriangleCount (&nt1, G, msg)) ;
315 9 : printf ("# triangles: %g Matrix: %s\n", (double) nt1, aname) ;
316 9 : TEST_CHECK (nt1 == ntriangles) ;
317 9 : OK (LG_check_tri (&nt0, G, msg)) ;
318 9 : TEST_CHECK (nt0 == nt1) ;
319 :
320 : // convert to directed but with symmetric pattern
321 9 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
322 9 : G->is_symmetric_structure = LAGraph_TRUE ;
323 9 : OK (LAGraph_TriangleCount (&nt1, G, msg)) ;
324 9 : TEST_CHECK (nt1 == ntriangles) ;
325 :
326 9 : OK (LG_check_tri (&nt0, G, msg)) ;
327 9 : TEST_CHECK (nt0 == nt1) ;
328 :
329 : // try each method
330 72 : for (int method = 0 ; method <= 6 ; method++)
331 : {
332 252 : for (int presort = 0 ; presort <= 2 ; presort++)
333 : {
334 189 : LAGr_TriangleCount_Presort s = presort ;
335 189 : LAGr_TriangleCount_Method m = method ;
336 189 : OK (LAGr_TriangleCount (&nt1, G, &m, &s, msg)) ;
337 189 : TEST_CHECK (nt1 == ntriangles) ;
338 : }
339 : }
340 :
341 : // invalid method
342 9 : LAGr_TriangleCount_Method method = 99 ;
343 9 : int result = LAGr_TriangleCount (&nt1, G, &method, NULL, msg) ;
344 9 : TEST_CHECK (result == GrB_INVALID_VALUE) ;
345 9 : LAGr_TriangleCount_Presort presort = 99 ;
346 9 : result = LAGr_TriangleCount (&nt1, G, NULL, &presort, msg) ;
347 9 : TEST_CHECK (result == GrB_INVALID_VALUE) ;
348 :
349 9 : OK (LAGraph_Delete (&G, msg)) ;
350 : }
351 :
352 1 : LAGraph_Finalize(msg);
353 1 : }
354 :
355 : //****************************************************************************
356 :
357 1 : void test_TriangleCount_autosort (void)
358 : {
359 1 : OK (LAGraph_Init(msg)) ;
360 :
361 : // create a banded matrix with a some dense rows/columns
362 1 : GrB_Index n = 50000 ;
363 1 : GrB_Matrix A = NULL ;
364 1 : OK (GrB_Matrix_new (&A, GrB_BOOL, n, n)) ;
365 :
366 12 : for (int k = 0 ; k <= 10 ; k++)
367 : {
368 550011 : for (int i = 0 ; i < n ; i++)
369 : {
370 550000 : OK (GrB_Matrix_setElement_BOOL (A, true, i, k)) ;
371 550000 : OK (GrB_Matrix_setElement_BOOL (A, true, k, i)) ;
372 : }
373 : }
374 :
375 : // create the graph
376 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
377 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
378 :
379 1 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
380 1 : TEST_CHECK (G->nself_edges == 0) ;
381 :
382 1 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
383 :
384 : // try each method; with autosort
385 1 : GrB_Index nt1 = 0 ;
386 8 : for (int method = 0 ; method <= 6 ; method++)
387 : {
388 7 : LAGr_TriangleCount_Presort presort = LAGr_TriangleCount_AutoSort ;
389 7 : LAGr_TriangleCount_Method m = method ;
390 7 : nt1 = 0 ;
391 7 : OK (LAGr_TriangleCount (&nt1, G, &m, &presort, msg)) ;
392 7 : TEST_CHECK (nt1 == 2749560) ;
393 : }
394 :
395 1 : nt1 = 0 ;
396 1 : OK (LAGraph_TriangleCount (&nt1, G, msg)) ;
397 1 : TEST_CHECK (nt1 == 2749560) ;
398 :
399 1 : OK (LAGraph_Finalize(msg)) ;
400 1 : }
401 :
402 : //------------------------------------------------------------------------------
403 : // test_TriangleCount_brutal
404 : //------------------------------------------------------------------------------
405 :
406 : #if LAGRAPH_SUITESPARSE
407 1 : void test_TriangleCount_brutal (void)
408 : {
409 1 : OK (LG_brutal_setup (msg)) ;
410 :
411 1 : GrB_Matrix A = NULL ;
412 1 : printf ("\n") ;
413 :
414 1 : for (int k = 0 ; ; k++)
415 9 : {
416 :
417 : // load the adjacency matrix as A
418 10 : const char *aname = files [k].name ;
419 10 : uint64_t ntriangles = files [k].ntriangles ;
420 10 : if (strlen (aname) == 0) break;
421 9 : printf ("\n================== Matrix: %s\n", aname) ;
422 9 : TEST_CASE (aname) ;
423 9 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
424 9 : FILE *f = fopen (filename, "r") ;
425 9 : TEST_CHECK (f != NULL) ;
426 9 : OK (LAGraph_MMRead (&A, f, msg)) ;
427 9 : OK (fclose (f)) ;
428 9 : TEST_MSG ("Loading of adjacency matrix failed") ;
429 :
430 : // create the graph
431 9 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
432 :
433 : // delete any diagonal entries
434 9 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
435 :
436 : // get the # of triangles
437 : uint64_t nt0, nt1 ;
438 192 : LG_BRUTAL_BURBLE (LAGraph_TriangleCount (&nt1, G, msg)) ;
439 9 : printf ("# triangles: %g Matrix: %s\n", (double) nt1, aname) ;
440 9 : TEST_CHECK (nt1 == ntriangles) ;
441 :
442 62 : LG_BRUTAL_BURBLE (LG_check_tri (&nt0, G, msg)) ;
443 9 : TEST_CHECK (nt0 == nt1) ;
444 :
445 : // convert to directed but with symmetric pattern
446 9 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
447 9 : G->is_symmetric_structure = LAGraph_TRUE ;
448 192 : LG_BRUTAL (LAGraph_TriangleCount (&nt1, G, msg)) ;
449 9 : TEST_CHECK (nt1 == ntriangles) ;
450 :
451 62 : LG_BRUTAL_BURBLE (LG_check_tri (&nt0, G, msg)) ;
452 9 : TEST_CHECK (nt0 == nt1) ;
453 :
454 : // try each method
455 72 : for (int method = 0 ; method <= 6 ; method++)
456 : {
457 252 : for (int presort = 0 ; presort <= 2 ; presort++)
458 : {
459 189 : LAGr_TriangleCount_Presort s = presort ;
460 189 : LAGr_TriangleCount_Method m = method ;
461 3833 : LG_BRUTAL_BURBLE (LAGr_TriangleCount (&nt1, G, &m, &s, msg)) ;
462 189 : TEST_CHECK (nt1 == ntriangles) ;
463 : }
464 : }
465 :
466 9 : OK (LAGraph_Delete (&G, msg)) ;
467 : }
468 :
469 1 : OK (LG_brutal_teardown (msg)) ;
470 1 : }
471 : #endif
472 :
473 :
474 : //****************************************************************************
475 : //****************************************************************************
476 : TEST_LIST = {
477 : {"TriangleCount_Methods1", test_TriangleCount_Methods1},
478 : {"TriangleCount_Methods2", test_TriangleCount_Methods2},
479 : {"TriangleCount_Methods3", test_TriangleCount_Methods3},
480 : {"TriangleCount_Methods4", test_TriangleCount_Methods4},
481 : {"TriangleCount_Methods5", test_TriangleCount_Methods5},
482 : {"TriangleCount_Methods6", test_TriangleCount_Methods6},
483 : {"TriangleCount" , test_TriangleCount},
484 : {"TriangleCount_many" , test_TriangleCount_many},
485 : {"TriangleCount_autosort", test_TriangleCount_autosort},
486 : #if LAGRAPH_SUITESPARSE
487 : {"TriangleCount_brutal" , test_TriangleCount_brutal},
488 : #endif
489 : {NULL, NULL}
490 : };
|
