Hi Thomas, On Sat, 28 Jul 2018, Thomas Gummerer wrote: > 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. Makes sense. Ciao, Dscho > > > + > > +/* > > + * 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 > > >
