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