Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_msf.c: test cases for Min Spanning Forest
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 : // todo: write a simple msf method, as LG_check_msf, and compare its results
19 : // with LAGraph_msf
20 :
21 : #include <stdio.h>
22 : #include <acutest.h>
23 :
24 : #include <LAGraphX.h>
25 : #include <LAGraph_test.h>
26 :
27 : char msg [LAGRAPH_MSG_LEN] ;
28 : LAGraph_Graph G = NULL, G_C = NULL;
29 : GrB_Matrix A = NULL ;
30 : GrB_Matrix S = NULL ;
31 : GrB_Matrix S_C = NULL ;
32 : GrB_Matrix C = NULL ;
33 : GrB_Matrix Ans = NULL ;
34 : #define LEN 512
35 : char filename [LEN+1] ;
36 :
37 : typedef struct
38 : {
39 : bool symmetric ;
40 : const char *name ;
41 : uint64_t ans_n;
42 : const uint64_t *ans_i;
43 : const uint64_t *ans_j;
44 : double ans_w;
45 : }
46 : matrix_info ;
47 : const uint64_t A_mtx_i [] = {1, 2, 3, 4, 5, 6};
48 : const uint64_t A_mtx_j [] = {0, 0, 1, 1, 1, 0};
49 : const uint64_t mtx8u_i [] = {1, 2, 3, 4, 5, 6};
50 : const uint64_t mtx8u_j [] = {4, 3, 0, 6, 2, 3};
51 : const uint64_t mtx8_i [] = {1, 2, 3, 4, 5, 6};
52 : const uint64_t mtx8_j [] = {4, 3, 0, 6, 2, 3};
53 : const matrix_info files [ ] =
54 : {
55 : { 1, "A.mtx", 6, A_mtx_i, A_mtx_j, NAN},
56 : { 1, "jagmesh7.mtx", 1137, NULL, NULL, NAN},
57 : { 0, "west0067.mtx", 66, NULL, NULL, -63.9103636}, // unsymmetric
58 : { 1, "bcsstk13.mtx", 2002, NULL, NULL, -27812381075940.4},
59 : { 0, "matrix_int8.mtx", 6, mtx8_i, mtx8_j, -120.0},
60 : { 0, "matrix_uint8.mtx", 6, mtx8u_i, mtx8u_j, 8.0},
61 : { 1, "karate.mtx", 33, NULL, NULL, NAN},
62 : { 1, "ldbc-cdlp-undirected-example.mtx", 7, NULL, NULL, NAN},
63 : { 1, "ldbc-undirected-example-bool.mtx", 8, NULL, NULL, NAN},
64 : { 1, "ldbc-undirected-example-unweighted.mtx", 8, NULL, NULL, NAN},
65 : { 1, "ldbc-undirected-example.mtx", 8, NULL, NULL, NAN},
66 : { 1, "ldbc-wcc-example.mtx", 9, NULL, NULL, NAN},
67 : { 0, "" },
68 : } ;
69 :
70 : //****************************************************************************
71 1 : void test_msf (void)
72 : {
73 : #if LG_SUITESPARSE_GRAPHBLAS_V10
74 1 : LAGraph_Init (msg) ;
75 1 : bool burble = false ;
76 1 : GrB_Scalar zeroB = NULL;
77 1 : GrB_Scalar_new(&zeroB, GrB_BOOL);
78 1 : GrB_Scalar_setElement_BOOL(zeroB, false);
79 1 : for (int k = 0 ; ; k++)
80 12 : {
81 :
82 : // load the matrix as A
83 13 : const char *aname = files [k].name ;
84 13 : bool symmetric = files [k].symmetric ;
85 13 : uint64_t branches = 0;
86 13 : if (strlen (aname) == 0) break;
87 12 : printf ("\n================================== %s:\n", aname) ;
88 12 : TEST_CASE (aname) ;
89 12 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
90 12 : FILE *f = fopen (filename, "r") ;
91 12 : TEST_CHECK (f != NULL) ;
92 12 : OK (LAGraph_MMRead (&A, f, msg)) ;
93 12 : fclose (f) ;
94 :
95 : // ensure A is uint64
96 12 : GrB_Index n = 0;
97 12 : OK (GrB_Matrix_nrows (&n, A)) ;
98 :
99 : // construct a directed graph G with adjacency matrix S
100 12 : TEST_CHECK (S == NULL) ;
101 :
102 12 : OK (LAGraph_Matrix_Print (A, LAGraph_SHORT, stdout, msg)) ;
103 12 : bool sanitize = (!symmetric) ;
104 :
105 12 : if (files[k].ans_i && files[k].ans_j)
106 : {
107 3 : OK (GrB_Matrix_new(&Ans, GrB_BOOL, n, n)) ;
108 3 : OK (GxB_Matrix_build_Scalar(
109 : Ans, files[k].ans_i, files[k].ans_j, zeroB, files[k].ans_n
110 : )) ;
111 : }
112 :
113 36 : for (int jit = 0 ; jit <= 1 ; jit++)
114 : {
115 24 : if (jit) printf ("\nJIT is enabled\n") ; else printf ("\nJIT is disabled\n") ;
116 :
117 : // connected components
118 24 : GrB_Vector cc0 = NULL, cc1 = NULL, cc2 = NULL;
119 :
120 24 : OK (GxB_Global_Option_set (GxB_JIT_C_CONTROL,
121 : jit ? GxB_JIT_ON : GxB_JIT_OFF)) ;
122 : // compute the min spanning forest
123 24 : C = NULL ;
124 24 : OK (LG_SET_BURBLE (burble)) ;
125 24 : int result = LAGraph_msf (&C, &cc0, A, sanitize, msg) ;
126 24 : OK (LG_SET_BURBLE (false)) ;
127 :
128 24 : printf ("result: %d\n", result) ;
129 24 : OK(result);
130 24 : GrB_Matrix_nvals(&branches, C);
131 24 : TEST_CHECK(branches == files[k].ans_n);
132 24 : LAGraph_PrintLevel pr = (n <= 100) ? LAGraph_COMPLETE : LAGraph_SHORT ;
133 :
134 24 : OK (GrB_Matrix_new(&S, GrB_BOOL, n, n)) ;
135 24 : OK (GrB_Matrix_assign_BOOL(
136 : S, A, NULL, (bool) true, GrB_ALL, n, GrB_ALL, n, GrB_DESC_S)) ;
137 24 : if(!symmetric)
138 : {
139 6 : OK (GrB_Matrix_eWiseAdd_BinaryOp(
140 : S, NULL, NULL, GxB_ANY_BOOL, S, S, GrB_DESC_T1)) ;
141 : }
142 24 : OK(LAGraph_New(&G, &S, LAGraph_ADJACENCY_UNDIRECTED, msg));
143 :
144 : //Check that the graph has all the same ccs.
145 24 : OK (LAGr_ConnectedComponents(&cc1, G, msg)) ;
146 24 : bool ok = false ;
147 24 : OK (GrB_Vector_new(&cc2, GrB_UINT64, n)) ;
148 : // cc1 and cc0 should have the same structure as cc2.
149 : // make their values equal and then compare them.
150 : // msf does not guarentee that the lower node is used as componentId
151 24 : OK (GxB_Vector_extract_Vector(cc2, NULL, NULL, cc0, cc1, NULL)) ;
152 24 : OK (LAGraph_Vector_IsEqual(&ok, cc2, cc0, msg)) ;
153 :
154 : // if(!ok)
155 : // {
156 : // GxB_print(cc2, GxB_SHORT);
157 : // GxB_print(cc0, GxB_SHORT);
158 : // }
159 24 : TEST_ASSERT(ok) ;
160 : // check result C for A.mtx
161 24 : if (files[k].ans_i && files[k].ans_j)
162 : {
163 6 : OK (GrB_Matrix_eWiseMult_BinaryOp(
164 : Ans, NULL, GxB_LOR_BOOL, GrB_ONEB_BOOL, Ans, C, NULL)) ;
165 6 : OK (GrB_Matrix_eWiseMult_BinaryOp(
166 : Ans, NULL, GxB_LOR_BOOL, GrB_ONEB_BOOL, Ans, C, GrB_DESC_T1
167 : )) ;
168 6 : OK (GrB_Matrix_reduce_BOOL(
169 : &ok, NULL, GrB_LAND_MONOID_BOOL, Ans, NULL));
170 6 : TEST_CHECK (ok) ;
171 : }
172 :
173 24 : printf ("\nmsf:\n") ;
174 24 : double tot_weight, ans_w = files[k].ans_w;
175 24 : OK (GrB_Matrix_reduce_FP64(&tot_weight, NULL, GrB_PLUS_MONOID_FP64, C, NULL)) ;
176 24 : TEST_CHECK (isnan(files[k].ans_w) ||
177 : fabs(tot_weight - ans_w) <= 1E-10 * fabs(ans_w)) ;
178 24 : OK (LAGraph_Matrix_Print (C, pr, stdout, msg)) ;
179 24 : OK (LAGraph_Delete (&G, msg)) ;
180 24 : OK (GrB_free (&cc0)) ;
181 24 : OK (GrB_free (&cc1)) ;
182 24 : OK (GrB_free (&cc2)) ;
183 24 : OK (GrB_free (&C)) ;
184 :
185 24 : printf ("JIT test is done\n") ;
186 : }
187 12 : OK (GrB_free(&Ans)) ;
188 12 : OK (GrB_free (&A)) ;
189 : }
190 1 : GrB_free(&zeroB);
191 1 : LAGraph_Finalize (msg) ;
192 : #endif
193 1 : }
194 :
195 : //------------------------------------------------------------------------------
196 : // infinity test
197 : //------------------------------------------------------------------------------
198 :
199 1 : void test_inf_msf (void)
200 : {
201 1 : LAGraph_Init (msg) ;
202 1 : bool burble = false ;
203 1 : GrB_Scalar zeroB = NULL;
204 1 : GrB_Scalar_new(&zeroB, GrB_BOOL);
205 1 : GrB_Scalar_setElement_BOOL(zeroB, false);
206 :
207 : // load the matrix as A
208 1 : const char *aname = "bcsstk13.mtx" ;
209 1 : bool symmetric = 1 ;
210 1 : printf ("\n================================== %s:\n", aname) ;
211 1 : TEST_CASE (aname) ;
212 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
213 1 : FILE *f = fopen (filename, "r") ;
214 1 : TEST_CHECK (f != NULL) ;
215 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
216 1 : fclose (f) ;
217 :
218 1 : GrB_Index n = 0;
219 1 : OK (GrB_Matrix_nrows (&n, A)) ;
220 1 : OK (GrB_Matrix_new(&S, GrB_BOOL, n, n)) ;
221 :
222 : // Make A be iso infinity and S iso true.
223 1 : OK (GrB_Matrix_assign_FP64(
224 : A, A, NULL, INFINITY, GrB_ALL, n, GrB_ALL, n, GrB_DESC_S)) ;
225 1 : OK (GrB_Matrix_assign_BOOL(
226 : S, A, NULL, (bool) true, GrB_ALL, n, GrB_ALL, n, GrB_DESC_S)) ;
227 :
228 : // compute the min spanning forest
229 1 : S_C = C = NULL ;
230 1 : OK (LG_SET_BURBLE (burble)) ;
231 1 : int result = LAGraph_msf (&C, NULL, A, false, msg) ;
232 1 : OK (LG_SET_BURBLE (false)) ;
233 1 : printf ("result: %d\n", result) ;
234 1 : OK(result);
235 :
236 1 : OK (LG_SET_BURBLE (burble)) ;
237 1 : result = LAGraph_msf (&S_C, NULL, S, false, msg) ;
238 1 : OK (LG_SET_BURBLE (false)) ;
239 1 : printf ("result: %d\n", result) ;
240 1 : OK(result);
241 :
242 1 : bool ok = false ;
243 : // check structure is equal.
244 1 : OK (LAGraph_Matrix_IsEqualOp(&ok, C, S_C, GrB_ONEB_BOOL, msg));
245 1 : TEST_CHECK(ok);
246 1 : OK (GrB_free (&S)) ;
247 1 : OK (GrB_free (&S_C)) ;
248 1 : OK (GrB_free (&C)) ;
249 1 : OK (GrB_free (&A)) ;
250 1 : GrB_free(&zeroB);
251 1 : LAGraph_Finalize (msg) ;
252 1 : }
253 :
254 : //------------------------------------------------------------------------------
255 : // test_errors
256 : //------------------------------------------------------------------------------
257 :
258 1 : void test_errors (void)
259 : {
260 1 : LAGraph_Init (msg) ;
261 :
262 : #if LG_SUITESPARSE_GRAPHBLAS_V10
263 : // C and A are NULL
264 1 : int result = LAGraph_msf (NULL, NULL, NULL, true, msg) ;
265 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
266 :
267 : // A must be square
268 1 : OK (GrB_Matrix_new (&A, GrB_UINT64, 3, 4)) ;
269 1 : result = LAGraph_msf (&C, NULL, A, true, msg) ;
270 1 : TEST_CHECK (result == GrB_DIMENSION_MISMATCH) ;
271 1 : OK (GrB_free (&A)) ;
272 :
273 : // A must real
274 1 : OK (GrB_Matrix_new (&A, GxB_FC32, 4, 4)) ;
275 1 : result = LAGraph_msf (&C, NULL, A, true, msg) ;
276 1 : TEST_CHECK (result == GrB_DOMAIN_MISMATCH) ;
277 :
278 : #else
279 : // Not implemented
280 : OK (GrB_Matrix_new (&A, GrB_BOOL, 4, 4)) ;
281 : int result = LAGraph_msf (&C, NULL, A, true, msg) ;
282 : TEST_CHECK (result == GrB_NOT_IMPLEMENTED) ;
283 : #endif
284 :
285 1 : OK (GrB_free (&A)) ;
286 1 : LAGraph_Finalize (msg) ;
287 1 : }
288 :
289 : //****************************************************************************
290 :
291 : TEST_LIST = {
292 : #if LG_SUITESPARSE_GRAPHBLAS_V10
293 : {"msf", test_msf},
294 : {"inf_msf", test_inf_msf},
295 : #endif
296 : {"msf_errors", test_errors},
297 : {NULL, NULL}
298 : };
|
