Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_BreadthFirstSearch_SSGrB_template: BFS using Suitesparse extensions
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2025 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 : // This is an Advanced algorithm. G->AT and G->out_degree are required for
19 : // this method to use push-pull optimization. If not provided, this method
20 : // defaults to a push-only algorithm, which can be slower. This is not
21 : // user-callable (see LAGr_BreadthFirstSearch instead). G->AT and
22 : // G->out_degree are not computed if not present.
23 :
24 : // References:
25 : //
26 : // Carl Yang, Aydin Buluc, and John D. Owens. 2018. Implementing Push-Pull
27 : // Efficiently in GraphBLAS. In Proceedings of the 47th International
28 : // Conference on Parallel Processing (ICPP 2018). ACM, New York, NY, USA,
29 : // Article 89, 11 pages. DOI: https://doi.org/10.1145/3225058.3225122
30 : //
31 : // Scott Beamer, Krste Asanovic and David A. Patterson, The GAP Benchmark
32 : // Suite, http://arxiv.org/abs/1508.03619, 2015. http://gap.cs.berkeley.edu/
33 :
34 : // revised by Tim Davis (davis@tamu.edu), Texas A&M University
35 :
36 : #define LG_FREE_WORK \
37 : { \
38 : GrB_free (&w) ; \
39 : GrB_free (&q) ; \
40 : }
41 :
42 : #define LG_FREE_ALL \
43 : { \
44 : LG_FREE_WORK ; \
45 : GrB_free (&pi) ; \
46 : GrB_free (&v) ; \
47 : }
48 :
49 : #include "LG_alg_internal.h"
50 :
51 : #ifdef LG_BFS_EXTENDED
52 40 : int LG_BreadthFirstSearch_SSGrB_Extended
53 : (
54 : GrB_Vector *level,
55 : GrB_Vector *parent,
56 : const LAGraph_Graph G,
57 : GrB_Index src,
58 : int64_t max_level, // < 0: no limit; otherwise, stop at this level
59 : int64_t dest, // < 0: no destination; otherwise, stop if dest
60 : // node is reached
61 : bool many_expected, // if true, the result is expected to include a fair
62 : // portion of the graph. If false, the result (parent
63 : // and level) is expected to be very sparse.
64 : char *msg
65 : )
66 : #else
67 9864 : int LG_BreadthFirstSearch_SSGrB
68 : (
69 : GrB_Vector *level,
70 : GrB_Vector *parent,
71 : const LAGraph_Graph G,
72 : GrB_Index src,
73 : char *msg
74 : )
75 : #endif
76 : {
77 : #if LAGRAPH_SUITESPARSE
78 :
79 : //--------------------------------------------------------------------------
80 : // check inputs
81 : //--------------------------------------------------------------------------
82 :
83 9904 : LG_CLEAR_MSG ;
84 9904 : GrB_Vector q = NULL ; // the current frontier
85 9904 : GrB_Vector w = NULL ; // to compute work remaining
86 9904 : GrB_Vector pi = NULL ; // parent vector
87 9904 : GrB_Vector v = NULL ; // level vector
88 :
89 9904 : bool compute_level = (level != NULL) ;
90 9904 : bool compute_parent = (parent != NULL) ;
91 9904 : if (compute_level ) (*level ) = NULL ;
92 9904 : if (compute_parent) (*parent) = NULL ;
93 9904 : LG_ASSERT_MSG (compute_level || compute_parent, GrB_NULL_POINTER,
94 : "either level or parent must be non-NULL") ;
95 :
96 9901 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
97 :
98 : //--------------------------------------------------------------------------
99 : // get the problem size and cached properties
100 : //--------------------------------------------------------------------------
101 :
102 9901 : GrB_Matrix A = G->A ;
103 :
104 : GrB_Index n, nvals ;
105 9901 : GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
106 9901 : LG_ASSERT_MSG (src < n, GrB_INVALID_INDEX, "invalid source node") ;
107 :
108 9899 : GRB_TRY (GrB_Matrix_nvals (&nvals, A)) ;
109 :
110 9899 : GrB_Matrix AT = NULL ;
111 9899 : GrB_Vector Degree = G->out_degree ;
112 9899 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
113 5709 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
114 5709 : G->is_symmetric_structure == LAGraph_TRUE))
115 : {
116 : // AT and A have the same structure and can be used in both directions
117 4190 : AT = G->A ;
118 : }
119 : else
120 : {
121 : // AT = A' is different from A. If G->AT is NULL, then a push-only
122 : // method is used.
123 5709 : AT = G->AT ;
124 : }
125 :
126 : // direction-optimization requires G->AT (if G is directed) and
127 : // G->out_degree (for both undirected and directed cases)
128 9899 : bool push_pull = (Degree != NULL && AT != NULL) ;
129 :
130 : // determine the semiring type
131 9899 : GrB_Type int_type = (n > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
132 : GrB_Semiring semiring ;
133 :
134 : #ifndef LG_BFS_EXTENDED
135 9859 : bool many_expected = (nvals >= n) ;
136 : #endif
137 :
138 9899 : if (compute_parent)
139 : {
140 : // use the ANY_SECONDI_INT* semiring: either 32 or 64-bit depending on
141 : // the # of nodes in the graph.
142 10914 : semiring = (n > INT32_MAX) ?
143 5457 : GxB_ANY_SECONDI_INT64 : GxB_ANY_SECONDI_INT32 ;
144 :
145 : // create the parent vector. pi(i) is the parent id of node i
146 5457 : GRB_TRY (GrB_Vector_new (&pi, int_type, n)) ;
147 5209 : if (many_expected)
148 : {
149 5209 : GRB_TRY (LG_SET_FORMAT_HINT (pi, LG_BITMAP + LG_FULL)) ;
150 : }
151 : // pi (src) = src denotes the root of the BFS tree
152 4961 : GRB_TRY (GrB_Vector_setElement (pi, src, src)) ;
153 :
154 : // create a sparse integer vector q, and set q(src) = src
155 4837 : GRB_TRY (GrB_Vector_new (&q, int_type, n)) ;
156 4589 : GRB_TRY (GrB_Vector_setElement (q, src, src)) ;
157 : }
158 : else
159 : {
160 : // only the level is needed, use the LAGraph_any_one_bool semiring
161 4442 : semiring = LAGraph_any_one_bool ;
162 :
163 : // create a sparse boolean vector q, and set q(src) = true
164 4442 : GRB_TRY (GrB_Vector_new (&q, GrB_BOOL, n)) ;
165 4194 : GRB_TRY (GrB_Vector_setElement (q, true, src)) ;
166 : }
167 :
168 8039 : if (compute_level)
169 : {
170 : // create the level vector. v(i) is the level of node i
171 : // v (src) = 0 denotes the source node
172 7859 : GRB_TRY (GrB_Vector_new (&v, int_type, n)) ;
173 7363 : if (many_expected)
174 : {
175 7326 : GRB_TRY (LG_SET_FORMAT_HINT (v, LG_BITMAP + LG_FULL)) ;
176 : }
177 6867 : GRB_TRY (GrB_Vector_setElement (v, 0, src)) ;
178 : }
179 :
180 : // workspace for computing work remaining
181 6799 : GRB_TRY (GrB_Vector_new (&w, GrB_INT64, n)) ;
182 :
183 6303 : GrB_Index nq = 1 ; // number of nodes in the current level
184 6303 : double alpha = 8.0 ;
185 6303 : double beta1 = 8.0 ;
186 6303 : double beta2 = 512.0 ;
187 6303 : int64_t n_over_beta1 = (int64_t) (((double) n) / beta1) ;
188 6303 : int64_t n_over_beta2 = (int64_t) (((double) n) / beta2) ;
189 :
190 : //--------------------------------------------------------------------------
191 : // BFS traversal and label the nodes
192 : //--------------------------------------------------------------------------
193 :
194 6303 : bool do_push = true ; // start with push
195 6303 : GrB_Index last_nq = 0 ;
196 6303 : int64_t edges_unexplored = nvals ;
197 6303 : bool any_pull = false ; // true if any pull phase has been done
198 :
199 : // {!mask} is the set of unvisited nodes
200 6303 : GrB_Vector mask = (compute_parent) ? pi : v ;
201 :
202 36984 : for (int64_t nvisited = 1, k = 1 ; nvisited < n ; nvisited += nq, k++)
203 : {
204 :
205 : //----------------------------------------------------------------------
206 : // check for early termination (extended version of the algorithm)
207 : //----------------------------------------------------------------------
208 :
209 : #ifdef LG_BFS_EXTENDED
210 : {
211 123 : if (max_level >= 0 && k > max_level)
212 : {
213 : // halt if max_level has been reached; if max_level is zero,
214 : // this will halt with just the src node. Note that k starts
215 : // at 1, and has just been advanced for subsequent iterations,
216 : // so k-1 is the last level added to pi and/or v. So the test
217 : // for the max level is "k > max_level". This differs from
218 : // the vanilla version (in that version current_level has not
219 : // been advanced yet, when the test is made).
220 4 : break ;
221 : }
222 119 : if (dest >= 0)
223 : {
224 : // halt if dest node has been found; this will stop at level 0
225 : // if src == dest. The mask is either pi or v, and is always
226 : // held in bitmap/full format, so this takes O(1) time.
227 105 : GrB_Info info = GxB_Vector_isStoredElement (mask, dest) ;
228 105 : if (info == GrB_SUCCESS)
229 : {
230 33 : break ;
231 : }
232 72 : GRB_TRY (info) ;
233 : }
234 : }
235 : #endif
236 :
237 : //----------------------------------------------------------------------
238 : // select push vs pull
239 : //----------------------------------------------------------------------
240 :
241 36386 : if (push_pull)
242 : {
243 16739 : if (do_push)
244 : {
245 : // check for switch from push to pull
246 15581 : bool growing = nq > last_nq ;
247 15581 : bool switch_to_pull = false ;
248 15581 : if (edges_unexplored < n)
249 : {
250 : // very little of the graph is left; disable the pull
251 30 : push_pull = false ;
252 : }
253 15551 : else if (any_pull)
254 : {
255 : // once any pull phase has been done, the # of edges in the
256 : // frontier has no longer been tracked. But now the BFS
257 : // has switched back to push, and we're checking for yet
258 : // another switch to pull. This switch is unlikely, so
259 : // just keep track of the size of the frontier, and switch
260 : // if it starts growing again and is getting big.
261 9003 : switch_to_pull = (growing && nq > n_over_beta1) ;
262 : }
263 : else
264 : {
265 : // update the # of unexplored edges
266 : // w<q>=Degree
267 : // w(i) = outdegree of node i if node i is in the queue
268 6548 : GRB_TRY (GrB_assign (w, q, NULL, Degree, GrB_ALL, n,
269 : GrB_DESC_RS)) ;
270 : // edges_in_frontier = sum (w) = # of edges incident on all
271 : // nodes in the current frontier
272 5424 : int64_t edges_in_frontier = 0 ;
273 5424 : GRB_TRY (GrB_reduce (&edges_in_frontier, NULL,
274 : GrB_PLUS_MONOID_INT64, w, NULL)) ;
275 5424 : edges_unexplored -= edges_in_frontier ;
276 8540 : switch_to_pull = growing &&
277 3116 : (edges_in_frontier > (edges_unexplored / alpha)) ;
278 : }
279 14457 : if (switch_to_pull)
280 : {
281 : // switch from push to pull
282 1049 : do_push = false ;
283 : }
284 : }
285 : else
286 : {
287 : // check for switch from pull to push
288 1158 : bool shrinking = nq < last_nq ;
289 1158 : if (shrinking && (nq <= n_over_beta2))
290 : {
291 : // switch from pull to push
292 9 : do_push = true ;
293 : }
294 : }
295 15615 : any_pull = any_pull || (!do_push) ;
296 : }
297 :
298 : //----------------------------------------------------------------------
299 : // q = kth level of the BFS
300 : //----------------------------------------------------------------------
301 :
302 : // mask is pi if computing parent, v if computing just level
303 35262 : if (do_push)
304 : {
305 : // push (saxpy-based vxm): q'{!mask} = q'*A
306 33064 : GRB_TRY (LG_SET_FORMAT_HINT (q, LG_SPARSE)) ;
307 32964 : GRB_TRY (GrB_vxm (q, mask, NULL, semiring, q, A, GrB_DESC_RSC)) ;
308 : }
309 : else
310 : {
311 : // pull (dot-product-based mxv): q{!mask} = AT*q
312 2198 : GRB_TRY (LG_SET_FORMAT_HINT (q, LG_BITMAP)) ;
313 2132 : GRB_TRY (GrB_mxv (q, mask, NULL, semiring, AT, q, GrB_DESC_RSC)) ;
314 : }
315 :
316 : //----------------------------------------------------------------------
317 : // done if q is empty
318 : //----------------------------------------------------------------------
319 :
320 31250 : last_nq = nq ;
321 31250 : GRB_TRY (GrB_Vector_nvals (&nq, q)) ;
322 31250 : if (nq == 0)
323 : {
324 230 : break ;
325 : }
326 :
327 : //----------------------------------------------------------------------
328 : // assign parents/levels
329 : //----------------------------------------------------------------------
330 :
331 31020 : if (compute_parent)
332 : {
333 : // q(i) currently contains the parent id of node i in tree.
334 : // pi{q} = q
335 19982 : GRB_TRY (GrB_assign (pi, q, NULL, q, GrB_ALL, n, GrB_DESC_S)) ;
336 : }
337 30913 : if (compute_level)
338 : {
339 : // v{q} = k, the kth level of the BFS
340 22126 : GRB_TRY (GrB_assign (v, q, NULL, k, GrB_ALL, n, GrB_DESC_S)) ;
341 : }
342 : }
343 :
344 : //--------------------------------------------------------------------------
345 : // free workspace and return result
346 : //--------------------------------------------------------------------------
347 :
348 828 : if (compute_parent) (*parent) = pi ;
349 828 : if (compute_level ) (*level ) = v ;
350 828 : LG_FREE_WORK ;
351 828 : return (GrB_SUCCESS) ;
352 : #else
353 : return (GrB_NOT_IMPLEMENTED) ;
354 : #endif
355 : }
|
