From c71967c1e5b8741165b6b266e8f943ba75044a64 Mon Sep 17 00:00:00 2001 From: Sebastian Buchwald Date: Fri, 23 Jan 2009 15:02:44 +0000 Subject: [PATCH] Added functions to get the index of the minimum element of a pbqp matrix row/column. [r25356] --- matrix.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ matrix.h | 3 +++ 2 files changed, 58 insertions(+) diff --git a/matrix.c b/matrix.c index b7016af0e..5dc33b657 100644 --- a/matrix.c +++ b/matrix.c @@ -149,6 +149,34 @@ num pbqp_matrix_get_col_min(pbqp_matrix *matrix, unsigned col_index, vector *fla return min; } +unsigned pbqp_matrix_get_col_min_index(pbqp_matrix *matrix, unsigned col_index, vector *flags) +{ + unsigned row_index; + unsigned min_index; + num min = INF_COSTS; + + assert(matrix); + assert(flags); + assert(matrix->rows == flags->len); + + unsigned col_len = matrix->cols; + unsigned row_len = matrix->rows; + + for (row_index = 0; row_index < row_len; ++row_index) { + /* Ignore virtual deleted columns. */ + if (flags->entries[row_index].data == INF_COSTS) continue; + + num elem = matrix->entries[row_index * col_len + col_index]; + + if (elem < min) { + min = elem; + min_index = row_index; + } + } + + return min_index; +} + void pbqp_matrix_sub_col_value(pbqp_matrix *matrix, unsigned col_index, vector *flags, num value) { @@ -201,6 +229,33 @@ num pbqp_matrix_get_row_min(pbqp_matrix *matrix, unsigned row_index, vector *fla return min; } +unsigned pbqp_matrix_get_row_min_index(pbqp_matrix *matrix, unsigned row_index, vector *flags) +{ + unsigned col_index; + unsigned min_index; + num min = INF_COSTS; + + assert(matrix); + assert(flags); + assert(matrix->cols == flags->len); + + unsigned len = flags->len; + + for (col_index = 0; col_index < len; ++col_index) { + /* Ignore virtual deleted columns. */ + if (flags->entries[col_index].data == INF_COSTS) continue; + + num elem = matrix->entries[row_index * len + col_index]; + + if (elem < min) { + min = elem; + min_index = col_index; + } + } + + return min_index; +} + void pbqp_matrix_sub_row_value(pbqp_matrix *matrix, unsigned row_index, vector *flags, num value) { diff --git a/matrix.h b/matrix.h index aa19ae165..fb9dcf4d6 100644 --- a/matrix.h +++ b/matrix.h @@ -20,6 +20,9 @@ void pbqp_matrix_set(pbqp_matrix *mat, unsigned row, unsigned col, num value); num pbqp_matrix_get_col_min(pbqp_matrix *matrix, unsigned col_index, vector *flags); num pbqp_matrix_get_row_min(pbqp_matrix *matrix, unsigned row_index, vector *flags); +unsigned pbqp_matrix_get_col_min_index(pbqp_matrix *matrix, unsigned col_index, vector *flags); +unsigned pbqp_matrix_get_row_min_index(pbqp_matrix *matrix, unsigned row_index, vector *flags); + void pbqp_matrix_set_col_value(pbqp_matrix *mat, unsigned col, num value); void pbqp_matrix_set_row_value(pbqp_matrix *mat, unsigned row, num value); -- 2.20.1