8 pbqp_matrix *pbqp_matrix_alloc(pbqp *pbqp, unsigned rows, unsigned cols)
13 unsigned length = rows * cols;
15 pbqp_matrix *mat = obstack_alloc(&pbqp->obstack, sizeof(*mat) + sizeof(*mat->entries) * length);
20 memset(mat->entries, 0, sizeof(*mat->entries) * length);
25 pbqp_matrix *pbqp_matrix_copy(pbqp *pbqp, pbqp_matrix *m)
27 unsigned len = m->rows * m->cols;
28 pbqp_matrix *copy = obstack_copy(&pbqp->obstack, m, sizeof(*copy) + sizeof(*copy->entries) * len);
34 pbqp_matrix *pbqp_matrix_copy_and_transpose(pbqp *pbqp, pbqp_matrix *m)
38 unsigned cols = m->cols;
39 unsigned rows = m->rows;
40 unsigned len = rows * cols;
41 pbqp_matrix *copy = obstack_alloc(&pbqp->obstack, sizeof(*copy) + sizeof(*copy->entries) * len);
44 for (i = 0; i < rows; ++i) {
45 for (j = 0; j < cols; ++j) {
46 copy->entries[j*rows+i] = m->entries[i*cols+j];
56 void pbqp_matrix_transpose(pbqp *pbqp, pbqp_matrix *mat)
61 len = mat->rows * mat->cols;
63 pbqp_matrix *tmp = pbqp_matrix_copy_and_transpose(pbqp, mat);
65 memcpy(mat, tmp, sizeof(*mat) + sizeof(*mat->entries) * len);
67 obstack_free(&pbqp->obstack, tmp);
70 void pbqp_matrix_add(pbqp_matrix *sum, pbqp_matrix *summand)
77 assert(sum->cols == summand->cols);
78 assert(sum->rows == summand->rows);
80 len = sum->rows * sum->cols;
82 for (i = 0; i < len; ++i) {
83 sum->entries[i] = pbqp_add(sum->entries[i], summand->entries[i]);
87 void pbqp_matrix_set_col_value(pbqp_matrix *mat, unsigned col, num value)
93 assert(col < mat->cols);
97 for (row_index = 0; row_index < row_len; ++row_index) {
98 mat->entries[row_index * mat->cols + col] = value;
102 void pbqp_matrix_set_row_value(pbqp_matrix *mat, unsigned row, num value)
108 assert(row < mat->rows);
112 for (col_index = 0; col_index < col_len; ++col_index) {
113 mat->entries[row * mat->cols + col_index] = value;
117 void pbqp_matrix_set(pbqp_matrix *mat, unsigned row, unsigned col, num value)
120 assert(col < mat->cols);
121 assert(row < mat->rows);
123 mat->entries[row * mat->cols + col] = value;
126 num pbqp_matrix_get_col_min(pbqp_matrix *matrix, unsigned col_index, vector *flags)
133 assert(matrix->rows == flags->len);
135 unsigned col_len = matrix->cols;
136 unsigned row_len = matrix->rows;
138 for (row_index = 0; row_index < row_len; ++row_index) {
139 /* Ignore virtual deleted columns. */
140 if (flags->entries[row_index].data == INF_COSTS) continue;
142 num elem = matrix->entries[row_index * col_len + col_index];
152 unsigned pbqp_matrix_get_col_min_index(pbqp_matrix *matrix, unsigned col_index, vector *flags)
160 assert(matrix->rows == flags->len);
162 unsigned col_len = matrix->cols;
163 unsigned row_len = matrix->rows;
165 for (row_index = 0; row_index < row_len; ++row_index) {
166 /* Ignore virtual deleted columns. */
167 if (flags->entries[row_index].data == INF_COSTS) continue;
169 num elem = matrix->entries[row_index * col_len + col_index];
173 min_index = row_index;
180 void pbqp_matrix_sub_col_value(pbqp_matrix *matrix, unsigned col_index,
181 vector *flags, num value)
189 assert(matrix->rows == flags->len);
191 col_len = matrix->cols;
192 row_len = matrix->rows;
194 for (row_index = 0; row_index < row_len; ++row_index) {
195 if (flags->entries[row_index].data == INF_COSTS) {
196 matrix->entries[row_index * col_len + col_index] = 0;
199 /* inf - x = inf if x < inf */
200 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
203 matrix->entries[row_index * col_len + col_index] -= value;
207 num pbqp_matrix_get_row_min(pbqp_matrix *matrix, unsigned row_index, vector *flags)
214 assert(matrix->cols == flags->len);
216 unsigned len = flags->len;
218 for (col_index = 0; col_index < len; ++col_index) {
219 /* Ignore virtual deleted columns. */
220 if (flags->entries[col_index].data == INF_COSTS) continue;
222 num elem = matrix->entries[row_index * len + col_index];
232 unsigned pbqp_matrix_get_row_min_index(pbqp_matrix *matrix, unsigned row_index, vector *flags)
240 assert(matrix->cols == flags->len);
242 unsigned len = flags->len;
244 for (col_index = 0; col_index < len; ++col_index) {
245 /* Ignore virtual deleted columns. */
246 if (flags->entries[col_index].data == INF_COSTS) continue;
248 num elem = matrix->entries[row_index * len + col_index];
252 min_index = col_index;
259 void pbqp_matrix_sub_row_value(pbqp_matrix *matrix, unsigned row_index,
260 vector *flags, num value)
267 assert(matrix->cols == flags->len);
269 col_len = matrix->cols;
271 for (col_index = 0; col_index < col_len; ++col_index) {
272 if (flags->entries[col_index].data == INF_COSTS) {
273 matrix->entries[row_index * col_len + col_index] = 0;
276 /* inf - x = inf if x < inf */
277 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
280 matrix->entries[row_index * col_len + col_index] -= value;
284 int pbqp_matrix_is_zero(pbqp_matrix *mat, vector *src_vec, vector *tgt_vec)
294 assert(mat->cols = tgt_vec->len);
295 assert(mat->rows = src_vec->len);
300 for (row_index = 0; row_index < row_len; ++row_index) {
301 if (src_vec->entries[row_index].data == INF_COSTS) continue;
302 for (col_index = 0; col_index < col_len; ++col_index) {
303 if (tgt_vec->entries[col_index].data == INF_COSTS) continue;
305 if (mat->entries[row_index * col_len + col_index] != 0) {
314 void pbqp_matrix_add_to_all_cols(pbqp_matrix *mat, vector *vec)
323 assert(mat->rows == vec->len);
328 for (row_index = 0; row_index < row_len; ++row_index) {
329 num value = vec->entries[row_index].data;
330 for (col_index = 0; col_index < col_len; ++col_index) {
331 mat->entries[row_index * col_len + col_index] = pbqp_add(
332 mat->entries[row_index * col_len + col_index], value);
337 void pbqp_matrix_add_to_all_rows(pbqp_matrix *mat, vector *vec)
346 assert(mat->cols == vec->len);
351 for (row_index = 0; row_index < row_len; ++row_index) {
352 for (col_index = 0; col_index < col_len; ++col_index) {
353 num value = vec->entries[col_index].data;
355 mat->entries[row_index * col_len + col_index] = pbqp_add(mat->entries[row_index * col_len + col_index], value);