Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/src/test/LG_check_bfs: stand-alone test for BFS
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 : #define LG_FREE_WORK \
19 : { \
20 : LAGraph_Free ((void **) &queue, NULL) ; \
21 : LAGraph_Free ((void **) &level_check, NULL) ; \
22 : LAGraph_Free ((void **) &level_in, NULL) ; \
23 : LAGraph_Free ((void **) &parent_in, NULL) ; \
24 : LAGraph_Free ((void **) &visited, NULL) ; \
25 : LAGraph_Free ((void **) &neighbors, NULL) ; \
26 : GrB_free (&Row) ; \
27 : }
28 :
29 : #define LG_FREE_ALL \
30 : { \
31 : LG_FREE_WORK ; \
32 : LAGraph_Free ((void **) &Ap, NULL) ; \
33 : LAGraph_Free ((void **) &Aj, NULL) ; \
34 : LAGraph_Free ((void **) &Ax, NULL) ; \
35 : }
36 :
37 : #include "LG_internal.h"
38 : #include "LG_test.h"
39 :
40 : //------------------------------------------------------------------------------
41 : // test the results from a BFS
42 : //------------------------------------------------------------------------------
43 :
44 : // Because this method does on GxB_unpack on G->A, it should not be used in a
45 : // brutal memory test, unless the caller is prepared to reconstruct G->A
46 : // when the brutal test causes this method to return early.
47 :
48 1539 : int LG_check_bfs
49 : (
50 : // input
51 : GrB_Vector Level, // optional; may be NULL
52 : GrB_Vector Parent, // optional; may be NULL
53 : LAGraph_Graph G,
54 : GrB_Index src,
55 : char *msg
56 : )
57 : {
58 :
59 : //--------------------------------------------------------------------------
60 : // check inputs
61 : //--------------------------------------------------------------------------
62 :
63 1539 : double tt = LAGraph_WallClockTime ( ) ;
64 :
65 1539 : GrB_Vector Row = NULL ;
66 1539 : GrB_Index *Ap = NULL, *Aj = NULL, *neighbors = NULL ;
67 1539 : void *Ax = NULL ;
68 : GrB_Index Ap_size, Aj_size, Ax_size, n, ncols ;
69 1539 : int64_t *queue = NULL, *level_in = NULL, *parent_in = NULL,
70 1539 : *level_check = NULL ;
71 1539 : bool *visited = NULL ;
72 1539 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
73 1539 : GRB_TRY (GrB_Matrix_nrows (&n, G->A)) ;
74 1539 : GRB_TRY (GrB_Matrix_ncols (&ncols, G->A)) ;
75 1539 : bool print_timings = (n >= 2000) ;
76 :
77 : //--------------------------------------------------------------------------
78 : // allocate workspace
79 : //--------------------------------------------------------------------------
80 :
81 1539 : LG_TRY (LAGraph_Malloc ((void **) &queue, n, sizeof (int64_t), msg)) ;
82 1539 : LG_TRY (LAGraph_Malloc ((void **) &level_check, n, sizeof (int64_t), msg)) ;
83 :
84 : //--------------------------------------------------------------------------
85 : // get the contents of the Level and Parent vectors
86 : //--------------------------------------------------------------------------
87 :
88 1539 : if (Level != NULL)
89 : {
90 1179 : LG_TRY (LAGraph_Malloc ((void **) &level_in, n, sizeof (int64_t), msg)) ;
91 1179 : LG_TRY (LG_check_vector (level_in, Level, n, -1)) ;
92 : }
93 :
94 1539 : if (Parent != NULL)
95 : {
96 932 : LG_TRY (LAGraph_Malloc ((void **) &parent_in, n, sizeof (int64_t), msg)) ;
97 932 : LG_TRY (LG_check_vector (parent_in, Parent, n, -1)) ;
98 : }
99 :
100 : //--------------------------------------------------------------------------
101 : // unpack the matrix in CSR form for SuiteSparse:GraphBLAS
102 : //--------------------------------------------------------------------------
103 :
104 : #if LAGRAPH_SUITESPARSE
105 : bool iso, jumbled ;
106 1539 : GRB_TRY (GxB_Matrix_unpack_CSR (G->A,
107 : &Ap, &Aj, &Ax, &Ap_size, &Aj_size, &Ax_size, &iso, &jumbled, NULL)) ;
108 : #endif
109 :
110 : //--------------------------------------------------------------------------
111 : // compute the level of each node
112 : //--------------------------------------------------------------------------
113 :
114 1539 : if (print_timings)
115 : {
116 72 : tt = LAGraph_WallClockTime ( ) - tt ;
117 72 : printf ("LG_check_bfs init time: %g sec\n", tt) ;
118 72 : tt = LAGraph_WallClockTime ( ) ;
119 : }
120 :
121 1539 : queue [0] = src ;
122 1539 : int64_t head = 0 ;
123 1539 : int64_t tail = 1 ;
124 1539 : LG_TRY (LAGraph_Calloc ((void **) &visited, n, sizeof (bool), msg)) ;
125 1539 : visited [src] = true ; // src is visited, and is level 0
126 :
127 279809 : for (int64_t i = 0 ; i < n ; i++)
128 : {
129 278270 : level_check [i] = -1 ;
130 : }
131 1539 : level_check [src] = 0 ;
132 :
133 : #if !LAGRAPH_SUITESPARSE
134 : GRB_TRY (GrB_Vector_new (&Row, GrB_BOOL, n)) ;
135 : LG_TRY (LAGraph_Malloc ((void **) &neighbors, n, sizeof (GrB_Index), msg)) ;
136 : #endif
137 :
138 277589 : while (head < tail)
139 : {
140 : // dequeue the node at the head of the queue
141 276050 : int64_t u = queue [head++] ;
142 :
143 : #if LAGRAPH_SUITESPARSE
144 : // directly access the indices of entries in A(u,:)
145 276050 : GrB_Index degree = Ap [u+1] - Ap [u] ;
146 276050 : GrB_Index *node_u_adjacency_list = Aj + Ap [u] ;
147 : #else
148 : // extract the indices of entries in A(u,:)
149 : GrB_Index degree = n ;
150 : GRB_TRY (GrB_Col_extract (Row, NULL, NULL, G->A, GrB_ALL, n, u,
151 : GrB_DESC_T0)) ;
152 : GRB_TRY (GrB_Vector_extractTuples_BOOL (neighbors, NULL, °ree, Row));
153 : GrB_Index *node_u_adjacency_list = neighbors ;
154 : #endif
155 :
156 : // traverse all entries in A(u,:)
157 7652626 : for (int64_t k = 0 ; k < degree ; k++)
158 : {
159 : // consider edge (u,v)
160 7376576 : int64_t v = node_u_adjacency_list [k] ;
161 7376576 : if (!visited [v])
162 : {
163 : // node v is not yet visited; set its level and add to the
164 : // end of the queue
165 274511 : visited [v] = true ;
166 274511 : level_check [v] = level_check [u] + 1 ;
167 274511 : queue [tail++] = v ;
168 : }
169 : }
170 : }
171 :
172 1539 : if (print_timings)
173 : {
174 72 : tt = LAGraph_WallClockTime ( ) - tt ;
175 72 : printf ("LG_check_bfs bfs time: %g sec\n", tt) ;
176 72 : tt = LAGraph_WallClockTime ( ) ;
177 : }
178 :
179 : //--------------------------------------------------------------------------
180 : // repack the matrix in CSR form for SuiteSparse:GraphBLAS
181 : //--------------------------------------------------------------------------
182 :
183 : #if LAGRAPH_SUITESPARSE
184 1539 : GRB_TRY (GxB_Matrix_pack_CSR (G->A,
185 : &Ap, &Aj, &Ax, Ap_size, Aj_size, Ax_size, iso, jumbled, NULL)) ;
186 : #endif
187 :
188 : //--------------------------------------------------------------------------
189 : // check the level of each node
190 : //--------------------------------------------------------------------------
191 :
192 1539 : if (level_in != NULL)
193 : {
194 188513 : for (int64_t i = 0 ; i < n ; i++)
195 : {
196 187334 : bool ok = (level_in [i] == level_check [i]) ;
197 187334 : LG_ASSERT_MSG (ok, -2000, "invalid level") ;
198 : }
199 : }
200 :
201 : //--------------------------------------------------------------------------
202 : // check the parent of each node
203 : //--------------------------------------------------------------------------
204 :
205 1539 : if (parent_in != NULL)
206 : {
207 184940 : for (int64_t i = 0 ; i < n ; i++)
208 : {
209 184008 : if (i == src)
210 : {
211 : // src node is its own parent
212 932 : bool ok = (parent_in [src] == src) && (visited [src]) ;
213 932 : LG_ASSERT_MSG (ok, -2001, "invalid parent") ;
214 : }
215 183076 : else if (visited [i])
216 : {
217 181744 : int64_t pi = parent_in [i] ;
218 : // ensure the parent pi is valid and has been visited
219 181744 : bool ok = (pi >= 0 && pi < n) && visited [pi] ;
220 181744 : LG_ASSERT_MSG (ok, -2001, "invalid parent") ;
221 : // ensure the edge (pi,i) exists
222 : bool x ;
223 181744 : int info = GrB_Matrix_extractElement_BOOL (&x, G->A, pi, i) ;
224 181744 : ok = (info == GrB_SUCCESS) ;
225 181744 : LG_ASSERT_MSG (ok, -2001, "invalid parent") ;
226 : // ensure the parent's level is ok
227 181744 : ok = (level_check [i] == level_check [pi] + 1) ;
228 181744 : LG_ASSERT_MSG (ok, -2001, "invalid parent") ;
229 : }
230 : }
231 : }
232 :
233 : //--------------------------------------------------------------------------
234 : // free workspace and return result
235 : //--------------------------------------------------------------------------
236 :
237 1539 : LG_FREE_WORK ;
238 :
239 1539 : if (print_timings)
240 : {
241 72 : tt = LAGraph_WallClockTime ( ) - tt ;
242 72 : printf ("LG_check_bfs check time: %g sec\n", tt) ;
243 : }
244 1539 : return (GrB_SUCCESS) ;
245 : }
|
