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;

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