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

diff --git a/ir/adt/hungarian.c b/ir/adt/hungarian.c
index d3e950752..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>
@@ -34,17 +41,21 @@
 #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      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 */
+	bitset_t *missing_right;    /**< right side nodes having no edge to the left side */
 	struct obstack obst;
 	DEBUG_ONLY(firm_dbg_module_t *dbg);
 };
@@ -76,12 +87,11 @@ void hungarian_print_costmatrix(hungarian_problem_t *p) {
 /**
  * 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 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");
 
@@ -94,12 +104,25 @@ hungarian_problem_t *hungarian_new(int rows, int cols, int width) {
 
 	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->width      = width;
+	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 = (int **)get_init_mem(&p->obst, rows * sizeof(p->cost[0]));
 	for (i = 0; i < p->num_rows; i++)
 		p->cost[i] = (int *)get_init_mem(&p->obst, cols * sizeof(p->cost[0][0]));
 
@@ -132,9 +155,15 @@ 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);
+
+	if (p->match_type == HUNGARIAN_MATCH_NORMAL) {
+		bitset_clear(p->missing_left, left);
+		bitset_clear(p->missing_right, right);
+	}
 }
 
 /**
@@ -145,6 +174,11 @@ void hungarian_remv(hungarian_problem_t *p, int left, int right) {
 	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);
+	}
 }
 
 /**
@@ -158,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;
@@ -183,21 +217,6 @@ int hungarian_solve(hungarian_problem_t* p, int *assignment) {
 	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
-
 	memset(assignment, -1, m * sizeof(assignment[0]));
 
 	/* Begin subtract column minima in order to start with lots of zeros 12 */
@@ -397,7 +416,18 @@ 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 */
+	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) {
@@ -423,5 +453,7 @@ done:
 	xfree(unchosen_row);
 	xfree(col_mate);
 
+	*final_cost = cost;
+
 	return 0;
 }