1 //------------------------------------------------------------------------------
2 // GB_build: build a matrix
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 // CALLED BY: GB_matvec_build
11 // CALLS: GB_builder
12
13 // GB_matvec_build constructs a GrB_Matrix or GrB_Vector from the tuples
14 // provided by the user. In that case, the tuples must be checked for
15 // duplicates. They might be sorted on input, so this condition is checked and
16 // exploited if that condition is found. All of these conditions are checked
17 // in GB_builder.
18
19 // GB_build constructs a matrix C from a list of indices and values. Any
20 // duplicate entries with identical indices are assembled using the binary dup
21 // operator provided on input. All three types (x,y,z for z=dup(x,y)) must be
22 // identical. The types of dup, S, and C must all be compatible.
23
24 // Duplicates are assembled using T(i,j) = dup (T (i,j), S (k)) into a
25 // temporary matrix T that has the same type as the dup operator. The
26 // GraphBLAS spec requires dup to be associative so that entries can be
27 // assembled in any order. There is no way to check this condition if dup is a
28 // user-defined operator. It could be checked for built-in operators, but the
29 // GraphBLAS spec does not require this condition to cause an error so that is
30 // not done here. If dup is not associative, the GraphBLAS spec states that
31 // the results are not defined.
32
33 // SuiteSparse:GraphBLAS provides a well-defined order of assembly, however.
34 // For a CSC format, entries in [I,J,S] are first sorted in increasing order of
35 // row and column index via a stable sort, with ties broken by the position of
36 // the tuple in the [I,J,S] list. If duplicates appear, they are assembled in
37 // the order they appear in the [I,J,S] input. That is, if the same indices i
38 // and j appear in positions k1, k2, k3, and k4 in [I,J,S], where k1 < k2 < k3
39 // < k4, then the following operations will occur in order:
40
41 // T (i,j) = S (k1) ;
42
43 // T (i,j) = dup (T (i,j), S (k2)) ;
44
45 // T (i,j) = dup (T (i,j), S (k3)) ;
46
47 // T (i,j) = dup (T (i,j), S (k4)) ;
48
49 // This is a well-defined order but the user should not depend upon it since
50 // the GraphBLAS spec does not require this ordering. Results may differ in
51 // different implementations of GraphBLAS.
52
53 // However, with this well-defined order, the SECOND operator will result in
54 // the last tuple overwriting the earlier ones. This is relied upon internally
55 // by GB_Matrix_wait.
56
57 // After the matrix T is assembled, it is typecasted into the type of C, the
58 // final output matrix. No typecasting is done during assembly of duplicates,
59 // since mixing the two can break associativity and lead to unpredictable
60 // results. Note that this is not the case for GB_Matrix_wait, which must
61 // typecast each tuple into its output matrix in the same order they are seen
62 // in the [I,J,S] pending tuples.
63
64 // On input, C must not be NULL. C->type, C->vlen, C->vdim and C->is_csc must
65 // be valid on input and are unchanged on output. C must not have any existing
66 // entries on input (GrB_*_nvals (C) must return zero, per the specification).
67 // However, all existing content in C is freed.
68
69 // The list of numerical values is given by the void * S array and a type code,
70 // scode. The latter is defined by the actual C type of the S parameter in
71 // the user-callable functions. However, for user-defined types, there is no
72 // way of knowing that the S array has the same type as dup or C, since in that
73 // case S is just a void * pointer. Behavior is undefined if the user breaks
74 // this condition.
75
76 // C is returned as hypersparse or non-hypersparse, depending on the number of
77 // non-empty vectors of C. If C has very few non-empty vectors, then it is
78 // returned as hypersparse. Only if the number of non-empty vectors is
79 // Omega(n) is C returned as non-hypersparse, which implies nvals is Omega(n),
80 // where n = # of columns of C if CSC, or # of rows if CSR. As a result, the
81 // time taken by this function is just O(nvals*log(nvals)), regardless of what
82 // format C is returned in.
83
84 // The input arrays I_input, J_input, and S_input are not modified.
85 // If nvals == 0, I_input, J_input, and S_input may be NULL.
86
87 #include "GB_build.h"
88
GB_build(GrB_Matrix C,const GrB_Index * I_input,const GrB_Index * J_input,const void * S_input,const GrB_Index nvals,const GrB_BinaryOp dup,const GB_Type_code scode,const bool is_matrix,GB_Context Context)89 GrB_Info GB_build // build matrix
90 (
91 GrB_Matrix C, // matrix to build
92 const GrB_Index *I_input, // "row" indices of tuples (as if CSC)
93 const GrB_Index *J_input, // "col" indices of tuples (as if CSC)
94 // J_input is NULL for GrB_Vector_build
95 const void *S_input, // values
96 const GrB_Index nvals, // number of tuples
97 const GrB_BinaryOp dup, // binary function to assemble duplicates
98 const GB_Type_code scode, // GB_Type_code of S_input array
99 const bool is_matrix, // true if C is a matrix, false if GrB_Vector
100 GB_Context Context
101 )
102 {
103
104 //--------------------------------------------------------------------------
105 // check inputs
106 //--------------------------------------------------------------------------
107
108 ASSERT (C != NULL) ;
109 ASSERT (dup != NULL) ;
110 ASSERT (!GB_OP_IS_POSITIONAL (dup)) ;
111
112 //--------------------------------------------------------------------------
113 // free all content of C
114 //--------------------------------------------------------------------------
115
116 // the type, dimensions, hyper_switch, bitmap_switch and sparsity control
117 // are still preserved in C.
118 GB_phbix_free (C) ;
119 ASSERT (GB_IS_EMPTY (C)) ;
120 ASSERT (!GB_ZOMBIES (C)) ;
121 ASSERT (C->magic == GB_MAGIC2) ;
122
123 //--------------------------------------------------------------------------
124 // build the matrix T
125 //--------------------------------------------------------------------------
126
127 // T is always built as hypersparse. Its type is the same as the z output
128 // of the z=dup(x,y) operator.
129
130 // S_input must be treated as read-only, so GB_builder is not allowed to
131 // transplant it into T->x.
132
133 int64_t *no_I_work = NULL ; size_t I_work_size = 0 ;
134 int64_t *no_J_work = NULL ; size_t J_work_size = 0 ;
135 GB_void *no_S_work = NULL ; size_t S_work_size = 0 ;
136 struct GB_Matrix_opaque T_header ;
137 GrB_Matrix T = GB_clear_static_header (&T_header) ;
138
139 GrB_Info info = GB_builder
140 (
141 T, // create T using a static header
142 dup->ztype, // T has the type determined by the dup operator
143 C->vlen, // T->vlen = C->vlen
144 C->vdim, // T->vdim = C->vdim
145 C->is_csc, // T has the same CSR/CSC format as C
146 &no_I_work, // I_work_handle, not used here
147 &I_work_size,
148 &no_J_work, // J_work_handle, not used here
149 &J_work_size,
150 &no_S_work, // S_work_handle, not used here
151 &S_work_size,
152 false, // known_sorted: not yet known
153 false, // known_no_duplicates: not yet known
154 0, // I_work, J_work, and S_work not used here
155 is_matrix, // true if T is a GrB_Matrix
156 (int64_t *) ((C->is_csc) ? I_input : J_input),
157 (int64_t *) ((C->is_csc) ? J_input : I_input),
158 (const GB_void *) S_input, // original values, each of size nvals
159 nvals, // number of tuples
160 dup, // operator to assemble duplicates
161 scode, // type of the S array
162 Context
163 ) ;
164
165 if (info != GrB_SUCCESS)
166 {
167 // out of memory
168 return (info) ;
169 }
170
171 //--------------------------------------------------------------------------
172 // transplant and typecast T into C, conform C, and free T
173 //--------------------------------------------------------------------------
174
175 ASSERT (GB_IS_HYPERSPARSE (T)) ;
176 ASSERT (!GB_ZOMBIES (T)) ;
177 ASSERT (!GB_JUMBLED (T)) ;
178 ASSERT (!GB_PENDING (T)) ;
179 return (GB_transplant_conform (C, C->type, &T, Context)) ;
180 }
181
182