nsz Git - libfirm/blob - include/libfirm/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" distribution!
  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 /**
  29  * @file
  30  * @brief   Solving the Minimum Assignment Problem using the Hungarian Method.
  31  */
  32 #ifndef FIRM_ADT_HUNGARIAN_H
  33 #define FIRM_ADT_HUNGARIAN_H
  34
  35 #include "../begin.h"
  36
  37 /**
  38  * @ingroup algorithms
  39  * @defgroup hungarian Hungarian Algorithm
  40  * Solves bipartite matching problems (minimize/maximize cost function)
  41  * @{
  42  */
  43
  44 /** type of matching */
  45 typedef enum match_type_t {
  46         HUNGARIAN_MATCH_NORMAL,   /**< ever nodes matches another node */
  47         HUNGARIAN_MATCH_PERFECT   /**< matchings of nodes having no edge getting
  48                                        removed */
  49 } match_type_t;
  50
  51 /** mode of matching (the optimization goal) */
  52 typedef enum hungarian_mode_t {
  53         HUNGARIAN_MODE_MINIMIZE_COST, /**< minimize cost */
  54         HUNGARIAN_MODE_MAXIMIZE_UTIL  /**< maximize cost */
  55 } hungarian_mode_t;
  56
  57 /**
  58  * Internal representation of a bipartite matching problem
  59  */
  60 typedef struct hungarian_problem_t hungarian_problem_t;
  61
  62 /**
  63  * This method initialize the hungarian_problem structure and init
  64  * the cost matrix (missing lines or columns are filled with 0).
  65  *
  66  * @param num_rows   Number of rows in the given matrix
  67  * @param num_cols   Number of cols in the given matrix
  68  * @param match_type The type of matching
  69  * @return The problem object.
  70  */
  71 FIRM_API hungarian_problem_t *hungarian_new(unsigned num_rows,
  72                                             unsigned num_cols,
  73                                             match_type_t match_type);
  74
  75 /**
  76  * Adds an edge from left to right with some costs.
  77  */
  78 FIRM_API void hungarian_add(hungarian_problem_t *p, unsigned left,
  79                             unsigned right, unsigned cost);
  80
  81 /**
  82  * Removes the edge from left to right.
  83  */
  84 FIRM_API void hungarian_remove(hungarian_problem_t *p, unsigned left,
  85                                unsigned right);
  86
  87 /**
  88  * Prepares the cost matrix dependent on the given mode.
  89  *
  90  * @param p     The hungarian object
  91  * @param mode  specify whether to minimize or maximize the costs
  92  */
  93 FIRM_API void hungarian_prepare_cost_matrix(hungarian_problem_t *p,
  94                                             hungarian_mode_t mode);
  95
  96 /**
  97  * Destroys the hungarian object.
  98  */
  99 FIRM_API void hungarian_free(hungarian_problem_t *p);
 100
 101 /**
 102  * This method computes the optimal assignment.
 103  * @param p              The hungarian object
 104  * @param assignment     The final assignment
 105  * @param final_cost     The final costs
 106  * @param cost_threshold Matchings with costs >= this limit will be removed (if limit > 0)
 107  * @return 0 on success, negative number otherwise
 108  */
 109 FIRM_API int hungarian_solve(hungarian_problem_t *p, unsigned *assignment,
 110                              unsigned *final_cost, unsigned cost_threshold);
 111
 112 /**
 113  * Print the cost matrix.
 114  * @param p          The hungarian object
 115  * @param cost_width The minimum field width of the costs
 116  */
 117 FIRM_API void hungarian_print_cost_matrix(hungarian_problem_t *p,
 118                                           int cost_width);
 119
 120 /** @} */
 121
 122 #include "../end.h"
 123
 124 #endif