1 //------------------------------------------------------------------------------
2 // GraphBLAS/Demo/Source/bfs6.c: breadth first search (vxm and apply)
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 // Modified from the GraphBLAS C API Specification, by Aydin Buluc, Timothy
11 // Mattson, Scott McMillan, Jose' Moreira, Carl Yang. Based on "GraphBLAS
12 // Mathematics" by Jeremy Kepner.
13
14 // No copyright claim is made for this particular file; the above copyright
15 // applies to all of SuiteSparse:GraphBLAS, not this file.
16
17 // This method has been updated as of Version 2.2 of SuiteSparse:GraphBLAS.
18 // It now assumes the matrix is held by row (GxB_BY_ROW) and uses GrB_vxm
19 // instead of GrB_mxv. It now more closely matches the BFS example in the
20 // GraphBLAS C API Specification.
21
22 // A must not have any explicit zeros.
23
24 // NOTE: this method can be *slow*, in special cases (v very sparse on output,
25 // A in CSC format instead of the default CSR, or if A has any explicit values
26 // equal to zero in its pattern). See LAGraph_bfs_pushpull for a faster method
27 // that handles these cases. Do not benchmark this code! It is just for
28 // simple illustration. Use the LAGraph_bfs_pushpull for benchmarking and
29 // production use.
30
31 #include "GraphBLAS.h"
32 #undef GB_PUBLIC
33 #define GB_LIBRARY
34 #include "graphblas_demos.h"
35
36 //------------------------------------------------------------------------------
37 // bfs_level: for unary operator
38 //------------------------------------------------------------------------------
39
40 // level = depth in BFS traversal, roots=1, unvisited=0.
41
42 // Note the operator accesses a global variable outside the control of
43 // GraphBLAS. This is safe, but care must be taken not to change the global
44 // variable "level" while pending operations have yet to be completed.
45
46 int32_t bfs_level_global = 0 ;
47
bfs_level(void * result,const void * element)48 void bfs_level (void *result, const void *element)
49 {
50 // Note this function does not depend on its input. It returns the value
51 // of the global variable level for all inputs. It is applied to the
52 // vector q via GrB_apply, which only applies the unary operator to entries
53 // in the pattern. Entries not in the pattern remain implicit (zero in
54 // this case), and then are not added by the GrB_PLUS_INT32 accum function.
55 (* ((int32_t *) result)) = bfs_level_global ;
56 }
57
58 //------------------------------------------------------------------------------
59 // bfs6: breadth first search using a Boolean semiring
60 //------------------------------------------------------------------------------
61
62 // Given a n x n adjacency matrix A and a source node s, performs a BFS
63 // traversal of the graph and sets v[i] to the level in which node i is
64 // visited (v[s] == 1). If i is not reacheable from s, then v[i] = 0. (Vector
65 // v should be empty on input.) The graph A need not be Boolean on input;
66 // if it isn't Boolean, the semiring will properly typecast it to Boolean.
67
68 GB_PUBLIC
bfs6(GrB_Vector * v_output,const GrB_Matrix A,GrB_Index s)69 GrB_Info bfs6 // BFS of a graph (using apply)
70 (
71 GrB_Vector *v_output, // v [i] is the BFS level of node i in the graph
72 const GrB_Matrix A, // input graph, treated as if boolean in semiring
73 GrB_Index s // starting node of the BFS
74 )
75 {
76
77 //--------------------------------------------------------------------------
78 // set up the semiring and initialize the vector v
79 //--------------------------------------------------------------------------
80
81 GrB_Index n ; // # of nodes in the graph
82 GrB_Vector q = NULL ; // nodes visited at each level
83 GrB_Vector v = NULL ; // result vector
84 GrB_Descriptor desc = NULL ; // Descriptor for vxm
85 GrB_UnaryOp apply_level = NULL ; // unary op:
86 // z = f(x) = bfs_level_global
87
88 GrB_Matrix_nrows (&n, A) ; // n = # of rows of A
89 GrB_Vector_new (&v, GrB_INT32, n) ; // Vector<int32_t> v(n) = 0
90 GrB_Vector_assign_INT32 (v, NULL, NULL, 0, GrB_ALL, n, NULL) ; // make dense
91 GrB_Vector_nvals (&n, v) ; // finish pending work on v
92
93 GrB_Vector_new (&q, GrB_BOOL, n) ; // Vector<bool> q(n) = false
94 GrB_Vector_setElement_BOOL (q, true, s) ; // q[s] = true, false elsewhere
95
96 GrB_Descriptor_new (&desc) ;
97 GrB_Descriptor_set (desc, GrB_MASK, GrB_COMP) ; // invert the mask
98 GrB_Descriptor_set (desc, GrB_OUTP, GrB_REPLACE) ; // clear q first
99
100 // create a unary operator
101 GrB_UnaryOp_new (&apply_level, bfs_level, GrB_INT32, GrB_BOOL) ;
102
103 //--------------------------------------------------------------------------
104 // BFS traversal and label the nodes
105 //--------------------------------------------------------------------------
106
107 bool successor = true ; // true when some successor found
108 for (bfs_level_global = 1 ; successor && bfs_level_global <= n ;
109 bfs_level_global++)
110 {
111
112 // v[q] = bfs_level_global, using apply. This function applies the
113 // unary operator to the entries in q, which are the unvisited
114 // successors, and then writes their levels to v, thus updating the
115 // levels of those nodes in v. The patterns of v and q are disjoint.
116 GrB_Vector_apply (v, NULL, GrB_PLUS_INT32, apply_level, q, NULL) ;
117
118 // q<!v> = q ||.&& A ; finds all the unvisited
119 // successors from current q, using !v as the mask
120 GrB_vxm (q, v, NULL, GrB_LOR_LAND_SEMIRING_BOOL, q, A, desc) ;
121
122 // successor = ||(q)
123 GrB_Vector_reduce_BOOL (&successor, NULL, GrB_LOR_MONOID_BOOL, q, NULL) ;
124 }
125
126 // make v sparse
127 GrB_Descriptor_set (desc, GrB_MASK, GxB_DEFAULT) ; // mask not inverted
128 GrB_Vector_assign (v, v, NULL, v, GrB_ALL, n, desc) ;
129
130 *v_output = v ; // return result
131
132 GrB_Vector_free (&q) ;
133 GrB_Descriptor_free (&desc) ;
134 GrB_UnaryOp_free (&apply_level) ;
135
136 return (GrB_SUCCESS) ;
137 }
138
139