1 /********************************************************************
2 ********************************************************************
4 ** libhungarian by Cyrill Stachniss, 2004
6 ** Added to libFirm by Christian Wuerdig, 2006
7 ** Added several options for not-perfect matchings.
9 ** Solving the Minimum Assignment Problem using the
12 ** ** This file may be freely copied and distributed! **
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!
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
25 ********************************************************************
26 ********************************************************************/
30 * @brief Solving the Minimum Assignment Problem using the Hungarian Method.
32 #ifndef FIRM_ADT_HUNGARIAN_H
33 #define FIRM_ADT_HUNGARIAN_H
39 * @defgroup hungarian Hungarian Algorithm
40 * Solves bipartite matching problems (minimize/maximize cost function)
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
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 */
58 * Internal representation of a bipartite matching problem
60 typedef struct hungarian_problem_t hungarian_problem_t;
63 * This method initialize the hungarian_problem structure and init
64 * the cost matrix (missing lines or columns are filled with 0).
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.
71 FIRM_API hungarian_problem_t *hungarian_new(unsigned num_rows,
73 match_type_t match_type);
76 * Adds an edge from left to right with some costs.
78 FIRM_API void hungarian_add(hungarian_problem_t *p, unsigned left,
79 unsigned right, unsigned cost);
82 * Removes the edge from left to right.
84 FIRM_API void hungarian_remove(hungarian_problem_t *p, unsigned left,
88 * Prepares the cost matrix dependent on the given mode.
90 * @param p The hungarian object
91 * @param mode specify whether to minimize or maximize the costs
93 FIRM_API void hungarian_prepare_cost_matrix(hungarian_problem_t *p,
94 hungarian_mode_t mode);
97 * Destroys the hungarian object.
99 FIRM_API void hungarian_free(hungarian_problem_t *p);
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
109 FIRM_API int hungarian_solve(hungarian_problem_t *p, unsigned *assignment,
110 unsigned *final_cost, unsigned cost_threshold);
113 * Print the cost matrix.
114 * @param p The hungarian object
115 * @param cost_width The minimum field width of the costs
117 FIRM_API void hungarian_print_cost_matrix(hungarian_problem_t *p,