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.
33 #ifndef FIRM_ADT_HUNGARIAN_H
34 #define FIRM_ADT_HUNGARIAN_H
36 #define HUNGARIAN_MODE_MINIMIZE_COST 0
37 #define HUNGARIAN_MODE_MAXIMIZE_UTIL 1
39 #define HUNGARIAN_MATCH_NORMAL 0
40 #define HUNGARIAN_MATCH_PERFECT 1
42 typedef struct _hungarian_problem_t hungarian_problem_t;
45 * This method initialize the hungarian_problem structure and init
46 * the cost matrix (missing lines or columns are filled with 0).
48 * @param rows Number of rows in the given matrix
49 * @param cols Number of cols in the given matrix
50 * @param match_type The type of matching:
51 * HUNGARIAN_MATCH_PERFECT - every nodes matches another node
52 * HUNGARIAN_MATCH_NORMAL - matchings of nodes having no edge getting removed
53 * @return The problem object.
55 hungarian_problem_t *hungarian_new(int rows, int cols, int match_type);
58 * Adds an edge from left to right with some costs.
60 void hungarian_add(hungarian_problem_t *p, int left, int right, int cost);
63 * Removes the edge from left to right.
65 void hungarian_remv(hungarian_problem_t *p, int left, int right);
68 * Prepares the cost matrix dependent on the given mode.
70 * @param p The hungarian object
71 * @param mode HUNGARIAN_MODE_MAXIMIZE_UTIL or HUNGARIAN_MODE_MINIMIZE_COST (default)
73 void hungarian_prepare_cost_matrix(hungarian_problem_t *p, int mode);
76 * Destroys the hungarian object.
78 void hungarian_free(hungarian_problem_t *p);
81 * This method computes the optimal assignment.
82 * @param p The hungarian object
83 * @param assignment The final assignment
84 * @param final_cost The final costs
85 * @param cost_threshold Matchings with costs >= this limit will be removed (if limit > 0)
86 * @return 0 on success, negative number otherwise
88 int hungarian_solve(hungarian_problem_t *p, int *assignment, int *final_cost, int cost_threshold);
91 * Print the cost matrix.
92 * @param p The hungarian object
93 * @param cost_width The minimum field width of the costs
95 void hungarian_print_costmatrix(hungarian_problem_t *p, int cost_width);
97 #endif /* _HUNGARIAN_H_ */