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