1 /********************************************************************
2 ********************************************************************
4 ** libhungarian by Cyrill Stachniss, 2004
6 ** Added and adapted to libFirm by Christian Wuerdig, 2006
8 ** Solving the Minimum Assignment Problem using the
11 ** ** This file may be freely copied and distributed! **
13 ** Parts of the used code was originally provided by the
14 ** "Stanford GraphGase", but I made changes to this code.
15 ** As asked by the copyright node of the "Stanford GraphGase",
16 ** I hereby proclaim that this file are *NOT* part of the
17 ** "Stanford GraphGase" distrubition!
19 ** This file is distributed in the hope that it will be useful,
20 ** but WITHOUT ANY WARRANTY; without even the implied
21 ** warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
24 ********************************************************************
25 ********************************************************************/
32 #define HUNGARIAN_MODE_MINIMIZE_COST 0
33 #define HUNGARIAN_MODE_MAXIMIZE_UTIL 1
35 #define HUNGARIAN_MATCH_NORMAL 0
36 #define HUNGARIAN_MATCH_PERFECT 1
38 typedef struct _hungarian_problem_t hungarian_problem_t;
41 * This method initialize the hungarian_problem structure and init
42 * the cost matrix (missing lines or columns are filled with 0).
44 * @param rows Number of rows in the given matrix
45 * @param cols Number of cols in the given matrix
46 * @param width Element width for matrix dumping
47 * @param match_type The type of matching HUNGARIAN_MATCH_NORMAL or HUNGARIAN_MATCH_PERFECT
48 * @return The problem object.
50 hungarian_problem_t *hungarian_new(int rows, int cols, int width, int match_type);
53 * Adds an edge from left to right with some costs.
55 void hungarian_add(hungarian_problem_t *p, int left, int right, int cost);
58 * Removes the edge from left to right.
60 void hungarian_remv(hungarian_problem_t *p, int left, int right);
63 * Prepares the cost matrix, dependend on the given mode.
65 * @param p The hungarian object
66 * @param mode HUNGARIAN_MODE_MAXIMIZE_UTIL or HUNGARIAN_MODE_MINIMIZE_COST (default)
68 void hungarian_prepare_cost_matrix(hungarian_problem_t *p, int mode);
71 * Destroys the hungarian object.
73 void hungarian_free(hungarian_problem_t *p);
76 * This method computes the optimal assignment.
77 * @param p The hungarian object
78 * @param assignment The final assignment
79 * @param final_cost The final costs
80 * @return 0 on success, negative number otherwise
82 int hungarian_solve(hungarian_problem_t *p, int *assignment, int *final_cost);
85 * Print the cost matrix.
86 * @param p The hungarian object
88 void hungarian_print_costmatrix(hungarian_problem_t *p);
90 #endif /* _HUNGARIAN_H_ */