* The parameter `cost` is the cost matrix: the cost to assign column j to row * i is `cost[j + column_count * i]. */
| 13 | * i is `cost[j + column_count * i]. |
| 14 | */ |
| 15 | void compute_assignment(int column_count, int row_count, int *cost, |
| 16 | int *column2row, int *row2column) |
| 17 | { |
| 18 | int *v, *d; |
| 19 | int *free_row, free_count = 0, saved_free_count, *pred, *col; |
| 20 | int i, j, phase; |
| 21 | |
| 22 | if (column_count < 2) { |
| 23 | MEMZERO_ARRAY(column2row, column_count); |
| 24 | MEMZERO_ARRAY(row2column, row_count); |
| 25 | return; |
| 26 | } |
| 27 | |
| 28 | memset(column2row, -1, sizeof(int) * column_count); |
| 29 | memset(row2column, -1, sizeof(int) * row_count); |
| 30 | ALLOC_ARRAY(v, column_count); |
| 31 | |
| 32 | /* column reduction */ |
| 33 | for (j = column_count - 1; j >= 0; j--) { |
| 34 | int i1 = 0; |
| 35 | |
| 36 | for (i = 1; i < row_count; i++) |
| 37 | if (COST(j, i1) > COST(j, i)) |
| 38 | i1 = i; |
| 39 | v[j] = COST(j, i1); |
| 40 | if (row2column[i1] == -1) { |
| 41 | /* row i1 unassigned */ |
| 42 | row2column[i1] = j; |
| 43 | column2row[j] = i1; |
| 44 | } else { |
| 45 | if (row2column[i1] >= 0) |
| 46 | row2column[i1] = -2 - row2column[i1]; |
| 47 | column2row[j] = -1; |
| 48 | } |
| 49 | } |
| 50 | |
| 51 | /* reduction transfer */ |
| 52 | ALLOC_ARRAY(free_row, row_count); |
| 53 | for (i = 0; i < row_count; i++) { |
| 54 | int j1 = row2column[i]; |
| 55 | if (j1 == -1) |
| 56 | free_row[free_count++] = i; |
| 57 | else if (j1 < -1) |
| 58 | row2column[i] = -2 - j1; |
| 59 | else { |
| 60 | int min = COST(!j1, i) - v[!j1]; |
| 61 | for (j = 1; j < column_count; j++) |
| 62 | if (j != j1 && min > COST(j, i) - v[j]) |
| 63 | min = COST(j, i) - v[j]; |
| 64 | v[j1] -= min; |
| 65 | } |
| 66 | } |
| 67 | |
| 68 | if (free_count == |
| 69 | (column_count < row_count ? row_count - column_count : 0)) { |
| 70 | free(v); |
| 71 | free(free_row); |
| 72 | return; |
no outgoing calls
no test coverage detected