Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/src/test/test_ConnectedComponents.c: test cases for CC
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 Timothy A. Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : #include <stdio.h>
19 : #include <acutest.h>
20 :
21 : #include "LAGraph_test.h"
22 : // also test LG_CC_FastSV5 and LAGraph_cc_lacc
23 : #include "LAGraphX.h"
24 : #include "LG_alg_internal.h"
25 :
26 : char msg [LAGRAPH_MSG_LEN] ;
27 : LAGraph_Graph G = NULL ;
28 : #define LEN 512
29 : char filename [LEN+1] ;
30 : GrB_Vector C = NULL, C2 = NULL ;
31 : GrB_Matrix A = NULL ;
32 :
33 : typedef struct
34 : {
35 : uint32_t ncomponents ;
36 : const char *name ;
37 : }
38 : matrix_info ;
39 :
40 : const matrix_info files [ ] =
41 : {
42 : { 1, "karate.mtx" },
43 : { 1, "A.mtx" },
44 : { 1, "jagmesh7.mtx" },
45 : { 1, "ldbc-cdlp-undirected-example.mtx" },
46 : { 1, "ldbc-undirected-example.mtx" },
47 : { 1, "ldbc-wcc-example.mtx" },
48 : { 3, "LFAT5.mtx" },
49 : { 1989, "LFAT5_hypersparse.mtx" },
50 : { 6, "LFAT5_two.mtx" },
51 : { 1, "bcsstk13.mtx" },
52 : { 1, "tree-example.mtx" },
53 : { 1391, "zenios.mtx" },
54 : { 0, "" },
55 : } ;
56 :
57 : //------------------------------------------------------------------------------
58 : // count_connected_components: count the # of components in a component vector
59 : //------------------------------------------------------------------------------
60 :
61 : int count_connected_components (GrB_Vector C) ;
62 :
63 169 : int count_connected_components (GrB_Vector C)
64 : {
65 169 : GrB_Index n = 0 ;
66 169 : OK (GrB_Vector_size (&n, C)) ;
67 169 : int ncomponents = 0 ;
68 114017 : for (int i = 0 ; i < n ; i++)
69 : {
70 113848 : int64_t comp = -1 ;
71 113848 : int result = GrB_Vector_extractElement (&comp, C, i) ;
72 113848 : if (result == GrB_SUCCESS && comp == i) ncomponents++ ;
73 : }
74 169 : return (ncomponents) ;
75 : }
76 :
77 : //----------------------------------------------------------------------------
78 : // test_cc_matrices: test with several matrices
79 : //----------------------------------------------------------------------------
80 :
81 1 : void test_cc_matrices (void)
82 : {
83 :
84 1 : OK (LAGraph_Init (msg)) ;
85 : // OK (LG_SET_BURBLE (true)) ;
86 1 : for (int k = 0 ; ; k++)
87 12 : {
88 :
89 : // load the adjacency matrix as A
90 13 : const char *aname = files [k].name ;
91 13 : uint32_t ncomp = files [k].ncomponents ;
92 13 : if (strlen (aname) == 0) break;
93 12 : printf ("\nMatrix: %s\n", aname) ;
94 12 : TEST_CASE (aname) ;
95 12 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
96 12 : FILE *f = fopen (filename, "r") ;
97 12 : TEST_CHECK (f != NULL) ;
98 12 : OK (LAGraph_MMRead (&A, f, msg)) ;
99 : // GxB_print (A, 2) ;
100 12 : OK (fclose (f)) ;
101 12 : TEST_MSG ("Loading of adjacency matrix failed") ;
102 : GrB_Index n ;
103 12 : OK (GrB_Matrix_nrows (&n, A)) ;
104 :
105 : // create the graph
106 12 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
107 12 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
108 :
109 36 : for (int trial = 0 ; trial <= 1 ; trial++)
110 : {
111 : // find the connected components
112 24 : printf ("\n--- CC: FastSV6/7 if SuiteSparse, Boruvka vanilla:\n") ;
113 24 : OK (LAGr_ConnectedComponents (&C, G, msg)) ;
114 :
115 24 : printf ("\nSV6/7 test result, parent vector:\n") ;
116 24 : OK (LAGraph_Vector_Print (C, 2, stdout, msg)) ;
117 :
118 : // count the # of connected components
119 24 : int ncomponents = count_connected_components (C) ;
120 24 : printf ("# components: %6u Matrix: %s\n", ncomponents, aname) ;
121 24 : TEST_CHECK (ncomponents == ncomp) ;
122 24 : GrB_Index cnvals = 0 ;
123 24 : OK (GrB_Vector_nvals (&cnvals, C)) ;
124 24 : TEST_CHECK (cnvals == n) ;
125 :
126 : // check the result
127 24 : OK (LG_check_cc (C, G, msg)) ;
128 24 : OK (GrB_free (&C)) ;
129 :
130 : // find the connected components with LG_CC_FastSV5
131 : #if LAGRAPH_SUITESPARSE
132 24 : printf ("\n------ CC_FastSV5:\n") ;
133 24 : OK (LG_CC_FastSV5 (&C2, G, msg)) ;
134 24 : ncomponents = count_connected_components (C2) ;
135 24 : TEST_CHECK (ncomponents == ncomp) ;
136 24 : OK (LG_check_cc (C2, G, msg)) ;
137 24 : OK (GrB_free (&C2)) ;
138 :
139 : // find the connected components with LG_CC_FastSV6
140 24 : printf ("\n------ CC_FastSV6:\n") ;
141 24 : OK (LG_CC_FastSV6 (&C2, G, msg)) ;
142 24 : ncomponents = count_connected_components (C2) ;
143 24 : TEST_CHECK (ncomponents == ncomp) ;
144 24 : OK (LG_check_cc (C2, G, msg)) ;
145 24 : OK (GrB_free (&C2)) ;
146 :
147 : // find the connected components with LG_CC_FastSV7
148 : #if GxB_IMPLEMENTATION >= GxB_VERSION (10,0,0)
149 24 : printf ("\n------ LG_CC_FastSV7_FA:\n") ;
150 24 : OK (LG_CC_FastSV7_FA (&C2, G, msg)) ;
151 24 : ncomponents = count_connected_components (C2) ;
152 24 : TEST_CHECK (ncomponents == ncomp) ;
153 24 : OK (LG_check_cc (C2, G, msg)) ;
154 24 : OK (GrB_free (&C2)) ;
155 24 : printf ("\n------ CC_FastSV7:\n") ;
156 24 : OK (LG_CC_FastSV7 (&C2, G, msg)) ;
157 24 : ncomponents = count_connected_components (C2) ;
158 24 : TEST_CHECK (ncomponents == ncomp) ;
159 24 : OK (LG_check_cc (C2, G, msg)) ;
160 24 : OK (GrB_free (&C2)) ;
161 : #else
162 : printf ("\n------ CC_FastSV7_FA: requires SS:GrB v10.0.0 or later\n") ;
163 : int result7 = LG_CC_FastSV7_FA (&C2, G, msg) ;
164 : TEST_CHECK (result7 == GrB_NOT_IMPLEMENTED) ;
165 : TEST_CHECK (C2 == NULL) ;
166 : printf ("\n------ CC_FastSV7: requires SS:GrB v10.0.0 or later\n") ;
167 : int result8 = LG_CC_FastSV7 (&C2, G, msg) ;
168 : TEST_CHECK (result8 == GrB_NOT_IMPLEMENTED) ;
169 : TEST_CHECK (C2 == NULL) ;
170 : #endif
171 :
172 : #endif
173 :
174 : // find the connected components with LG_CC_Boruvka
175 24 : printf ("\n------ CC_BORUVKA:\n") ;
176 24 : OK (LG_CC_Boruvka (&C2, G, msg)) ;
177 24 : ncomponents = count_connected_components (C2) ;
178 24 : TEST_CHECK (ncomponents == ncomp) ;
179 24 : OK (LG_check_cc (C2, G, msg)) ;
180 24 : OK (GrB_free (&C2)) ;
181 :
182 24 : int result = LG_CC_Boruvka (NULL, G, msg) ;
183 24 : TEST_CHECK (result == GrB_NULL_POINTER) ;
184 :
185 24 : if (trial == 0)
186 : {
187 36 : for (int sanitize = 0 ; sanitize <= 1 ; sanitize++)
188 : {
189 : // find the connected components with cc_lacc
190 24 : printf ("\n------ CC_LACC:\n") ;
191 24 : OK (LAGraph_cc_lacc (&C2, G->A, sanitize, msg)) ;
192 24 : ncomponents = count_connected_components (C2) ;
193 24 : TEST_CHECK (ncomponents == ncomp) ;
194 24 : OK (LG_check_cc (C2, G, msg)) ;
195 24 : OK (GrB_free (&C2)) ;
196 : }
197 :
198 12 : result = LAGraph_cc_lacc (NULL, G->A, false, msg) ;
199 12 : TEST_CHECK (result == GrB_NULL_POINTER) ;
200 : }
201 :
202 : // convert to directed with symmetric pattern for next trial
203 24 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
204 24 : G->is_symmetric_structure = LAGraph_TRUE ;
205 : }
206 :
207 12 : OK (LAGraph_Delete (&G, msg)) ;
208 : }
209 :
210 1 : OK (LAGraph_Finalize (msg)) ;
211 1 : }
212 :
213 : //------------------------------------------------------------------------------
214 : // test_CC_errors:
215 : //------------------------------------------------------------------------------
216 :
217 1 : void test_cc_errors (void)
218 : {
219 1 : OK (LAGraph_Init (msg)) ;
220 : // OK (LG_SET_BURBLE (true)) ;
221 1 : printf ("\n") ;
222 :
223 : // check for null pointers
224 1 : int result = LG_CC_Boruvka (NULL, NULL, msg) ;
225 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
226 : #if LAGRAPH_SUITESPARSE
227 1 : result = LG_CC_FastSV6 (NULL, NULL, msg) ;
228 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
229 : #if GxB_IMPLEMENTATION >= GxB_VERSION (10,0,0)
230 1 : result = LG_CC_FastSV7_FA (NULL, NULL, msg) ;
231 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
232 : #endif
233 : #endif
234 :
235 :
236 : // load a valid matrix
237 1 : FILE *f = fopen (LG_DATA_DIR "LFAT5_two.mtx", "r") ;
238 1 : TEST_CHECK (f != NULL) ;
239 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
240 1 : OK (fclose (f)) ;
241 :
242 : // create an valid directed graph (not known to be symmetric)
243 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
244 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
245 :
246 1 : result = LG_CC_Boruvka (&C, G, msg) ;
247 1 : TEST_CHECK (result == -1001) ;
248 1 : printf ("result expected: %d msg:\n%s\n", result, msg) ;
249 : #if LAGRAPH_SUITESPARSE
250 1 : result = LG_CC_FastSV6 (&C, G, msg) ;
251 1 : TEST_CHECK (result == -1001) ;
252 1 : printf ("result expected: %d msg:\n%s\n", result, msg) ;
253 : #if GxB_IMPLEMENTATION >= GxB_VERSION (10,0,0)
254 1 : result = LG_CC_FastSV7_FA (&C, G, msg) ;
255 1 : TEST_CHECK (result == -1001) ;
256 1 : printf ("result expected: %d msg:\n%s\n", result, msg) ;
257 : #endif
258 : #endif
259 :
260 1 : OK (LAGraph_Delete (&G, msg)) ;
261 1 : OK (LAGraph_Finalize (msg)) ;
262 1 : }
263 :
264 : //------------------------------------------------------------------------------
265 : // test_CC_brutal:
266 : //------------------------------------------------------------------------------
267 :
268 : #if LG_BRUTAL_TESTS
269 1 : void test_cc_brutal (void)
270 : {
271 1 : OK (LG_brutal_setup (msg)) ;
272 :
273 : // load a valid adjacency matrix
274 1 : TEST_CASE ("LFAT5_two") ;
275 1 : uint32_t ncomp = 6 ;
276 1 : FILE *f = fopen (LG_DATA_DIR "LFAT5_two.mtx", "r") ;
277 1 : TEST_CHECK (f != NULL) ;
278 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
279 1 : OK (fclose (f)) ;
280 1 : TEST_MSG ("Loading of LFAT5_two.mtx failed") ;
281 1 : printf ("\n") ;
282 :
283 : // create an valid graph
284 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
285 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
286 1 : LG_BRUTAL_BURBLE (LAGraph_CheckGraph (G, msg)) ;
287 :
288 : // find the connected components
289 1 : printf ("\n--- CC: FastSV6/7 if SuiteSparse, Boruvka if vanilla:\n") ;
290 59 : LG_BRUTAL_BURBLE (LAGr_ConnectedComponents (&C, G, msg)) ;
291 :
292 : #if GxB_IMPLEMENTATION >= GxB_VERSION (10,0,0)
293 1 : OK (GrB_free (&C)) ;
294 1 : printf ("\n--- CC: FastSV7_FA\n") ;
295 77 : LG_BRUTAL_BURBLE (LG_CC_FastSV7_FA (&C, G, msg)) ;
296 : #endif
297 : // printf ("\nSV6/7 test result, parent vector:\n") ;
298 : // LG_BRUTAL_BURBLE (LAGraph_Vector_Print (C, LAGraph_SHORT, stdout, msg)) ;
299 :
300 : // count the # of connected components
301 1 : int ncomponents = count_connected_components (C) ;
302 1 : printf ("# components: %6u Matrix: %s\n", ncomponents, "LFAT_two") ;
303 1 : TEST_CHECK (ncomponents == ncomp) ;
304 1 : OK (LG_check_cc (C, G, msg)) ;
305 :
306 1 : OK (LAGraph_Delete (&G, msg)) ;
307 1 : OK (GrB_free (&C)) ;
308 1 : OK (LG_brutal_teardown (msg)) ;
309 1 : }
310 : #endif
311 :
312 : //****************************************************************************
313 : //****************************************************************************
314 : TEST_LIST = {
315 : {"cc", test_cc_matrices},
316 : #if LG_BRUTAL_TESTS
317 : {"cc_brutal", test_cc_brutal},
318 : #endif
319 : {"cc_errors", test_cc_errors},
320 : {NULL, NULL}
321 : };
|
