From 22d87333e5ee8871a9d42a15834ad91168a95928 Mon Sep 17 00:00:00 2001 From: Johannes Schindelin Date: Mon, 13 Aug 2018 04:33:00 -0700 Subject: linear-assignment: a function to solve least-cost assignment problems 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 Signed-off-by: Junio C Hamano --- linear-assignment.h | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) create mode 100644 linear-assignment.h (limited to 'linear-assignment.h') diff --git a/linear-assignment.h b/linear-assignment.h new file mode 100644 index 0000000000..1dfea76629 --- /dev/null +++ b/linear-assignment.h @@ -0,0 +1,22 @@ +#ifndef LINEAR_ASSIGNMENT_H +#define LINEAR_ASSIGNMENT_H + +/* + * 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 -- cgit v1.2.1