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

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