git.oblomov.eu Git - git/blob - linear-assignment.h

   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  */
  16 void 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