hungarian.c 11.2 KB
 Christian Würdig committed Sep 13, 2006 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ``````/******************************************************************** ******************************************************************** ** ** libhungarian by Cyrill Stachniss, 2004 ** ** Added and adapted to libFirm by Christian Wuerdig, 2006 ** ** Solving the Minimum Assignment Problem using the ** Hungarian Method. ** ** ** This file may be freely copied and distributed! ** ** ** Parts of the used code was originally provided by the ** "Stanford GraphGase", but I made changes to this code. ** As asked by the copyright node of the "Stanford GraphGase", ** I hereby proclaim that this file are *NOT* part of the ** "Stanford GraphGase" distrubition! ** ** This file is distributed in the hope that it will be useful, ** but WITHOUT ANY WARRANTY; without even the implied ** warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR ** PURPOSE. ** ******************************************************************** ********************************************************************/ `````` 27 28 29 30 ``````/** * @file * @brief Solving the Minimum Assignment Problem using the Hungarian Method. */ `````` Matthias Braun committed Oct 11, 2008 31 ``````#include "config.h" `````` Matthias Braun committed Dec 10, 2006 32 `````` `````` Christian Würdig committed Sep 13, 2006 33 34 35 36 ``````#include #include #include `````` Matthias Braun committed Oct 20, 2011 37 ``````#include "util.h" `````` Christian Würdig committed Sep 13, 2006 38 39 ``````#include "xmalloc.h" #include "debug.h" `````` Christian Würdig committed Sep 13, 2006 40 ``````#include "bitset.h" `````` Matthias Braun committed Jul 26, 2010 41 ``````#include "error.h" `````` Christian Würdig committed Sep 13, 2006 42 43 44 `````` #include "hungarian.h" `````` yb9976 committed Sep 15, 2011 45 ``````DEBUG_ONLY(static firm_dbg_module_t *dbg;) `````` Matthias Braun committed Aug 09, 2010 46 `````` `````` Matthias Braun committed Jul 26, 2010 47 ``````struct hungarian_problem_t { `````` Matthias Braun committed Aug 09, 2010 48 49 50 51 52 53 54 55 56 `````` unsigned num_rows; /**< number of rows */ unsigned num_cols; /**< number of columns */ unsigned *cost; /**< the cost matrix */ unsigned max_cost; /**< the maximal costs in the matrix */ match_type_t match_type; /**< PERFECT or NORMAL matching */ unsigned *missing_left; /**< bitset: left side nodes having no edge to the right side */ unsigned *missing_right; /**< bitset: right side nodes having no edge to the left side */ `````` Christian Würdig committed Sep 13, 2006 57 58 ``````}; `````` Matthias Braun committed Aug 09, 2010 59 60 ``````static void hungarian_dump_f(FILE *f, const unsigned *cost, unsigned num_rows, unsigned num_cols, int width) `````` Christoph Mallon committed Feb 13, 2010 61 ``````{ `````` Matthias Braun committed Aug 09, 2010 62 `````` unsigned r, c; `````` Christian Würdig committed Sep 13, 2006 63 64 `````` fprintf(f , "\n"); `````` Matthias Braun committed Aug 09, 2010 65 `````` for (r = 0; r < num_rows; r++) { `````` Christian Würdig committed Sep 13, 2006 66 `````` fprintf(f, " ["); `````` Matthias Braun committed Aug 09, 2010 67 68 `````` for (c = 0; c < num_cols; c++) { fprintf(f, "%*u", width, cost[r*num_cols + c]); `````` Christian Würdig committed Sep 13, 2006 69 70 71 72 73 74 `````` } fprintf(f, "]\n"); } fprintf(f, "\n"); } `````` Christoph Mallon committed Feb 13, 2010 75 76 ``````void hungarian_print_cost_matrix(hungarian_problem_t *p, int width) { `````` Matthias Braun committed Mar 02, 2009 77 `````` hungarian_dump_f(stderr, p->cost, p->num_rows, p->num_cols, width); `````` Christian Würdig committed Sep 13, 2006 78 79 ``````} `````` Matthias Braun committed Aug 09, 2010 80 ``````hungarian_problem_t *hungarian_new(unsigned num_rows, unsigned num_cols, `````` Matthias Braun committed Jul 26, 2010 81 `````` match_type_t match_type) `````` Christoph Mallon committed Feb 13, 2010 82 ``````{ `````` 83 `````` hungarian_problem_t *p = XMALLOCZ(hungarian_problem_t); `````` Christian Würdig committed Sep 13, 2006 84 `````` `````` Matthias Braun committed Aug 09, 2010 85 `````` FIRM_DBG_REGISTER(dbg, "firm.hungarian"); `````` Christian Würdig committed Sep 13, 2006 86 87 88 89 90 `````` /* Is the number of cols not equal to number of rows ? If yes, expand with 0 - cols / 0 - cols */ `````` Matthias Braun committed Aug 09, 2010 91 92 `````` num_rows = MAX(num_cols, num_rows); num_cols = num_rows; `````` Christian Würdig committed Sep 13, 2006 93 `````` `````` Matthias Braun committed Aug 09, 2010 94 95 `````` p->num_rows = num_rows; p->num_cols = num_cols; `````` Christian Würdig committed Sep 13, 2006 96 97 98 99 100 101 102 103 `````` p->match_type = match_type; /* In case of normal matching, we have to keep track of nodes without edges to kill them in the assignment later. */ if (match_type == HUNGARIAN_MATCH_NORMAL) { `````` Matthias Braun committed Aug 09, 2010 104 105 106 107 `````` p->missing_left = rbitset_malloc(num_rows); p->missing_right = rbitset_malloc(num_cols); rbitset_set_all(p->missing_left, num_rows); rbitset_set_all(p->missing_right, num_cols); `````` Christian Würdig committed Sep 13, 2006 108 `````` } `````` Christian Würdig committed Sep 13, 2006 109 110 `````` /* allocate space for cost matrix */ `````` Matthias Braun committed Aug 09, 2010 111 `````` p->cost = XMALLOCNZ(unsigned, num_rows * num_cols); `````` Christian Würdig committed Sep 13, 2006 112 113 114 `````` return p; } `````` Matthias Braun committed Jul 26, 2010 115 116 ``````void hungarian_prepare_cost_matrix(hungarian_problem_t *p, hungarian_mode_t mode) `````` Christoph Mallon committed Feb 13, 2010 117 ``````{ `````` Christian Würdig committed Sep 13, 2006 118 `````` if (mode == HUNGARIAN_MODE_MAXIMIZE_UTIL) { `````` Matthias Braun committed Aug 09, 2010 119 120 121 122 `````` unsigned r, c; unsigned num_cols = p->num_cols; unsigned *cost = p->cost; unsigned max_cost = p->max_cost; `````` Matthias Braun committed Jul 26, 2010 123 124 `````` for (r = 0; r < p->num_rows; r++) { for (c = 0; c < p->num_cols; c++) { `````` Matthias Braun committed Aug 09, 2010 125 `````` cost[r*num_cols + c] = max_cost - cost[r*num_cols + c]; `````` Christian Würdig committed Sep 13, 2006 126 127 `````` } } `````` Matthias Braun committed Jul 26, 2010 128 `````` } else if (mode == HUNGARIAN_MODE_MINIMIZE_COST) { `````` Christian Würdig committed Sep 13, 2006 129 `````` /* nothing to do */ `````` Matthias Braun committed Jul 26, 2010 130 `````` } else { `````` Christoph Mallon committed Jul 19, 2012 131 `````` panic("Unknown hungarian problem mode"); `````` Christian Würdig committed Sep 13, 2006 132 133 134 `````` } } `````` Matthias Braun committed Jul 26, 2010 135 ``````void hungarian_add(hungarian_problem_t *p, unsigned left, unsigned right, `````` Matthias Braun committed Aug 09, 2010 136 `````` unsigned cost) `````` Christoph Mallon committed Feb 13, 2010 137 ``````{ `````` Christian Würdig committed Sep 13, 2006 138 139 140 `````` assert(p->num_rows > left && "Invalid row selected."); assert(p->num_cols > right && "Invalid column selected."); `````` Matthias Braun committed Aug 09, 2010 141 142 `````` p->cost[left*p->num_cols + right] = cost; p->max_cost = MAX(p->max_cost, cost); `````` Christian Würdig committed Sep 13, 2006 143 144 `````` if (p->match_type == HUNGARIAN_MATCH_NORMAL) { `````` Matthias Braun committed Aug 09, 2010 145 146 `````` rbitset_clear(p->missing_left, left); rbitset_clear(p->missing_right, right); `````` Christian Würdig committed Sep 13, 2006 147 `````` } `````` Christian Würdig committed Sep 13, 2006 148 149 ``````} `````` Matthias Braun committed Jul 26, 2010 150 ``````void hungarian_remove(hungarian_problem_t *p, unsigned left, unsigned right) `````` Christoph Mallon committed Feb 13, 2010 151 ``````{ `````` Christian Würdig committed Sep 13, 2006 152 153 154 `````` assert(p->num_rows > left && "Invalid row selected."); assert(p->num_cols > right && "Invalid column selected."); `````` Matthias Braun committed Aug 09, 2010 155 `````` p->cost[left*p->num_cols + right] = 0; `````` Christian Würdig committed Sep 13, 2006 156 157 `````` if (p->match_type == HUNGARIAN_MATCH_NORMAL) { `````` Matthias Braun committed Aug 09, 2010 158 159 `````` rbitset_set(p->missing_left, left); rbitset_set(p->missing_right, right); `````` Christian Würdig committed Sep 13, 2006 160 `````` } `````` Christian Würdig committed Sep 13, 2006 161 162 ``````} `````` Christoph Mallon committed Feb 13, 2010 163 164 ``````void hungarian_free(hungarian_problem_t* p) { `````` Matthias Braun committed Aug 09, 2010 165 166 167 `````` xfree(p->missing_left); xfree(p->missing_right); xfree(p->cost); `````` Christian Würdig committed Sep 13, 2006 168 169 170 `````` xfree(p); } `````` Matthias Braun committed Jul 26, 2010 171 ``````int hungarian_solve(hungarian_problem_t* p, unsigned *assignment, `````` Matthias Braun committed Aug 09, 2010 172 `````` unsigned *final_cost, unsigned cost_threshold) `````` Christoph Mallon committed Feb 13, 2010 173 ``````{ `````` Matthias Braun committed Aug 09, 2010 174 175 176 177 178 179 180 181 182 183 184 185 `````` unsigned res_cost = 0; unsigned num_rows = p->num_rows; unsigned num_cols = p->num_cols; unsigned *cost = p->cost; unsigned *col_mate = XMALLOCNZ(unsigned, num_rows); unsigned *row_mate = XMALLOCNZ(unsigned, num_cols); unsigned *parent_row = XMALLOCNZ(unsigned, num_cols); unsigned *unchosen_row = XMALLOCNZ(unsigned, num_rows); int *row_dec = XMALLOCNZ(int, num_rows); int *col_inc = XMALLOCNZ(int, num_cols); int *slack = XMALLOCNZ(int, num_cols); unsigned *slack_row = XMALLOCNZ(unsigned, num_rows); `````` Matthias Braun committed Jul 26, 2010 186 187 188 189 190 191 `````` unsigned r; unsigned c; unsigned t; unsigned unmatched; memset(assignment, -1, num_rows * sizeof(assignment[0])); `````` Christian Würdig committed Sep 13, 2006 192 193 `````` /* Begin subtract column minima in order to start with lots of zeros 12 */ `````` Matthias Braun committed Aug 09, 2010 194 `````` DBG((dbg, LEVEL_1, "Using heuristic\n")); `````` Christian Würdig committed Sep 13, 2006 195 `````` `````` Matthias Braun committed Jul 26, 2010 196 `````` for (c = 0; c < num_cols; ++c) { `````` Matthias Braun committed Aug 09, 2010 197 `````` unsigned col_mininum = cost[0*num_cols + c]; `````` Christian Würdig committed Sep 13, 2006 198 `````` `````` Matthias Braun committed Jul 26, 2010 199 `````` for (r = 1; r < num_rows; ++r) { `````` Matthias Braun committed Aug 09, 2010 200 201 `````` if (cost[r*num_cols + c] < col_mininum) col_mininum = cost[r*num_cols + c]; `````` Christian Würdig committed Sep 13, 2006 202 203 `````` } `````` Matthias Braun committed Aug 09, 2010 204 `````` if (col_mininum == 0) `````` Matthias Braun committed Jul 26, 2010 205 `````` continue; `````` Christian Würdig committed Sep 13, 2006 206 `````` `````` Matthias Braun committed Aug 09, 2010 207 `````` res_cost += col_mininum; `````` Matthias Braun committed Jul 26, 2010 208 `````` for (r = 0; r < num_rows; ++r) `````` Matthias Braun committed Aug 09, 2010 209 `````` cost[r*num_cols + c] -= col_mininum; `````` Christian Würdig committed Sep 13, 2006 210 211 212 213 `````` } /* End subtract column minima in order to start with lots of zeros 12 */ /* Begin initial state 16 */ `````` Matthias Braun committed Aug 09, 2010 214 `````` unmatched = 0; `````` Matthias Braun committed Jul 26, 2010 215 216 217 218 219 `````` for (c = 0; c < num_cols; ++c) { row_mate[c] = (unsigned) -1; parent_row[c] = (unsigned) -1; col_inc[c] = 0; slack[c] = INT_MAX; `````` Christian Würdig committed Sep 13, 2006 220 221 `````` } `````` Matthias Braun committed Jul 26, 2010 222 `````` for (r = 0; r < num_rows; ++r) { `````` Matthias Braun committed Aug 09, 2010 223 `````` unsigned row_minimum = cost[r*num_cols + 0]; `````` Christian Würdig committed Sep 13, 2006 224 `````` `````` Matthias Braun committed Jul 26, 2010 225 `````` for (c = 1; c < num_cols; ++c) { `````` Matthias Braun committed Aug 09, 2010 226 227 `````` if (cost[r*num_cols + c] < row_minimum) row_minimum = cost[r*num_cols + c]; `````` Christian Würdig committed Sep 13, 2006 228 229 `````` } `````` Matthias Braun committed Aug 09, 2010 230 `````` row_dec[r] = row_minimum; `````` Christian Würdig committed Sep 13, 2006 231 `````` `````` Matthias Braun committed Jul 26, 2010 232 `````` for (c = 0; c < num_cols; ++c) { `````` Matthias Braun committed Aug 09, 2010 233 234 235 236 237 238 239 240 241 `````` if (cost[r*num_cols + c] != row_minimum) continue; if (row_mate[c] != (unsigned)-1) continue; col_mate[r] = c; row_mate[c] = r; DBG((dbg, LEVEL_1, "matching col %u == row %u\n", c, r)); goto row_done; `````` Christian Würdig committed Sep 13, 2006 242 243 `````` } `````` Matthias Braun committed Jul 26, 2010 244 `````` col_mate[r] = (unsigned)-1; `````` Matthias Braun committed Aug 09, 2010 245 246 `````` DBG((dbg, LEVEL_1, "node %u: unmatched row %u\n", unmatched, r)); unchosen_row[unmatched++] = r; `````` Christian Würdig committed Sep 13, 2006 247 248 249 250 251 ``````row_done: ; } /* End initial state 16 */ /* Begin Hungarian algorithm 18 */ `````` Matthias Braun committed Aug 09, 2010 252 `````` if (unmatched == 0) `````` Christian Würdig committed Sep 13, 2006 253 254 `````` goto done; `````` Matthias Braun committed Aug 09, 2010 255 `````` t = unmatched; `````` Christoph Mallon committed Feb 13, 2010 256 `````` for (;;) { `````` Matthias Braun committed Jul 26, 2010 257 258 `````` unsigned q = 0; unsigned j; `````` Matthias Braun committed Aug 09, 2010 259 `````` DBG((dbg, LEVEL_1, "Matched %u rows.\n", num_rows - t)); `````` Christian Würdig committed Sep 13, 2006 260 `````` `````` Christoph Mallon committed Feb 13, 2010 261 `````` for (;;) { `````` Matthias Braun committed Jul 26, 2010 262 `````` int s; `````` Christian Würdig committed Sep 13, 2006 263 264 `````` while (q < t) { /* Begin explore node q of the forest 19 */ `````` Matthias Braun committed Jul 26, 2010 265 266 `````` r = unchosen_row[q]; s = row_dec[r]; `````` Christian Würdig committed Sep 13, 2006 267 `````` `````` Matthias Braun committed Jul 26, 2010 268 269 `````` for (c = 0; c < num_cols; ++c) { if (slack[c]) { `````` Matthias Braun committed Aug 09, 2010 270 `````` int del = cost[r*num_cols + c] - s + col_inc[c]; `````` Christian Würdig committed Sep 13, 2006 271 `````` `````` Matthias Braun committed Jul 26, 2010 272 `````` if (del < slack[c]) { `````` Christian Würdig committed Sep 13, 2006 273 `````` if (del == 0) { `````` Matthias Braun committed Jul 26, 2010 274 `````` if (row_mate[c] == (unsigned)-1) `````` Christian Würdig committed Sep 13, 2006 275 276 `````` goto breakthru; `````` Matthias Braun committed Jul 26, 2010 277 278 `````` slack[c] = 0; parent_row[c] = r; `````` Matthias Braun committed Aug 09, 2010 279 `````` DBG((dbg, LEVEL_1, "node %u: row %u == col %u -- row %u\n", t, row_mate[c], c, r)); `````` Matthias Braun committed Jul 26, 2010 280 281 282 283 `````` unchosen_row[t++] = row_mate[c]; } else { slack[c] = del; slack_row[c] = r; `````` Christian Würdig committed Sep 13, 2006 284 285 286 287 288 289 290 291 292 `````` } } } } /* End explore node q of the forest 19 */ q++; } /* Begin introduce a new zero into the matrix 21 */ `````` Matthias Braun committed Jul 26, 2010 293 294 295 296 `````` s = INT_MAX; for (c = 0; c < num_cols; ++c) { if (slack[c] && slack[c] < s) s = slack[c]; `````` Christian Würdig committed Sep 13, 2006 297 298 299 300 301 `````` } for (q = 0; q < t; ++q) row_dec[unchosen_row[q]] += s; `````` Matthias Braun committed Jul 26, 2010 302 303 304 305 `````` for (c = 0; c < num_cols; ++c) { if (slack[c]) { slack[c] -= s; if (slack[c] == 0) { `````` Christian Würdig committed Sep 13, 2006 306 `````` /* Begin look at a new zero 22 */ `````` Matthias Braun committed Jul 26, 2010 307 `````` r = slack_row[c]; `````` Matthias Braun committed Aug 09, 2010 308 `````` DBG((dbg, LEVEL_1, "Decreasing uncovered elements by %d produces zero at [%u, %u]\n", s, r, c)); `````` Matthias Braun committed Jul 26, 2010 309 310 `````` if (row_mate[c] == (unsigned)-1) { for (j = c + 1; j < num_cols; ++j) { `````` Christian Würdig committed Sep 13, 2006 311 312 313 314 `````` if (slack[j] == 0) col_inc[j] += s; } goto breakthru; `````` Matthias Braun committed Jul 26, 2010 315 316 `````` } else { parent_row[c] = r; `````` Matthias Braun committed Aug 09, 2010 317 `````` DBG((dbg, LEVEL_1, "node %u: row %u == col %u -- row %u\n", t, row_mate[c], c, r)); `````` Matthias Braun committed Jul 26, 2010 318 `````` unchosen_row[t++] = row_mate[c]; `````` Christian Würdig committed Sep 13, 2006 319 320 321 `````` } /* End look at a new zero 22 */ } `````` Matthias Braun committed Jul 26, 2010 322 323 `````` } else { col_inc[c] += s; `````` Christian Würdig committed Sep 13, 2006 324 325 326 327 328 329 `````` } } /* End introduce a new zero into the matrix 21 */ } breakthru: /* Begin update the matching 20 */ `````` Matthias Braun committed Aug 09, 2010 330 `````` DBG((dbg, LEVEL_1, "Breakthrough at node %u of %u.\n", q, t)); `````` Christoph Mallon committed Feb 13, 2010 331 `````` for (;;) { `````` Matthias Braun committed Jul 26, 2010 332 333 334 `````` j = col_mate[r]; col_mate[r] = c; row_mate[c] = r; `````` Christian Würdig committed Sep 13, 2006 335 `````` `````` Matthias Braun committed Aug 09, 2010 336 `````` DBG((dbg, LEVEL_1, "rematching col %u == row %u\n", c, r)); `````` Matthias Braun committed Jul 26, 2010 337 `````` if (j == (unsigned)-1) `````` Christian Würdig committed Sep 13, 2006 338 339 `````` break; `````` Matthias Braun committed Jul 26, 2010 340 341 `````` r = parent_row[j]; c = j; `````` Christian Würdig committed Sep 13, 2006 342 343 344 345 346 347 348 349 `````` } /* End update the matching 20 */ if (--unmatched == 0) goto done; /* Begin get ready for another stage 17 */ t = 0; `````` Matthias Braun committed Jul 26, 2010 350 `````` for (c = 0; c < num_cols; ++c) { `````` Matthias Braun committed Aug 09, 2010 351 `````` parent_row[c] = (unsigned) -1; `````` Matthias Braun committed Jul 26, 2010 352 `````` slack[c] = INT_MAX; `````` Christian Würdig committed Sep 13, 2006 353 354 `````` } `````` Matthias Braun committed Jul 26, 2010 355 356 `````` for (r = 0; r < num_rows; ++r) { if (col_mate[r] == (unsigned)-1) { `````` Matthias Braun committed Aug 09, 2010 357 `````` DBG((dbg, LEVEL_1, "node %u: unmatched row %u\n", t, r)); `````` Matthias Braun committed Jul 26, 2010 358 `````` unchosen_row[t++] = r; `````` Christian Würdig committed Sep 13, 2006 359 360 361 362 363 364 365 `````` } } /* End get ready for another stage 17 */ } done: /* Begin double check the solution 23 */ `````` Matthias Braun committed Jul 26, 2010 366 367 `````` for (r = 0; r < num_rows; ++r) { for (c = 0; c < num_cols; ++c) { `````` Matthias Braun committed Aug 09, 2010 368 `````` if ((int) cost[r*num_cols + c] < row_dec[r] - col_inc[c]) `````` Christian Würdig committed Sep 13, 2006 369 370 371 372 `````` return -1; } } `````` Matthias Braun committed Jul 26, 2010 373 374 `````` for (r = 0; r < num_rows; ++r) { c = col_mate[r]; `````` Matthias Braun committed Aug 09, 2010 375 376 `````` if (c == (unsigned)-1 || cost[r*num_cols + c] != (unsigned) (row_dec[r] - col_inc[c])) `````` Christian Würdig committed Sep 13, 2006 377 378 379 `````` return -2; } `````` Matthias Braun committed Jul 26, 2010 380 381 382 `````` for (r = c = 0; c < num_cols; ++c) { if (col_inc[c]) r++; `````` Christian Würdig committed Sep 13, 2006 383 384 `````` } `````` Matthias Braun committed Jul 26, 2010 385 `````` if (r > num_rows) `````` Christian Würdig committed Sep 13, 2006 386 387 388 389 390 391 `````` return -3; /* End double check the solution 23 */ /* End Hungarian algorithm 18 */ /* collect the assigned values */ `````` Matthias Braun committed Jul 26, 2010 392 `````` for (r = 0; r < num_rows; ++r) { `````` Matthias Braun committed Aug 09, 2010 393 394 `````` if (cost_threshold > 0 && cost[r*num_cols + col_mate[r]] >= cost_threshold) `````` Matthias Braun committed Jul 26, 2010 395 `````` assignment[r] = -1; /* remove matching having cost > threshold */ `````` Christian Würdig committed Sep 25, 2006 396 `````` else `````` Matthias Braun committed Jul 26, 2010 397 `````` assignment[r] = col_mate[r]; `````` Christian Würdig committed Sep 13, 2006 398 399 `````` } `````` Christian Würdig committed Sep 13, 2006 400 401 `````` /* In case of normal matching: remove impossible ones */ if (p->match_type == HUNGARIAN_MATCH_NORMAL) { `````` Matthias Braun committed Jul 26, 2010 402 `````` for (r = 0; r < num_rows; ++r) { `````` Matthias Braun committed Aug 09, 2010 403 404 `````` if (rbitset_is_set(p->missing_left, r) || rbitset_is_set(p->missing_right, col_mate[r])) `````` Matthias Braun committed Jul 26, 2010 405 `````` assignment[r] = -1; `````` Christian Würdig committed Sep 13, 2006 406 407 408 `````` } } `````` Matthias Braun committed Jul 26, 2010 409 410 `````` for (r = 0; r < num_rows; ++r) { for (c = 0; c < num_cols; ++c) { `````` Matthias Braun committed Aug 09, 2010 411 `````` cost[r*num_cols + c] = cost[r*num_cols + c] - row_dec[r] + col_inc[c]; `````` Christian Würdig committed Sep 13, 2006 412 413 414 `````` } } `````` Matthias Braun committed Jul 26, 2010 415 `````` for (r = 0; r < num_rows; ++r) `````` Matthias Braun committed Aug 09, 2010 416 `````` res_cost += row_dec[r]; `````` Christian Würdig committed Sep 13, 2006 417 `````` `````` Matthias Braun committed Jul 26, 2010 418 `````` for (c = 0; c < num_cols; ++c) `````` Matthias Braun committed Aug 09, 2010 419 `````` res_cost -= col_inc[c]; `````` Christian Würdig committed Sep 13, 2006 420 `````` `````` Matthias Braun committed Aug 09, 2010 421 `````` DBG((dbg, LEVEL_1, "Cost is %d\n", res_cost)); `````` Christian Würdig committed Sep 13, 2006 422 423 424 425 426 427 428 429 430 431 `````` xfree(slack); xfree(col_inc); xfree(parent_row); xfree(row_mate); xfree(slack_row); xfree(row_dec); xfree(unchosen_row); xfree(col_mate); `````` Matthias Braun committed Sep 05, 2009 432 `````` if (final_cost != NULL) `````` Matthias Braun committed Aug 09, 2010 433 `````` *final_cost = res_cost; `````` 434 435 `````` return 0; `````` Christian Würdig committed Sep 13, 2006 436 ``}``