From c8bae7493d2f2910b57f13ded012e86bdcfb0532 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 16:47:53 +0200 Subject: Adding upstream version 1:2.39.2. Signed-off-by: Daniel Baumann --- 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 0000000..1dfea76 --- /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.3