Fawkes API  Fawkes Development Version
hungarian.h
1 
2 /***************************************************************************
3  * hungarian.h - Hungarian Method
4  *
5  * Created: Thu Apr 18 17:09:58 2013
6  * Copyright 2004 Cyrill Stachniss
7  * 2008 Masrur Doostdar
8  * 2008 Stefan Schiffer
9  * 2013 Tim Niemueller [www.niemueller.de]
10  ****************************************************************************/
11 
12 /* This program is free software; you can redistribute it and/or modify
13  * it under the terms of the GNU General Public License as published by
14  * the Free Software Foundation; either version 2 of the License, or
15  * (at your option) any later version. A runtime exception applies to
16  * this software (see LICENSE.GPL_WRE file mentioned below for details).
17  *
18  * This program is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21  * GNU Library General Public License for more details.
22  *
23  * Read the full text in the LICENSE.GPL_WRE file in the doc directory.
24  */
25 
26 #ifndef _UTILS_HUNGARIAN_METHOD_HUNGARIAN_H_
27 #define _UTILS_HUNGARIAN_METHOD_HUNGARIAN_H_
28 
29 #define HUNGARIAN_NOT_ASSIGNED 0
30 #define HUNGARIAN_ASSIGNED 1
31 
32 #define HUNGARIAN_MODE_MINIMIZE_COST 0
33 #define HUNGARIAN_MODE_MAXIMIZE_UTIL 1
34 
35 namespace fawkes {
36 
37 /// @cond INTERNAL
38 typedef struct
39 {
40  int num_rows;
41  int num_cols;
42  int **cost;
43  int **assignment;
44 } hungarian_problem_t;
45 /// @endcond
46 
48 {
49 public:
52 
53  int init(int **cost_matrix, int rows, int cols, int mode);
54 
55  void free();
56 
57  void solve();
58 
59  bool is_available();
60 
61  int get_column_assignment(const int &col);
62  int get_row_assignment(const int &row);
63  int *get_assignment(int &size);
64 
65  int **array_to_matrix(int *m, int rows, int cols);
66 
67  void print_assignment();
68  void print_cost_matrix();
69  void print_status();
70 
71  /** our problem instance member. */
72  hungarian_problem_t *p;
73 
74 protected:
75  void print_matrix(int **C, int rows, int cols);
76 
77 private:
78  bool available_;
79  int num_cols_;
80  int num_rows_;
81 
82  int *col_mates_;
83  int *row_mates_;
84 };
85 
86 } // end namespace fawkes
87 
88 #endif
Hungarian method assignment solver.
Definition: hungarian.h:48
void print_cost_matrix()
Print the cost matrix.
Definition: hungarian.cpp:122
~HungarianMethod()
Destructor.
Definition: hungarian.cpp:61
void free()
Free space alloacted by method.
Definition: hungarian.cpp:223
int get_row_assignment(const int &row)
Get row assignment.
Definition: hungarian.cpp:547
void print_assignment()
Print the assignment matrix.
Definition: hungarian.cpp:112
void print_matrix(int **C, int rows, int cols)
Print matrix to stdout.
Definition: hungarian.cpp:73
void print_status()
Print the current status.
Definition: hungarian.cpp:133
hungarian_problem_t * p
our problem instance member.
Definition: hungarian.h:72
int get_column_assignment(const int &col)
Get column assignment.
Definition: hungarian.cpp:533
HungarianMethod()
Constructor.
Definition: hungarian.cpp:52
int * get_assignment(int &size)
Get assignment and size.
Definition: hungarian.cpp:571
int init(int **cost_matrix, int rows, int cols, int mode)
Initialize hungarian method.
Definition: hungarian.cpp:147
int ** array_to_matrix(int *m, int rows, int cols)
Convert an array to a matrix.
Definition: hungarian.cpp:97
bool is_available()
Check if data is available.
Definition: hungarian.cpp:561
void solve()
Solve the assignment problem.
Definition: hungarian.cpp:248
Fawkes library namespace.