Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph_MultiSourceBFS: BFS from several source nodes in parallel
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2021 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : // See additional acknowledgments in the LICENSE file,
8 : // or contact permission@sei.cmu.edu for the full terms.
9 :
10 : // Contributed by Alexandra Goff
11 :
12 : //------------------------------------------------------------------------------
13 :
14 : // TODO: almost ready for src; need a vanilla method
15 :
16 : // Takes in a vector of source nodes and finds level and/or parent vectors for each,
17 : // stored together in a matrix
18 :
19 : #define LG_FREE_WORK \
20 : { \
21 : GrB_free (&q) ; \
22 : }
23 :
24 : #define LG_FREE_ALL \
25 : { \
26 : LG_FREE_WORK ; \
27 : GrB_free (&pi) ; \
28 : GrB_free (&v) ; \
29 : }
30 :
31 : #include "LG_internal.h"
32 : #include "LAGraphX.h"
33 :
34 474 : int LAGraph_MultiSourceBFS
35 : (
36 : // outputs:
37 : GrB_Matrix *level,
38 : GrB_Matrix *parent,
39 : // inputs:
40 : const LAGraph_Graph G,
41 : GrB_Vector src,
42 : char *msg
43 : )
44 : {
45 : #if LAGRAPH_SUITESPARSE
46 :
47 : //--------------------------------------------------------------------------
48 : // check inputs
49 : //--------------------------------------------------------------------------
50 :
51 474 : LG_CLEAR_MSG ;
52 474 : GrB_Matrix q = NULL ; // the current frontier
53 : // GrB_Vector w = NULL ; to compute work remaining, removed since not doing push-pull
54 474 : GrB_Matrix pi = NULL ; // parent matrix
55 474 : GrB_Matrix v = NULL ; // level matrix
56 :
57 474 : bool compute_level = (level != NULL) ;
58 474 : bool compute_parent = (parent != NULL) ;
59 474 : if (compute_level ) (*level ) = NULL ;
60 474 : if (compute_parent) (*parent) = NULL ;
61 474 : LG_ASSERT_MSG (compute_level || compute_parent, GrB_NULL_POINTER,
62 : "either level or parent must be non-NULL") ;
63 :
64 474 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
65 :
66 : //--------------------------------------------------------------------------
67 : // get the problem size and cached properties
68 : //--------------------------------------------------------------------------
69 :
70 474 : GrB_Matrix A = G->A ;
71 :
72 : GrB_Index nsrc; // holds the number of source nodes
73 : GrB_Index n, nvals ;
74 474 : GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
75 474 : GRB_TRY (GrB_Matrix_nvals (&nvals, A)) ;
76 474 : GRB_TRY (GrB_Vector_size (&nsrc, src)) ;
77 4080 : for (int64_t s = 0; s < nsrc; s++)
78 : {
79 : GrB_Index currsrc;
80 3606 : GRB_TRY (GrB_Vector_extractElement (&currsrc, src, s)) ;
81 3606 : LG_ASSERT_MSG (currsrc < n, GrB_INVALID_INDEX, "invalid source node") ;
82 : }
83 474 : bool very_sparse = (nvals <= n/16) ;
84 :
85 : // determine the semiring type
86 474 : GrB_Type int_type = (n > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
87 : GrB_Semiring semiring ;
88 :
89 474 : if (compute_parent)
90 : {
91 : // use the ANY_SECONDI_INT* semiring: either 32 or 64-bit depending on
92 : // the # of nodes in the graph.
93 22 : semiring = (n > INT32_MAX) ?
94 11 : GxB_ANY_SECONDI_INT64 : GxB_ANY_SECONDI_INT32 ;
95 :
96 : // create the parent matrix. pi(i, j) is the parent id of node j in source i's BFS
97 11 : GRB_TRY (GrB_Matrix_new (&pi, int_type, nsrc, n)) ;
98 11 : if (!very_sparse)
99 : {
100 10 : GRB_TRY (LG_SET_FORMAT_HINT (pi, LG_BITMAP + LG_FULL)) ;
101 : }
102 :
103 : // pi (i, src) = src denotes the root of that row's BFS tree
104 55 : for (int64_t s = 0; s < nsrc; s++)
105 : {
106 : GrB_Index currsrc;
107 44 : GRB_TRY (GrB_Vector_extractElement (&currsrc, src, s)) ;
108 : // now s contains the row associated with the current source node
109 : // and currsrc contains the column that should index itself
110 44 : GRB_TRY (GrB_Matrix_setElement (pi, currsrc, s, currsrc)) ;
111 : }
112 :
113 : // create a sparse integer matrix q, and set q(s, src) = src for each row's source
114 11 : GRB_TRY (GrB_Matrix_new (&q, int_type, nsrc, n)) ;
115 55 : for (int64_t s = 0; s < nsrc; s++)
116 : {
117 : GrB_Index currsrc;
118 44 : GRB_TRY (GrB_Vector_extractElement (&currsrc, src, s)) ;
119 : // now s contains the row associated with the current source node
120 : // and currsrc contains the column that should index itself
121 44 : GRB_TRY (GrB_Matrix_setElement (q, currsrc, s, currsrc)) ;
122 : }
123 : }
124 : else
125 : {
126 : // only the level is needed, use the LAGraph_any_one_bool semiring
127 463 : semiring = LAGraph_any_one_bool ;
128 :
129 : // create a sparse boolean matrix q, and set q(s, src) = true for the source in each row
130 463 : GRB_TRY (GrB_Matrix_new (&q, GrB_BOOL, nsrc, n)) ;
131 4025 : for (int64_t s = 0; s < nsrc; s++)
132 : {
133 : GrB_Index currsrc;
134 3562 : GRB_TRY (GrB_Vector_extractElement (&currsrc, src, s)) ;
135 : // now s contains the row associated with the current source node
136 : // and currsrc contains the column that should be true
137 3562 : GRB_TRY (GrB_Matrix_setElement (q, true, s, currsrc)) ;
138 : }
139 : }
140 :
141 474 : if (compute_level)
142 : {
143 : // create the level matrix. v(i,j) is the level of node j in source i's BFS
144 : // v (s, src) = 0 denotes the source node of that row
145 474 : GRB_TRY (GrB_Matrix_new (&v, int_type, nsrc, n)) ;
146 474 : if (!very_sparse)
147 : {
148 472 : GRB_TRY (LG_SET_FORMAT_HINT (v, LG_BITMAP + LG_FULL)) ;
149 : }
150 4080 : for (int64_t s = 0; s < nsrc; s++)
151 : {
152 : GrB_Index currsrc;
153 3606 : GRB_TRY (GrB_Vector_extractElement (&currsrc, src, s)) ;
154 : // now s contains the row associated with the current source node
155 : // and currsrc contains the column that should be 0
156 3606 : GRB_TRY (GrB_Matrix_setElement (v, 0, s, currsrc)) ;
157 : }
158 : }
159 :
160 474 : GrB_Index nq = nsrc ; // number of nodes in the current level
161 : // skipping work remaining computation set-up since we're not doing push-pull
162 :
163 : //--------------------------------------------------------------------------
164 : // BFS traversal and label the nodes
165 : //--------------------------------------------------------------------------
166 :
167 : // {!mask} is the set of unvisited nodes
168 474 : GrB_Matrix mask = (compute_parent) ? pi : v ;
169 :
170 10805 : for (int64_t nvisited = nsrc, k = 1 ; nvisited < n*nsrc ; nvisited += nq, k++)
171 : {
172 :
173 : //----------------------------------------------------------------------
174 : // q = frontier at the kth level of the BFS
175 : //----------------------------------------------------------------------
176 :
177 : // mask is pi if computing parent, v if computing just level
178 :
179 : // push (saxpy-based mxm): q'{!mask} = q'*A
180 10333 : GRB_TRY (GrB_mxm (q, mask, NULL, semiring, q, A, GrB_DESC_RSC)) ;
181 :
182 : //----------------------------------------------------------------------
183 : // done if q is empty
184 : //----------------------------------------------------------------------
185 :
186 10333 : GRB_TRY (GrB_Matrix_nvals (&nq, q)) ;
187 10333 : if (nq == 0)
188 : {
189 2 : break ;
190 : }
191 :
192 : //----------------------------------------------------------------------
193 : // assign parents/levels
194 : //----------------------------------------------------------------------
195 :
196 10331 : if (compute_parent)
197 : {
198 : // q(s, i) currently contains the parent id of node i in tree s.
199 : // pi{q} = q
200 100 : GRB_TRY (GrB_assign (pi, q, NULL, q, GrB_ALL, nsrc, GrB_ALL, n, GrB_DESC_S)) ;
201 : }
202 10331 : if (compute_level)
203 : {
204 : // v{q} = k, the kth level of the BFS
205 10331 : GRB_TRY (GrB_assign (v, q, NULL, k, GrB_ALL, nsrc, GrB_ALL, n, GrB_DESC_S)) ;
206 : }
207 : }
208 :
209 : //--------------------------------------------------------------------------
210 : // free workspace and return result
211 : //--------------------------------------------------------------------------
212 :
213 474 : if (compute_parent) (*parent) = pi ;
214 474 : if (compute_level ) (*level ) = v ;
215 474 : LG_FREE_WORK ;
216 474 : return (GrB_SUCCESS) ;
217 : #else
218 : return (GrB_NOT_IMPLEMENTED) ;
219 : #endif
220 : }
|
