fix

[libfirm] / ir / adt / hungarian.h

diff --git a/ir/adt/hungarian.h b/ir/adt/hungarian.h
index 75d7c3e..1c5851a 100644 (file)
--- 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.
@@ -24,26 +25,35 @@
  ********************************************************************
  ********************************************************************/
 
-/* $Id$ */
-
-#ifndef _HUNGARIAN_H_
-#define _HUNGARIAN_H_
+/**
+ * @file
+ * @brief   Solving the Minimum Assignment Problem using the Hungarian Method.
+ * @version $Id$
+ */
+#ifndef FIRM_ADT_HUNGARIAN_H
+#define FIRM_ADT_HUNGARIAN_H
 
 #define HUNGARIAN_MODE_MINIMIZE_COST 0
 #define HUNGARIAN_MODE_MAXIMIZE_UTIL 1
 
+#define HUNGARIAN_MATCH_NORMAL  0
+#define HUNGARIAN_MATCH_PERFECT 1
+
 typedef struct _hungarian_problem_t hungarian_problem_t;
 
 /**
  * This method initialize the hungarian_problem structure and init
  * the cost matrix (missing lines or columns are filled with 0).
  *
- * @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 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_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);
+hungarian_problem_t *hungarian_new(int rows, int cols, int width, int match_type);
 
 /**
  * Adds an edge from left to right with some costs.
@@ -70,11 +80,13 @@ void hungarian_free(hungarian_problem_t *p);
 
 /**
  * This method computes the optimal assignment.
- * @param p          The hungarian object
- * @param assignment The final assignment
- * @return Negative value if solution is invalid, 0 otherwise
+ * @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 hungarian_solve(hungarian_problem_t *p, int *assignment, int *final_cost, int cost_threshold);
 
 /**
  * Print the cost matrix.