Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_BF
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 Jinhao Chen and Tim Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : #include <stdio.h>
19 : #include <acutest.h>
20 : #include <LAGraphX.h>
21 : #include <LAGraph_test.h>
22 : #include <LG_Xtest.h>
23 :
24 : //------------------------------------------------------------------------------
25 : // globals
26 : //------------------------------------------------------------------------------
27 :
28 : #define LEN 512
29 : char filename [LEN+1] ;
30 : char msg [LAGRAPH_MSG_LEN] ;
31 :
32 : //------------------------------------------------------------------------------
33 : // test cases
34 : //------------------------------------------------------------------------------
35 :
36 : typedef struct
37 : {
38 : bool has_negative_cycle ;
39 : bool has_integer_weights ;
40 : const char *name ;
41 : }
42 : matrix_info ;
43 :
44 : const matrix_info files [ ] =
45 : {
46 : 0, 1, "karate.mtx",
47 : 1, 0, "west0067.mtx",
48 : 1, 1, "matrix_int8.mtx",
49 : 0, 0, ""
50 : } ;
51 :
52 : //------------------------------------------------------------------------------
53 : // setup: start a test
54 : //------------------------------------------------------------------------------
55 :
56 1 : void setup (void)
57 : {
58 1 : OK (LAGraph_Init (msg)) ;
59 : // OK (LG_SET_BURBLE (true)) ;
60 1 : }
61 :
62 : //------------------------------------------------------------------------------
63 : // teardown: finalize a test
64 : //------------------------------------------------------------------------------
65 :
66 1 : void teardown (void)
67 : {
68 1 : OK (LAGraph_Finalize (msg)) ;
69 1 : }
70 :
71 1 : void test_BF (void)
72 : {
73 :
74 : GrB_Info info ;
75 1 : setup ( ) ;
76 :
77 1 : for (int k = 0 ; ; k++)
78 3 : {
79 4 : GrB_Matrix A = NULL, AT = NULL, A_orig = NULL ;
80 4 : GrB_Index *I = NULL, *J = NULL ; // for col/row indices of entries in A
81 4 : double *W = NULL, *d = NULL ;
82 4 : int64_t *pi = NULL, *pi10 = NULL ;
83 4 : int32_t *W_int32 = NULL, *d10 = NULL ;
84 4 : GrB_Vector d1 = NULL, d2 = NULL, d3 = NULL, d4 = NULL, d5 = NULL,
85 4 : d5a = NULL, d6 = NULL, d7 = NULL, d8 = NULL, d9 = NULL, h1 = NULL,
86 4 : h2 = NULL, h5 = NULL, h5a = NULL, h6 = NULL, pi1 = NULL, pi2 = NULL,
87 4 : pi5 = NULL, pi5a = NULL, pi6 = NULL ;
88 :
89 : //----------------------------------------------------------------------
90 : // read in a matrix from a file
91 : //----------------------------------------------------------------------
92 :
93 : // load the matrix as A_orig
94 4 : const char *aname = files [k].name ;
95 4 : if (strlen (aname) == 0) break;
96 3 : TEST_CASE (aname) ;
97 3 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
98 3 : FILE *f = fopen (filename, "r") ;
99 3 : TEST_CHECK (f != NULL) ;
100 3 : OK (LAGraph_MMRead (&A_orig, f, msg)) ;
101 3 : OK (fclose (f)) ;
102 3 : TEST_MSG ("Loading of valued matrix failed") ;
103 3 : printf ("\nMatrix: %s\n", aname) ;
104 3 : OK (LAGraph_Matrix_Print (A_orig, LAGraph_SHORT, stdout, NULL)) ;
105 :
106 3 : bool has_negative_cycle = files [k].has_negative_cycle ;
107 3 : bool has_integer_weights = files [k].has_integer_weights ;
108 3 : int ktrials = (has_negative_cycle) ? 2 : 1 ;
109 :
110 : //----------------------------------------------------------------------
111 : // get the size of the problem
112 : //----------------------------------------------------------------------
113 :
114 : GrB_Index nvals ;
115 3 : GrB_Matrix_nvals (&nvals, A_orig) ;
116 : GrB_Index nrows, ncols ;
117 3 : OK (GrB_Matrix_nrows (&nrows, A_orig)) ;
118 3 : OK (GrB_Matrix_ncols (&ncols, A_orig)) ;
119 3 : GrB_Index n = nrows ;
120 3 : OK (LAGraph_Malloc ((void **) &I, nvals, sizeof (GrB_Index), msg)) ;
121 3 : OK (LAGraph_Malloc ((void **) &J, nvals, sizeof (GrB_Index), msg)) ;
122 3 : OK (LAGraph_Malloc ((void **) &W, nvals, sizeof (double), msg)) ;
123 3 : OK (LAGraph_Malloc ((void **) &W_int32, nvals, sizeof (int32_t), msg)) ;
124 :
125 3 : OK (GrB_Matrix_extractTuples_FP64 (I, J, W, &nvals, A_orig)) ;
126 3 : if (has_integer_weights)
127 : {
128 2 : OK (GrB_Matrix_extractTuples_INT32 (I, J, W_int32, &nvals,
129 : A_orig)) ;
130 : }
131 :
132 : //----------------------------------------------------------------------
133 : // copy the matrix and set its diagonal to 0
134 : //----------------------------------------------------------------------
135 :
136 3 : OK (GrB_Matrix_dup (&A, A_orig)) ;
137 111 : for (GrB_Index i = 0; i < n; i++)
138 : {
139 108 : OK (GrB_Matrix_setElement_FP64 (A, 0, i, i)) ;
140 : }
141 :
142 : //----------------------------------------------------------------------
143 : // AT = A'
144 : //----------------------------------------------------------------------
145 :
146 3 : double tt = LAGraph_WallClockTime ( ) ;
147 3 : OK (GrB_Matrix_free (&AT)) ;
148 3 : OK (GrB_Matrix_new (&AT, GrB_FP64, ncols, nrows)) ;
149 3 : OK (GrB_transpose (AT, NULL, NULL, A, NULL)) ;
150 3 : double transpose_time = LAGraph_WallClockTime ( ) - tt ;
151 : // fprintf (stderr, "transpose time: %g\n", transpose_time) ;
152 :
153 : //----------------------------------------------------------------------
154 : // get the source node
155 : //----------------------------------------------------------------------
156 :
157 3 : GrB_Index s = 0 ;
158 : // fprintf (stderr, "\n==========input graph: nodes: %g edges: %g "
159 : // "source node: %g\n", (double) n, (double) nvals, (double) s) ;
160 :
161 : //----------------------------------------------------------------------
162 : // run 1 or 2 trials (2 negative weight cycles)
163 : //----------------------------------------------------------------------
164 :
165 8 : for (int kk = 1 ; kk <= ktrials ; kk++)
166 : {
167 5 : int valid = (has_negative_cycle) ? GrB_NO_VALUE : GrB_SUCCESS ;
168 :
169 : //------------------------------------------------------------------
170 : // run LAGraph_BF_full1 before setting the diagonal to 0
171 : //------------------------------------------------------------------
172 :
173 5 : int ntrials = 1 ; // increase this to 10, 100, whatever, for more
174 : // accurate timing
175 : // start the timer
176 5 : double t5 = LAGraph_WallClockTime ( ) ;
177 : int result ;
178 :
179 10 : for (int trial = 0 ; trial < ntrials ; trial++)
180 : {
181 5 : GrB_free (&d5) ;
182 5 : GrB_free (&pi5) ;
183 5 : GrB_free (&h5) ;
184 5 : result = (LAGraph_BF_full1 (&d5, &pi5, &h5, A_orig, s)) ;
185 5 : printf ("result: %d\n", result) ;
186 5 : TEST_CHECK (result == valid) ;
187 : }
188 :
189 : // stop the timer
190 5 : t5 = LAGraph_WallClockTime ( ) - t5 ;
191 5 : t5 = t5 / ntrials;
192 : // fprintf (stderr, "BF_full1 time: %12.6e (sec), rate:"
193 : // " %g (1e6 edges/sec)\n", t5, 1e-6*((double) nvals) / t5) ;
194 :
195 : //------------------------------------------------------------------
196 : // run LAGraph_BF_full1a before setting the diagonal to 0
197 : //------------------------------------------------------------------
198 :
199 : // start the timer
200 5 : double t5a = LAGraph_WallClockTime ( ) ;
201 :
202 10 : for (int trial = 0 ; trial < ntrials ; trial++)
203 : {
204 5 : GrB_free (&d5a) ;
205 5 : GrB_free (&pi5a) ;
206 5 : GrB_free (&h5a) ;
207 5 : result = (LAGraph_BF_full1a (&d5a, &pi5a, &h5a, A_orig, s)) ;
208 5 : TEST_CHECK (result == valid) ;
209 : }
210 :
211 : // stop the timer
212 5 : t5a = LAGraph_WallClockTime ( ) - t5a ;
213 5 : t5a = t5a / ntrials;
214 : // fprintf (stderr, "BF_full1a time: %12.6e (sec), rate:"
215 : // " %g (1e6 edges/sec)\n", t5a, 1e-6*((double) nvals) / t5a) ;
216 :
217 : //------------------------------------------------------------------
218 : // run LAGraph_BF_full2 before setting the diagonal to 0
219 : //------------------------------------------------------------------
220 :
221 : // start the timer
222 5 : double t6 = LAGraph_WallClockTime ( ) ;
223 :
224 10 : for (int trial = 0 ; trial < ntrials ; trial++)
225 : {
226 5 : GrB_free (&d6) ;
227 5 : GrB_free (&pi6) ;
228 5 : GrB_free (&h6) ;
229 5 : result = LAGraph_BF_full2 (&d6, &pi6, &h6, A_orig, s) ;
230 5 : TEST_CHECK (result == valid) ;
231 : }
232 :
233 : // stop the timer
234 5 : t6 = LAGraph_WallClockTime ( ) - t6 ;
235 5 : t6 = t6 / ntrials;
236 : // fprintf (stderr, "BF_full2 time: %12.6e (sec), rate:"
237 : // " %g (1e6 edges/sec)\n", t6, 1e-6*((double) nvals) / t6) ;
238 :
239 : //------------------------------------------------------------------
240 : // run the LAGraph_BF_full on node s
241 : //------------------------------------------------------------------
242 :
243 : // start the timer
244 5 : double t1 = LAGraph_WallClockTime ( ) ;
245 :
246 10 : for (int trial = 0 ; trial < ntrials ; trial++)
247 : {
248 5 : GrB_free (&d1) ;
249 5 : GrB_free (&pi1) ;
250 5 : GrB_free (&h1) ;
251 5 : result = LAGraph_BF_full (&d1, &pi1, &h1, A, s) ;
252 5 : printf ("result %d\n", result) ;
253 5 : TEST_CHECK (result == valid) ;
254 : }
255 :
256 : // stop the timer
257 5 : t1 = LAGraph_WallClockTime ( ) - t1 ;
258 5 : t1 = t1 / ntrials;
259 : // fprintf (stderr, "BF_full time: %12.6e (sec), rate:"
260 : // " %g (1e6 edges/sec)\n", t1, 1e-6*((double) nvals) / t1) ;
261 : // fprintf (stderr, "t(BF_full1) / t(BF_full): %g\n", t5/t1) ;
262 :
263 : //------------------------------------------------------------------
264 : // run the BF on node s with LAGraph_BF_basic
265 : //------------------------------------------------------------------
266 :
267 : // start the timer
268 5 : double t2 = LAGraph_WallClockTime ( ) ;
269 :
270 10 : for (int trial = 0 ; trial < ntrials ; trial++)
271 : {
272 5 : GrB_free (&d3) ;
273 5 : result = LAGraph_BF_basic (&d3, A, s) ;
274 5 : TEST_CHECK (result == valid) ;
275 : }
276 :
277 : // stop the timer
278 5 : t2 = LAGraph_WallClockTime ( ) - t2 ;
279 5 : t2 = t2 / ntrials;
280 : // fprintf (stderr, "BF_basic time: %12.6e (sec), rate:"
281 : // " %g (1e6 edges/sec)\n", t2, 1e-6*((double) nvals) / t2) ;
282 : // fprintf (stderr, "speedup of BF_basic: %g\n", t1/t2) ;
283 :
284 : //------------------------------------------------------------------
285 : // run the BF on node s with LAGraph_pure_c
286 : //------------------------------------------------------------------
287 :
288 : // start the timer
289 5 : double t3 = LAGraph_WallClockTime ( ) ;
290 :
291 10 : for (int trial = 0 ; trial < ntrials ; trial++)
292 : {
293 5 : LAGraph_Free ((void **) &d, NULL) ;
294 5 : LAGraph_Free ((void **) &pi, NULL) ;
295 5 : result = LAGraph_BF_pure_c_double (&d, &pi, s, n, nvals,
296 : (const int64_t *) I, (const int64_t *) J, W) ;
297 5 : TEST_CHECK (result == valid) ;
298 : }
299 :
300 : // stop the timer
301 5 : t3 = LAGraph_WallClockTime ( ) - t3 ;
302 5 : t3 = t3 / ntrials;
303 : // fprintf (stderr, "BF_pure_c_double : %12.6e (sec), rate:"
304 : // " %g (1e6 edges/sec)\n", t3, 1e-6*((double) nvals) / t3) ;
305 : // fprintf (stderr, "speedup of BF_pure_c: %g\n", t1/t3) ;
306 :
307 5 : if (has_integer_weights)
308 : {
309 3 : printf ("pure_c integer:\n") ;
310 3 : LAGraph_Free ((void **) &d10, NULL) ;
311 3 : LAGraph_Free ((void **) &pi10, NULL) ;
312 3 : result = LAGraph_BF_pure_c (&d10, &pi10, s, n, nvals,
313 : (const int64_t *) I, (const int64_t *) J, W_int32) ;
314 3 : LAGraph_Free ((void **) &pi10, NULL) ;
315 3 : TEST_CHECK (result == valid) ;
316 : }
317 :
318 : //------------------------------------------------------------------
319 : // run the LAGraph_BF_full_mxv on node s
320 : //------------------------------------------------------------------
321 :
322 : // start the timer
323 5 : double t4 = LAGraph_WallClockTime ( ) ;
324 :
325 10 : for (int trial = 0 ; trial < ntrials ; trial++)
326 : {
327 5 : GrB_free (&d2) ;
328 5 : GrB_free (&pi2) ;
329 5 : GrB_free (&h2) ;
330 5 : result = LAGraph_BF_full_mxv (&d2, &pi2, &h2, AT, s) ;
331 5 : TEST_CHECK (result == valid) ;
332 : }
333 :
334 : // stop the timer
335 5 : t4 = LAGraph_WallClockTime ( ) - t4 ;
336 5 : t4 = t4 / ntrials;
337 : // fprintf (stderr, "BF_full_mxv time: %12.6e (sec), rate:"
338 : // " %g (1e6 edges/sec)\n", t4, 1e-6*((double) nvals) / t4) ;
339 : // fprintf (stderr, "speedup of BF_full_mxv: %g\n", t1/t4) ;
340 :
341 : //------------------------------------------------------------------
342 : // run the BF on node s with LAGraph_BF_basic_mxv
343 : //------------------------------------------------------------------
344 :
345 : // start the timer
346 5 : double t7 = LAGraph_WallClockTime ( ) ;
347 :
348 10 : for (int trial = 0 ; trial < ntrials ; trial++)
349 : {
350 5 : GrB_free (&d4) ;
351 5 : result = LAGraph_BF_basic_mxv (&d4, AT, s) ;
352 5 : TEST_CHECK (result == valid) ;
353 : }
354 :
355 : // stop the timer
356 5 : t7 = LAGraph_WallClockTime ( ) - t7 ;
357 5 : t7 = t7 / ntrials;
358 : // fprintf (stderr, "BF_basic_mxv time: %12.6e (sec), rate:"
359 : // " %g (1e6 edges/sec)\n", t7, 1e-6*((double) nvals) / t7) ;
360 : // fprintf (stderr, "speedup of BF_basic_mxv: %g\n", t1/t7) ;
361 :
362 : //------------------------------------------------------------------
363 : // run the BF on node s with LAGraph_BF_basic_pushpull
364 : //------------------------------------------------------------------
365 :
366 5 : GrB_free (&d7) ;
367 5 : result = (LAGraph_BF_basic_pushpull (&d7, A, AT, s)) ;
368 5 : TEST_CHECK (result == valid) ;
369 :
370 5 : GrB_free (&d8) ;
371 5 : result = (LAGraph_BF_basic_pushpull (&d8, NULL, AT, s)) ;
372 5 : TEST_CHECK (result == valid) ;
373 :
374 5 : GrB_free (&d9) ;
375 5 : result = (LAGraph_BF_basic_pushpull (&d9, A, NULL, s)) ;
376 5 : TEST_CHECK (result == valid) ;
377 :
378 : //------------------------------------------------------------------
379 : // check results
380 : //------------------------------------------------------------------
381 :
382 5 : bool isequal = false ;
383 :
384 5 : if (!has_negative_cycle)
385 : {
386 3 : TEST_CHECK (d != NULL && d1 != NULL) ;
387 :
388 111 : for (int64_t i = 0 ; i < n ; i++)
389 : {
390 108 : double di = INFINITY ;
391 108 : int64_t pii = 0;
392 108 : OK (GrB_Vector_extractElement (&di, d1, i)) ;
393 108 : TEST_CHECK (di == d[i]) ;
394 :
395 : // since d5 is a dense vector filled with infinity, we have
396 : // to compare it against d seperaterly
397 108 : OK (GrB_Vector_extractElement (&di, d5, i)) ;
398 108 : TEST_CHECK (di == d[i]) ;
399 :
400 : // since d5a is a dense vector filled with infinity, we
401 : // have to compare it against d seperaterly
402 108 : OK (GrB_Vector_extractElement (&di, d5a, i)) ;
403 108 : TEST_CHECK (di == d[i]) ;
404 : /*
405 : OK (GrB_Vector_extractElement (&pii, pi1, i)) ;
406 : TEST_CHECK (pii == pi[i]+1) ;
407 : */
408 : }
409 :
410 3 : if (has_integer_weights)
411 : {
412 : // compare d and d10
413 43 : for (int64_t i = 0 ; i < n ; i++)
414 : {
415 41 : double d10i = (double) d10 [i] ;
416 41 : double di = (isinf (d [i])) ? INT32_MAX : d [i] ;
417 41 : TEST_CHECK (d10i == di) ;
418 : }
419 : }
420 :
421 3 : OK (LAGraph_Vector_IsEqual (&isequal, d1, d3, NULL)) ;
422 3 : TEST_CHECK (isequal) ;
423 :
424 3 : OK (LAGraph_Vector_IsEqual (&isequal, d1, d4, NULL)) ;
425 3 : TEST_CHECK (isequal) ;
426 :
427 3 : OK (LAGraph_Vector_IsEqual (&isequal, d1, d2, NULL)) ;
428 3 : TEST_CHECK (isequal) ;
429 :
430 3 : OK (LAGraph_Vector_IsEqual (&isequal, d1, d6, NULL)) ;
431 3 : TEST_CHECK (isequal) ;
432 :
433 : /*
434 : OK (LAGraph_Vector_IsEqual (&isequal, pi1, pi2, NULL)) ;
435 : TEST_CHECK (isequal) ;
436 : */
437 :
438 3 : OK (LAGraph_Vector_IsEqual (&isequal, d1, d7, NULL)) ;
439 3 : TEST_CHECK (isequal) ;
440 :
441 3 : OK (LAGraph_Vector_IsEqual (&isequal, d1, d8, NULL)) ;
442 3 : TEST_CHECK (isequal) ;
443 :
444 3 : OK (LAGraph_Vector_IsEqual (&isequal, d1, d9, NULL)) ;
445 3 : TEST_CHECK (isequal) ;
446 : }
447 :
448 : //------------------------------------------------------------------
449 : // ensure the matrix has all positive weights for next trial
450 : //------------------------------------------------------------------
451 :
452 5 : if (has_negative_cycle)
453 : {
454 2 : printf ("\n-------------------------- A = abs (A)\n") ;
455 2 : OK (GrB_apply (A, NULL, NULL, GrB_ABS_FP64, A, NULL)) ;
456 2 : OK (GrB_apply (AT, NULL, NULL, GrB_ABS_FP64, AT, NULL)) ;
457 2 : OK (GrB_apply (A_orig, NULL, NULL, GrB_ABS_FP64, A_orig, NULL));
458 2 : OK (GrB_Matrix_extractTuples_FP64 (I, J, W, &nvals, A_orig)) ;
459 2 : if (has_integer_weights)
460 : {
461 1 : OK (GrB_Matrix_extractTuples_INT32 (I, J, W_int32, &nvals,
462 : A_orig)) ;
463 : }
464 2 : has_negative_cycle = false ;
465 : }
466 : }
467 :
468 : //----------------------------------------------------------------------
469 : // free all workspace and finish
470 : //----------------------------------------------------------------------
471 :
472 3 : GrB_free (&A) ;
473 3 : GrB_free (&A_orig) ;
474 3 : GrB_free (&AT) ;
475 3 : LAGraph_Free ((void **) &I, NULL) ;
476 3 : LAGraph_Free ((void **) &J, NULL) ;
477 3 : LAGraph_Free ((void **) &W, NULL) ;
478 3 : LAGraph_Free ((void **) &W_int32, NULL) ;
479 3 : LAGraph_Free ((void **) &d, NULL) ;
480 3 : LAGraph_Free ((void **) &pi, NULL) ;
481 3 : GrB_free (&d1) ;
482 3 : GrB_free (&pi1) ;
483 3 : GrB_free (&h1) ;
484 3 : GrB_free (&d2) ;
485 3 : GrB_free (&pi2) ;
486 3 : GrB_free (&h2) ;
487 3 : GrB_free (&d3) ;
488 3 : GrB_free (&d4) ;
489 3 : GrB_free (&d5) ;
490 3 : GrB_free (&pi5) ;
491 3 : GrB_free (&h5) ;
492 3 : GrB_free (&d5a) ;
493 3 : GrB_free (&pi5a) ;
494 3 : GrB_free (&h5a) ;
495 3 : GrB_free (&d6) ;
496 3 : GrB_free (&d7) ;
497 3 : GrB_free (&d8) ;
498 3 : GrB_free (&d9) ;
499 3 : GrB_free (&pi6) ;
500 3 : GrB_free (&h6) ;
501 3 : LAGraph_Free ((void **) &d10, NULL) ;
502 : }
503 :
504 1 : teardown ( ) ;
505 1 : }
506 :
507 : //------------------------------------------------------------------------------
508 : // TEST_LIST: list of tasks for this entire test
509 : //------------------------------------------------------------------------------
510 :
511 : TEST_LIST =
512 : {
513 : { "test_BF", test_BF },
514 : { NULL, NULL }
515 : } ;
|
