X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fadt%2Fhungarian.c;h=32f1d6879e3ccbaffa89952bf10e2cad8d0aff12;hb=f44b4b1268e91fedfa29f670189b8ca84866bb9a;hp=d3e95075233257567e7ae60844efae34fce5a180;hpb=7a254bd63e66b7ef7e70d5d8f37ed30c872c9333;p=libfirm diff --git a/ir/adt/hungarian.c b/ir/adt/hungarian.c index d3e950752..32f1d6879 100644 --- a/ir/adt/hungarian.c +++ b/ir/adt/hungarian.c @@ -24,7 +24,12 @@ ******************************************************************** ********************************************************************/ -/* $Id$ */ +/** + * @file + * @brief Solving the Minimum Assignment Problem using the Hungarian Method. + * @version $Id$ + */ +#include "config.h" #include #include @@ -34,22 +39,26 @@ #include "xmalloc.h" #include "debug.h" #include "obst.h" +#include "bitset.h" #include "hungarian.h" #define INF (0x7FFFFFFF) struct _hungarian_problem_t { - int num_rows; - int num_cols; - int **cost; - int width; - int max_cost; + int num_rows; /**< number of rows */ + int num_cols; /**< number of columns */ + int **cost; /**< the cost matrix */ + int width; /**< the width for cost matrix dumper */ + int max_cost; /**< the maximal costs in the matrix */ + int match_type; /**< PERFECT or NORMAL matching */ + bitset_t *missing_left; /**< left side nodes having no edge to the right side */ + bitset_t *missing_right; /**< right side nodes having no edge to the left side */ struct obstack obst; DEBUG_ONLY(firm_dbg_module_t *dbg); }; -static INLINE void *get_init_mem(struct obstack *obst, long sz) { +static inline void *get_init_mem(struct obstack *obst, long sz) { void *p = obstack_alloc(obst, sz); memset(p, 0, sz); return p; @@ -76,12 +85,9 @@ void hungarian_print_costmatrix(hungarian_problem_t *p) { /** * Create the object and allocate memory for the data structures. */ -hungarian_problem_t *hungarian_new(int rows, int cols, int width) { +hungarian_problem_t *hungarian_new(int rows, int cols, int width, int match_type) { int i; - int max_cost = 0; - hungarian_problem_t *p = xmalloc(sizeof(*p)); - - memset(p, 0, sizeof(p)); + hungarian_problem_t *p = XMALLOCZ(hungarian_problem_t); FIRM_DBG_REGISTER(p->dbg, "firm.hungarian"); @@ -94,12 +100,25 @@ hungarian_problem_t *hungarian_new(int rows, int cols, int width) { obstack_init(&p->obst); - p->num_rows = rows; - p->num_cols = cols; - p->width = width; - p->cost = (int **)get_init_mem(&p->obst, rows * sizeof(p->cost[0])); + p->num_rows = rows; + p->num_cols = cols; + p->width = width; + 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) { + p->missing_left = bitset_obstack_alloc(&p->obst, rows); + p->missing_right = bitset_obstack_alloc(&p->obst, cols); + bitset_set_all(p->missing_left); + bitset_set_all(p->missing_right); + } /* allocate space for cost matrix */ + p->cost = (int **)get_init_mem(&p->obst, rows * sizeof(p->cost[0])); for (i = 0; i < p->num_rows; i++) p->cost[i] = (int *)get_init_mem(&p->obst, cols * sizeof(p->cost[0][0])); @@ -132,9 +151,15 @@ void hungarian_prepare_cost_matrix(hungarian_problem_t *p, int mode) { void hungarian_add(hungarian_problem_t *p, int left, int right, int cost) { assert(p->num_rows > left && "Invalid row selected."); assert(p->num_cols > right && "Invalid column selected."); + assert(cost >= 0); p->cost[left][right] = cost; p->max_cost = MAX(p->max_cost, cost); + + if (p->match_type == HUNGARIAN_MATCH_NORMAL) { + bitset_clear(p->missing_left, left); + bitset_clear(p->missing_right, right); + } } /** @@ -145,6 +170,11 @@ void hungarian_remv(hungarian_problem_t *p, int left, int right) { assert(p->num_cols > right && "Invalid column selected."); p->cost[left][right] = 0; + + if (p->match_type == HUNGARIAN_MATCH_NORMAL) { + bitset_set(p->missing_left, left); + bitset_set(p->missing_right, right); + } } /** @@ -158,7 +188,7 @@ void hungarian_free(hungarian_problem_t* p) { /** * Do the assignment. */ -int hungarian_solve(hungarian_problem_t* p, int *assignment) { +int hungarian_solve(hungarian_problem_t* p, int *assignment, int *final_cost, int cost_threshold) { int i, j, m, n, k, l, s, t, q, unmatched, cost; int *col_mate; int *row_mate; @@ -173,30 +203,15 @@ int hungarian_solve(hungarian_problem_t* p, int *assignment) { m = p->num_rows; n = p->num_cols; - col_mate = xcalloc(p->num_rows, sizeof(col_mate[0])); - unchosen_row = xcalloc(p->num_rows, sizeof(unchosen_row[0])); - row_dec = xcalloc(p->num_rows, sizeof(row_dec[0])); - slack_row = xcalloc(p->num_rows, sizeof(slack_row[0])); - - row_mate = xcalloc(p->num_cols, sizeof(row_mate[0])); - parent_row = xcalloc(p->num_cols, sizeof(parent_row[0])); - col_inc = xcalloc(p->num_cols, sizeof(col_inc[0])); - slack = xcalloc(p->num_cols, sizeof(slack[0])); - -#if 0 - for (i = 0; i < p->num_rows; ++i) { - col_mate[i] = 0; - unchosen_row[i] = 0; - row_dec[i] = 0; - slack_row[i]=0; - } - for (j=0;jnum_cols;j++) { - row_mate[j]=0; - parent_row[j] = 0; - col_inc[j]=0; - slack[j]=0; - } -#endif + col_mate = XMALLOCNZ(int, p->num_rows); + unchosen_row = XMALLOCNZ(int, p->num_rows); + row_dec = XMALLOCNZ(int, p->num_rows); + slack_row = XMALLOCNZ(int, p->num_rows); + + row_mate = XMALLOCNZ(int, p->num_cols); + parent_row = XMALLOCNZ(int, p->num_cols); + col_inc = XMALLOCNZ(int, p->num_cols); + slack = XMALLOCNZ(int, p->num_cols); memset(assignment, -1, m * sizeof(assignment[0])); @@ -397,7 +412,18 @@ done: /* collect the assigned values */ for (i = 0; i < m; ++i) { - assignment[i] = col_mate[i]; + if (cost_threshold > 0 && p->cost[i][col_mate[i]] >= cost_threshold) + assignment[i] = -1; /* remove matching having cost > threshold */ + else + assignment[i] = col_mate[i]; + } + + /* In case of normal matching: remove impossible ones */ + if (p->match_type == HUNGARIAN_MATCH_NORMAL) { + for (i = 0; i < m; ++i) { + if (bitset_is_set(p->missing_left, i) || bitset_is_set(p->missing_right, col_mate[i])) + assignment[i] = -1; + } } for (k = 0; k < m; ++k) { @@ -423,5 +449,7 @@ done: xfree(unchosen_row); xfree(col_mate); + *final_cost = cost; + return 0; }