Re: [PATCH v2 01/18] Add a function to solve least-cost assignment problems

From: SZEDER Gábor <szeder.dev@gmail.com>
Date: May 30, 2018, 13:55 UTC
Message-ID: <20180530135505.9569-1-szeder.dev@gmail.com>
In-Reply-To: <3f51970cbc44bfe34133c48c0844ed3723e83808.1525448066.git.johannes.schindelin@gmx.de>

Show 10 quoted lines

> The Jonker-Volgenant algorithm was implemented to answer questions such
> as: given two different versions of a topic branch (or iterations of a
> patch series), what is the best pairing of commits/patches between the
> different versions?
> 
> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
> ---
>  Makefile    |   1 +
>  hungarian.c | 205 ++++++++++++++++++++++++++++++++++++++++++++++++++++
>  hungarian.h |  19 +++++

(Nit: I personally don't really like these filenames, I know they will surprise and distract me every time I notice them for years to come... :)

Show 6 quoted lines

> +int compute_assignment(int column_count, int row_count, double *cost,
> +		       int *column2row, int *row2column)
> +{
> +	double *v = xmalloc(sizeof(double) * column_count), *d;
> +	int *free_row, free_count = 0, saved_free_count, *pred, *col;
> +	int i, j, phase;

<snip>

> +	for (free_count = 0; free_count < saved_free_count; free_count++) {
> +		int i1 = free_row[free_count], low = 0, up = 0, last, k;
> +		double min, c, u1;

<snip most of the loop's body>

Show 9 quoted lines

> +		/* 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 to replace the last three lines above with:

  SWAP(j, row2column[i]);

I think it's right, using the SWAP macro makes the resulting code not only shorter and clearer, but it also saves the reader from thinking about whether it's important to set 'k = j' (I think it's not), or 'k' is just used here in lieu of a dedicated 'tmp' variable (I think it is).

> +		} while (i1 != i);
> +	}
> +