1 /********************************************************************
2 ********************************************************************
4 ** libhungarian by Cyrill Stachniss, 2004
7 ** Solving the Minimum Assignment Problem using the
10 ** ** This file may be freely copied and distributed! **
12 ** Parts of the used code was originally provided by the
13 ** "Stanford GraphGase", but I made changes to this code.
14 ** As asked by the copyright node of the "Stanford GraphGase",
15 ** I hereby proclaim that this file are *NOT* part of the
16 ** "Stanford GraphGase" distrubition!
18 ** This file is distributed in the hope that it will be useful,
19 ** but WITHOUT ANY WARRANTY; without even the implied
20 ** warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
23 ********************************************************************
24 ********************************************************************/
29 #define HUNGARIAN_MODE_MINIMIZE_COST 0
30 #define HUNGARIAN_MODE_MAXIMIZE_UTIL 1
32 typedef struct _hungarian_problem_t hungarian_problem_t;
35 * This method initialize the hungarian_problem structure and init
36 * the cost matrix (missing lines or columns are filled with 0).
38 * @param rows Number of rows in the given matrix
39 * @param cols Number of cols in the given matrix
40 * @param width Element width for matrix dumping
41 * @return The problem object.
43 hungarian_problem_t *hungarian_new(int rows, int cols, int width);
46 * Adds an edge from left to right with some costs.
48 void hungarian_add(hungarian_problem_t *p, int left, int right, int cost);
51 * Removes the edge from left to right.
53 void hungarian_remv(hungarian_problem_t *p, int left, int right);
56 * Prepares the cost matrix, dependend on the given mode.
58 * @param p The hungarian object
59 * @param mode HUNGARIAN_MODE_MAXIMIZE_UTIL or HUNGARIAN_MODE_MINIMIZE_COST (default)
61 void hungarian_prepare_cost_matrix(hungarian_problem_t *p, int mode);
64 * Destroys the hungarian object.
66 void hungarian_free(hungarian_problem_t *p);
69 * This method computes the optimal assignment.
70 * @param p The hungarian object
71 * @param assignment The final assignment
72 * @return Negative value if solution is invalid, 0 otherwise
74 int hungarian_solve(hungarian_problem_t *p, int *assignment);
77 * Print the cost matrix.
78 * @param p The hungarian object
80 void hungarian_print_costmatrix(hungarian_problem_t *p);
82 #endif /* _HUNGARIAN_H_ */