# Re: [PATCH v3 01/20] linear-assignment: a function to solve least-cost assignment problems

```> diff --git a/linear-assignment.c b/linear-assignment.c
> new file mode 100644
> index 000000000..0b0344b5f
> --- /dev/null
> +++ b/linear-assignment.c
> @@ -0,0 +1,203 @@
> +/*
> + * Based on: Jonker, R., & Volgenant, A. (1987). <i>A shortest augmenting
> path
> + * algorithm for dense and sparse linear assignment problems</i>. Computing,
> + * 38(4), 325-340.
> + */
> +#include "cache.h"
> +#include "linear-assignment.h"
> +
> +#define COST(column, row) cost[(column) + column_count * (row)]
> +
> +/*
> + * The parameter `cost` is the cost matrix: the cost to assign column j to
> row
> + * i is `cost[j + column_count * i].
> + */
> +void compute_assignment(int column_count, int row_count, int *cost,
> +                     int *column2row, int *row2column)
> +{```
```
[...]

> +update:
> +             /* updating of the column pieces */
> +             for (k = 0; k < last; k++) {
> +                     int j1 = col[k];
> +                     v[j1] += d[j1] - min;
> +             }
> +
> +             /* augmentation */
> +             do {
> +                     if (j < 0)
> +                             BUG("negative j: %d", j);
> +                     i = pred[j];
> +                     column2row[j] = i;
> +                     k = j;
> +                     j = row2column[i];
> +                     row2column[i] = k;

Coccinelle suggests using SWAP(j, row2column[i]) instead of the last
three lines above.
It's more idiomatic, and it avoids (ab)using the 'k' variable
(elsewhere used as loop variable) as a temporary variable.

> +             } while (i1 != i);
> +     }
> +
> +     free(col);
> +     free(pred);
> +     free(d);
> +     free(v);
> +     free(free_row);
> +}
```