X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fhungarian.c;h=05910a9010090fc96b4a3d2c573adb760616689f;hb=b3af383e58b7f5e16695d0f72073094081ea09b3;hp=953cf7db378d1a2f0c2b21685c8e9fde70ffbc61;hpb=a464ca473530b17ceca697f30c47e7d3bcff638b;p=libfirm

diff --git a/ir/adt/hungarian.c b/ir/adt/hungarian.c
index 953cf7db3..05910a901 100644
--- a/ir/adt/hungarian.c
+++ b/ir/adt/hungarian.c
@@ -24,7 +24,14 @@
  ********************************************************************
  ********************************************************************/
 
-/* $Id$ */
+/**
+ * @file
+ * @brief   Solving the Minimum Assignment Problem using the Hungarian Method.
+ * @version $Id$
+ */
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
 
 #include <stdio.h>
 #include <stdlib.h>
@@ -82,10 +89,9 @@ void hungarian_print_costmatrix(hungarian_problem_t *p) {
  */
 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));
+	memset(p, 0, sizeof(p[0]));
 
 	FIRM_DBG_REGISTER(p->dbg, "firm.hungarian");
 
@@ -149,6 +155,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);
@@ -185,7 +192,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;
@@ -409,7 +416,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 */
@@ -443,5 +453,7 @@ done:
 	xfree(unchosen_row);
 	xfree(col_mate);
 
-	return cost;
+	*final_cost = cost;
+
+	return 0;
 }