On 07/21, Johannes Schindelin via GitGitGadget wrote: > From: Johannes Schindelin <johannes.schindelin@xxxxxx> > > 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@xxxxxx> > --- > 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. > + > +/* > + * 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 >
