Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_BreadthFirstSearch_vanilla_template: BFS using only GraphBLAS API
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 Scott McMillan, derived from examples in the appendix of
15 : // The GraphBLAS C API Specification, v1.3.0
16 :
17 : //------------------------------------------------------------------------------
18 :
19 : // This is a Basic algorithm (no extra cached properties are required),
20 : // but it is not user-callable (see LAGr_BreadthFirstSearch instead).
21 :
22 : #define LG_FREE_WORK \
23 : { \
24 : GrB_free (&frontier); \
25 : }
26 :
27 : #define LG_FREE_ALL \
28 : { \
29 : LG_FREE_WORK ; \
30 : GrB_free (&l_parent); \
31 : GrB_free (&l_level); \
32 : }
33 :
34 : #include "LG_internal.h"
35 :
36 : #ifdef LG_BFS_EXTENDED
37 40 : int LG_BreadthFirstSearch_vanilla_Extended
38 : (
39 : GrB_Vector *level,
40 : GrB_Vector *parent,
41 : const LAGraph_Graph G,
42 : GrB_Index src,
43 : int64_t max_level, // < 0: no limit; otherwise, stop at this level
44 : int64_t dest, // < 0: no destination; otherwise, stop if dest
45 : // node is reached
46 : char *msg
47 : )
48 : #else
49 9496 : int LG_BreadthFirstSearch_vanilla
50 : (
51 : GrB_Vector *level,
52 : GrB_Vector *parent,
53 : const LAGraph_Graph G,
54 : GrB_Index src,
55 : char *msg
56 : )
57 : #endif
58 : {
59 :
60 : //--------------------------------------------------------------------------
61 : // check inputs
62 : //--------------------------------------------------------------------------
63 :
64 9536 : LG_CLEAR_MSG ;
65 9536 : GrB_Vector frontier = NULL; // the current frontier
66 9536 : GrB_Vector l_parent = NULL; // parent vector
67 9536 : GrB_Vector l_level = NULL; // level vector
68 :
69 9536 : bool compute_level = (level != NULL);
70 9536 : bool compute_parent = (parent != NULL);
71 9536 : if (compute_level ) (*level ) = NULL;
72 9536 : if (compute_parent) (*parent) = NULL;
73 9536 : LG_ASSERT_MSG (compute_level || compute_parent, GrB_NULL_POINTER,
74 : "either level or parent must be non-NULL") ;
75 :
76 9533 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
77 :
78 : //--------------------------------------------------------------------------
79 : // get the problem size
80 : //--------------------------------------------------------------------------
81 :
82 9533 : GrB_Matrix A = G->A ;
83 :
84 : GrB_Index n;
85 9533 : GRB_TRY( GrB_Matrix_nrows (&n, A) );
86 9533 : LG_ASSERT_MSG (src < n, GrB_INVALID_INDEX, "invalid source node") ;
87 :
88 : // determine the semiring type
89 9531 : GrB_Type int_type = (n > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
90 : GrB_BinaryOp
91 9531 : second_op = (n > INT32_MAX) ? GrB_SECOND_INT64 : GrB_SECOND_INT32 ;
92 9531 : GrB_Semiring semiring = NULL;
93 9531 : GrB_IndexUnaryOp ramp = NULL ;
94 :
95 9531 : if (compute_parent)
96 : {
97 : // create the parent vector. l_parent(i) is the parent id of node i
98 5354 : GRB_TRY (GrB_Vector_new(&l_parent, int_type, n)) ;
99 :
100 10212 : semiring = (n > INT32_MAX) ?
101 5106 : GrB_MIN_FIRST_SEMIRING_INT64 : GrB_MIN_FIRST_SEMIRING_INT32;
102 :
103 : // create a sparse integer vector frontier, and set frontier(src) = src
104 5106 : GRB_TRY (GrB_Vector_new(&frontier, int_type, n)) ;
105 4858 : GRB_TRY (GrB_Vector_setElement(frontier, src, src)) ;
106 :
107 : // pick the ramp operator
108 4486 : ramp = (n > INT32_MAX) ? GrB_ROWINDEX_INT64 : GrB_ROWINDEX_INT32 ;
109 : }
110 : else
111 : {
112 : // only the level is needed
113 4177 : semiring = LAGraph_any_one_bool ;
114 :
115 : // create a sparse boolean vector frontier, and set frontier(src) = true
116 4177 : GRB_TRY (GrB_Vector_new(&frontier, GrB_BOOL, n)) ;
117 3929 : GRB_TRY (GrB_Vector_setElement(frontier, true, src)) ;
118 : }
119 :
120 8043 : if (compute_level)
121 : {
122 : // create the level vector. v(i) is the level of node i
123 : // v (src) = 0 denotes the source node
124 7863 : GRB_TRY (GrB_Vector_new(&l_level, int_type, n)) ;
125 : }
126 :
127 : //--------------------------------------------------------------------------
128 : // BFS traversal and label the nodes
129 : //--------------------------------------------------------------------------
130 :
131 7547 : GrB_Index nq = 1 ; // number of nodes in the current level
132 7547 : GrB_Index last_nq = 0 ;
133 7547 : GrB_Index current_level = 0;
134 7547 : GrB_Index nvals = 1;
135 :
136 : // {!mask} is the set of unvisited nodes
137 7547 : GrB_Vector mask = (compute_parent) ? l_parent : l_level ;
138 :
139 : // parent BFS
140 : do
141 : {
142 39553 : if (compute_level)
143 : {
144 : // assign levels: l_level<s(frontier)> = current_level
145 30586 : GRB_TRY( GrB_assign(l_level, frontier, GrB_NULL,
146 : current_level, GrB_ALL, n, GrB_DESC_S) );
147 : }
148 :
149 37191 : if (compute_parent)
150 : {
151 : // frontier(i) currently contains the parent id of node i in tree.
152 : // l_parent<s(frontier)> = frontier
153 23577 : GRB_TRY( GrB_assign(l_parent, frontier, GrB_NULL,
154 : frontier, GrB_ALL, n, GrB_DESC_S) );
155 :
156 : // convert all stored values in frontier to their indices
157 23021 : GRB_TRY (GrB_apply (frontier, GrB_NULL, GrB_NULL, ramp,
158 : frontier, 0, GrB_NULL)) ;
159 : }
160 :
161 : // check for early termination (extended version of the algorithm)
162 : #ifdef LG_BFS_EXTENDED
163 : {
164 126 : if (max_level >= 0 && current_level >= max_level)
165 : {
166 : // halt if max_level has been reached; if max_level is zero,
167 : // this will halt with just the src node. Note that
168 : // current_level has not yet been advanced, so the test is
169 : // "current_level >= max_level". See the SSGrB version,
170 : // where the test is done just after the current level (k)
171 : // has been advanced.
172 5 : break ;
173 : }
174 121 : if (dest >= 0)
175 : {
176 : // halt if dest node has been found; this will stop at level 0
177 : // if src == dest.
178 : int64_t x ; // value is unused
179 106 : GrB_Info info = GrB_Vector_extractElement (&x, mask, dest) ;
180 106 : if (info == GrB_SUCCESS)
181 : {
182 34 : break ;
183 : }
184 72 : GRB_TRY (info) ;
185 : }
186 : }
187 : #endif
188 :
189 : // advance to the next level
190 36472 : ++current_level;
191 :
192 : // frontier = kth level of the BFS
193 : // mask is l_parent if computing parent, l_level if computing just level
194 36472 : GRB_TRY( GrB_vxm(frontier, mask, GrB_NULL, semiring,
195 : frontier, A, GrB_DESC_RSC) );
196 :
197 : // done if frontier is empty
198 32758 : GRB_TRY( GrB_Vector_nvals(&nvals, frontier) );
199 32758 : } while (nvals > 0);
200 :
201 : //--------------------------------------------------------------------------
202 : // free workspace and return result
203 : //--------------------------------------------------------------------------
204 :
205 791 : if (compute_parent) (*parent) = l_parent ;
206 791 : if (compute_level ) (*level ) = l_level ;
207 791 : LG_FREE_WORK ;
208 791 : return (GrB_SUCCESS) ;
209 : }
|
