From b1562190f073db4e4db8917798adc20b207a38c0 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Christian=20W=C3=BCrdig?=
 <chriswue@ipd.info.uni-karlsruhe.de>
Date: Mon, 25 Sep 2006 11:29:15 +0000
Subject: [PATCH] changed api

[r8292]
---
 ir/adt/hungarian.c |  7 +++++--
 ir/adt/hungarian.h | 16 ++++++++++------
 2 files changed, 15 insertions(+), 8 deletions(-)

diff --git a/ir/adt/hungarian.c b/ir/adt/hungarian.c
index bbb859049..19ce38665 100644
--- a/ir/adt/hungarian.c
+++ b/ir/adt/hungarian.c
@@ -184,7 +184,7 @@ void hungarian_free(hungarian_problem_t* p) {
 /**
  * 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;
@@ -408,7 +408,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 */
diff --git a/ir/adt/hungarian.h b/ir/adt/hungarian.h
index 2ac922d10..1c6b122cb 100644
--- a/ir/adt/hungarian.h
+++ b/ir/adt/hungarian.h
@@ -3,7 +3,8 @@
  **
  ** libhungarian by Cyrill Stachniss, 2004
  **
- ** Added and adapted to libFirm by Christian Wuerdig, 2006
+ ** Added to libFirm by Christian Wuerdig, 2006
+ ** Added several options for not-perfect matchings.
  **
  ** Solving the Minimum Assignment Problem using the
  ** Hungarian Method.
@@ -44,7 +45,9 @@ typedef struct _hungarian_problem_t hungarian_problem_t;
  * @param rows       Number of rows in the given matrix
  * @param cols       Number of cols in the given matrix
  * @param width      Element width for matrix dumping
- * @param match_type The type of matching HUNGARIAN_MATCH_NORMAL or HUNGARIAN_MATCH_PERFECT
+ * @param match_type The type of matching:
+ *                   HUNGARIAN_MATCH_PERFECT - every nodes matches another node
+ *                   HUNGARIAN_MATCH_NORMAL  - matchings of nodes having no edge getting removed
  * @return The problem object.
  */
 hungarian_problem_t *hungarian_new(int rows, int cols, int width, int match_type);
@@ -74,12 +77,13 @@ void hungarian_free(hungarian_problem_t *p);
 
 /**
  * This method computes the optimal assignment.
- * @param p          The hungarian object
- * @param assignment The final assignment
- * @param final_cost The final costs
+ * @param p              The hungarian object
+ * @param assignment     The final assignment
+ * @param final_cost     The final costs
+ * @param cost_threshold Matchings with costs >= this limit will be removed (if limit > 0)
  * @return 0 on success, negative number otherwise
  */
-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);
 
 /**
  * Print the cost matrix.
-- 
2.20.1