********************************************************************
********************************************************************/
-/* $Id$ */
+/**
+ * @file
+ * @brief Solving the Minimum Assignment Problem using the Hungarian Method.
+ * @version $Id$
+ */
+#include "config.h"
#include <stdio.h>
#include <stdlib.h>
#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 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) {
- void *p = obstack_alloc(obst, sz);
- memset(p, 0, sz);
- return p;
-}
-
-static void hungarian_dump_f(FILE *f, int **C, int rows, int cols, int width) {
+static void hungarian_dump_f(FILE *f, int **C, int rows, int cols, int width)
+{
int i, j;
fprintf(f , "\n");
fprintf(f, "\n");
}
-void hungarian_print_costmatrix(hungarian_problem_t *p) {
- hungarian_dump_f(stderr, p->cost, p->num_rows, p->num_cols, p->width);
+void hungarian_print_cost_matrix(hungarian_problem_t *p, int width)
+{
+ hungarian_dump_f(stderr, p->cost, p->num_rows, p->num_cols, width);
}
/**
* 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 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");
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->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 = OALLOCNZ(&p->obst, int*, rows);
for (i = 0; i < p->num_rows; i++)
- p->cost[i] = (int *)get_init_mem(&p->obst, cols * sizeof(p->cost[0][0]));
+ p->cost[i] = OALLOCNZ(&p->obst, int, cols);
return p;
}
/**
* Prepare the cost matrix.
*/
-void hungarian_prepare_cost_matrix(hungarian_problem_t *p, int mode) {
+void hungarian_prepare_cost_matrix(hungarian_problem_t *p, int mode)
+{
int i, j;
if (mode == HUNGARIAN_MODE_MAXIMIZE_UTIL) {
/**
* Set cost[left][right] to cost.
*/
-void hungarian_add(hungarian_problem_t *p, int left, int right, int cost) {
+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);
+ }
}
/**
* Set cost[left][right] to 0.
*/
-void hungarian_remv(hungarian_problem_t *p, int left, int right) {
+void hungarian_remv(hungarian_problem_t *p, int left, int right)
+{
assert(p->num_rows > left && "Invalid row selected.");
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);
+ }
}
/**
* Frees all allocated memory.
*/
-void hungarian_free(hungarian_problem_t* p) {
+void hungarian_free(hungarian_problem_t* p)
+{
obstack_free(&p->obst, NULL);
xfree(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;
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;j<p->num_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]));
goto done;
unmatched = t;
- while (1) {
+ for (;;) {
DBG((p->dbg, LEVEL_1, "Matched %d rows.\n", m - t));
q = 0;
- while (1) {
+ for (;;) {
while (q < t) {
/* Begin explore node q of the forest 19 */
k = unchosen_row[q];
breakthru:
/* Begin update the matching 20 */
DBG((p->dbg, LEVEL_1, "Breakthrough at node %d of %d.\n", q, t));
- while (1) {
+ for (;;) {
j = col_mate[k];
col_mate[k] = l;
row_mate[l] = k;
/* 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) {
xfree(unchosen_row);
xfree(col_mate);
+ if (final_cost != NULL)
+ *final_cost = cost;
+
return 0;
}
projects / libfirm / blobdiff