nsz Git - libfirm/blob - ir/adt/hungarian.h

   1 /********************************************************************
   2  ********************************************************************
   3  **
   4  ** libhungarian by Cyrill Stachniss, 2004
   5  **
   6  ** Added and adapted to libFirm by Christian Wuerdig, 2006
   7  **
   8  ** Solving the Minimum Assignment Problem using the
   9  ** Hungarian Method.
  10  **
  11  ** ** This file may be freely copied and distributed! **
  12  **
  13  ** Parts of the used code was originally provided by the
  14  ** "Stanford GraphGase", but I made changes to this code.
  15  ** As asked by  the copyright node of the "Stanford GraphGase",
  16  ** I hereby proclaim that this file are *NOT* part of the
  17  ** "Stanford GraphGase" distrubition!
  18  **
  19  ** This file is distributed in the hope that it will be useful,
  20  ** but WITHOUT ANY WARRANTY; without even the implied
  21  ** warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  22  ** PURPOSE.
  23  **
  24  ********************************************************************
  25  ********************************************************************/
  26
  27 /* $Id$ */
  28
  29 #ifndef _HUNGARIAN_H_
  30 #define _HUNGARIAN_H_
  31
  32 #define HUNGARIAN_MODE_MINIMIZE_COST 0
  33 #define HUNGARIAN_MODE_MAXIMIZE_UTIL 1
  34
  35 #define HUNGARIAN_MATCH_NORMAL  0
  36 #define HUNGARIAN_MATCH_PERFECT 1
  37
  38 typedef struct _hungarian_problem_t hungarian_problem_t;
  39
  40 /**
  41  * This method initialize the hungarian_problem structure and init
  42  * the cost matrix (missing lines or columns are filled with 0).
  43  *
  44  * @param rows       Number of rows in the given matrix
  45  * @param cols       Number of cols in the given matrix
  46  * @param width      Element width for matrix dumping
  47  * @param match_type The type of matching HUNGARIAN_MATCH_NORMAL or HUNGARIAN_MATCH_PERFECT
  48  * @return The problem object.
  49  */
  50 hungarian_problem_t *hungarian_new(int rows, int cols, int width, int match_type);
  51
  52 /**
  53  * Adds an edge from left to right with some costs.
  54  */
  55 void hungarian_add(hungarian_problem_t *p, int left, int right, int cost);
  56
  57 /**
  58 * Removes the edge from left to right.
  59 */
  60 void hungarian_remv(hungarian_problem_t *p, int left, int right);
  61
  62 /**
  63  * Prepares the cost matrix, dependend on the given mode.
  64  *
  65  * @param p     The hungarian object
  66  * @param mode  HUNGARIAN_MODE_MAXIMIZE_UTIL or HUNGARIAN_MODE_MINIMIZE_COST (default)
  67  */
  68 void hungarian_prepare_cost_matrix(hungarian_problem_t *p, int mode);
  69
  70 /**
  71  * Destroys the hungarian object.
  72  */
  73 void hungarian_free(hungarian_problem_t *p);
  74
  75 /**
  76  * This method computes the optimal assignment.
  77  * @param p          The hungarian object
  78  * @param assignment The final assignment
  79  * @return The resulting cost or a negative value if matching is invalid.
  80  */
  81 int hungarian_solve(hungarian_problem_t *p, int *assignment);
  82
  83 /**
  84  * Print the cost matrix.
  85  * @param p The hungarian object
  86  */
  87 void hungarian_print_costmatrix(hungarian_problem_t *p);
  88
  89 #endif /* _HUNGARIAN_H_ */