> 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);
> +}
