Hi Gábor,
On Wed, 11 Jul 2018, SZEDER Gábor wrote:
> > 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.
Good point.
I audited the rest of the code in this file, and there are no more swap
operations.
Thanks,
Dscho
