1 //------------------------------------------------------------------------------
2 // GraphBLAS/Demo/Program/bfs_demo.c: breadth first search using vxm with a mask
3 //------------------------------------------------------------------------------
4
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7
8 //------------------------------------------------------------------------------
9
10 // Read a graph from a file and performs a BFS using four different methods.
11
12 // Usage:
13 //
14 // bfs_demo < infile
15 // bfs_demo 0 nrows ncols ntuples method
16 // bfs_demo 1 nx ny method
17 //
18 // Where infile has one line per edge in the graph; these have the form
19 //
20 // i j x
21 //
22 // where A(i,j)=x is performed by GrB_Matrix_build, to construct the matrix.
23 // The dimensions of A are assumed to be the largest row and column indices,
24 // plus one (in read_matrix.c).
25 //
26 // For the second usage (bfs_demo 0 ...), a random symmetric matrix is created
27 // of size nrows-by-ncols with ntuples edges (some will be duplicates so the
28 // actual number of edges will be slightly less). The method is 0 for
29 // setElement and 1 for build.
30 //
31 // The 3rd usage (bfs_demo 1 ...) creates a finite-element matrix on an
32 // nx-by-ny grid. Method is 0 to 3; refer to wathen.c for details.
33
34 // macro used by OK(...) to free workspace if an error occurs
35 #define FREE_ALL \
36 GrB_Vector_free (&v) ; \
37 GrB_Vector_free (&v0) ; \
38 GrB_Matrix_free (&A) ; \
39 GrB_Matrix_free (&Abool) ; \
40 GrB_Vector_free (&is_reachable) ; \
41 GrB_Monoid_free (&max_monoid) ;
42
43 #include "graphblas_demos.h"
44
main(int argc,char ** argv)45 int main (int argc, char **argv)
46 {
47 GrB_Info info ;
48 GrB_Matrix A = NULL ;
49 GrB_Matrix A2, Abool = NULL ;
50 GrB_Vector v = NULL, v0 = NULL ;
51 GrB_Vector is_reachable = NULL ;
52 GrB_Monoid max_monoid = NULL ;
53 GrB_Index nreach0 = 0 ;
54 int64_t nlevel0 = -1 ;
55 double tic [2], t ;
56 OK (GrB_init (GrB_NONBLOCKING)) ;
57 int nthreads ;
58 OK (GxB_Global_Option_get (GxB_GLOBAL_NTHREADS, &nthreads)) ;
59 OK (GxB_Global_Option_set (GxB_BURBLE, false)) ;
60 fprintf (stderr, "bfs_demo: nthreads %d\n", nthreads) ;
61
62 //--------------------------------------------------------------------------
63 // read a matrix from stdin
64 //--------------------------------------------------------------------------
65
66 // self edges are OK
67 OK (get_matrix (&A, argc, argv, false, true, true)) ;
68 GrB_Index n ;
69 OK (GrB_Matrix_nrows (&n, A)) ;
70
71 printf ("number of nodes: %g\n", (double) n) ;
72
73 // typecast A to boolean, if needed. This is not required but it
74 // speeds up the BFS
75 A2 = A ;
76
77 GrB_Type atype ;
78 OK (GxB_Matrix_type (&atype, A)) ;
79 if (atype != GrB_BOOL)
80 {
81 OK (GrB_Matrix_new (&Abool, GrB_BOOL, n, n)) ;
82 OK (GrB_Matrix_apply (Abool, NULL, NULL, GrB_IDENTITY_BOOL, A, NULL)) ;
83 A2 = Abool ;
84 }
85
86 for (int method = 0 ; method <= 3 ; method++)
87 {
88
89 //----------------------------------------------------------------------
90 // do the BFS, starting at node zero
91 //----------------------------------------------------------------------
92
93 // All methods give identical results, just using different methods
94
95 GrB_Index s = 0 ;
96
97 switch (method)
98 {
99
100 case 0:
101 // BFS using vector assign and reduce
102 printf ("\nmethod 5: vector assign and reduce:\n") ;
103 simple_tic (tic) ;
104 OK (bfs5m (&v, A2, s)) ;
105 break ;
106
107 case 1:
108 // BFS using vector assign and reduce
109 printf ("\nmethod 5: same but check each result\n") ;
110 simple_tic (tic) ;
111 OK (bfs5m_check (&v, A2, s)) ;
112 break ;
113
114 case 2:
115 // BFS using unary operator
116 printf ("\nmethod 6: apply unary operator\n") ;
117 simple_tic (tic) ;
118 OK (bfs6 (&v, A2, s)) ;
119 break ;
120
121 case 3:
122 // BFS using unary operator
123 printf ("\nmethod 6: same but check each result\n") ;
124 simple_tic (tic) ;
125 OK (bfs6_check (&v, A2, s)) ;
126 break ;
127
128 default:
129 CHECK (false, GrB_INVALID_VALUE) ;
130 break ;
131 }
132
133 //----------------------------------------------------------------------
134 // report the results
135 //----------------------------------------------------------------------
136
137 t = simple_toc (tic) ;
138 printf ("BFS time in seconds: %14.6f\n", t) ;
139
140 GrB_Index nreachable = 0 ;
141
142 OK (GrB_Vector_new (&is_reachable, GrB_BOOL, n)) ;
143 OK (GrB_Vector_apply (is_reachable, NULL, NULL, GrB_IDENTITY_BOOL,
144 v, NULL)) ;
145 OK (GrB_Vector_reduce_UINT64 (&nreachable, NULL, GrB_PLUS_MONOID_INT32,
146 is_reachable, NULL)) ;
147 OK (GrB_Vector_free (&is_reachable)) ;
148 // OK (GrB_Vector_nvals (&nreachable, v)) ;
149 printf ("nodes reachable from node %.16g: %.16g out of %.16g\n",
150 (double) s, (double) nreachable, (double) n) ;
151
152 // find the max BFS level
153 int64_t nlevels = -1 ;
154 OK (GrB_Vector_reduce_INT64 (&nlevels, NULL, GrB_MAX_MONOID_INT32,
155 v, NULL)) ;
156 printf ("max BFS level: %.16g\n", (double) nlevels) ;
157
158 fprintf (stderr, "nodes reached: %.16g of %.16g levels: %.16g "
159 "time: %12.6f seconds\n", (double) nreachable, (double) n,
160 (double) nlevels, t) ;
161
162 if (method == 0)
163 {
164 v0 = v ;
165 nreach0 = nreachable ;
166 nlevel0 = nlevels ;
167 v = NULL ;
168 }
169 else
170 {
171 bool ok = true ;
172 if (nreachable != nreach0 || nlevels != nlevel0)
173 {
174 ok = false ;
175 }
176 // see LAGraph_Vector_isequal for a better method
177 for (int64_t i = 0 ; i < n ; i++)
178 {
179 int32_t v0i = -1, vi = -1 ;
180 OK (GrB_Vector_extractElement_INT32 (&v0i, v0, i)) ;
181 OK (GrB_Vector_extractElement_INT32 (&vi , v , i)) ;
182 if (v0i != vi)
183 {
184 fprintf (stderr, "v failure!\n") ;
185 printf ("v failure!\n") ;
186 ok = false ;
187 break ;
188 }
189 }
190 if (!ok)
191 {
192 fprintf (stderr, "test failure!\n") ;
193 printf ("test failure!\n") ;
194 GxB_Vector_fprint (v0, "v0", GxB_COMPLETE, stdout) ;
195 GxB_Vector_fprint (v , "v", GxB_COMPLETE, stdout) ;
196 exit (1) ;
197 }
198 }
199
200 OK (GrB_Vector_free (&v)) ;
201 }
202
203 // free all workspace, including A, v, and max_monoid if allocated
204 FREE_ALL ;
205
206 //--------------------------------------------------------------------------
207 // now break something on purpose and report the error:
208 //--------------------------------------------------------------------------
209
210 if (n == 4)
211 {
212 // this fails because the compiler selects the GrB_Monoid_new_INT32
213 // function (clang 8.0 on MacOSX, at least), since false is merely the
214 // constant "0".
215 GrB_Monoid Lor ;
216 info = GrB_Monoid_new_INT32 (&Lor, GrB_LOR, false) ;
217 printf ("\n------------------- this fails: info %d\n", info) ;
218 GrB_Monoid_free (&Lor) ;
219
220 // this selects the correct GrB_Monoid_new_BOOL function
221 info = GrB_Monoid_new_BOOL (&Lor, GrB_LOR, (bool) false) ;
222 printf ("\n------------------- this is OK %d (should be"
223 " GrB_SUCCESS = %d)\n", info, GrB_SUCCESS) ;
224 GrB_Monoid_free (&Lor) ;
225 }
226
227 fprintf (stderr, "\n") ;
228 GrB_finalize ( ) ;
229 }
230
231