summaryrefslogtreecommitdiffhomepage
path: root/ir/adt
diff options
context:
space:
mode:
authorMatthias Braun <matze@braunis.de>2015-09-07 10:09:01 +0200
committerMatthias Braun <matze@braunis.de>2015-09-07 19:58:32 +0200
commit41057476683b57136af9f56fd62d544cf5ad51e2 (patch)
tree10cb970293894d55002640ab7ccfbc5605e5ce70 /ir/adt
parent0553e2d56e2f8fe403849d267e72b25d080c4d51 (diff)
hungarian: Cleanup
Diffstat (limited to 'ir/adt')
-rw-r--r--ir/adt/hungarian.c268
1 files changed, 131 insertions, 137 deletions
diff --git a/ir/adt/hungarian.c b/ir/adt/hungarian.c
index 225ad93..40fcb32 100644
--- a/ir/adt/hungarian.c
+++ b/ir/adt/hungarian.c
@@ -28,6 +28,8 @@
* @file
* @brief Solving the Minimum Assignment Problem using the Hungarian Method.
*/
+#include "hungarian.h"
+
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
@@ -37,7 +39,6 @@
#include "xmalloc.h"
#include "debug.h"
#include "panic.h"
-#include "hungarian.h"
#include "raw_bitset.h"
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
@@ -54,84 +55,77 @@ struct hungarian_problem_t {
the left side */
};
-static void hungarian_dump_f(FILE *f, const unsigned *cost,
- unsigned num_rows, unsigned num_cols, int width)
+static void hungarian_dump_f(FILE *const f, const unsigned *const cost,
+ unsigned const num_rows, unsigned const num_cols,
+ int const width)
{
- unsigned r, c;
-
- fprintf(f , "\n");
- for (r = 0; r < num_rows; r++) {
- fprintf(f, " [");
- for (c = 0; c < num_cols; c++) {
+ fputs("\n", f);
+ for (unsigned r = 0; r < num_rows; ++r) {
+ fputs(" [", f);
+ for (unsigned c = 0; c < num_cols; ++c) {
fprintf(f, "%*u", width, cost[r*num_cols + c]);
}
- fprintf(f, "]\n");
+ fputs("]\n", f);
}
- fprintf(f, "\n");
+ fputs("\n", f);
}
-void hungarian_print_cost_matrix(hungarian_problem_t *p, int width)
+void hungarian_print_cost_matrix(hungarian_problem_t const *const p,
+ int const width)
{
hungarian_dump_f(stderr, p->cost, p->num_rows, p->num_cols, width);
}
-hungarian_problem_t *hungarian_new(unsigned num_rows, unsigned num_cols,
- match_type_t match_type)
+hungarian_problem_t *hungarian_new(unsigned const num_rows,
+ unsigned const num_cols,
+ match_type_t const match_type)
{
hungarian_problem_t *p = XMALLOCZ(hungarian_problem_t);
FIRM_DBG_REGISTER(dbg, "firm.hungarian");
- /*
- Is the number of cols not equal to number of rows ?
- If yes, expand with 0 - cols / 0 - cols
- */
- num_rows = MAX(num_cols, num_rows);
- num_cols = num_rows;
-
- p->num_rows = num_rows;
- p->num_cols = num_cols;
+ /* Is the number of cols not equal to number of rows ?
+ * If yes, expand with 0 - cols / 0 - cols */
+ unsigned const size = MAX(num_cols, num_rows);
+ p->num_rows = size;
+ p->num_cols = size;
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.
- */
+ /* 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) {
- 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);
+ p->missing_left = rbitset_malloc(size);
+ p->missing_right = rbitset_malloc(size);
+ rbitset_set_all(p->missing_left, size);
+ rbitset_set_all(p->missing_right, size);
}
- /* allocate space for cost matrix */
- p->cost = XMALLOCNZ(unsigned, num_rows * num_cols);
+ /* Allocate space for cost matrix */
+ p->cost = XMALLOCNZ(unsigned, size*size);
return p;
}
-void hungarian_prepare_cost_matrix(hungarian_problem_t *p,
- hungarian_mode_t mode)
+void hungarian_prepare_cost_matrix(hungarian_problem_t *const p,
+ hungarian_mode_t const mode)
{
if (mode == HUNGARIAN_MODE_MAXIMIZE_UTIL) {
- unsigned r, c;
- unsigned num_cols = p->num_cols;
- unsigned *cost = p->cost;
- unsigned max_cost = p->max_cost;
- for (r = 0; r < p->num_rows; r++) {
- for (c = 0; c < p->num_cols; c++) {
+ unsigned const num_cols = p->num_cols;
+ unsigned *const cost = p->cost;
+ unsigned const max_cost = p->max_cost;
+ for (unsigned r = 0; r < p->num_rows; ++r) {
+ for (unsigned c = 0; c < p->num_cols; ++c) {
cost[r*num_cols + c] = max_cost - cost[r*num_cols + c];
}
}
} else if (mode == HUNGARIAN_MODE_MINIMIZE_COST) {
- /* nothing to do */
+ /* Nothing to do */
} else {
panic("unknown hungarian problem mode");
}
}
-void hungarian_add(hungarian_problem_t *p, unsigned left, unsigned right,
- unsigned cost)
+void hungarian_add(hungarian_problem_t *const p, unsigned const left,
+ unsigned const right, unsigned const cost)
{
assert(p->num_rows > left && "Invalid row selected.");
assert(p->num_cols > right && "Invalid column selected.");
@@ -158,7 +152,7 @@ void hungarian_remove(hungarian_problem_t *p, unsigned left, unsigned right)
}
}
-void hungarian_free(hungarian_problem_t* p)
+void hungarian_free(hungarian_problem_t *const p)
{
free(p->missing_left);
free(p->missing_right);
@@ -166,72 +160,65 @@ void hungarian_free(hungarian_problem_t* p)
free(p);
}
-int hungarian_solve(hungarian_problem_t* p, unsigned *assignment,
- unsigned *final_cost, unsigned cost_threshold)
+int hungarian_solve(hungarian_problem_t *const p, unsigned *const assignment,
+ unsigned *const final_cost, unsigned const cost_threshold)
{
- int result = 0;
- 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);
- unsigned r;
- unsigned c;
- unsigned t;
- unsigned unmatched;
+ int result = 0;
+ unsigned res_cost = 0;
+ unsigned const num_rows = p->num_rows;
+ unsigned const num_cols = p->num_cols;
+ unsigned *const cost = p->cost;
+ unsigned *const col_mate = XMALLOCNZ(unsigned, num_rows);
+ unsigned *const row_mate = XMALLOCNZ(unsigned, num_cols);
+ unsigned *const parent_row = XMALLOCNZ(unsigned, num_cols);
+ unsigned *const unchosen_row = XMALLOCNZ(unsigned, num_rows);
+ int *const row_dec = XMALLOCNZ(int, num_rows);
+ int *const col_inc = XMALLOCNZ(int, num_cols);
+ int *const slack = XMALLOCNZ(int, num_cols);
+ unsigned *const slack_row = XMALLOCNZ(unsigned, num_rows);
memset(assignment, -1, num_rows * sizeof(assignment[0]));
/* Begin subtract column minima in order to start with lots of zeros 12 */
DBG((dbg, LEVEL_1, "Using heuristic\n"));
- for (c = 0; c < num_cols; ++c) {
+ for (unsigned c = 0; c < num_cols; ++c) {
unsigned col_mininum = cost[0*num_cols + c];
-
- for (r = 1; r < num_rows; ++r) {
+ for (unsigned r = 1; r < num_rows; ++r) {
if (cost[r*num_cols + c] < col_mininum)
col_mininum = cost[r*num_cols + c];
}
-
if (col_mininum == 0)
continue;
res_cost += col_mininum;
- for (r = 0; r < num_rows; ++r)
+ for (unsigned r = 0; r < num_rows; ++r)
cost[r*num_cols + c] -= col_mininum;
}
/* End subtract column minima in order to start with lots of zeros 12 */
/* Begin initial state 16 */
- unmatched = 0;
- for (c = 0; c < num_cols; ++c) {
- row_mate[c] = (unsigned) -1;
- parent_row[c] = (unsigned) -1;
+ for (unsigned c = 0; c < num_cols; ++c) {
+ row_mate[c] = ~0u;
+ parent_row[c] = ~0u;
col_inc[c] = 0;
slack[c] = INT_MAX;
}
- for (r = 0; r < num_rows; ++r) {
+ unsigned unmatched = 0;
+ for (unsigned r = 0; r < num_rows; ++r) {
unsigned row_minimum = cost[r*num_cols + 0];
-
- for (c = 1; c < num_cols; ++c) {
+ for (unsigned c = 1; c < num_cols; ++c) {
if (cost[r*num_cols + c] < row_minimum)
row_minimum = cost[r*num_cols + c];
}
row_dec[r] = row_minimum;
- for (c = 0; c < num_cols; ++c) {
+ for (unsigned c = 0; c < num_cols; ++c) {
if (cost[r*num_cols + c] != row_minimum)
continue;
- if (row_mate[c] != (unsigned)-1)
+ if (row_mate[c] != ~0u)
continue;
col_mate[r] = c;
@@ -240,7 +227,7 @@ int hungarian_solve(hungarian_problem_t* p, unsigned *assignment,
goto row_done;
}
- col_mate[r] = (unsigned)-1;
+ col_mate[r] = ~0u;
DBG((dbg, LEVEL_1, "node %u: unmatched row %u\n", unmatched, r));
unchosen_row[unmatched++] = r;
row_done: ;
@@ -251,46 +238,49 @@ row_done: ;
if (unmatched == 0)
goto done;
- t = unmatched;
+ unsigned t = unmatched;
for (;;) {
unsigned q = 0;
- unsigned j;
DBG((dbg, LEVEL_1, "Matched %u rows.\n", num_rows - t));
+ unsigned breakthru_c;
+ unsigned breakthru_r;
for (;;) {
- int s;
while (q < t) {
/* Begin explore node q of the forest 19 */
- r = unchosen_row[q];
- s = row_dec[r];
-
- for (c = 0; c < num_cols; ++c) {
- if (slack[c]) {
- int del = cost[r*num_cols + c] - s + col_inc[c];
-
- if (del < slack[c]) {
- if (del == 0) {
- if (row_mate[c] == (unsigned)-1)
- goto breakthru;
-
- slack[c] = 0;
- parent_row[c] = r;
- DBG((dbg, LEVEL_1, "node %u: row %u == col %u -- row %u\n", t, row_mate[c], c, r));
- unchosen_row[t++] = row_mate[c];
- } else {
- slack[c] = del;
- slack_row[c] = r;
+ unsigned r = unchosen_row[q];
+ int s = row_dec[r];
+
+ for (unsigned c = 0; c < num_cols; ++c) {
+ if (!slack[c])
+ continue;
+
+ int del = cost[r*num_cols + c] - s + col_inc[c];
+ if (del < slack[c]) {
+ if (del == 0) {
+ if (row_mate[c] == ~0u) {
+ breakthru_r = r;
+ breakthru_c = c;
+ goto breakthru;
}
+
+ slack[c] = 0;
+ parent_row[c] = r;
+ DBG((dbg, LEVEL_1, "node %u: row %u == col %u -- row %u\n", t, row_mate[c], c, r));
+ unchosen_row[t++] = row_mate[c];
+ } else {
+ slack[c] = del;
+ slack_row[c] = r;
}
}
}
/* End explore node q of the forest 19 */
- q++;
+ ++q;
}
/* Begin introduce a new zero into the matrix 21 */
- s = INT_MAX;
- for (c = 0; c < num_cols; ++c) {
+ int s = INT_MAX;
+ for (unsigned c = 0; c < num_cols; ++c) {
if (slack[c] && slack[c] < s)
s = slack[c];
}
@@ -298,18 +288,20 @@ row_done: ;
for (q = 0; q < t; ++q)
row_dec[unchosen_row[q]] += s;
- for (c = 0; c < num_cols; ++c) {
+ for (unsigned c = 0; c < num_cols; ++c) {
if (slack[c]) {
slack[c] -= s;
if (slack[c] == 0) {
/* Begin look at a new zero 22 */
- r = slack_row[c];
+ unsigned r = slack_row[c];
DBG((dbg, LEVEL_1, "Decreasing uncovered elements by %d produces zero at [%u, %u]\n", s, r, c));
- if (row_mate[c] == (unsigned)-1) {
- for (j = c + 1; j < num_cols; ++j) {
+ if (row_mate[c] == ~0u) {
+ for (unsigned j = c + 1; j < num_cols; ++j) {
if (slack[j] == 0)
col_inc[j] += s;
}
+ breakthru_r = r;
+ breakthru_c = c;
goto breakthru;
} else {
parent_row[c] = r;
@@ -327,13 +319,15 @@ row_done: ;
breakthru:
/* Begin update the matching 20 */
DBG((dbg, LEVEL_1, "Breakthrough at node %u of %u.\n", q, t));
+ unsigned r = breakthru_r;
+ unsigned c = breakthru_c;
for (;;) {
- j = col_mate[r];
+ unsigned j = col_mate[r];
col_mate[r] = c;
row_mate[c] = r;
DBG((dbg, LEVEL_1, "rematching col %u == row %u\n", c, r));
- if (j == (unsigned)-1)
+ if (j == ~0u)
break;
r = parent_row[j];
@@ -345,14 +339,14 @@ breakthru:
goto done;
/* Begin get ready for another stage 17 */
- t = 0;
- for (c = 0; c < num_cols; ++c) {
- parent_row[c] = (unsigned) -1;
+ for (unsigned c = 0; c < num_cols; ++c) {
+ parent_row[c] = ~0u;
slack[c] = INT_MAX;
}
- for (r = 0; r < num_rows; ++r) {
- if (col_mate[r] == (unsigned)-1) {
+ t = 0;
+ for (unsigned r = 0; r < num_rows; ++r) {
+ if (col_mate[r] == ~0u) {
DBG((dbg, LEVEL_1, "node %u: unmatched row %u\n", t, r));
unchosen_row[t++] = r;
}
@@ -362,8 +356,8 @@ breakthru:
done:
/* Begin double check the solution 23 */
- for (r = 0; r < num_rows; ++r) {
- for (c = 0; c < num_cols; ++c) {
+ for (unsigned r = 0; r < num_rows; ++r) {
+ for (unsigned c = 0; c < num_cols; ++c) {
if ((int) cost[r*num_cols + c] < row_dec[r] - col_inc[c]) {
result = -1;
goto ret;
@@ -371,32 +365,32 @@ done:
}
}
- for (r = 0; r < num_rows; ++r) {
- c = col_mate[r];
- if (c == (unsigned)-1
+ for (unsigned r = 0; r < num_rows; ++r) {
+ unsigned c = col_mate[r];
+ if (c == ~0u
|| cost[r*num_cols + c] != (unsigned) (row_dec[r] - col_inc[c])) {
result = -2;
goto ret;
}
}
- for (r = c = 0; c < num_cols; ++c) {
- if (col_inc[c])
- r++;
- }
-
- if (r > num_rows) {
- result = -3;
- goto ret;
+ for (unsigned c = 0, r = 0; c < num_cols; ++c) {
+ if (col_inc[c]) {
+ ++r;
+ if (r > num_rows) {
+ result = -3;
+ goto ret;
+ }
+ }
}
/* End double check the solution 23 */
/* End Hungarian algorithm 18 */
/* collect the assigned values */
- for (r = 0; r < num_rows; ++r) {
+ for (unsigned r = 0; r < num_rows; ++r) {
if (cost_threshold > 0
- && cost[r*num_cols + col_mate[r]] >= cost_threshold)
+ && cost[r*num_cols + col_mate[r]] >= cost_threshold)
assignment[r] = -1; /* remove matching having cost > threshold */
else
assignment[r] = col_mate[r];
@@ -404,23 +398,23 @@ done:
/* In case of normal matching: remove impossible ones */
if (p->match_type == HUNGARIAN_MATCH_NORMAL) {
- for (r = 0; r < num_rows; ++r) {
+ for (unsigned r = 0; r < num_rows; ++r) {
if (rbitset_is_set(p->missing_left, r)
- || rbitset_is_set(p->missing_right, col_mate[r]))
+ || rbitset_is_set(p->missing_right, col_mate[r]))
assignment[r] = -1;
}
}
- for (r = 0; r < num_rows; ++r) {
- for (c = 0; c < num_cols; ++c) {
+ for (unsigned r = 0; r < num_rows; ++r) {
+ for (unsigned c = 0; c < num_cols; ++c) {
cost[r*num_cols + c] = cost[r*num_cols + c] - row_dec[r] + col_inc[c];
}
}
- for (r = 0; r < num_rows; ++r)
+ for (unsigned r = 0; r < num_rows; ++r)
res_cost += row_dec[r];
- for (c = 0; c < num_cols; ++c)
+ for (unsigned c = 0; c < num_cols; ++c)
res_cost -= col_inc[c];
DBG((dbg, LEVEL_1, "Cost is %d\n", res_cost));