Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/src/test/test_BreadthFirstSearch.c: test cases for triangle
3 : // counting algorithms
4 : // ----------------------------------------------------------------------------
5 :
6 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
7 : // SPDX-License-Identifier: BSD-2-Clause
8 : //
9 : // For additional details (including references to third party source code and
10 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
11 : // Contributors.txt for a full list of contributors. Created, in part, with
12 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
13 : // DM22-0790
14 :
15 : // Contributed by Scott McMillan, SEI/CMU, and Timothy A. Davis, Texas A&M
16 : // University
17 :
18 : //-----------------------------------------------------------------------------
19 :
20 : #include <stdio.h>
21 : #include <acutest.h>
22 :
23 : #include <LAGraph_test.h>
24 : #include <graph_zachary_karate.h>
25 : #include "LG_alg_internal.h"
26 : #include "LAGraphX.h"
27 :
28 : char msg[LAGRAPH_MSG_LEN];
29 : LAGraph_Graph G = NULL;
30 :
31 : //-----------------------------------------------------------------------------
32 : // Valid results for Karate graph:
33 : //-----------------------------------------------------------------------------
34 :
35 : GrB_Index const SRC = 30;
36 : // the levels of the tree for the Karate graph, assuming source node 30:
37 : GrB_Index const LEVELS30[] = {2, 1, 2, 2, 3, 3, 3, 2, 1, 2, 3, 3,
38 : 3, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2,
39 : 3, 3, 2, 2, 2, 2, 0, 2, 1, 1};
40 : // Karate BFS parents, with source node 30. This assumes the parent is the min
41 : // of the valid set of parents:
42 : // GrB_Index const PARENT30[] = { 1, 30, 1, 1, 0, 0, 0, 1, 30, 33, 0, 0,
43 : // 0, 1, 32, 32, 5, 1, 32, 1, 32, 1, 32, 32,
44 : // 27, 23, 33, 33, 33, 32, 30, 32, 30, 30};
45 : #define xx (-1)
46 : // The following are valid parents for each node, with source node of 30:
47 : GrB_Index const PARENT30 [34][3] = {
48 : { 1, 8, xx }, // node 0 can have parents 1 or 8
49 : { 30, xx, xx }, // node 1, parent 30
50 : { 1, 8, 32 }, // node 2, parents 1, 8, or 32, etc
51 : { 1, xx, xx }, // node 3
52 : { 0, xx, xx }, // node 4
53 : { 0, xx, xx }, // node 5
54 : { 0, xx, xx }, // node 6
55 : { 1, xx, xx }, // node 7
56 : { 30, xx, xx }, // node 8
57 : { 33, xx, xx }, // node 9
58 : { 0, xx, xx }, // node 10
59 : { 0, xx, xx }, // node 11
60 : { 0, 3, xx }, // node 12
61 : { 1, 33, xx }, // node 13
62 : { 32, 33, xx }, // node 14
63 : { 32, 33, xx }, // node 15
64 : { 5, 6, xx }, // node 16
65 : { 1, xx, xx }, // node 17
66 : { 32, 33, xx }, // node 18
67 : { 1, 33, xx }, // node 19
68 : { 32, 33, xx }, // node 20
69 : { 1, xx, xx }, // node 21
70 : { 32, 33, xx }, // node 22
71 : { 32, 33, xx }, // node 23
72 : { 27, 31, xx }, // node 24
73 : { 23, 31, xx }, // node 25
74 : { 33, xx, xx }, // node 26
75 : { 33, xx, xx }, // node 27
76 : { 33, xx, xx }, // node 28
77 : { 32, 33, xx }, // node 29
78 : { 30, xx, xx }, // node 30, source node
79 : { 32, 33, xx }, // node 31
80 : { 30, xx, xx }, // node 32
81 : { 30, xx, xx }} ; // node 33
82 : #undef xx
83 :
84 : //-----------------------------------------------------------------------------
85 :
86 : #define LEN 512
87 : char filename [LEN+1] ;
88 :
89 : typedef struct
90 : {
91 : LAGraph_Kind kind ;
92 : const char *name ;
93 : }
94 : matrix_info ;
95 :
96 : const matrix_info files [ ] =
97 : {
98 : { LAGraph_ADJACENCY_UNDIRECTED, "jagmesh7.mtx" },
99 : { LAGraph_ADJACENCY_UNDIRECTED, "A.mtx" },
100 : { LAGraph_ADJACENCY_DIRECTED, "cover.mtx" },
101 : { LAGraph_ADJACENCY_DIRECTED, "ldbc-cdlp-directed-example.mtx" },
102 : { LAGraph_ADJACENCY_UNDIRECTED, "ldbc-cdlp-undirected-example.mtx" },
103 : { LAGraph_ADJACENCY_DIRECTED, "ldbc-directed-example.mtx" },
104 : { LAGraph_ADJACENCY_UNDIRECTED, "ldbc-undirected-example.mtx" },
105 : { LAGraph_ADJACENCY_UNDIRECTED, "ldbc-wcc-example.mtx" },
106 : { LAGraph_ADJACENCY_UNDIRECTED, "LFAT5.mtx" },
107 : { LAGraph_ADJACENCY_DIRECTED, "msf1.mtx" },
108 : { LAGraph_ADJACENCY_DIRECTED, "msf2.mtx" },
109 : { LAGraph_ADJACENCY_DIRECTED, "msf3.mtx" },
110 : { LAGraph_ADJACENCY_DIRECTED, "sample2.mtx" },
111 : { LAGraph_ADJACENCY_DIRECTED, "sample.mtx" },
112 : { LAGraph_ADJACENCY_DIRECTED, "olm1000.mtx" },
113 : { LAGraph_ADJACENCY_UNDIRECTED, "bcsstk13.mtx" },
114 : { LAGraph_ADJACENCY_DIRECTED, "cryg2500.mtx" },
115 : { LAGraph_ADJACENCY_UNDIRECTED, "tree-example.mtx" },
116 : { LAGraph_ADJACENCY_DIRECTED, "west0067.mtx" },
117 : { LAGraph_ADJACENCY_UNDIRECTED, "karate.mtx" },
118 : { LAGraph_ADJACENCY_DIRECTED, "matrix_bool.mtx" },
119 : { LAGraph_ADJACENCY_DIRECTED, "skew_fp32.mtx" },
120 : { LAGraph_ADJACENCY_UNDIRECTED, "pushpull.mtx" },
121 : { LAGRAPH_UNKNOWN, "" },
122 : } ;
123 :
124 : //****************************************************************************
125 7 : bool check_karate_parents30(GrB_Vector parents)
126 : {
127 : // An update to SS:GrB can result in different, yet valid, parent vectors
128 : // (even single-threaded). The LG_check_bfs works fine and those tests
129 : // pass. This parent test looks for any valid parent vector.
130 :
131 7 : GrB_Index n = 0;
132 7 : TEST_CHECK(0 == GrB_Vector_size(&n, parents));
133 7 : TEST_CHECK(ZACHARY_NUM_NODES == n);
134 7 : TEST_CHECK(0 == GrB_Vector_nvals(&n, parents));
135 7 : TEST_CHECK(ZACHARY_NUM_NODES == n);
136 :
137 7 : bool ok = false ;
138 : int64_t parent_id;
139 211 : for (GrB_Index ix = 0; ix < ZACHARY_NUM_NODES; ++ix)
140 : {
141 205 : TEST_CHECK(0 == GrB_Vector_extractElement(&parent_id, parents, ix));
142 : // prior test:
143 : // TEST_CHECK(parent_id == PARENT30[ix][0]);
144 : // TEST_MSG("Parent check failed for node %ld: ans,comp = %ld,%ld\n",
145 : // ix, PARENT30[ix][0], parent_id);
146 : // more general test:
147 205 : ok = false ;
148 207 : for (int k = 0 ; k <= 2 ; k++)
149 : {
150 207 : int valid_parent_id = PARENT30 [ix][k] ;
151 207 : if (valid_parent_id < 0)
152 : {
153 : // end of the list of valid parent ids
154 1 : ok = false ;
155 1 : break ;
156 : }
157 206 : if (parent_id == valid_parent_id)
158 : {
159 : // a match is found
160 204 : ok = true ;
161 204 : break ;
162 : }
163 : }
164 205 : if (!ok) break ;
165 : }
166 :
167 7 : return ok;
168 : }
169 :
170 : //****************************************************************************
171 5 : bool check_karate_levels30(GrB_Vector levels)
172 : {
173 5 : GrB_Index n = 0;
174 5 : TEST_CHECK(0 == GrB_Vector_size(&n, levels) );
175 5 : TEST_CHECK(ZACHARY_NUM_NODES == n);
176 5 : TEST_CHECK(0 == GrB_Vector_nvals(&n, levels) );
177 5 : TEST_CHECK(ZACHARY_NUM_NODES == n);
178 :
179 : int64_t lvl;
180 175 : for (GrB_Index ix = 0; ix < ZACHARY_NUM_NODES; ++ix)
181 : {
182 170 : TEST_CHECK(0 == GrB_Vector_extractElement(&lvl, levels, ix) );
183 170 : TEST_CHECK(lvl == LEVELS30[ix] );
184 170 : TEST_MSG("Level check failed for node %g: ans,comp = %g,%g\n",
185 : (double) ix, (double) LEVELS30[ix], (double) lvl);
186 : }
187 :
188 5 : return true;
189 : }
190 :
191 : //****************************************************************************
192 7 : void setup(void)
193 : {
194 7 : LAGraph_Init(msg);
195 : // OK (LG_SET_BURBLE (true)) ;
196 : int retval;
197 7 : GrB_Matrix A = NULL;
198 :
199 7 : TEST_CHECK(0 == GrB_Matrix_new(&A, GrB_UINT32,
200 : ZACHARY_NUM_NODES, ZACHARY_NUM_NODES) );
201 7 : TEST_CHECK(0 == GrB_Matrix_build(A, ZACHARY_I, ZACHARY_J, ZACHARY_V,
202 : ZACHARY_NUM_EDGES, GrB_LOR) );
203 :
204 7 : retval = LAGraph_New(&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg);
205 7 : TEST_CHECK(retval == 0);
206 7 : TEST_MSG("retval = %d (%s)", retval, msg);
207 7 : }
208 :
209 : //****************************************************************************
210 7 : void teardown(void)
211 : {
212 7 : int retval = LAGraph_Delete(&G, msg);
213 7 : TEST_CHECK(retval == 0);
214 7 : TEST_MSG("retval = %d (%s)", retval, msg);
215 :
216 7 : G = NULL;
217 7 : LAGraph_Finalize(msg);
218 7 : }
219 :
220 : //****************************************************************************
221 1 : void test_BreadthFirstSearch_invalid_graph(void)
222 : {
223 1 : setup();
224 : int retval;
225 1 : LAGraph_Graph graph = NULL;
226 :
227 1 : retval = LAGr_BreadthFirstSearch(NULL, NULL, graph, 0, msg);
228 1 : TEST_CHECK(retval == GrB_NULL_POINTER);
229 1 : TEST_MSG("retval = %d (%s)", retval, msg);
230 :
231 1 : retval = LG_BreadthFirstSearch_vanilla(NULL, NULL, graph, 0, msg);
232 1 : TEST_CHECK(retval == GrB_NULL_POINTER);
233 1 : TEST_MSG("retval = %d (%s)", retval, msg);
234 :
235 1 : teardown();
236 1 : }
237 :
238 : //****************************************************************************
239 1 : void test_BreadthFirstSearch_invalid_src(void)
240 : {
241 1 : setup();
242 : int retval;
243 : GrB_Index n;
244 1 : TEST_CHECK(0 == GrB_Matrix_nrows(&n, (G->A)));
245 :
246 1 : GrB_Vector parent = NULL ;
247 1 : GrB_Vector level = NULL ;
248 :
249 1 : retval = LAGr_BreadthFirstSearch(&level, NULL, G, n, msg);
250 1 : TEST_CHECK(retval == GrB_INVALID_INDEX);
251 1 : TEST_MSG("retval = %d (%s)", retval, msg);
252 :
253 1 : retval = LG_BreadthFirstSearch_vanilla(&level, NULL, G, n, msg);
254 1 : TEST_CHECK(retval == GrB_INVALID_INDEX);
255 1 : TEST_MSG("retval = %d (%s)", retval, msg);
256 :
257 1 : retval = LAGr_BreadthFirstSearch(NULL, &parent, G, n, msg);
258 1 : TEST_CHECK(retval == GrB_INVALID_INDEX);
259 1 : TEST_MSG("retval = %d (%s)", retval, msg);
260 :
261 1 : retval = LG_BreadthFirstSearch_vanilla(NULL, &parent, G, n, msg);
262 1 : TEST_CHECK(retval == GrB_INVALID_INDEX);
263 1 : TEST_MSG("retval = %d (%s)", retval, msg);
264 :
265 1 : teardown();
266 1 : }
267 :
268 : //****************************************************************************
269 1 : void test_BreadthFirstSearch_neither(void)
270 : {
271 1 : setup();
272 : int retval;
273 :
274 1 : printf ("\nTest level and parent both NULL:\n") ;
275 :
276 1 : LAGraph_PrintLevel pr = LAGraph_COMPLETE_VERBOSE ;
277 1 : retval = LAGraph_Graph_Print (G, pr, stdout, msg) ;
278 1 : TEST_CHECK(retval == GrB_SUCCESS);
279 :
280 1 : retval = LAGr_BreadthFirstSearch(NULL, NULL, G, 0, msg);
281 1 : TEST_CHECK(retval == GrB_NULL_POINTER);
282 1 : TEST_MSG("retval = %d (%s)", retval, msg);
283 :
284 1 : retval = LG_BreadthFirstSearch_vanilla(NULL, NULL, G, 0, msg);
285 1 : TEST_CHECK(retval == GrB_NULL_POINTER);
286 1 : TEST_MSG("retval = %d (%s)", retval, msg);
287 :
288 1 : retval = LAGr_BreadthFirstSearch(NULL, NULL, G, 0, msg);
289 1 : TEST_CHECK(retval == GrB_NULL_POINTER);
290 1 : TEST_MSG("retval = %d (%s)", retval, msg);
291 :
292 1 : retval = LG_BreadthFirstSearch_vanilla(NULL, NULL, G, 0, msg);
293 1 : TEST_CHECK(retval == GrB_NULL_POINTER);
294 1 : TEST_MSG("retval = %d (%s)", retval, msg);
295 :
296 1 : teardown();
297 1 : }
298 :
299 : //****************************************************************************
300 1 : void test_BreadthFirstSearch_parent(void)
301 : {
302 1 : setup();
303 : int retval;
304 :
305 1 : GrB_Vector parent = NULL;
306 1 : GrB_Vector parent_do = NULL;
307 :
308 1 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
309 :
310 1 : retval = LAGr_BreadthFirstSearch(NULL, &parent, G, 30, msg);
311 1 : TEST_CHECK(retval == 0);
312 1 : TEST_MSG("retval = %d (%s)", retval, msg);
313 1 : TEST_CHECK(check_karate_parents30(parent));
314 1 : retval = LG_check_bfs (NULL, parent, G, 30, msg) ;
315 1 : TEST_CHECK (retval == 0) ;
316 :
317 : // mangle the parent vector, just to check check_karate_parents30
318 1 : OK (GrB_Vector_setElement (parent, 0, 0)) ;
319 1 : TEST_CHECK(!check_karate_parents30(parent));
320 1 : TEST_CHECK(0 == GrB_free(&parent));
321 :
322 1 : retval = LG_BreadthFirstSearch_vanilla(NULL, &parent, G, 30, msg);
323 1 : TEST_CHECK(retval == 0);
324 1 : TEST_MSG("retval = %d (%s)", retval, msg);
325 1 : TEST_CHECK(check_karate_parents30(parent));
326 1 : retval = LG_check_bfs (NULL, parent, G, 30, msg) ;
327 1 : TEST_CHECK (retval == 0) ;
328 1 : TEST_CHECK(0 == GrB_free(&parent));
329 :
330 1 : retval = LAGr_BreadthFirstSearch(NULL, &parent_do, G, 30, msg);
331 1 : TEST_CHECK(retval == 0);
332 1 : TEST_MSG("retval = %d (%s)", retval, msg);
333 1 : TEST_CHECK(check_karate_parents30(parent_do));
334 1 : retval = LG_check_bfs (NULL, parent_do, G, 30, msg) ;
335 1 : TEST_CHECK (retval == 0) ;
336 1 : TEST_CHECK(0 == GrB_free(&parent_do));
337 :
338 1 : retval = LG_BreadthFirstSearch_vanilla(NULL, &parent_do, G, 30, msg);
339 1 : TEST_CHECK(retval == 0);
340 1 : TEST_MSG("retval = %d (%s)", retval, msg);
341 1 : TEST_CHECK(check_karate_parents30(parent_do));
342 1 : retval = LG_check_bfs (NULL, parent_do, G, 30, msg) ;
343 1 : TEST_CHECK (retval == 0) ;
344 1 : TEST_CHECK(0 == GrB_free(&parent_do));
345 :
346 1 : GrB_Index n = 0 ;
347 1 : TEST_CHECK (0 == GrB_Matrix_nrows (&n, G->A)) ;
348 35 : for (GrB_Index src = 0 ; src < n ; src++)
349 : {
350 34 : retval = LAGr_BreadthFirstSearch(NULL, &parent, G, src, msg);
351 34 : TEST_CHECK(retval == 0);
352 34 : retval = LG_check_bfs (NULL, parent, G, src, msg) ;
353 34 : TEST_CHECK (retval == 0) ;
354 34 : TEST_CHECK(0 == GrB_free(&parent));
355 :
356 34 : retval = LG_BreadthFirstSearch_vanilla(NULL, &parent, G, src, msg);
357 34 : TEST_CHECK(retval == 0);
358 34 : retval = LG_check_bfs (NULL, parent, G, src, msg) ;
359 34 : TEST_CHECK (retval == 0) ;
360 34 : TEST_CHECK(0 == GrB_free(&parent));
361 : }
362 :
363 1 : teardown();
364 1 : }
365 :
366 : //****************************************************************************
367 1 : void test_BreadthFirstSearch_level(void)
368 : {
369 1 : setup();
370 : int retval;
371 :
372 1 : GrB_Vector level = NULL;
373 1 : GrB_Vector level_do = NULL;
374 1 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
375 :
376 1 : retval = LAGr_BreadthFirstSearch(&level, NULL, G, 30, msg);
377 1 : TEST_CHECK(retval == 0);
378 1 : TEST_MSG("retval = %d (%s)", retval, msg);
379 1 : TEST_CHECK(check_karate_levels30(level));
380 1 : retval = LG_check_bfs (level, NULL, G, 30, msg) ;
381 1 : TEST_CHECK (retval == 0) ;
382 1 : TEST_CHECK(0 == GrB_free(&level));
383 :
384 1 : retval = LG_BreadthFirstSearch_vanilla(&level, NULL, G, 30, msg);
385 1 : TEST_CHECK(retval == 0);
386 1 : TEST_MSG("retval = %d (%s)", retval, msg);
387 1 : TEST_CHECK(check_karate_levels30(level));
388 1 : retval = LG_check_bfs (level, NULL, G, 30, msg) ;
389 1 : TEST_CHECK (retval == 0) ;
390 1 : TEST_CHECK(0 == GrB_free(&level));
391 :
392 1 : retval = LAGr_BreadthFirstSearch(&level_do, NULL, G, 30, msg);
393 1 : TEST_CHECK(retval == 0);
394 1 : TEST_MSG("retval = %d (%s)", retval, msg);
395 1 : TEST_CHECK(check_karate_levels30(level_do));
396 1 : retval = LG_check_bfs (level_do, NULL, G, 30, msg) ;
397 1 : TEST_CHECK (retval == 0) ;
398 1 : TEST_CHECK(0 == GrB_free(&level_do));
399 :
400 1 : GrB_Index n = 0 ;
401 1 : TEST_CHECK (0 == GrB_Matrix_nrows (&n, G->A)) ;
402 35 : for (GrB_Index src = 0 ; src < n ; src++)
403 : {
404 :
405 34 : retval = LAGr_BreadthFirstSearch(&level, NULL, G, src, msg);
406 34 : TEST_CHECK(retval == 0);
407 34 : retval = LG_check_bfs (level, NULL, G, src, msg) ;
408 34 : TEST_CHECK (retval == 0) ;
409 34 : TEST_CHECK(0 == GrB_free(&level));
410 :
411 34 : retval = LG_BreadthFirstSearch_vanilla(&level, NULL, G, src, msg);
412 34 : TEST_CHECK(retval == 0);
413 34 : retval = LG_check_bfs (level, NULL, G, src, msg) ;
414 34 : TEST_CHECK (retval == 0) ;
415 34 : TEST_CHECK(0 == GrB_free(&level));
416 :
417 : }
418 :
419 1 : teardown();
420 1 : }
421 :
422 : //****************************************************************************
423 1 : void test_BreadthFirstSearch_both(void)
424 : {
425 1 : setup();
426 : int retval;
427 :
428 1 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
429 1 : GrB_Vector parent = NULL;
430 1 : GrB_Vector level = NULL;
431 1 : retval = LAGr_BreadthFirstSearch(&level, &parent, G, 30, msg);
432 1 : TEST_CHECK(retval == 0);
433 1 : TEST_MSG("retval = %d (%s)", retval, msg);
434 1 : TEST_CHECK(check_karate_levels30(level));
435 1 : TEST_CHECK(check_karate_parents30(parent));
436 :
437 1 : retval = LG_check_bfs (level, parent, G, 30, msg) ;
438 1 : TEST_CHECK (retval == 0) ;
439 :
440 1 : TEST_CHECK(0 == GrB_free(&parent));
441 1 : TEST_CHECK(0 == GrB_free(&level));
442 :
443 1 : GrB_Vector parent_do = NULL;
444 1 : GrB_Vector level_do = NULL;
445 1 : retval = LAGr_BreadthFirstSearch(&level_do, &parent_do, G, 30, msg);
446 1 : TEST_CHECK(retval == 0);
447 1 : TEST_MSG("retval = %d (%s)", retval, msg);
448 1 : TEST_CHECK(check_karate_levels30(level_do));
449 1 : TEST_CHECK(check_karate_parents30(parent_do));
450 1 : retval = LG_check_bfs (level_do, parent_do, G, 30, msg) ;
451 1 : TEST_CHECK (retval == 0) ;
452 1 : TEST_CHECK(0 == GrB_free(&parent_do));
453 1 : TEST_CHECK(0 == GrB_free(&level_do));
454 :
455 1 : GrB_Index n = 0 ;
456 1 : TEST_CHECK (0 == GrB_Matrix_nrows (&n, G->A)) ;
457 :
458 35 : for (GrB_Index src = 0 ; src < n ; src++)
459 : {
460 34 : retval = LAGr_BreadthFirstSearch(&level, &parent, G, src, msg);
461 34 : TEST_CHECK(retval == 0);
462 34 : retval = LG_check_bfs (level, parent, G, src, msg) ;
463 34 : TEST_CHECK (retval == 0) ;
464 34 : TEST_CHECK(0 == GrB_free(&parent));
465 34 : TEST_CHECK(0 == GrB_free(&level));
466 : }
467 :
468 1 : teardown();
469 1 : }
470 :
471 : //------------------------------------------------------------------------------
472 : // test_BreadthFirstSearch_Extended: test max_level and dest
473 : //------------------------------------------------------------------------------
474 :
475 1 : void test_BreadthFirstSearch_Extended(void)
476 : {
477 1 : setup();
478 1 : GrB_Vector level = NULL ;
479 :
480 7 : for (int64_t max_level = 0 ; max_level <= 5 ; max_level++)
481 : {
482 6 : printf ("\nmax_level: %" PRId64 "\n", max_level) ;
483 18 : for (int vanilla = 0 ; vanilla <= 1 ; vanilla++)
484 : {
485 : int retval ;
486 12 : if (vanilla)
487 : {
488 6 : retval = LG_BreadthFirstSearch_vanilla_Extended (&level,
489 : NULL, G, SRC, max_level, -1, msg) ;
490 : }
491 : else
492 : {
493 6 : retval = LAGr_BreadthFirstSearch_Extended (&level,
494 : NULL, G, SRC, max_level, -1, max_level > 2, msg) ;
495 : }
496 12 : TEST_CHECK (retval == GrB_SUCCESS) ;
497 :
498 : GrB_Index nvals ;
499 12 : OK (GrB_Vector_nvals (&nvals, level)) ;
500 12 : printf ("vanilla: %d nvals: %" PRIu64 "\n", vanilla, nvals) ;
501 :
502 : // check the levels of all nodes
503 420 : for (int64_t k = 0 ; k < 34 ; k++)
504 : {
505 408 : int64_t lvl = -1 ;
506 408 : int64_t valid_level = LEVELS30 [k] ;
507 408 : retval = GrB_Vector_extractElement (&lvl, level, k) ;
508 408 : if (valid_level <= max_level)
509 : {
510 264 : TEST_CHECK (retval == GrB_SUCCESS) ;
511 264 : TEST_CHECK (lvl == valid_level) ;
512 : }
513 : else
514 : {
515 144 : TEST_CHECK (retval == GrB_NO_VALUE) ;
516 : }
517 : }
518 12 : OK (GrB_free (&level)) ;
519 : }
520 : }
521 :
522 35 : for (int64_t dest = 0 ; dest < 34 ; dest++)
523 : {
524 34 : printf ("\ndest: %" PRId64 "\n", dest) ;
525 :
526 102 : for (int vanilla = 0 ; vanilla <= 1 ; vanilla++)
527 : {
528 : int retval ;
529 68 : if (vanilla)
530 : {
531 34 : retval = LG_BreadthFirstSearch_vanilla_Extended (&level,
532 : NULL, G, SRC, -1, dest, msg) ;
533 : }
534 : else
535 : {
536 34 : retval = LAGr_BreadthFirstSearch_Extended (&level,
537 : NULL, G, SRC, -1, dest, false, msg) ;
538 : }
539 68 : TEST_CHECK (retval == GrB_SUCCESS) ;
540 :
541 68 : int64_t lvl = -1 ;
542 68 : OK (GrB_Vector_extractElement (&lvl, level, dest)) ;
543 68 : int64_t valid_level = LEVELS30 [dest] ;
544 68 : TEST_CHECK (lvl == valid_level) ;
545 :
546 : GrB_Index nvals ;
547 68 : OK (GrB_Vector_nvals (&nvals, level)) ;
548 :
549 68 : printf (" vanilla: %d level %" PRId64 " nvals: %" PRIu64 "\n",
550 : vanilla, lvl, nvals) ;
551 :
552 68 : int64_t max_level = -1 ;
553 68 : OK (GrB_reduce (&max_level, NULL, GrB_MAX_MONOID_INT64, level,
554 : NULL)) ;
555 68 : TEST_CHECK (lvl == max_level) ;
556 68 : OK (GrB_free (&level)) ;
557 : }
558 : }
559 :
560 1 : teardown();
561 1 : }
562 :
563 : //****************************************************************************
564 1 : void test_BreadthFirstSearch_many(void)
565 : {
566 1 : LAGraph_Init(msg);
567 : // OK (LG_SET_BURBLE (true)) ;
568 1 : GrB_Matrix A = NULL ;
569 :
570 1 : for (int k = 0 ; ; k++)
571 23 : {
572 :
573 : // load the adjacency matrix as A
574 24 : const char *aname = files [k].name ;
575 24 : LAGraph_Kind kind = files [k].kind ;
576 24 : if (strlen (aname) == 0) break;
577 23 : TEST_CASE (aname) ;
578 23 : printf ("\nMatrix: %s\n", aname) ;
579 23 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
580 23 : FILE *f = fopen (filename, "r") ;
581 23 : TEST_CHECK (f != NULL) ;
582 23 : OK (LAGraph_MMRead (&A, f, msg)) ;
583 23 : OK (fclose (f)) ;
584 23 : TEST_MSG ("Loading of adjacency matrix failed") ;
585 :
586 : // create the graph
587 23 : OK (LAGraph_New (&G, &A, kind, msg)) ;
588 23 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
589 :
590 23 : GrB_Index n = 0 ;
591 23 : OK (GrB_Matrix_nrows (&n, G->A)) ;
592 :
593 69 : for (int caching = 0 ; caching <= 1 ; caching++)
594 : {
595 : // run the BFS
596 46 : int64_t step = (n > 100) ? (3*n/4) : ((n/4) + 1) ;
597 190 : for (int64_t src = 0 ; src < n ; src += step)
598 : {
599 144 : GrB_Vector parent = NULL ;
600 144 : GrB_Vector level = NULL ;
601 :
602 144 : int64_t maxlevel = -9999 ;
603 : GrB_Index nvisited ;
604 :
605 144 : OK (LAGr_BreadthFirstSearch (&level, &parent, G, src, msg)) ;
606 144 : OK (LG_check_bfs (level, parent, G, src, msg)) ;
607 144 : OK (GrB_reduce (&maxlevel, NULL, GrB_MAX_MONOID_INT64,
608 : level, NULL)) ;
609 144 : TEST_CHECK (maxlevel != -9999) ;
610 144 : OK (GrB_Vector_nvals (&nvisited, level)) ;
611 : {
612 144 : printf ("src %g n: %g max level: %g nvisited: %g\n",
613 : (double) src, (double) n, (double) maxlevel,
614 : (double) nvisited) ;
615 : }
616 144 : OK (GrB_free(&parent));
617 144 : OK (GrB_free(&level));
618 :
619 144 : OK (LG_BreadthFirstSearch_vanilla (&level, &parent,
620 : G, src, msg)) ;
621 144 : OK (LG_check_bfs (level, parent, G, src, msg)) ;
622 144 : OK (GrB_reduce (&maxlevel, NULL, GrB_MAX_MONOID_INT64,
623 : level, NULL)) ;
624 144 : OK (GrB_Vector_nvals (&nvisited, level)) ;
625 : {
626 144 : printf ("src %g n: %g max level: %g nvisited: %g\n",
627 : (double) src, (double) n, (double) maxlevel,
628 : (double) nvisited) ;
629 : }
630 144 : OK (GrB_free(&parent));
631 144 : OK (GrB_free(&level));
632 :
633 144 : OK (LAGr_BreadthFirstSearch (NULL, &parent, G, src, msg)) ;
634 144 : OK (LG_check_bfs (NULL, parent, G, src, msg)) ;
635 144 : OK (GrB_free(&parent));
636 :
637 144 : OK (LG_BreadthFirstSearch_vanilla (NULL, &parent,
638 : G, src, msg)) ;
639 144 : OK (LG_check_bfs (NULL, parent, G, src, msg)) ;
640 144 : OK (GrB_free(&parent));
641 :
642 144 : OK (LAGr_BreadthFirstSearch (&level, NULL, G, src, msg)) ;
643 144 : OK (LG_check_bfs (level, NULL, G, src, msg)) ;
644 144 : OK (GrB_free(&level));
645 :
646 144 : OK (LG_BreadthFirstSearch_vanilla (&level, NULL, G, src, msg)) ;
647 144 : OK (LG_check_bfs (level, NULL, G, src, msg)) ;
648 144 : OK (GrB_free(&level));
649 :
650 : }
651 :
652 : // create its cached properties
653 46 : int ok_result = (kind == LAGraph_ADJACENCY_UNDIRECTED) ?
654 46 : LAGRAPH_CACHE_NOT_NEEDED : GrB_SUCCESS ;
655 46 : int result = LAGraph_Cached_AT (G, msg) ;
656 46 : TEST_CHECK (result == ok_result) ;
657 46 : OK (LAGraph_CheckGraph (G, msg)) ;
658 46 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
659 46 : OK (LAGraph_CheckGraph (G, msg)) ;
660 46 : result = LAGraph_Cached_InDegree (G, msg) ;
661 46 : TEST_CHECK (result == ok_result) ;
662 46 : OK (LAGraph_CheckGraph (G, msg)) ;
663 : }
664 :
665 23 : OK (LAGraph_Delete (&G, msg)) ;
666 : }
667 :
668 1 : LAGraph_Finalize(msg);
669 1 : }
670 :
671 : //------------------------------------------------------------------------------
672 : // test_bfs_brutal
673 : //------------------------------------------------------------------------------
674 :
675 : #if LG_BRUTAL_TESTS
676 1 : void test_bfs_brutal (void)
677 : {
678 1 : OK (LG_brutal_setup (msg)) ;
679 1 : GrB_Matrix A = NULL ;
680 :
681 1 : for (int k = 0 ; ; k++)
682 23 : {
683 : // load the adjacency matrix as A
684 24 : const char *aname = files [k].name ;
685 24 : LAGraph_Kind kind = files [k].kind ;
686 24 : if (strlen (aname) == 0) break;
687 23 : TEST_CASE (aname) ;
688 23 : printf ("\nMatrix: %s\n", aname) ;
689 23 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
690 23 : FILE *f = fopen (filename, "r") ;
691 23 : TEST_CHECK (f != NULL) ;
692 23 : OK (LAGraph_MMRead (&A, f, msg)) ;
693 23 : OK (fclose (f)) ;
694 23 : TEST_MSG ("Loading of adjacency matrix failed") ;
695 : // create the graph
696 23 : OK (LAGraph_New (&G, &A, kind, msg)) ;
697 23 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
698 23 : GrB_Index n = 0 ;
699 23 : OK (GrB_Matrix_nrows (&n, G->A)) ;
700 23 : if (n >= 1000)
701 : {
702 : // only do the small graphs
703 5 : printf ("skipped\n") ;
704 5 : OK (LAGraph_Delete (&G, msg)) ;
705 5 : continue ;
706 : }
707 :
708 54 : for (int caching = 0 ; caching <= 1 ; caching++)
709 : {
710 : // run the BFS
711 36 : int64_t step = (n > 100) ? (3*n/4) : ((n/4) + 1) ;
712 160 : for (int64_t src = 0 ; src < n ; src += step)
713 : {
714 124 : GrB_Vector parent = NULL ;
715 124 : GrB_Vector level = NULL ;
716 :
717 : // parent and level with SS:GrB
718 5097 : LG_BRUTAL_BURBLE (LAGr_BreadthFirstSearch (&level, &parent, G, src, msg)) ;
719 124 : OK (LG_check_bfs (level, parent, G, src, msg)) ;
720 124 : OK (GrB_free (&parent)) ;
721 124 : OK (GrB_free (&level)) ;
722 :
723 : // level only with SS:GrB
724 4222 : LG_BRUTAL (LAGr_BreadthFirstSearch (&level, NULL, G, src, msg)) ;
725 124 : OK (LG_check_bfs (level, NULL, G, src, msg)) ;
726 124 : OK (GrB_free (&level)) ;
727 :
728 : // parent and level with vanilla
729 5030 : LG_BRUTAL (LG_BreadthFirstSearch_vanilla (&level,
730 : &parent, G, src, msg)) ;
731 124 : OK (LG_check_bfs (level, parent, G, src, msg)) ;
732 124 : OK (GrB_free (&parent)) ;
733 124 : OK (GrB_free (&level)) ;
734 :
735 : // level-only with vanilla
736 3958 : LG_BRUTAL (LG_BreadthFirstSearch_vanilla (&level, NULL,
737 : G, src, msg)) ;
738 124 : OK (LG_check_bfs (level, NULL, G, src, msg)) ;
739 124 : OK (GrB_free (&level)) ;
740 : }
741 :
742 : // create its cached properties
743 36 : int ok_result = (kind == LAGraph_ADJACENCY_UNDIRECTED) ?
744 36 : LAGRAPH_CACHE_NOT_NEEDED : GrB_SUCCESS ;
745 36 : int result = LAGraph_Cached_AT (G, msg) ;
746 36 : TEST_CHECK (result == ok_result) ;
747 36 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
748 36 : result = LAGraph_Cached_InDegree (G, msg) ;
749 36 : TEST_CHECK (result == ok_result) ;
750 : }
751 :
752 18 : OK (LAGraph_Delete (&G, msg)) ;
753 : }
754 :
755 1 : OK (LG_brutal_teardown (msg)) ;
756 1 : }
757 : #endif
758 :
759 : //****************************************************************************
760 : //****************************************************************************
761 : TEST_LIST = {
762 : {"BreadthFirstSearch_invalid_graph", test_BreadthFirstSearch_invalid_graph},
763 : {"BreadthFirstSearch_invalid_src", test_BreadthFirstSearch_invalid_src},
764 : {"BreadthFirstSearch_neither", test_BreadthFirstSearch_neither},
765 : {"BreadthFirstSearch_parent", test_BreadthFirstSearch_parent},
766 : {"BreadthFirstSearch_level", test_BreadthFirstSearch_level},
767 : {"BreadthFirstSearch_both", test_BreadthFirstSearch_both},
768 : {"BreadthFirstSearch_many", test_BreadthFirstSearch_many},
769 : #if LG_BRUTAL_TESTS
770 : {"BreadthFirstSearch_brutal", test_bfs_brutal },
771 : #endif
772 : {"BreadthFirstSearch_Extended", test_BreadthFirstSearch_Extended},
773 : {NULL, NULL}
774 : } ;
|
