1 //------------------------------------------------------------------------------
2 // GB_conform: conform any matrix to its desired sparsity structure
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 // On input, the matrix has any one of four sparsity structures: hypersparse,
11 // sparse, bitmap, or full. A bitmap or full matrix never has pending work. A
12 // sparse or hypersparse matrix may have pending work (zombies, jumbled, and/or
13 // pending tuples). The pending work is not finished unless the matrix is
14 // converted to bitmap or full. If this method fails, the matrix is cleared
15 // of all entries.
16
17 #include "GB.h"
18
19 #define GB_FREE_ALL ;
20
21 //------------------------------------------------------------------------------
22 // GB_hyper_or_bitmap: ensure a matrix is either hypersparse or bitmap
23 //------------------------------------------------------------------------------
24
GB_hyper_or_bitmap(bool is_hyper,bool is_sparse,bool is_bitmap,bool is_full,GrB_Matrix A,GB_Context Context)25 static inline GrB_Info GB_hyper_or_bitmap
26 (
27 bool is_hyper, bool is_sparse, bool is_bitmap, bool is_full,
28 GrB_Matrix A, GB_Context Context
29 )
30 {
31 GrB_Info info ;
32 if (is_full || ((is_hyper || is_sparse) &&
33 GB_convert_sparse_to_bitmap_test (A->bitmap_switch,
34 GB_NNZ (A), A->vlen, A->vdim)))
35 {
36 // if full or sparse/hypersparse with many entries: to bitmap
37 GB_OK (GB_convert_any_to_bitmap (A, Context)) ;
38 }
39 else if (is_sparse || (is_bitmap &&
40 GB_convert_bitmap_to_sparse_test (A->bitmap_switch,
41 GB_NNZ (A), A->vlen, A->vdim)))
42 {
43 // if sparse or bitmap with few entries: to hypersparse
44 GB_OK (GB_convert_any_to_hyper (A, Context)) ;
45 }
46 return (GrB_SUCCESS) ;
47 }
48
49 //------------------------------------------------------------------------------
50 // GB_sparse_or_bitmap: ensure a matrix is either sparse or bitmap
51 //------------------------------------------------------------------------------
52
GB_sparse_or_bitmap(bool is_hyper,bool is_sparse,bool is_bitmap,bool is_full,GrB_Matrix A,GB_Context Context)53 static inline GrB_Info GB_sparse_or_bitmap
54 (
55 bool is_hyper, bool is_sparse, bool is_bitmap, bool is_full,
56 GrB_Matrix A, GB_Context Context
57 )
58 {
59 GrB_Info info ;
60 if (is_full || ((is_hyper || is_sparse) &&
61 GB_convert_sparse_to_bitmap_test (A->bitmap_switch,
62 GB_NNZ (A), A->vlen, A->vdim)))
63 {
64 // if full or sparse/hypersparse with many entries: to bitmap
65 GB_OK (GB_convert_any_to_bitmap (A, Context)) ;
66 }
67 else if (is_hyper || (is_bitmap &&
68 GB_convert_bitmap_to_sparse_test (A->bitmap_switch,
69 GB_NNZ (A), A->vlen, A->vdim)))
70 {
71 // if hypersparse or bitmap with few entries: to sparse
72 GB_OK (GB_convert_any_to_sparse (A, Context)) ;
73 }
74 return (GrB_SUCCESS) ;
75 }
76
77 //------------------------------------------------------------------------------
78 // GB_hyper_sparse_or_bitmap: ensure a matrix is hypersparse, sparse, or bitmap
79 //------------------------------------------------------------------------------
80
GB_hyper_sparse_or_bitmap(bool is_hyper,bool is_sparse,bool is_bitmap,bool is_full,GrB_Matrix A,GB_Context Context)81 static inline GrB_Info GB_hyper_sparse_or_bitmap
82 (
83 bool is_hyper, bool is_sparse, bool is_bitmap, bool is_full,
84 GrB_Matrix A, GB_Context Context
85 )
86 {
87 GrB_Info info ;
88 if (is_full || ((is_hyper || is_sparse) &&
89 GB_convert_sparse_to_bitmap_test (A->bitmap_switch,
90 GB_NNZ (A), A->vlen, A->vdim)))
91 {
92 // if full or sparse/hypersparse with many entries: to bitmap
93 GB_OK (GB_convert_any_to_bitmap (A, Context)) ;
94 }
95 else if (is_bitmap)
96 {
97 if (GB_convert_bitmap_to_sparse_test (A->bitmap_switch,
98 GB_NNZ (A), A->vlen, A->vdim))
99 {
100 // if bitmap with few entries: to sparse
101 GB_OK (GB_convert_bitmap_to_sparse (A, Context)) ;
102 // conform between sparse and hypersparse
103 GB_OK (GB_conform_hyper (A, Context)) ;
104 }
105 }
106 else // is_hyper || is_sparse
107 {
108 // conform between sparse and hypersparse
109 GB_OK (GB_conform_hyper (A, Context)) ;
110 }
111 return (GrB_SUCCESS) ;
112 }
113
114 //------------------------------------------------------------------------------
115 // GB_conform
116 //------------------------------------------------------------------------------
117
GB_conform(GrB_Matrix A,GB_Context Context)118 GrB_Info GB_conform // conform a matrix to its desired sparsity structure
119 (
120 GrB_Matrix A, // matrix to conform
121 GB_Context Context
122 )
123 {
124
125 //--------------------------------------------------------------------------
126 // check inputs
127 //--------------------------------------------------------------------------
128
129 GrB_Info info ;
130 ASSERT_MATRIX_OK (A, "A to conform", GB0) ;
131 ASSERT (GB_ZOMBIES_OK (A)) ;
132 ASSERT (GB_JUMBLED_OK (A)) ;
133 ASSERT (GB_PENDING_OK (A)) ;
134 bool is_hyper = GB_IS_HYPERSPARSE (A) ;
135 bool is_sparse = GB_IS_SPARSE (A) ;
136 bool is_full = GB_IS_FULL (A) ;
137 bool is_bitmap = GB_IS_BITMAP (A) ;
138 bool is_full_or_dense_with_no_pending_work = is_full || (GB_is_dense (A)
139 && !GB_ZOMBIES (A) && !GB_JUMBLED (A) && !GB_PENDING (A)) ;
140
141 //--------------------------------------------------------------------------
142 // select the sparsity structure
143 //--------------------------------------------------------------------------
144
145 switch (GB_sparsity_control (A->sparsity, A->vdim))
146 {
147
148 //----------------------------------------------------------------------
149 // (1) always hypersparse
150 //----------------------------------------------------------------------
151
152 case GxB_HYPERSPARSE :
153
154 GB_OK (GB_convert_any_to_hyper (A, Context)) ;
155 break ;
156
157 //----------------------------------------------------------------------
158 // (2) always sparse
159 //----------------------------------------------------------------------
160
161 case GxB_SPARSE :
162
163 GB_OK (GB_convert_any_to_sparse (A, Context)) ;
164 break ;
165
166 //----------------------------------------------------------------------
167 // (3) sparse or hypersparse
168 //----------------------------------------------------------------------
169
170 case GxB_HYPERSPARSE + GxB_SPARSE :
171
172 if (is_full || is_bitmap)
173 {
174 // if full or bitmap: to sparse
175 GB_OK (GB_convert_any_to_sparse (A, Context)) ;
176 }
177 // conform between sparse and hypersparse
178 GB_OK (GB_conform_hyper (A, Context)) ;
179 break ;
180
181 //----------------------------------------------------------------------
182 // (4) always bitmap
183 //----------------------------------------------------------------------
184
185 case GxB_BITMAP :
186
187 GB_OK (GB_convert_any_to_bitmap (A, Context)) ;
188 break ;
189
190 //----------------------------------------------------------------------
191 // (5) hypersparse or bitmap
192 //----------------------------------------------------------------------
193
194 case GxB_HYPERSPARSE + GxB_BITMAP :
195
196 // ensure the matrix is hypersparse or bitmap
197 GB_OK (GB_hyper_or_bitmap (is_hyper, is_sparse, is_bitmap,
198 is_full, A, Context)) ;
199 break ;
200
201 //----------------------------------------------------------------------
202 // (6) sparse or bitmap
203 //----------------------------------------------------------------------
204
205 case GxB_SPARSE + GxB_BITMAP :
206
207 // ensure the matrix is sparse or bitmap
208 GB_OK (GB_sparse_or_bitmap (is_hyper, is_sparse, is_bitmap,
209 is_full, A, Context)) ;
210 break ;
211
212 //----------------------------------------------------------------------
213 // (7) hypersparse, sparse, or bitmap
214 //----------------------------------------------------------------------
215
216 case GxB_HYPERSPARSE + GxB_SPARSE + GxB_BITMAP :
217
218 // ensure the matrix is hypersparse, sparse, or bitmap
219 GB_OK (GB_hyper_sparse_or_bitmap (is_hyper, is_sparse,
220 is_bitmap, is_full, A, Context)) ;
221 break ;
222
223 //----------------------------------------------------------------------
224 // (8): full
225 //----------------------------------------------------------------------
226
227 case GxB_FULL :
228
229 if (is_full_or_dense_with_no_pending_work)
230 {
231 // if full or all entries present: to full
232 GB_convert_any_to_full (A) ;
233 }
234 else
235 {
236 // otherwise: to bitmap
237 GB_OK (GB_convert_any_to_bitmap (A, Context)) ;
238 }
239 break ;
240
241 //----------------------------------------------------------------------
242 // (9) hypersparse or full
243 //----------------------------------------------------------------------
244
245 case GxB_HYPERSPARSE + GxB_FULL :
246
247 if (is_full_or_dense_with_no_pending_work)
248 {
249 // if all entries present: to full
250 GB_convert_any_to_full (A) ;
251 }
252 else
253 {
254 // otherwise: to hypersparse
255 GB_OK (GB_convert_any_to_hyper (A, Context)) ;
256 }
257 break ;
258
259 //----------------------------------------------------------------------
260 // (10) sparse or full
261 //----------------------------------------------------------------------
262
263 case GxB_SPARSE + GxB_FULL :
264
265 if (is_full_or_dense_with_no_pending_work)
266 {
267 // if full or all entries present: to full
268 GB_convert_any_to_full (A) ;
269 }
270 else
271 {
272 // otherwise: to sparse
273 GB_OK (GB_convert_any_to_sparse (A, Context)) ;
274 }
275 break ;
276
277 //----------------------------------------------------------------------
278 // (11) hypersparse, sparse, or full
279 //----------------------------------------------------------------------
280
281 case GxB_HYPERSPARSE + GxB_SPARSE + GxB_FULL :
282
283 if (is_full_or_dense_with_no_pending_work)
284 {
285 // if full or all entries present: to full
286 GB_convert_any_to_full (A) ;
287 }
288 else if (is_bitmap)
289 {
290 // if bitmap: to sparse
291 GB_OK (GB_convert_bitmap_to_sparse (A, Context)) ;
292 // conform between sparse and hypersparse
293 GB_OK (GB_conform_hyper (A, Context)) ;
294 }
295 else
296 {
297 // conform between sparse and hypersparse
298 GB_OK (GB_conform_hyper (A, Context)) ;
299 }
300 break ;
301
302 //----------------------------------------------------------------------
303 // (12): bitmap or full
304 //----------------------------------------------------------------------
305
306 case GxB_FULL + GxB_BITMAP :
307
308 if (is_bitmap)
309 {
310 // leave in bitmap form, even if it can be converted to full
311 }
312 else if (is_full_or_dense_with_no_pending_work)
313 {
314 // if full or all entries present: to full
315 GB_convert_any_to_full (A) ;
316 }
317 else
318 {
319 // otherwise: to bitmap
320 GB_OK (GB_convert_any_to_bitmap (A, Context)) ;
321 }
322 break ;
323
324 //----------------------------------------------------------------------
325 // (13) hypersparse, bitmap, or full
326 //----------------------------------------------------------------------
327
328 case GxB_HYPERSPARSE + GxB_BITMAP + GxB_FULL :
329
330 if (is_full_or_dense_with_no_pending_work && !is_bitmap)
331 {
332 // if full or all entries present (and not bitmap): to full
333 GB_convert_any_to_full (A) ;
334 }
335 else
336 {
337 // ensure the matrix is hypersparse or bitmap
338 GB_OK (GB_hyper_or_bitmap (is_hyper, is_sparse, is_bitmap,
339 is_full, A, Context)) ;
340 }
341 break ;
342
343 //----------------------------------------------------------------------
344 // (14) sparse, bitmap, or full
345 //----------------------------------------------------------------------
346
347 case GxB_SPARSE + GxB_BITMAP + GxB_FULL :
348
349 if (is_full_or_dense_with_no_pending_work && !is_bitmap)
350 {
351 // if full or all entries present (and not bitmap): to full
352 GB_convert_any_to_full (A) ;
353 }
354 else
355 {
356 // ensure the matrix is sparse or bitmap
357 GB_OK (GB_sparse_or_bitmap (is_hyper, is_sparse, is_bitmap,
358 is_full, A, Context)) ;
359 }
360 break ;
361
362 //----------------------------------------------------------------------
363 // (15) hypersparse, sparse, bitmap, or full
364 //----------------------------------------------------------------------
365
366 default:
367 case GxB_HYPERSPARSE + GxB_SPARSE + GxB_BITMAP + GxB_FULL :
368
369 if (is_full_or_dense_with_no_pending_work && !is_bitmap)
370 {
371 // if full or all entries present (and not bitmap): to full
372 GB_convert_any_to_full (A) ;
373 }
374 else
375 {
376 // ensure the matrix is hypersparse, sparse, or bitmap
377 GB_OK (GB_hyper_sparse_or_bitmap (is_hyper, is_sparse,
378 is_bitmap, is_full, A, Context)) ;
379 }
380 break ;
381 }
382
383 //--------------------------------------------------------------------------
384 // return result
385 //--------------------------------------------------------------------------
386
387 ASSERT_MATRIX_OK (A, "A conformed", GB0) ;
388 return (GrB_SUCCESS) ;
389 }
390
391