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
47int **
48array_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
61int
62main(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}