********************************************************************
********************************************************************/
-/* $Id$ */
+/**
+ * @file
+ * @brief Solving the Minimum Assignment Problem using the Hungarian Method.
+ * @version $Id$
+ */
+#include "config.h"
#include <stdio.h>
#include <stdlib.h>
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;
*/
hungarian_problem_t *hungarian_new(int rows, int cols, int width, int match_type) {
int i;
- 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");
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);
/**
* Do the assignment.
*/
-int hungarian_solve(hungarian_problem_t* p, int *assignment, int *final_cost) {
+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]));
+ 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 = 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]));
+ 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]));
/* 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 */