Re: [PATCH v4 01/21] linear-assignment: a function to solve least-cost assignment problems
On 07/21, Johannes Schindelin via GitGitGadget wrote:
Show 32 quoted lines
> From: Johannes Schindelin <johannes.schindelin@gmx.de>
>
> The problem solved by the code introduced in this commit goes like this:
> given two sets of items, and a cost matrix which says how much it
> "costs" to assign any given item of the first set to any given item of
> the second, assign all items (except when the sets have different size)
> in the cheapest way.
>
> We use the Jonker-Volgenant algorithm to solve the assignment problem 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 +
> linear-assignment.c | 201 ++++++++++++++++++++++++++++++++++++++++++++
> linear-assignment.h | 22 +++++
> 3 files changed, 224 insertions(+)
> create mode 100644 linear-assignment.c
> create mode 100644 linear-assignment.h
>
> [...]
>
> diff --git a/linear-assignment.h b/linear-assignment.h
> new file mode 100644
> index 000000000..fc4c502c8
> --- /dev/null
> +++ b/linear-assignment.h
> @@ -0,0 +1,22 @@
> +#ifndef HUNGARIAN_H
> +#define HUNGARIAN_H
nit: maybe s/HUNGARIAN/LINEAR_ASSIGNMENT/ in the two lines above.
Show 23 quoted lines
> +
> +/*
> + * Compute an assignment of columns -> rows (and vice versa) such that every
> + * column is assigned to at most one row (and vice versa) minimizing the
> + * overall cost.
> + *
> + * The parameter `cost` is the cost matrix: the cost to assign column j to row
> + * i is `cost[j + column_count * i].
> + *
> + * The arrays column2row and row2column will be populated with the respective
> + * assignments (-1 for unassigned, which can happen only if column_count !=
> + * row_count).
> + */
> +void compute_assignment(int column_count, int row_count, int *cost,
> + int *column2row, int *row2column);
> +
> +/* The maximal cost in the cost matrix (to prevent integer overflows). */
> +#define COST_MAX (1<<16)
> +
> +#endif
> --
> gitgitgadget
>
Thomas Gummerer <t.gummerer@gmail.com>