26 #include <utils/hungarian_method/hungarian.h>
32 #define INF (0x7FFFFFFF)
37 #define hungarian_test_alloc(X) \
39 if ((void *)(X) == NULL) \
40 fprintf(stderr, "Out of memory in %s, (%s, line %d).\n", __FUNCTION__, __FILE__, __LINE__); \
54 p = (hungarian_problem_t *)malloc(
sizeof(hungarian_problem_t));
76 std::cerr << std::endl;
77 for (i = 0; i < rows; i++) {
78 std::cerr <<
" " << i <<
"'th row [" << std::flush;
79 for (j = 0; j < cols; j++) {
80 std::cerr << C[i][j] <<
" ";
85 std::cerr <<
" ]" << std::endl << std::flush;
87 std::cerr << std::endl;
101 r = (
int **)calloc(rows,
sizeof(
int *));
102 for (i = 0; i < rows; i++) {
103 r[i] = (
int *)calloc(cols,
sizeof(
int));
104 for (j = 0; j < cols; j++)
105 r[i][j] = m[i * cols + j];
115 std::cerr <<
"HungarianMethod: == Assignment ==" << std::endl;
125 std::cerr <<
"HungarianMethod: == CostMatrix ==" << std::endl;
151 int i, j, org_cols, org_rows;
160 rows = std::max(cols, rows);
166 p->cost = (
int **)calloc(rows,
sizeof(
int *));
167 hungarian_test_alloc(
p->cost);
168 p->assignment = (
int **)calloc(rows,
sizeof(
int *));
169 hungarian_test_alloc(
p->assignment);
172 for (i = 0; i <
p->num_rows; i++) {
173 p->cost[i] = (
int *)calloc(cols,
sizeof(
int));
174 hungarian_test_alloc(
p->cost[i]);
175 p->assignment[i] = (
int *)calloc(cols,
sizeof(
int));
176 hungarian_test_alloc(
p->assignment[i]);
177 for (j = 0; j <
p->num_cols; j++) {
178 p->cost[i][j] = (i < org_rows && j < org_cols) ? cost_matrix[i][j] : 0;
179 p->assignment[i][j] = 0;
181 if (max_cost < p->cost[i][j])
182 max_cost =
p->cost[i][j];
186 if (mode == HUNGARIAN_MODE_MAXIMIZE_UTIL) {
187 for (i = 0; i <
p->num_rows; i++) {
188 for (j = 0; j <
p->num_cols; j++) {
189 p->cost[i][j] = max_cost -
p->cost[i][j];
192 }
else if (mode == HUNGARIAN_MODE_MINIMIZE_COST) {
196 "%s: unknown mode. Mode was set to HUNGARIAN_MODE_MINIMIZE_COST !\n",
203 col_mates_ = (
int *)calloc(cols,
sizeof(
int));
204 hungarian_test_alloc(col_mates_);
205 for (
int j = 0; j < num_cols_; ++j) {
210 row_mates_ = (
int *)calloc(rows,
sizeof(
int));
211 hungarian_test_alloc(row_mates_);
212 for (
int i = 0; i < num_rows_; ++i) {
227 for (i = 0; i <
p->num_rows; i++) {
234 p->assignment = NULL;
250 int i, j, m, n, k, l, s, t, q, unmatched, cost;
264 col_mate = (
int *)calloc(
p->num_rows,
sizeof(
int));
265 hungarian_test_alloc(col_mate);
266 unchosen_row = (
int *)calloc(
p->num_rows,
sizeof(
int));
267 hungarian_test_alloc(unchosen_row);
268 row_dec = (
int *)calloc(
p->num_rows,
sizeof(
int));
269 hungarian_test_alloc(row_dec);
270 slack_row = (
int *)calloc(
p->num_rows,
sizeof(
int));
271 hungarian_test_alloc(slack_row);
273 row_mate = (
int *)calloc(
p->num_cols,
sizeof(
int));
274 hungarian_test_alloc(row_mate);
275 parent_row = (
int *)calloc(
p->num_cols,
sizeof(
int));
276 hungarian_test_alloc(parent_row);
277 col_inc = (
int *)calloc(
p->num_cols,
sizeof(
int));
278 hungarian_test_alloc(col_inc);
279 slack = (
int *)calloc(
p->num_cols,
sizeof(
int));
280 hungarian_test_alloc(slack);
282 for (i = 0; i <
p->num_rows; i++) {
288 for (j = 0; j <
p->num_cols; j++) {
295 for (i = 0; i <
p->num_rows; ++i)
296 for (j = 0; j <
p->num_cols; ++j)
297 p->assignment[i][j] = HUNGARIAN_NOT_ASSIGNED;
301 fprintf(stderr,
"Using heuristic\n");
302 for (l = 0; l < n; l++) {
304 for (k = 1; k < m; k++)
305 if (
p->cost[k][l] < s)
309 for (k = 0; k < m; k++)
316 for (l = 0; l < n; l++) {
322 for (k = 0; k < m; k++) {
324 for (l = 1; l < n; l++)
325 if (
p->cost[k][l] < s)
328 for (l = 0; l < n; l++)
329 if (s ==
p->cost[k][l] && row_mate[l] < 0) {
333 fprintf(stderr,
"matching col %d==row %d\n", l, k);
338 fprintf(stderr,
"node %d: unmatched row %d\n", t, k);
339 unchosen_row[t++] = k;
350 fprintf(stderr,
"Matched %d rows.\n", m - t);
358 for (l = 0; l < n; l++)
361 del =
p->cost[k][l] - s + col_inc[l];
362 if (del < slack[l]) {
369 fprintf(stderr,
"node %d: row %d==col %d--row %d\n", t, row_mate[l], l, k);
370 unchosen_row[t++] = row_mate[l];
384 for (l = 0; l < n; l++)
385 if (slack[l] && slack[l] < s)
387 for (q = 0; q < t; q++)
388 row_dec[unchosen_row[q]] += s;
389 for (l = 0; l < n; l++)
397 stderr,
"Decreasing uncovered elements by %d produces zero at [%d,%d]\n", s, k, l);
398 if (row_mate[l] < 0) {
399 for (j = l + 1; j < n; j++)
406 fprintf(stderr,
"node %d: row %d==col %d--row %d\n", t, row_mate[l], l, k);
407 unchosen_row[t++] = row_mate[l];
418 fprintf(stderr,
"Breakthrough at node %d of %d!\n", q, t);
424 fprintf(stderr,
"rematching col %d==row %d\n", l, k);
431 if (--unmatched == 0)
435 for (l = 0; l < n; l++) {
439 for (k = 0; k < m; k++)
440 if (col_mate[k] < 0) {
442 fprintf(stderr,
"node %d: unmatched row %d\n", t, k);
443 unchosen_row[t++] = k;
450 for (k = 0; k < m; k++)
451 for (l = 0; l < n; l++)
452 if (
p->cost[k][l] < row_dec[k] - col_inc[l]) {
453 printf(
"boom1: p->cost[%i][%i]=%i < row_dec[%i]-col_inc[%i]=%i\n",
459 row_dec[k] - col_inc[l]);
462 for (k = 0; k < m; k++) {
464 if (l < 0 || p->cost[k][l] != row_dec[k] - col_inc[l]) {
465 printf(
"boom2: %i<0 || p->cost[%i][%i]=%i != row_dec[%i]-col_inc[%i]=%i\n",
472 row_dec[k] - col_inc[l]);
477 for (l = 0; l < n; l++)
481 printf(
"boom3: %i > %i\n", k, m);
487 for (i = 0; i < m; ++i) {
488 p->assignment[i][col_mate[i]] = HUNGARIAN_ASSIGNED;
491 for (k = 0; k < m; ++k) {
492 for (l = 0; l < n; ++l) {
494 p->cost[k][l] =
p->cost[k][l] - row_dec[k] + col_inc[l];
498 for (i = 0; i < m; i++)
500 for (i = 0; i < n; i++)
503 fprintf(stderr,
"Cost is %d\n", cost);
508 for (
int i = 0; i < num_rows_; ++i) {
509 row_mates_[i] = row_mate[i];
511 for (
int j = 0; j < num_cols_; ++j) {
512 col_mates_[j] = col_mate[j];
536 if (col < num_cols_) {
537 return (
int)col_mates_[col];
550 if (row < num_rows_) {
551 return (
int)row_mates_[row];
void print_cost_matrix()
Print the cost matrix.
~HungarianMethod()
Destructor.
void free()
Free space alloacted by method.
int get_row_assignment(const int &row)
Get row assignment.
void print_assignment()
Print the assignment matrix.
void print_matrix(int **C, int rows, int cols)
Print matrix to stdout.
void print_status()
Print the current status.
hungarian_problem_t * p
our problem instance member.
int get_column_assignment(const int &col)
Get column assignment.
HungarianMethod()
Constructor.
int * get_assignment(int &size)
Get assignment and size.
int init(int **cost_matrix, int rows, int cols, int mode)
Initialize hungarian method.
int ** array_to_matrix(int *m, int rows, int cols)
Convert an array to a matrix.
bool is_available()
Check if data is available.
void solve()
Solve the assignment problem.
Fawkes library namespace.