Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/src/test/test_SingleSourceShortestPath.c: test cases for SSSP
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 : #include <LAGraph_test.h>
21 : #include "LG_internal.h"
22 :
23 : char msg [LAGRAPH_MSG_LEN] ;
24 : LAGraph_Graph G = NULL ;
25 :
26 : #define LEN 512
27 : char filename [LEN+1] ;
28 : char atype_name [LAGRAPH_MAX_NAME_LEN] ;
29 :
30 : typedef struct
31 : {
32 : const char *name ;
33 : }
34 : matrix_info ;
35 :
36 : const matrix_info files [ ] =
37 : {
38 : { "A.mtx" },
39 : { "cover.mtx" },
40 : { "jagmesh7.mtx" },
41 : { "ldbc-cdlp-directed-example.mtx" },
42 : { "ldbc-cdlp-undirected-example.mtx" },
43 : { "ldbc-directed-example.mtx" },
44 : { "ldbc-undirected-example.mtx" },
45 : { "ldbc-wcc-example.mtx" },
46 : { "LFAT5.mtx" },
47 : { "LFAT5_hypersparse.mtx" },
48 : { "msf1.mtx" },
49 : { "msf2.mtx" },
50 : { "msf3.mtx" },
51 : { "sample2.mtx" },
52 : { "sample.mtx" },
53 : { "olm1000.mtx" },
54 : { "bcsstk13.mtx" },
55 : { "cryg2500.mtx" },
56 : { "tree-example.mtx" },
57 : { "west0067.mtx" },
58 : { "karate.mtx" },
59 : { "matrix_bool.mtx" },
60 : { "test_BF.mtx" },
61 : { "test_FW_1000.mtx" },
62 : { "test_FW_2003.mtx" },
63 : { "test_FW_2500.mtx" },
64 : { "skew_fp32.mtx" },
65 : { "matrix_uint32.mtx" },
66 : { "matrix_uint64.mtx" },
67 : { "" },
68 : } ;
69 :
70 : //****************************************************************************
71 1 : void test_SingleSourceShortestPath(void)
72 : {
73 1 : LAGraph_Init(msg);
74 : // OK (LG_SET_BURBLE (true)) ;
75 1 : GrB_Matrix A = NULL, T = NULL ;
76 1 : GrB_Scalar Delta = NULL ;
77 1 : OK (GrB_Scalar_new (&Delta, GrB_INT32)) ;
78 :
79 1 : for (int k = 0 ; ; k++)
80 29 : {
81 :
82 : // load the adjacency matrix as A
83 30 : const char *aname = files [k].name ;
84 30 : LAGraph_Kind kind = LAGraph_ADJACENCY_DIRECTED ;
85 : // LAGraph_Kind kind = files [k].kind ;
86 30 : if (strlen (aname) == 0) break;
87 29 : TEST_CASE (aname) ;
88 29 : printf ("\nMatrix: %s\n", aname) ;
89 29 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
90 29 : FILE *f = fopen (filename, "r") ;
91 29 : TEST_CHECK (f != NULL) ;
92 29 : OK (LAGraph_MMRead (&A, f, msg)) ;
93 29 : OK (fclose (f)) ;
94 29 : TEST_MSG ("Loading of adjacency matrix failed") ;
95 :
96 29 : GrB_Index n = 0, ncols = 1 ;
97 29 : OK (GrB_Matrix_nrows (&n, A)) ;
98 29 : OK (GrB_Matrix_ncols (&ncols, A)) ;
99 29 : TEST_CHECK (n == ncols) ;
100 :
101 : // convert A to int32
102 29 : OK (LAGraph_Matrix_TypeName (atype_name, A, msg)) ;
103 29 : if (!MATCHNAME (atype_name, "int32_t"))
104 : {
105 28 : OK (GrB_Matrix_new (&T, GrB_INT32, n, n)) ;
106 28 : OK (GrB_assign (T, NULL, NULL, A, GrB_ALL, n, GrB_ALL, n, NULL)) ;
107 28 : OK (GrB_free (&A)) ;
108 28 : A = T ;
109 : }
110 :
111 : // ensure all entries are positive, and in the range 1 to 255
112 29 : OK (GrB_Matrix_apply_BinaryOp2nd_INT32 (A, NULL, NULL,
113 : GrB_BAND_INT32, A, 255, NULL)) ;
114 : int32_t x ;
115 29 : OK (GrB_reduce (&x, NULL, GrB_MIN_MONOID_INT32, A, NULL)) ;
116 29 : if (x < 1)
117 : {
118 14 : OK (GrB_Matrix_apply_BinaryOp2nd_INT32 (A, NULL, NULL,
119 : GrB_MAX_INT32, A, 1, NULL)) ;
120 : }
121 :
122 : // create the graph
123 29 : OK (LAGraph_New (&G, &A, kind, msg)) ;
124 29 : OK (LAGraph_CheckGraph (G, msg)) ;
125 29 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
126 :
127 : // no need to compute emin; just use a bound
128 29 : OK (GrB_Scalar_new (&(G->emin), GrB_INT32)) ;
129 29 : OK (GrB_Scalar_setElement (G->emin, 1)) ;
130 :
131 : // delta values to try
132 29 : int32_t Deltas [ ] = { 30, 100, 50000 } ;
133 :
134 : // run the SSSP
135 29 : GrB_Vector path_length = NULL ;
136 29 : int64_t step = (n > 100) ? (3*n/4) : ((n/4) + 1) ;
137 : // int64_t src = 0 ;
138 119 : for (int64_t src = 0 ; src < n ; src += step)
139 : {
140 : // int32_t kk = 0 ;
141 328 : for (int32_t kk = 0 ; kk < ((n > 100) ? 1 : 3) ; kk++)
142 : {
143 238 : int32_t delta = Deltas [kk] ;
144 238 : printf ("src %d delta %d n %d\n", (int) src, delta, (int) n) ;
145 238 : OK (GrB_Scalar_setElement (Delta, delta)) ;
146 238 : OK (LAGr_SingleSourceShortestPath (&path_length, G,
147 : src, Delta, msg)) ;
148 238 : int res = LG_check_sssp (path_length, G, src, msg) ;
149 238 : if (res != GrB_SUCCESS) printf ("res: %d msg: %s\n", res, msg) ;
150 238 : OK (res) ;
151 238 : OK (GrB_free(&path_length)) ;
152 : }
153 : }
154 :
155 : // add a single negative edge and try again
156 29 : OK (GrB_free (&(G->emin))) ;
157 29 : G->emin_state = LAGRAPH_UNKNOWN ;
158 29 : OK (GrB_Matrix_setElement_INT32 (G->A, -1, 0, 1)) ;
159 29 : OK (GrB_Scalar_setElement (Delta, 30)) ;
160 29 : OK (LAGr_SingleSourceShortestPath (&path_length, G, 0, Delta, msg)) ;
161 29 : OK (LAGraph_Vector_Print (path_length, LAGraph_SHORT, stdout, msg)) ;
162 29 : int32_t len = 0 ;
163 29 : OK (GrB_Vector_extractElement (&len, path_length, 1)) ;
164 29 : TEST_CHECK (len == -1) ;
165 29 : OK (GrB_free(&path_length)) ;
166 :
167 29 : OK (LAGraph_Delete (&G, msg)) ;
168 : }
169 :
170 1 : GrB_free (&Delta) ;
171 1 : LAGraph_Finalize(msg);
172 1 : }
173 :
174 : //------------------------------------------------------------------------------
175 : // test_SingleSourceShortestPath_types
176 : //------------------------------------------------------------------------------
177 :
178 1 : void test_SingleSourceShortestPath_types (void)
179 : {
180 1 : LAGraph_Init (msg) ;
181 1 : GrB_Matrix A = NULL, T = NULL ;
182 1 : GrB_Scalar Delta = NULL ;
183 1 : OK (GrB_Scalar_new (&Delta, GrB_INT32)) ;
184 :
185 1 : for (int k = 0 ; ; k++)
186 29 : {
187 :
188 : // load the adjacency matrix as A
189 30 : const char *aname = files [k].name ;
190 30 : LAGraph_Kind kind = LAGraph_ADJACENCY_DIRECTED ;
191 : // LAGraph_Kind kind = files [k].kind ;
192 30 : if (strlen (aname) == 0) break;
193 29 : TEST_CASE (aname) ;
194 29 : printf ("\nMatrix: %s\n", aname) ;
195 29 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
196 29 : FILE *f = fopen (filename, "r") ;
197 29 : TEST_CHECK (f != NULL) ;
198 29 : OK (LAGraph_MMRead (&A, f, msg)) ;
199 29 : OK (fclose (f)) ;
200 29 : TEST_MSG ("Loading of adjacency matrix failed") ;
201 :
202 29 : GrB_Index n = 0, ncols = 1 ;
203 29 : OK (GrB_Matrix_nrows (&n, A)) ;
204 29 : OK (GrB_Matrix_ncols (&ncols, A)) ;
205 29 : TEST_CHECK (n == ncols) ;
206 :
207 : // ensure A has the right type
208 29 : OK (LAGraph_Matrix_TypeName (atype_name, A, msg)) ;
209 : // fprintf (stderr, "matrix %s type: %s\n", aname, atype_name) ;
210 29 : if (MATCHNAME (atype_name, "int32_t"))
211 : {
212 : // use A as-is, but ensure it's positive and nonzero,
213 : // and in range 1 to 255
214 1 : OK (GrB_apply (A, NULL, NULL, GrB_ABS_INT32, A, NULL)) ;
215 1 : OK (GrB_apply (A, NULL, NULL, GrB_MAX_INT32, A, 1, NULL)) ;
216 1 : OK (GrB_apply (A, NULL, NULL, GrB_MIN_INT32, A, 255, NULL)) ;
217 : }
218 28 : else if (MATCHNAME (atype_name, "int64_t"))
219 : {
220 : // use A as-is, but ensure it's positive and nonzero,
221 : // and in range 1 to 255
222 5 : OK (GrB_apply (A, NULL, NULL, GrB_ABS_INT64, A, NULL)) ;
223 5 : OK (GrB_apply (A, NULL, NULL, GrB_MAX_INT64, A, 1, NULL)) ;
224 5 : OK (GrB_apply (A, NULL, NULL, GrB_MIN_INT64, A, 255, NULL)) ;
225 : }
226 23 : else if (MATCHNAME (atype_name, "uint32_t"))
227 : {
228 : // use A as-is, but ensure it's nonzero
229 : // and in range 1 to 255
230 1 : OK (GrB_apply (A, NULL, NULL, GrB_MAX_UINT32, A, 1, NULL)) ;
231 1 : OK (GrB_apply (A, NULL, NULL, GrB_MIN_UINT32, A, 255, NULL)) ;
232 : }
233 22 : else if (MATCHNAME (atype_name, "uint64_t"))
234 : {
235 : // use A as-is, but ensure it's nonzero
236 : // and in range 1 to 255
237 1 : OK (GrB_apply (A, NULL, NULL, GrB_MAX_UINT64, A, 1, NULL)) ;
238 1 : OK (GrB_apply (A, NULL, NULL, GrB_MIN_UINT64, A, 255, NULL)) ;
239 : }
240 21 : else if (MATCHNAME (atype_name, "float"))
241 : {
242 : // use A as-is, but ensure it's positive, with values in range
243 : // 1 to 255
244 1 : OK (GrB_apply (A, NULL, NULL, GrB_ABS_FP32, A, NULL)) ;
245 1 : float emax = 0 ;
246 1 : OK (GrB_reduce (&emax, NULL, GrB_MAX_MONOID_FP32, A, NULL)) ;
247 1 : emax = 255. / emax ;
248 1 : OK (GrB_apply (A, NULL, NULL, GrB_TIMES_FP32, A, emax, NULL)) ;
249 1 : OK (GrB_apply (A, NULL, NULL, GrB_MAX_FP32, A, 1, NULL)) ;
250 : }
251 20 : else if (MATCHNAME (atype_name, "double"))
252 : {
253 : // use A as-is, but ensure it's positive, with values in range
254 : // 1 to 255
255 12 : OK (GrB_apply (A, NULL, NULL, GrB_ABS_FP64, A, NULL)) ;
256 12 : double emax = 0 ;
257 12 : OK (GrB_reduce (&emax, NULL, GrB_MAX_MONOID_FP64, A, NULL)) ;
258 12 : emax = 255. / emax ;
259 12 : OK (GrB_apply (A, NULL, NULL, GrB_TIMES_FP64, A, emax, NULL)) ;
260 12 : OK (GrB_apply (A, NULL, NULL, GrB_MAX_FP64, A, 1, NULL)) ;
261 : }
262 : else
263 : {
264 : // T = max (abs (double (A)), 0.1)
265 8 : OK (GrB_Matrix_new (&T, GrB_FP64, n, n)) ;
266 8 : OK (GrB_apply (T, NULL, NULL, GrB_ABS_FP64, A, NULL)) ;
267 8 : OK (GrB_apply (T, NULL, NULL, GrB_MAX_FP64, T, 0.1, NULL)) ;
268 8 : OK (GrB_free (&A)) ;
269 8 : A = T ;
270 : }
271 :
272 : // create the graph
273 29 : OK (LAGraph_New (&G, &A, kind, msg)) ;
274 29 : OK (LAGraph_CheckGraph (G, msg)) ;
275 29 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
276 :
277 : // find the smallest entry
278 29 : OK (LAGraph_Cached_EMin (G, msg)) ;
279 :
280 : // delta values to try
281 29 : int32_t Deltas [ ] = { 30, 100, 50000 } ;
282 :
283 : // run the SSSP
284 29 : GrB_Vector path_length = NULL ;
285 29 : int64_t step = (n > 100) ? (3*n/4) : ((n/4) + 1) ;
286 119 : for (int64_t src = 0 ; src < n ; src += step)
287 : {
288 328 : for (int32_t kk = 0 ; kk < ((n > 100) ? 1 : 3) ; kk++)
289 : {
290 238 : int32_t delta = Deltas [kk] ;
291 238 : printf ("src %d delta %d n %d\n", (int) src, delta, (int) n) ;
292 238 : OK (GrB_Scalar_setElement (Delta, delta)) ;
293 238 : OK (LAGr_SingleSourceShortestPath (&path_length, G, src,
294 : Delta, msg)) ;
295 238 : int res = LG_check_sssp (path_length, G, src, msg) ;
296 238 : if (res != GrB_SUCCESS) printf ("res: %d msg: %s\n", res, msg) ;
297 238 : OK (res) ;
298 238 : OK (GrB_free(&path_length)) ;
299 : }
300 : }
301 :
302 29 : OK (LAGraph_Delete (&G, msg)) ;
303 : }
304 :
305 1 : GrB_free (&Delta) ;
306 1 : LAGraph_Finalize (msg) ;
307 1 : }
308 :
309 : //------------------------------------------------------------------------------
310 : // test_SingleSourceShortestPath_failure
311 : //------------------------------------------------------------------------------
312 :
313 1 : void test_SingleSourceShortestPath_failure (void)
314 : {
315 1 : LAGraph_Init (msg) ;
316 1 : GrB_Scalar Delta = NULL ;
317 1 : OK (GrB_Scalar_new (&Delta, GrB_INT32)) ;
318 1 : OK (GrB_Scalar_setElement (Delta, 1)) ;
319 :
320 : // load the karate adjacency matrix as A
321 1 : GrB_Matrix A = NULL ;
322 1 : FILE *f = fopen (LG_DATA_DIR "karate.mtx", "r") ;
323 1 : TEST_CHECK (f != NULL) ;
324 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
325 1 : OK (fclose (f)) ;
326 1 : TEST_MSG ("Loading of adjacency matrix failed") ;
327 :
328 : // create the graph
329 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
330 1 : OK (LAGraph_CheckGraph (G, msg)) ;
331 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
332 :
333 1 : GrB_Vector path_length = NULL ;
334 1 : int result = LAGr_SingleSourceShortestPath (&path_length, G, 0, Delta, msg) ;
335 1 : printf ("\nres: %d msg: %s\n", result, msg) ;
336 1 : TEST_CHECK (path_length == NULL) ;
337 1 : TEST_CHECK (result == GrB_NOT_IMPLEMENTED) ;
338 :
339 1 : OK (GrB_Scalar_clear (Delta)) ;
340 1 : result = LAGr_SingleSourceShortestPath (&path_length, G, 0, Delta, msg) ;
341 1 : printf ("\nres: %d msg: %s\n", result, msg) ;
342 1 : TEST_CHECK (path_length == NULL) ;
343 1 : TEST_CHECK (result == GrB_EMPTY_OBJECT) ;
344 :
345 1 : OK (GrB_free (&Delta)) ;
346 1 : OK (LAGraph_Delete (&G, msg)) ;
347 1 : LAGraph_Finalize (msg) ;
348 1 : }
349 :
350 : //------------------------------------------------------------------------------
351 : // test_SingleSourceShortestPath_brutal
352 : //------------------------------------------------------------------------------
353 :
354 : #if LG_BRUTAL_TESTS
355 1 : void test_SingleSourceShortestPath_brutal (void)
356 : {
357 1 : OK (LG_brutal_setup (msg)) ;
358 1 : GrB_Scalar Delta = NULL ;
359 1 : OK (GrB_Scalar_new (&Delta, GrB_INT32)) ;
360 :
361 1 : GrB_Matrix A = NULL, T = NULL ;
362 :
363 : // just test with the first 8 matrices
364 9 : for (int k = 0 ; k < 8 ; k++)
365 : {
366 :
367 : // load the adjacency matrix as A
368 8 : const char *aname = files [k].name ;
369 8 : LAGraph_Kind kind = LAGraph_ADJACENCY_DIRECTED ;
370 : // LAGraph_Kind kind = files [k].kind ;
371 8 : if (strlen (aname) == 0) break;
372 8 : TEST_CASE (aname) ;
373 8 : printf ("\nMatrix: %s\n", aname) ;
374 8 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
375 8 : FILE *f = fopen (filename, "r") ;
376 8 : TEST_CHECK (f != NULL) ;
377 8 : OK (LAGraph_MMRead (&A, f, msg)) ;
378 8 : OK (fclose (f)) ;
379 8 : TEST_MSG ("Loading of adjacency matrix failed") ;
380 :
381 8 : GrB_Index n = 0 ;
382 8 : OK (GrB_Matrix_nrows (&n, A)) ;
383 8 : if (n > 30)
384 : {
385 1 : printf ("skipped -- only using small matrices for brutal test\n") ;
386 1 : OK (GrB_free (&A)) ;
387 1 : continue ;
388 : }
389 :
390 : // convert A to int32
391 7 : OK (LAGraph_Matrix_TypeName (atype_name, A, msg)) ;
392 7 : if (!MATCHNAME (atype_name, "int32_t"))
393 : {
394 6 : OK (GrB_Matrix_new (&T, GrB_INT32, n, n)) ;
395 6 : OK (GrB_assign (T, NULL, NULL, A, GrB_ALL, n, GrB_ALL, n, NULL)) ;
396 6 : OK (GrB_free (&A)) ;
397 6 : A = T ;
398 : }
399 :
400 : // ensure all entries are positive, and in the range 1 to 255
401 7 : OK (GrB_Matrix_apply_BinaryOp2nd_INT32 (A, NULL, NULL,
402 : GrB_BAND_INT32, A, 255, NULL)) ;
403 : int32_t x ;
404 7 : OK (GrB_reduce (&x, NULL, GrB_MIN_MONOID_INT32, A, NULL)) ;
405 7 : if (x < 1)
406 : {
407 2 : OK (GrB_Matrix_apply_BinaryOp2nd_INT32 (A, NULL, NULL,
408 : GrB_MAX_INT32, A, 1, NULL)) ;
409 : }
410 :
411 : // create the graph
412 7 : OK (LAGraph_New (&G, &A, kind, msg)) ;
413 7 : OK (LAGraph_CheckGraph (G, msg)) ;
414 :
415 : // run the SSSP on a single source node with one delta
416 7 : GrB_Vector path_length = NULL ;
417 7 : int64_t src = 0 ;
418 7 : int32_t delta = 30 ;
419 7 : printf ("src %d delta %d n %d\n", (int) src, delta, (int) n) ;
420 7 : OK (GrB_Scalar_setElement (Delta, delta)) ;
421 1459 : LG_BRUTAL (LAGr_SingleSourceShortestPath (&path_length, G, src,
422 : Delta, msg)) ;
423 7 : int rr = (LG_check_sssp (path_length, G, src, msg)) ;
424 7 : printf ("rr %d msg %s\n", rr, msg) ;
425 7 : OK (rr) ;
426 7 : OK (GrB_free(&path_length)) ;
427 :
428 : // add a single negative edge and try again
429 7 : OK (GrB_Matrix_setElement_INT32 (G->A, -1, 0, 1)) ;
430 7 : OK (GrB_wait (G->A, GrB_MATERIALIZE)) ;
431 2471 : LG_BRUTAL (LAGr_SingleSourceShortestPath (&path_length, G, 0,
432 : Delta, msg)) ;
433 7 : int32_t len = 0 ;
434 7 : OK (GrB_Vector_extractElement (&len, path_length, 1)) ;
435 7 : TEST_CHECK (len == -1) ;
436 7 : OK (GrB_free(&path_length)) ;
437 :
438 7 : OK (LAGraph_Delete (&G, msg)) ;
439 : }
440 :
441 1 : GrB_free (&Delta) ;
442 1 : OK (LG_brutal_teardown (msg)) ;
443 1 : }
444 : #endif
445 :
446 : //****************************************************************************
447 : //****************************************************************************
448 :
449 : TEST_LIST = {
450 : {"SSSP", test_SingleSourceShortestPath},
451 : {"SSSP_types", test_SingleSourceShortestPath_types},
452 : {"SSSP_failure", test_SingleSourceShortestPath_failure},
453 : #if LG_BRUTAL_TESTS
454 : {"SSSP_brutal", test_SingleSourceShortestPath_brutal },
455 : #endif
456 : {NULL, NULL}
457 : };
|
