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 <stdio.h>
42 #include <stdlib.h>
43 #include <iostream>
44 #include "hungarian.h"
45 
46 int** array_to_matrix(int* m, int rows, int cols) {
47  int i,j;
48  int** r;
49  r = (int**)calloc(rows,sizeof(int*));
50  for(i=0;i<rows;i++)
51  {
52  r[i] = (int*)calloc(cols,sizeof(int));
53  for(j=0;j<cols;j++)
54  r[i][j] = m[i*cols+j];
55  }
56  return r;
57 }
58 
59 
60 int
61 main( int argc, char * argv[] )
62 {
63  std::cout << "QAHungarian: creating HungarianMethod object" << std::endl;
64  HungarianMethod * hungarian = new HungarianMethod();
65 
66  /* an example cost matrix */
67  int r[4*3] = { 100, 1, 1,
68  100, 2, 2,
69  1, 0, 0,
70  0, 2, 0 };
71  int** m = array_to_matrix(r,4,3);
72 
73  std::cout << "QAHungarian: init HungarianMethod object" << std::endl;
74  /* initialize the hungarian_problem using the cost matrix*/
75  int matrix_size = hungarian->Init( m , 4, 3, HUNGARIAN_MODE_MINIMIZE_COST );
76 
77  std::cout << "QAHungarian: Assignement matrix has a now a size '" << matrix_size << "' rows "
78  << "and '" << matrix_size << "' columns." << std::endl;
79 
80  hungarian->PrintCostmatrix();
81 
82  std::cout << "QAHungarian: calling solve on HungarianMethod object" << std::endl;
83  /* solve the assignement problem */
84  hungarian->Solve();
85 
86  hungarian->PrintAssignment();
87 
88  std::cout << "QAHungarian: calling free on HungarianMethod object" << std::endl;
89  /* free used memory */
90  hungarian->Free();
91 
92  free(m);
93 
94  return 0;
95 }
96