1 //------------------------------------------------------------------------------
2 // GB_mask: apply a mask: C<M> = Z
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 // C<M> = Z
11
12 // GB_mask is only called by GB_accum_mask.
13
14 // If M is NULL, C can have any sparsity. Otherwise, if M is present then
15 // C is sparse or hypersparse; if bitmap or full, GB_subassign is used instead.
16
17 // Nearly all GraphBLAS operations take a mask, which controls how the result
18 // of the computations, Z, are copied into the result matrix C. The following
19 // working MATLAB script, GB_spec_mask, defines how this is done. In the
20 // comments, C(i,j) is shorthand for the index i in the jth vector, and
21 // likewise for M, Z, and R. If the matrices are all CSC, then this is row i
22 // and column j. If the matrices are all CSR, then it is row j and column i.
23
24 #include "GB_mask.h"
25
26 /*
27
28 function R = GB_spec_mask (C, M, Z, C_replace, Mask_comp,identity)
29 %GB_SPEC_MASK: a pure MATLAB implementation of GB_mask
30 %
31 % Computes C<M> = Z, in GraphBLAS notation.
32 %
33 % Usage:
34 % C = GB_spec_mask (C, M, Z, C_replace, Mask_comp, identity)
35 %
36 % C and Z: matrices of the same size.
37 %
38 % optional inputs:
39 % M: if empty or not present, M = ones (size (C))
40 % C_replace: set C to zero first. Default is false.
41 % Mask_comp: use ~M instead of M. Default is false.
42 % identity: the additive identity of the semiring. Default is zero.
43 % This is only needed because the GB_spec_* routines operate on dense
44 % matrices, and thus they need to know the value of the implicit 'zero'.
45 %
46 % This method operates on both plain matrices and on structs with
47 % matrix, pattern, and class components.
48
49 if (nargin < 6)
50 identity = 0 ;
51 end
52 if (nargin < 5)
53 Mask_comp = false ;
54 end
55 if (nargin < 4)
56 C_replace = false ;
57 end
58
59 if (isstruct (C))
60 % apply the mask to both the matrix and the pattern
61 R.matrix = GB_spec_mask (C.matrix, M, Z.matrix, C_replace, ...
62 Mask_comp, identity) ;
63 R.pattern = GB_spec_mask (C.pattern, M, Z.pattern, C_replace, ...
64 Mask_comp, false) ;
65 R.class = C.class ;
66 return
67 end
68
69 if (~isequal (size (C), size (Z)))
70 error ('C and Z must have the same size') ;
71 end
72 if (~isempty (M))
73 if (~isequal (size (C), size (M)))
74 error ('C and M must have the same size') ;
75 end
76 end
77
78 % replace C if requested
79 if (C_replace)
80 C (:,:) = identity ;
81 end
82
83 if (isempty (M))
84 % in GraphBLAS, this means M is NULL;
85 % implicitly, M = ones (size (C))
86 if (~Mask_comp)
87 R = Z ;
88 else
89 % note that Z need never have been computed
90 R = C ;
91 end
92 else
93 % form the Boolean mask. For GraphBLAS, this does the
94 % right thing and ignores explicit zeros in M.
95 M = (M ~= 0) ;
96 if (~Mask_comp)
97 % R will equal C where M is false
98 R = C ;
99 % overwrite R with Z where M is true
100 R (M) = Z (M) ;
101 else
102 % M is complemented
103 % R will equal Z where M is false
104 R = Z ;
105 % overwrite R with C where M is true
106 R (M) = C (M) ;
107 end
108 end
109
110 */
111
112 #define GB_FREE_ALL \
113 { \
114 GB_Matrix_free (Zhandle) ; \
115 GB_phbix_free (C0) ; \
116 GB_phbix_free (R) ; \
117 }
118
119 //------------------------------------------------------------------------------
120
GB_mask(GrB_Matrix C_result,const GrB_Matrix M,GrB_Matrix * Zhandle,const bool C_replace,const bool Mask_comp,const bool Mask_struct,GB_Context Context)121 GrB_Info GB_mask // C<M> = Z
122 (
123 GrB_Matrix C_result, // both input C and result matrix
124 const GrB_Matrix M, // optional mask matrix, can be NULL
125 GrB_Matrix *Zhandle, // Z = results of computation, perhaps shallow.
126 // Z is freed when done.
127 const bool C_replace, // true if clear(C) to be done first
128 const bool Mask_comp, // true if M is to be complemented
129 const bool Mask_struct, // if true, use the only structure of M
130 GB_Context Context
131 )
132 {
133
134 //--------------------------------------------------------------------------
135 // check inputs
136 //--------------------------------------------------------------------------
137
138 // C_result may be aliased with M
139 ASSERT_MATRIX_OK (C_result, "C_result for GB_mask", GB0) ;
140 ASSERT (!C_result->static_header) ;
141 // C may be cleared anyway, without the need for finishing it
142 ASSERT (GB_ZOMBIES_OK (C_result)) ;
143 ASSERT (GB_JUMBLED_OK (C_result)) ;
144 ASSERT (GB_PENDING_OK (C_result)) ;
145
146 ASSERT_MATRIX_OK_OR_NULL (M, "M for GB_mask", GB0) ;
147 // M may have zombies and pending tuples
148 ASSERT (GB_PENDING_OK (M)) ;
149 ASSERT (GB_JUMBLED_OK (M)) ;
150 ASSERT (GB_ZOMBIES_OK (M)) ;
151
152 // Z has the same type as C_result, with no zombies or pending tuples
153 ASSERT (Zhandle != NULL) ;
154 GrB_Matrix Z = *Zhandle ;
155 ASSERT_MATRIX_OK (Z, "Z for GB_mask", GB0) ;
156 ASSERT (!GB_PENDING (Z)) ;
157 ASSERT (GB_JUMBLED_OK (Z)) ;
158 ASSERT (!GB_ZOMBIES (Z)) ;
159 ASSERT (Z->type == C_result->type) ;
160 // Z and C_result are never aliased. C_result and M might be.
161 ASSERT (Z != C_result) ;
162 // Z and C_result must have the same format and dimensions
163 ASSERT (C_result->vlen == Z->vlen) ;
164 ASSERT (C_result->vdim == Z->vdim) ;
165
166 // M must be compatible with C_result
167 ASSERT_OK (GB_Mask_compatible (M, Mask_struct, C_result, 0, 0, Context)) ;
168
169 GrB_Info info = GrB_SUCCESS ;
170
171 GrB_Matrix C = NULL ;
172
173 struct GB_Matrix_opaque C0_header, R_header ;
174 GrB_Matrix C0 = GB_clear_static_header (&C0_header) ;
175 GrB_Matrix R = GB_clear_static_header (&R_header) ;
176
177 //--------------------------------------------------------------------------
178 // apply the mask
179 //--------------------------------------------------------------------------
180
181 if (M == NULL)
182 {
183
184 //----------------------------------------------------------------------
185 // there is no mask (implicitly M(i,j)=1 for all i and j)
186 //----------------------------------------------------------------------
187
188 // Any pending work on C is abandoned (zombies and/or pending tuples).
189 // C and Z can have any sparsity, including bitmap or full.
190
191 if (!Mask_comp)
192 {
193
194 //------------------------------------------------------------------
195 // mask is not complemented: this is the default
196 //------------------------------------------------------------------
197
198 // C_result = Z, but make sure a deep copy is made as needed. It is
199 // possible that Z is a shallow copy of another matrix.
200 // Z is freed by GB_transplant_conform.
201 ASSERT (!C_result->p_shallow) ;
202 ASSERT (!C_result->h_shallow) ;
203
204 // transplant Z into C_result and conform to desired hypersparsity
205 return (GB_transplant_conform (C_result, C_result->type, Zhandle,
206 Context)) ;
207 }
208 else
209 {
210
211 //------------------------------------------------------------------
212 // an empty mask is complemented: Z is ignored
213 //------------------------------------------------------------------
214
215 // Z is ignored, and can even be NULL. The method that calls
216 // GB_mask can short circuit its computation, ignore accum, and
217 // apply the mask immediately, and then return to its caller.
218 // This done by the GB_RETURN_IF_QUICK_MASK macro.
219
220 // In the current version, this work is always done by the
221 // GB_RETURN_IF_QUICK_MASK macro, and GB_mask is no longer called
222 // with an empty complemented mask. The following is thus dead
223 // code. It is kept here in case this function is called to handle
224 // this case in a future version.
225
226 ASSERT (GB_DEAD_CODE) ; // the following is no longer used
227
228 // free Z if it exists (this is OK if Zhandle is NULL)
229 GB_Matrix_free (Zhandle) ;
230
231 if (C_replace)
232 {
233 // C_result = 0
234 return (GB_clear (C_result, Context)) ;
235 }
236 else
237 {
238 // nothing happens
239 return (GrB_SUCCESS) ;
240 }
241 }
242
243 }
244 else
245 {
246
247 //----------------------------------------------------------------------
248 // the mask is present
249 //----------------------------------------------------------------------
250
251 // delete any lingering zombies and assemble any pending tuples
252 GB_MATRIX_WAIT (M) ; // also sort M if jumbled
253 GB_MATRIX_WAIT (Z) ; // also sort Z if jumbled
254
255 // R has the same CSR/CSC format as C_result. It is hypersparse if
256 // both C and Z are hypersparse.
257
258 bool R_is_csc = C_result->is_csc ;
259 int64_t vdim = C_result->vdim ;
260 int64_t vlen = C_result->vlen ;
261
262 if (C_replace)
263 {
264 if (GB_aliased (C_result, M))
265 {
266 // C_result and M are aliased. This is OK, unless C_replace is
267 // true. In this case, M must be left unchanged but C_result
268 // must be cleared. To resolve this, a new matrix C0 is
269 // created, which is what C_result would look like if cleared.
270 // C_result is left unchanged since changing it would change M.
271 // The C0 matrix is created as hypersparse.
272 int sparsity = GxB_HYPERSPARSE ;
273 GB_OK (
274 GB_new_bix (&C0, true, // sparse or hyper, static header
275 C_result->type, vlen, vdim, GB_Ap_calloc, R_is_csc,
276 sparsity, true, C_result->hyper_switch, 0, 0, true,
277 Context)) ;
278 C = C0 ;
279 ASSERT (C->static_header) ;
280 }
281 else
282 {
283 // Clear all entries from C_result, and ensure C is hypersparse
284 // by temporarily changing the sparsity control
285 int save = C_result->sparsity ; // save control
286 C_result->sparsity = GxB_HYPERSPARSE ;
287 GB_OK (GB_clear (C_result, Context)) ;
288 C_result->sparsity = save ; // restore control
289 C = C_result ; // C must have a dynamic header
290 ASSERT (!C->static_header) ;
291 }
292 // C has been cleared, so it has no zombies or pending tuples
293 }
294 else
295 {
296 // C has already been finished if C_replace is false, via the
297 // GB_MATRIX_WAIT (C) in GB_accum_mask.
298 C = C_result ;
299 ASSERT (!C->static_header) ;
300 }
301
302 // C cannot be bitmap or full for GB_masker
303 ASSERT (!GB_IS_BITMAP (C)) ;
304 ASSERT (!GB_IS_FULL (C)) ;
305
306 // no more zombies or pending tuples in M or C
307 ASSERT (!GB_PENDING (M)) ;
308 ASSERT (!GB_JUMBLED (M)) ;
309 ASSERT (!GB_ZOMBIES (M)) ;
310 ASSERT (!GB_PENDING (C)) ;
311 ASSERT (!GB_JUMBLED (C)) ;
312 ASSERT (!GB_ZOMBIES (C)) ;
313
314 // continue with C, do not use C_result until the end since it may be
315 // aliased with M.
316
317 //----------------------------------------------------------------------
318 // R = masker (C, M, Z): compute C<M>=Z, placing results in R
319 //----------------------------------------------------------------------
320
321 GB_OK (GB_masker (R, R_is_csc, M, Mask_comp, Mask_struct, C, Z,
322 Context)) ;
323
324 //----------------------------------------------------------------------
325 // free temporary matrices Z and C0
326 //----------------------------------------------------------------------
327
328 GB_Matrix_free (Zhandle) ;
329 GB_phbix_free (C0) ;
330
331 //----------------------------------------------------------------------
332 // transplant the result, conform, and free R
333 //----------------------------------------------------------------------
334
335 // finished using the mask M, so it is now safe to modify C_result,
336 // even if C_result and M are aliased
337
338 return (GB_transplant_conform (C_result, R->type, &R, Context)) ;
339 }
340 }
341
342