Fawkes API  Fawkes Development Version
qa_hungarian.cpp
1 
2 /***************************************************************************
3  * hungarian.cpp - Hungarian Method
4  *
5  * Created: Thu Apr 18 17:09:58 2013
6  * Copyright 2004 Cyrill Stachniss
7  * 2008 Stefan Schiffer
8  ****************************************************************************/
9 
10 /* This program is free software; you can redistribute it and/or modify
11  * it under the terms of the GNU General Public License as published by
12  * the Free Software Foundation; either version 2 of the License, or
13  * (at your option) any later version. A runtime exception applies to
14  * this software (see LICENSE.GPL_WRE file mentioned below for details).
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU Library General Public License for more details.
20  *
21  * Read the full text in the LICENSE.GPL_WRE file in the doc directory.
22  */
23 
24 /* Solving the Minimum Assignment Problem using the
25  * Hungarian Method.
26  *
27  * ** This file may be freely copied and distributed! **
28  *
29  * Parts of the used code was originally provided by the
30  * "Stanford GraphGase", but I made changes to this code.
31  * As asked by the copyright node of the "Stanford GraphGase",
32  * I hereby proclaim that this file are *NOT* part of the
33  * "Stanford GraphGase" distrubition!
34  *
35  * This file is distributed in the hope that it will be useful,
36  * but WITHOUT ANY WARRANTY; without even the implied
37  * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
38  * PURPOSE.
39  */
40 
41 #include "hungarian.h"
42 
43 #include <iostream>
44 #include <stdio.h>
45 #include <stdlib.h>
46 
47 int **
48 array_to_matrix(int *m, int rows, int cols)
49 {
50  int i, j;
51  int **r;
52  r = (int **)calloc(rows, sizeof(int *));
53  for (i = 0; i < rows; i++) {
54  r[i] = (int *)calloc(cols, sizeof(int));
55  for (j = 0; j < cols; j++)
56  r[i][j] = m[i * cols + j];
57  }
58  return r;
59 }
60 
61 int
62 main(int argc, char *argv[])
63 {
64  std::cout << "QAHungarian: creating HungarianMethod object" << std::endl;
65  HungarianMethod *hungarian = new HungarianMethod();
66 
67  /* an example cost matrix */
68  int r[4 * 3] = {100, 1, 1, 100, 2, 2, 1, 0, 0, 0, 2, 0};
69  int **m = array_to_matrix(r, 4, 3);
70 
71  std::cout << "QAHungarian: init HungarianMethod object" << std::endl;
72  /* initialize the hungarian_problem using the cost matrix*/
73  int matrix_size = hungarian->Init(m, 4, 3, HUNGARIAN_MODE_MINIMIZE_COST);
74 
75  std::cout << "QAHungarian: Assignement matrix has a now a size '" << matrix_size << "' rows "
76  << "and '" << matrix_size << "' columns." << std::endl;
77 
78  hungarian->PrintCostmatrix();
79 
80  std::cout << "QAHungarian: calling solve on HungarianMethod object" << std::endl;
81  /* solve the assignement problem */
82  hungarian->Solve();
83 
84  hungarian->PrintAssignment();
85 
86  std::cout << "QAHungarian: calling free on HungarianMethod object" << std::endl;
87  /* free used memory */
88  hungarian->Free();
89 
90  free(m);
91 
92  return 0;
93 }