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