]> git.ipfire.org Git - thirdparty/git.git/blame - linear-assignment.h
git-submodule.sh: shorten submodule SHA-1s using rev-parse
[thirdparty/git.git] / linear-assignment.h
CommitLineData
22d87333
JS
1#ifndef LINEAR_ASSIGNMENT_H
2#define LINEAR_ASSIGNMENT_H
3
4/*
5 * Compute an assignment of columns -> rows (and vice versa) such that every
6 * column is assigned to at most one row (and vice versa) minimizing the
7 * overall cost.
8 *
9 * The parameter `cost` is the cost matrix: the cost to assign column j to row
10 * i is `cost[j + column_count * i].
11 *
12 * The arrays column2row and row2column will be populated with the respective
13 * assignments (-1 for unassigned, which can happen only if column_count !=
14 * row_count).
15 */
16void compute_assignment(int column_count, int row_count, int *cost,
17 int *column2row, int *row2column);
18
19/* The maximal cost in the cost matrix (to prevent integer overflows). */
20#define COST_MAX (1<<16)
21
22#endif