projects
/
libfirm
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
shorter version of fehler56
[libfirm]
/
ir
/
adt
/
hungarian.c
diff --git
a/ir/adt/hungarian.c
b/ir/adt/hungarian.c
index
bbb8590
..
05910a9
100644
(file)
--- 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>
#include <stdio.h>
#include <stdlib.h>
@@
-84,7
+91,7
@@
hungarian_problem_t *hungarian_new(int rows, int cols, int width, int match_type
int i;
hungarian_problem_t *p = xmalloc(sizeof(*p));
int i;
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");
FIRM_DBG_REGISTER(p->dbg, "firm.hungarian");
@@
-148,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.");
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);
p->cost[left][right] = cost;
p->max_cost = MAX(p->max_cost, cost);
@@
-184,7
+192,7
@@
void hungarian_free(hungarian_problem_t* p) {
/**
* Do the assignment.
*/
/**
* 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;
int i, j, m, n, k, l, s, t, q, unmatched, cost;
int *col_mate;
int *row_mate;
@@
-408,7
+416,10
@@
done:
/* collect the assigned values */
for (i = 0; i < m; ++i) {
/* 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 */
}
/* In case of normal matching: remove impossible ones */