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

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