Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_BreadthFirstSearch_vanilla: BFS using only GraphBLAS API
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 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 9464 : int LG_BreadthFirstSearch_vanilla
37 : (
38 : GrB_Vector *level,
39 : GrB_Vector *parent,
40 : const LAGraph_Graph G,
41 : GrB_Index src,
42 : char *msg
43 : )
44 : {
45 :
46 : //--------------------------------------------------------------------------
47 : // check inputs
48 : //--------------------------------------------------------------------------
49 :
50 9464 : LG_CLEAR_MSG ;
51 9464 : GrB_Vector frontier = NULL; // the current frontier
52 9464 : GrB_Vector l_parent = NULL; // parent vector
53 9464 : GrB_Vector l_level = NULL; // level vector
54 :
55 9464 : bool compute_level = (level != NULL);
56 9464 : bool compute_parent = (parent != NULL);
57 9464 : if (compute_level ) (*level ) = NULL;
58 9464 : if (compute_parent) (*parent) = NULL;
59 9464 : LG_ASSERT_MSG (compute_level || compute_parent, GrB_NULL_POINTER,
60 : "either level or parent must be non-NULL") ;
61 :
62 9461 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
63 :
64 : //--------------------------------------------------------------------------
65 : // get the problem size
66 : //--------------------------------------------------------------------------
67 :
68 9461 : GrB_Matrix A = G->A ;
69 :
70 : GrB_Index n;
71 9461 : GRB_TRY( GrB_Matrix_nrows (&n, A) );
72 9461 : LG_ASSERT_MSG (src < n, GrB_INVALID_INDEX, "invalid source node") ;
73 :
74 : // determine the semiring type
75 9459 : GrB_Type int_type = (n > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
76 : GrB_BinaryOp
77 9459 : second_op = (n > INT32_MAX) ? GrB_SECOND_INT64 : GrB_SECOND_INT32 ;
78 9459 : GrB_Semiring semiring = NULL;
79 9459 : GrB_IndexUnaryOp ramp = NULL ;
80 :
81 9459 : if (compute_parent)
82 : {
83 : // create the parent vector. l_parent(i) is the parent id of node i
84 5338 : GRB_TRY (GrB_Vector_new(&l_parent, int_type, n)) ;
85 :
86 10180 : semiring = (n > INT32_MAX) ?
87 5090 : GrB_MIN_FIRST_SEMIRING_INT64 : GrB_MIN_FIRST_SEMIRING_INT32;
88 :
89 : // create a sparse integer vector frontier, and set frontier(src) = src
90 5090 : GRB_TRY (GrB_Vector_new(&frontier, int_type, n)) ;
91 4842 : GRB_TRY (GrB_Vector_setElement(frontier, src, src)) ;
92 :
93 : // pick the ramp operator
94 4470 : ramp = (n > INT32_MAX) ? GrB_ROWINDEX_INT64 : GrB_ROWINDEX_INT32 ;
95 : }
96 : else
97 : {
98 : // only the level is needed
99 4121 : semiring = LAGraph_any_one_bool ;
100 :
101 : // create a sparse boolean vector frontier, and set frontier(src) = true
102 4121 : GRB_TRY (GrB_Vector_new(&frontier, GrB_BOOL, n)) ;
103 3873 : GRB_TRY (GrB_Vector_setElement(frontier, true, src)) ;
104 : }
105 :
106 7971 : if (compute_level)
107 : {
108 : // create the level vector. v(i) is the level of node i
109 : // v (src) = 0 denotes the source node
110 7791 : GRB_TRY (GrB_Vector_new(&l_level, int_type, n)) ;
111 : }
112 :
113 : //--------------------------------------------------------------------------
114 : // BFS traversal and label the nodes
115 : //--------------------------------------------------------------------------
116 :
117 7475 : GrB_Index nq = 1 ; // number of nodes in the current level
118 7475 : GrB_Index last_nq = 0 ;
119 7475 : GrB_Index current_level = 0;
120 7475 : GrB_Index nvals = 1;
121 :
122 : // {!mask} is the set of unvisited nodes
123 7475 : GrB_Vector mask = (compute_parent) ? l_parent : l_level ;
124 :
125 : // parent BFS
126 : do
127 : {
128 39395 : if (compute_level)
129 : {
130 : // assign levels: l_level<s(frontier)> = current_level
131 30428 : GRB_TRY( GrB_assign(l_level, frontier, GrB_NULL,
132 : current_level, GrB_ALL, n, GrB_DESC_S) );
133 28066 : ++current_level;
134 : }
135 :
136 37033 : if (compute_parent)
137 : {
138 : // frontier(i) currently contains the parent id of node i in tree.
139 : // l_parent<s(frontier)> = frontier
140 23561 : GRB_TRY( GrB_assign(l_parent, frontier, GrB_NULL,
141 : frontier, GrB_ALL, n, GrB_DESC_S) );
142 :
143 : // convert all stored values in frontier to their indices
144 23005 : GRB_TRY (GrB_apply (frontier, GrB_NULL, GrB_NULL, ramp,
145 : frontier, 0, GrB_NULL)) ;
146 : }
147 :
148 : // frontier = kth level of the BFS
149 : // mask is l_parent if computing parent, l_level if computing just level
150 36353 : GRB_TRY( GrB_vxm(frontier, mask, GrB_NULL, semiring,
151 : frontier, A, GrB_DESC_RSC) );
152 :
153 : // done if frontier is empty
154 32671 : GRB_TRY( GrB_Vector_nvals(&nvals, frontier) );
155 32671 : } while (nvals > 0);
156 :
157 : //--------------------------------------------------------------------------
158 : // free workspace and return result
159 : //--------------------------------------------------------------------------
160 :
161 751 : if (compute_parent) (*parent) = l_parent ;
162 751 : if (compute_level ) (*level ) = l_level ;
163 751 : LG_FREE_WORK ;
164 751 : return (GrB_SUCCESS) ;
165 : }
|
