X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fhungarian.c;h=26c4fe5970e1349ffbb50e31952d015bedd2abdb;hb=1852308bd33b77378f0fca9e5347d4f9082464c4;hp=5be8b71e4ea3fba372746e2f6f1e0e0791e72029;hpb=29cb8f40c1c928f01de15e270487ba4810f30ad8;p=libfirm

diff --git a/ir/adt/hungarian.c b/ir/adt/hungarian.c
index 5be8b71e4..26c4fe597 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 <stdio.h>
 #include <stdlib.h>
@@ -44,7 +49,6 @@ struct _hungarian_problem_t {
 	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 */
@@ -53,12 +57,6 @@ struct _hungarian_problem_t {
 	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) {
 	int i, j;
 
@@ -73,18 +71,16 @@ static void hungarian_dump_f(FILE *f, int **C, int rows, int cols, int width) {
 	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, int match_type) {
+hungarian_problem_t *hungarian_new(int rows, int cols, 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");
 
@@ -99,7 +95,6 @@ hungarian_problem_t *hungarian_new(int rows, int cols, int width, int match_type
 
 	p->num_rows   = rows;
 	p->num_cols   = cols;
-	p->width      = width;
 	p->match_type = match_type;
 
 	/*
@@ -115,9 +110,9 @@ hungarian_problem_t *hungarian_new(int rows, int cols, int width, int match_type
 	}
 
 	/* allocate space for cost matrix */
-	p->cost = (int **)get_init_mem(&p->obst, rows * sizeof(p->cost[0]));
+	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;
 }
@@ -148,6 +143,7 @@ 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);
@@ -184,7 +180,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;
@@ -199,15 +195,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]));
+	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]));
 
@@ -408,7 +404,10 @@ 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 */
@@ -442,5 +441,8 @@ done:
 	xfree(unchosen_row);
 	xfree(col_mate);
 
-	return cost;
+	if (final_cost != NULL)
+		*final_cost = cost;
+
+	return 0;
 }