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