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 : #undef NDEBUG
27 : #include <assert.h>
28 :
29 : char msg [LAGRAPH_MSG_LEN] ;
30 : LAGraph_Graph G = NULL ;
31 : #define LEN 512
32 : char filename [LEN+1] ;
33 : GrB_Vector C = NULL, C2 = NULL ;
34 : GrB_Matrix A = NULL ;
35 :
36 : typedef struct
37 : {
38 : uint32_t ncomponents ;
39 : const char *name ;
40 : }
41 : matrix_info ;
42 :
43 : const matrix_info files [ ] =
44 : {
45 : { 1, "karate.mtx" },
46 : { 1, "A.mtx" },
47 : { 1, "jagmesh7.mtx" },
48 : { 1, "ldbc-cdlp-undirected-example.mtx" },
49 : { 1, "ldbc-undirected-example.mtx" },
50 : { 1, "ldbc-wcc-example.mtx" },
51 : { 3, "LFAT5.mtx" },
52 : { 1989, "LFAT5_hypersparse.mtx" },
53 : { 6, "LFAT5_two.mtx" },
54 : { 1, "bcsstk13.mtx" },
55 : { 1, "tree-example.mtx" },
56 : { 1391, "zenios.mtx" },
57 : { 0, "" },
58 : } ;
59 :
60 : //------------------------------------------------------------------------------
61 : // count_connected_components: count the # of components in a component vector
62 : //------------------------------------------------------------------------------
63 :
64 : int count_connected_components (GrB_Vector C) ;
65 :
66 97 : int count_connected_components (GrB_Vector C)
67 : {
68 97 : GrB_Index n = 0 ;
69 97 : OK (GrB_Vector_size (&n, C)) ;
70 97 : int ncomponents = 0 ;
71 65165 : for (int i = 0 ; i < n ; i++)
72 : {
73 65068 : int64_t comp = -1 ;
74 65068 : int result = GrB_Vector_extractElement (&comp, C, i) ;
75 65068 : if (result == GrB_SUCCESS && comp == i) ncomponents++ ;
76 : }
77 97 : return (ncomponents) ;
78 : }
79 :
80 : //----------------------------------------------------------------------------
81 : // test_cc_matrices: test with several matrices
82 : //----------------------------------------------------------------------------
83 :
84 1 : void test_cc_matrices (void)
85 : {
86 :
87 1 : OK (LAGraph_Init (msg)) ;
88 : // OK (GxB_set (GxB_BURBLE, true)) ;
89 :
90 1 : for (int k = 0 ; ; k++)
91 12 : {
92 :
93 : // load the adjacency matrix as A
94 13 : const char *aname = files [k].name ;
95 13 : uint32_t ncomp = files [k].ncomponents ;
96 13 : if (strlen (aname) == 0) break;
97 12 : printf ("\nMatrix: %s\n", aname) ;
98 12 : TEST_CASE (aname) ;
99 12 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
100 12 : FILE *f = fopen (filename, "r") ;
101 12 : TEST_CHECK (f != NULL) ;
102 12 : OK (LAGraph_MMRead (&A, f, msg)) ;
103 12 : OK (fclose (f)) ;
104 12 : TEST_MSG ("Loading of adjacency matrix failed") ;
105 : GrB_Index n ;
106 12 : OK (GrB_Matrix_nrows (&n, A)) ;
107 :
108 : // create the graph
109 12 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
110 12 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
111 :
112 36 : for (int trial = 0 ; trial <= 1 ; trial++)
113 : {
114 : // find the connected components
115 24 : printf ("\n--- CC: FastSV6 if SuiteSparse, Boruvka if vanilla:\n") ;
116 24 : OK (LAGr_ConnectedComponents (&C, G, msg)) ;
117 24 : OK (LAGraph_Vector_Print (C, 2, stdout, msg)) ;
118 :
119 : // count the # of connected components
120 24 : int ncomponents = count_connected_components (C) ;
121 24 : printf ("# components: %6u Matrix: %s\n", ncomponents, aname) ;
122 24 : TEST_CHECK (ncomponents == ncomp) ;
123 : GrB_Index cnvals ;
124 24 : OK (GrB_Vector_nvals (&cnvals, C)) ;
125 24 : TEST_CHECK (cnvals == n) ;
126 :
127 : // check the result
128 24 : OK (LG_check_cc (C, G, msg)) ;
129 24 : OK (GrB_free (&C)) ;
130 :
131 : // find the connected components with LG_CC_FastSV5
132 : #if LAGRAPH_SUITESPARSE
133 24 : printf ("\n------ CC_FastSV5:\n") ;
134 24 : OK (LG_CC_FastSV5 (&C2, G, msg)) ;
135 24 : ncomponents = count_connected_components (C2) ;
136 24 : TEST_CHECK (ncomponents == ncomp) ;
137 24 : OK (LG_check_cc (C2, G, msg)) ;
138 24 : OK (GrB_free (&C2)) ;
139 : #endif
140 :
141 : // find the connected components with LG_CC_Boruvka
142 24 : int result = GrB_SUCCESS ;
143 24 : printf ("\n------ CC_BORUVKA:\n") ;
144 24 : result = LG_CC_Boruvka (&C2, G, msg) ;
145 24 : OK (result) ;
146 24 : ncomponents = count_connected_components (C2) ;
147 24 : TEST_CHECK (ncomponents == ncomp) ;
148 24 : OK (LG_check_cc (C2, G, msg)) ;
149 24 : OK (GrB_free (&C2)) ;
150 :
151 24 : result = LG_CC_Boruvka (NULL, G, msg) ;
152 24 : TEST_CHECK (result == GrB_NULL_POINTER) ;
153 :
154 24 : if (trial == 0)
155 : {
156 36 : for (int sanitize = 0 ; sanitize <= 1 ; sanitize++)
157 : {
158 : // find the connected components with cc_lacc
159 24 : printf ("\n------ CC_LACC:\n") ;
160 24 : OK (LAGraph_cc_lacc (&C2, G->A, sanitize, msg)) ;
161 24 : ncomponents = count_connected_components (C2) ;
162 24 : TEST_CHECK (ncomponents == ncomp) ;
163 24 : OK (LG_check_cc (C2, G, msg)) ;
164 24 : OK (GrB_free (&C2)) ;
165 : }
166 :
167 12 : result = LAGraph_cc_lacc (NULL, G->A, false, msg) ;
168 12 : TEST_CHECK (result == GrB_NULL_POINTER) ;
169 : }
170 :
171 : // convert to directed with symmetric pattern for next trial
172 24 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
173 24 : G->is_symmetric_structure = LAGraph_TRUE ;
174 : }
175 :
176 12 : OK (LAGraph_Delete (&G, msg)) ;
177 : }
178 :
179 1 : OK (LAGraph_Finalize (msg)) ;
180 1 : }
181 :
182 : //------------------------------------------------------------------------------
183 : // test_CC_errors:
184 : //------------------------------------------------------------------------------
185 :
186 1 : void test_cc_errors (void)
187 : {
188 1 : OK (LAGraph_Init (msg)) ;
189 1 : printf ("\n") ;
190 :
191 : // check for null pointers
192 1 : int result = GrB_SUCCESS ;
193 :
194 1 : result = LG_CC_Boruvka (NULL, NULL, msg) ;
195 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
196 :
197 : #if LAGRAPH_SUITESPARSE
198 1 : result = LG_CC_FastSV6 (NULL, NULL, msg) ;
199 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
200 : #endif
201 :
202 : // load a valid matrix
203 1 : FILE *f = fopen (LG_DATA_DIR "LFAT5_two.mtx", "r") ;
204 1 : TEST_CHECK (f != NULL) ;
205 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
206 1 : OK (fclose (f)) ;
207 :
208 : // create an valid directed graph (not known to be symmetric)
209 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
210 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
211 :
212 1 : result = LG_CC_Boruvka (&C, G, msg) ;
213 1 : TEST_CHECK (result == -1001) ;
214 1 : printf ("result expected: %d msg:\n%s\n", result, msg) ;
215 :
216 : #if LAGRAPH_SUITESPARSE
217 1 : result = LG_CC_FastSV6 (&C, G, msg) ;
218 1 : TEST_CHECK (result == -1001) ;
219 1 : printf ("result expected: %d msg:\n%s\n", result, msg) ;
220 : #endif
221 :
222 1 : OK (LAGraph_Finalize (msg)) ;
223 1 : }
224 :
225 : //------------------------------------------------------------------------------
226 : // test_CC_brutal:
227 : //------------------------------------------------------------------------------
228 :
229 : #if LAGRAPH_SUITESPARSE
230 1 : void test_cc_brutal (void)
231 : {
232 1 : OK (LG_brutal_setup (msg)) ;
233 :
234 : // load a valid adjacency matrix
235 1 : TEST_CASE ("LFAT5_two") ;
236 1 : uint32_t ncomp = 6 ;
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 1 : TEST_MSG ("Loading of LFAT5_two.mtx failed") ;
242 1 : printf ("\n") ;
243 :
244 : // create an valid graph
245 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
246 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
247 1 : LG_BRUTAL_BURBLE (LAGraph_CheckGraph (G, msg)) ;
248 :
249 : // find the connected components
250 1 : printf ("\n--- CC: FastSV6 if SuiteSparse, Boruvka if vanilla:\n") ;
251 38 : LG_BRUTAL_BURBLE (LAGr_ConnectedComponents (&C, G, msg)) ;
252 3 : LG_BRUTAL_BURBLE (LAGraph_Vector_Print (C, LAGraph_SHORT, stdout, msg)) ;
253 :
254 : // count the # of connected components
255 1 : int ncomponents = count_connected_components (C) ;
256 1 : printf ("# components: %6u Matrix: %s\n", ncomponents, "LFAT_two") ;
257 1 : TEST_CHECK (ncomponents == ncomp) ;
258 1 : OK (LG_check_cc (C, G, msg)) ;
259 :
260 1 : OK (LAGraph_Delete (&G, msg)) ;
261 1 : OK (GrB_free (&C)) ;
262 1 : OK (LG_brutal_teardown (msg)) ;
263 1 : }
264 : #endif
265 :
266 : //****************************************************************************
267 : //****************************************************************************
268 : TEST_LIST = {
269 : {"cc", test_cc_matrices},
270 : #if LAGRAPH_SUITESPARSE
271 : {"cc_brutal", test_cc_brutal},
272 : #endif
273 : {"cc_errors", test_cc_errors},
274 : {NULL, NULL}
275 : };
|
