29 #include <utils/hungarian_method/hungarian.h> 31 #define INF (0x7FFFFFFF) 39 #define hungarian_test_alloc(X) do {if ((void *)(X) == NULL) \ 40 fprintf(stderr, "Out of memory in %s, (%s, line %d).\n", \ 41 __FUNCTION__, __FILE__, __LINE__); } while (0) 54 p = (hungarian_problem_t *)malloc(
sizeof(hungarian_problem_t));
75 std::cerr << std::endl;
76 for(i=0; i<rows; i++) {
77 std::cerr <<
" " << i <<
"'th row [" << std::flush;
78 for(j=0; j<cols; j++) {
79 std::cerr << C[i][j] <<
" ";
84 std::cerr <<
" ]" << std::endl << std::flush;
86 std::cerr << std::endl;
100 r = (
int**)calloc(rows,
sizeof(
int*));
103 r[i] = (
int*)calloc(cols,
sizeof(
int));
105 r[i][j] = m[i*cols+j];
116 std::cerr <<
"HungarianMethod: == Assignment ==" << std::endl;
126 std::cerr <<
"HungarianMethod: == CostMatrix ==" << std::endl;
152 int i,j, org_cols, org_rows;
161 rows = std::max(cols, rows);
167 p->cost = (
int**)calloc(rows,
sizeof(
int*));
168 hungarian_test_alloc(
p->cost);
169 p->assignment = (
int**)calloc(rows,
sizeof(
int*));
170 hungarian_test_alloc(
p->assignment);
173 for(i=0; i<
p->num_rows; i++) {
174 p->cost[i] = (
int*)calloc(cols,
sizeof(
int));
175 hungarian_test_alloc(
p->cost[i]);
176 p->assignment[i] = (
int*)calloc(cols,
sizeof(
int));
177 hungarian_test_alloc(
p->assignment[i]);
178 for(j=0; j<
p->num_cols; j++) {
179 p->cost[i][j] = (i < org_rows && j < org_cols) ? cost_matrix[i][j] : 0;
180 p->assignment[i][j] = 0;
182 if (max_cost < p->cost[i][j])
183 max_cost =
p->cost[i][j];
188 if (mode == HUNGARIAN_MODE_MAXIMIZE_UTIL) {
189 for(i=0; i<
p->num_rows; i++) {
190 for(j=0; j<
p->num_cols; j++) {
191 p->cost[i][j] = max_cost -
p->cost[i][j];
195 else if (mode == HUNGARIAN_MODE_MINIMIZE_COST) {
199 fprintf(stderr,
"%s: unknown mode. Mode was set to HUNGARIAN_MODE_MINIMIZE_COST !\n", __FUNCTION__);
205 col_mates_ = (
int*)calloc(cols,
sizeof(
int));
206 hungarian_test_alloc(col_mates_);
207 for(
int j = 0; j < num_cols_; ++j ) {
212 row_mates_ = (
int*)calloc(rows,
sizeof(
int));
213 hungarian_test_alloc(row_mates_);
214 for(
int i = 0; i < num_rows_; ++i ) {
229 for(i=0; i<
p->num_rows; i++) {
236 p->assignment = NULL;
253 int i, j, m, n, k, l, s, t, q, unmatched, cost;
267 col_mate = (
int*)calloc(
p->num_rows,
sizeof(
int));
268 hungarian_test_alloc(col_mate);
269 unchosen_row = (
int*)calloc(
p->num_rows,
sizeof(
int));
270 hungarian_test_alloc(unchosen_row);
271 row_dec = (
int*)calloc(
p->num_rows,
sizeof(
int));
272 hungarian_test_alloc(row_dec);
273 slack_row = (
int*)calloc(
p->num_rows,
sizeof(
int));
274 hungarian_test_alloc(slack_row);
276 row_mate = (
int*)calloc(
p->num_cols,
sizeof(
int));
277 hungarian_test_alloc(row_mate);
278 parent_row = (
int*)calloc(
p->num_cols,
sizeof(
int));
279 hungarian_test_alloc(parent_row);
280 col_inc = (
int*)calloc(
p->num_cols,
sizeof(
int));
281 hungarian_test_alloc(col_inc);
282 slack = (
int*)calloc(
p->num_cols,
sizeof(
int));
283 hungarian_test_alloc(slack);
285 for (i=0;i<
p->num_rows;i++) {
291 for (j=0;j<
p->num_cols;j++) {
298 for (i=0;i<
p->num_rows;++i)
299 for (j=0;j<
p->num_cols;++j)
300 p->assignment[i][j]=HUNGARIAN_NOT_ASSIGNED;
304 fprintf(stderr,
"Using heuristic\n");
335 if (s==
p->cost[k][l] && row_mate[l]<0)
340 fprintf(stderr,
"matching col %d==row %d\n",l,k);
345 fprintf(stderr,
"node %d: unmatched row %d\n",t,k);
359 fprintf(stderr,
"Matched %d rows.\n",m-t);
373 del=
p->cost[k][l]-s+col_inc[l];
383 fprintf(stderr,
"node %d: row %d==col %d--row %d\n",
385 unchosen_row[t++]=row_mate[l];
402 if (slack[l] && slack[l]<s)
405 row_dec[unchosen_row[q]]+=s;
416 "Decreasing uncovered elements by %d produces zero at [%d,%d]\n",
429 fprintf(stderr,
"node %d: row %d==col %d--row %d\n",t,row_mate[l],l,k);
430 unchosen_row[t++]=row_mate[l];
442 fprintf(stderr,
"Breakthrough at node %d of %d!\n",q,t);
449 fprintf(stderr,
"rematching col %d==row %d\n",l,k);
469 fprintf(stderr,
"node %d: unmatched row %d\n",t,k);
479 if (
p->cost[k][l]<row_dec[k]-col_inc[l]) {
480 printf(
"boom1: p->cost[%i][%i]=%i < row_dec[%i]-col_inc[%i]=%i\n", k, l,
p->cost[k][l], k, l, row_dec[k]-col_inc[l]);
486 if (l<0 || p->cost[k][l]!=row_dec[k]-col_inc[l]) {
487 printf(
"boom2: %i<0 || p->cost[%i][%i]=%i != row_dec[%i]-col_inc[%i]=%i\n", l, k, l,
p->cost[k][l], k, l, row_dec[k]-col_inc[l]);
496 printf(
"boom3: %i > %i\n", k, m);
504 p->assignment[i][col_mate[i]]=HUNGARIAN_ASSIGNED;
512 p->cost[k][l]=
p->cost[k][l]-row_dec[k]+col_inc[l];
521 fprintf(stderr,
"Cost is %d\n",cost);
526 for(
int i = 0; i < num_rows_; ++i ) {
527 row_mates_[i] = row_mate[i];
529 for(
int j = 0; j < num_cols_; ++j ) {
530 col_mates_[j] = col_mate[j];
555 if( col < num_cols_ ) {
556 return (
int)col_mates_[col];
570 if( row < num_rows_ ) {
571 return (
int)row_mates_[row];
int get_column_assignment(const int &col)
Get column assignment.
int get_row_assignment(const int &row)
Get row assignment.
void print_status()
Print the current status.
void print_matrix(int **C, int rows, int cols)
Print matrix to stdout.
~HungarianMethod()
Destructor.
void solve()
Solve the assignment problem.
Fawkes library namespace.
bool is_available()
Check if data is available.
hungarian_problem_t * p
our problem instance member.
void print_cost_matrix()
Print the cost matrix.
void print_assignment()
Print the assignment matrix.
int init(int **cost_matrix, int rows, int cols, int mode)
Initialize hungarian method.
int * get_assignment(int &size)
Get assignment and size.
void free()
Free space alloacted by method.
HungarianMethod()
Constructor.
int ** array_to_matrix(int *m, int rows, int cols)
Convert an array to a matrix.