Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_BreadthFirstSearch_SSGrB: BFS using Suitesparse extensions
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 : // 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_internal.h"
50 :
51 9462 : int LG_BreadthFirstSearch_SSGrB
52 : (
53 : GrB_Vector *level,
54 : GrB_Vector *parent,
55 : const LAGraph_Graph G,
56 : GrB_Index src,
57 : char *msg
58 : )
59 : {
60 :
61 : //--------------------------------------------------------------------------
62 : // check inputs
63 : //--------------------------------------------------------------------------
64 :
65 9462 : LG_CLEAR_MSG ;
66 9462 : GrB_Vector q = NULL ; // the current frontier
67 9462 : GrB_Vector w = NULL ; // to compute work remaining
68 9462 : GrB_Vector pi = NULL ; // parent vector
69 9462 : GrB_Vector v = NULL ; // level vector
70 :
71 : #if !LAGRAPH_SUITESPARSE
72 : LG_ASSERT (false, GrB_NOT_IMPLEMENTED) ;
73 : #else
74 :
75 9462 : bool compute_level = (level != NULL) ;
76 9462 : bool compute_parent = (parent != NULL) ;
77 9462 : if (compute_level ) (*level ) = NULL ;
78 9462 : if (compute_parent) (*parent) = NULL ;
79 9462 : LG_ASSERT_MSG (compute_level || compute_parent, GrB_NULL_POINTER,
80 : "either level or parent must be non-NULL") ;
81 :
82 9459 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
83 :
84 : //--------------------------------------------------------------------------
85 : // get the problem size and cached properties
86 : //--------------------------------------------------------------------------
87 :
88 9459 : GrB_Matrix A = G->A ;
89 :
90 : GrB_Index n, nvals ;
91 9459 : GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
92 9459 : LG_ASSERT_MSG (src < n, GrB_INVALID_INDEX, "invalid source node") ;
93 :
94 9457 : GRB_TRY (GrB_Matrix_nvals (&nvals, A)) ;
95 :
96 9457 : GrB_Matrix AT = NULL ;
97 9457 : GrB_Vector Degree = G->out_degree ;
98 9457 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
99 5478 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
100 5478 : G->is_symmetric_structure == LAGraph_TRUE))
101 : {
102 : // AT and A have the same structure and can be used in both directions
103 3979 : AT = G->A ;
104 : }
105 : else
106 : {
107 : // AT = A' is different from A. If G->AT is NULL, then a push-only
108 : // method is used.
109 5478 : AT = G->AT ;
110 : }
111 :
112 : // direction-optimization requires G->AT (if G is directed) and
113 : // G->out_degree (for both undirected and directed cases)
114 9457 : bool push_pull = (Degree != NULL && AT != NULL) ;
115 :
116 : // determine the semiring type
117 9457 : GrB_Type int_type = (n > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
118 : GrB_Semiring semiring ;
119 :
120 9457 : if (compute_parent)
121 : {
122 : // use the ANY_SECONDI_INT* semiring: either 32 or 64-bit depending on
123 : // the # of nodes in the graph.
124 10562 : semiring = (n > INT32_MAX) ?
125 5281 : GxB_ANY_SECONDI_INT64 : GxB_ANY_SECONDI_INT32 ;
126 :
127 : // create the parent vector. pi(i) is the parent id of node i
128 5281 : GRB_TRY (GrB_Vector_new (&pi, int_type, n)) ;
129 5033 : GRB_TRY (GxB_set (pi, GxB_SPARSITY_CONTROL, GxB_BITMAP + GxB_FULL)) ;
130 : // pi (src) = src denotes the root of the BFS tree
131 4785 : GRB_TRY (GrB_Vector_setElement (pi, src, src)) ;
132 :
133 : // create a sparse integer vector q, and set q(src) = src
134 4661 : GRB_TRY (GrB_Vector_new (&q, int_type, n)) ;
135 4413 : GRB_TRY (GrB_Vector_setElement (q, src, src)) ;
136 : }
137 : else
138 : {
139 : // only the level is needed, use the LAGraph_any_one_bool semiring
140 4176 : semiring = LAGraph_any_one_bool ;
141 :
142 : // create a sparse boolean vector q, and set q(src) = true
143 4176 : GRB_TRY (GrB_Vector_new (&q, GrB_BOOL, n)) ;
144 3928 : GRB_TRY (GrB_Vector_setElement (q, true, src)) ;
145 : }
146 :
147 7597 : if (compute_level)
148 : {
149 : // create the level vector. v(i) is the level of node i
150 : // v (src) = 0 denotes the source node
151 7417 : GRB_TRY (GrB_Vector_new (&v, int_type, n)) ;
152 6921 : GRB_TRY (GxB_set (v, GxB_SPARSITY_CONTROL, GxB_BITMAP + GxB_FULL)) ;
153 6425 : GRB_TRY (GrB_Vector_setElement (v, 0, src)) ;
154 : }
155 :
156 : // workspace for computing work remaining
157 6357 : GRB_TRY (GrB_Vector_new (&w, GrB_INT64, n)) ;
158 :
159 5861 : GrB_Index nq = 1 ; // number of nodes in the current level
160 5861 : double alpha = 8.0 ;
161 5861 : double beta1 = 8.0 ;
162 5861 : double beta2 = 512.0 ;
163 5861 : int64_t n_over_beta1 = (int64_t) (((double) n) / beta1) ;
164 5861 : int64_t n_over_beta2 = (int64_t) (((double) n) / beta2) ;
165 :
166 : //--------------------------------------------------------------------------
167 : // BFS traversal and label the nodes
168 : //--------------------------------------------------------------------------
169 :
170 5861 : bool do_push = true ; // start with push
171 5861 : GrB_Index last_nq = 0 ;
172 5861 : int64_t edges_unexplored = nvals ;
173 5861 : bool any_pull = false ; // true if any pull phase has been done
174 :
175 : // {!mask} is the set of unvisited nodes
176 5861 : GrB_Vector mask = (compute_parent) ? pi : v ;
177 :
178 36082 : for (int64_t nvisited = 1, k = 1 ; nvisited < n ; nvisited += nq, k++)
179 : {
180 :
181 : //----------------------------------------------------------------------
182 : // select push vs pull
183 : //----------------------------------------------------------------------
184 :
185 35524 : if (push_pull)
186 : {
187 16599 : if (do_push)
188 : {
189 : // check for switch from push to pull
190 15441 : bool growing = nq > last_nq ;
191 15441 : bool switch_to_pull = false ;
192 15441 : if (edges_unexplored < n)
193 : {
194 : // very little of the graph is left; disable the pull
195 28 : push_pull = false ;
196 : }
197 15413 : else if (any_pull)
198 : {
199 : // once any pull phase has been done, the # of edges in the
200 : // frontier has no longer been tracked. But now the BFS
201 : // has switched back to push, and we're checking for yet
202 : // another switch to pull. This switch is unlikely, so
203 : // just keep track of the size of the frontier, and switch
204 : // if it starts growing again and is getting big.
205 9003 : switch_to_pull = (growing && nq > n_over_beta1) ;
206 : }
207 : else
208 : {
209 : // update the # of unexplored edges
210 : // w<q>=Degree
211 : // w(i) = outdegree of node i if node i is in the queue
212 6410 : GRB_TRY (GrB_assign (w, q, NULL, Degree, GrB_ALL, n,
213 : GrB_DESC_RS)) ;
214 : // edges_in_frontier = sum (w) = # of edges incident on all
215 : // nodes in the current frontier
216 5286 : int64_t edges_in_frontier = 0 ;
217 5286 : GRB_TRY (GrB_reduce (&edges_in_frontier, NULL,
218 : GrB_PLUS_MONOID_INT64, w, NULL)) ;
219 5286 : edges_unexplored -= edges_in_frontier ;
220 8296 : switch_to_pull = growing &&
221 3010 : (edges_in_frontier > (edges_unexplored / alpha)) ;
222 : }
223 14317 : if (switch_to_pull)
224 : {
225 : // switch from push to pull
226 1049 : do_push = false ;
227 : }
228 : }
229 : else
230 : {
231 : // check for switch from pull to push
232 1158 : bool shrinking = nq < last_nq ;
233 1158 : if (shrinking && (nq <= n_over_beta2))
234 : {
235 : // switch from pull to push
236 9 : do_push = true ;
237 : }
238 : }
239 15475 : any_pull = any_pull || (!do_push) ;
240 : }
241 :
242 : //----------------------------------------------------------------------
243 : // q = kth level of the BFS
244 : //----------------------------------------------------------------------
245 :
246 34400 : int sparsity = do_push ? GxB_SPARSE : GxB_BITMAP ;
247 34400 : GRB_TRY (GxB_set (q, GxB_SPARSITY_CONTROL, sparsity)) ;
248 :
249 : // mask is pi if computing parent, v if computing just level
250 34234 : if (do_push)
251 : {
252 : // push (saxpy-based vxm): q'{!mask} = q'*A
253 32102 : GRB_TRY (GrB_vxm (q, mask, NULL, semiring, q, A, GrB_DESC_RSC)) ;
254 : }
255 : else
256 : {
257 : // pull (dot-product-based mxv): q{!mask} = AT*q
258 2132 : GRB_TRY (GrB_mxv (q, mask, NULL, semiring, AT, q, GrB_DESC_RSC)) ;
259 : }
260 :
261 : //----------------------------------------------------------------------
262 : // done if q is empty
263 : //----------------------------------------------------------------------
264 :
265 30790 : last_nq = nq ;
266 30790 : GRB_TRY (GrB_Vector_nvals (&nq, q)) ;
267 30790 : if (nq == 0)
268 : {
269 230 : break ;
270 : }
271 :
272 : //----------------------------------------------------------------------
273 : // assign parents/levels
274 : //----------------------------------------------------------------------
275 :
276 30560 : if (compute_parent)
277 : {
278 : // q(i) currently contains the parent id of node i in tree.
279 : // pi{q} = q
280 19824 : GRB_TRY (GrB_assign (pi, q, NULL, q, GrB_ALL, n, GrB_DESC_S)) ;
281 : }
282 30453 : if (compute_level)
283 : {
284 : // v{q} = k, the kth level of the BFS
285 21666 : GRB_TRY (GrB_assign (v, q, NULL, k, GrB_ALL, n, GrB_DESC_S)) ;
286 : }
287 : }
288 :
289 : //--------------------------------------------------------------------------
290 : // free workspace and return result
291 : //--------------------------------------------------------------------------
292 :
293 788 : if (compute_parent) (*parent) = pi ;
294 788 : if (compute_level ) (*level ) = v ;
295 788 : LG_FREE_WORK ;
296 788 : return (GrB_SUCCESS) ;
297 : #endif
298 : }
|
