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