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 #if 0 /* just to make Emacs auto-indent happy */
37 }
38 #endif
39 
40 /// @cond INTERNAL
41 typedef struct {
42  int num_rows;
43  int num_cols;
44  int** cost;
45  int** assignment;
46 } hungarian_problem_t;
47 /// @endcond
48 
50 {
51  public:
54 
55  int init( int** cost_matrix,
56  int rows, int cols, int mode);
57 
58  void free();
59 
60  void solve();
61 
62  bool is_available();
63 
64  int get_column_assignment( const int & col );
65  int get_row_assignment( const int & row );
66  int* get_assignment(int & size);
67 
68  int** array_to_matrix(int* m, int rows, int cols);
69 
70  void print_assignment();
71  void print_cost_matrix();
72  void print_status();
73 
74  /** our problem instance member. */
75  hungarian_problem_t * p;
76 
77  protected:
78  void print_matrix( int** C, int rows, int cols );
79 
80  private:
81  bool available_;
82  int num_cols_;
83  int num_rows_;
84 
85  int * col_mates_;
86  int * row_mates_;
87 };
88 
89 } // end namespace fawkes
90 
91 #endif
92 
93 
94 
int get_column_assignment(const int &col)
Get column assignment.
Definition: hungarian.cpp:552
int get_row_assignment(const int &row)
Get row assignment.
Definition: hungarian.cpp:567
void print_status()
Print the current status.
Definition: hungarian.cpp:134
void print_matrix(int **C, int rows, int cols)
Print matrix to stdout.
Definition: hungarian.cpp:72
~HungarianMethod()
Destructor.
Definition: hungarian.cpp:61
void solve()
Solve the assignment problem.
Definition: hungarian.cpp:251
Fawkes library namespace.
bool is_available()
Check if data is available.
Definition: hungarian.cpp:581
hungarian_problem_t * p
our problem instance member.
Definition: hungarian.h:75
Hungarian method assignment solver.
Definition: hungarian.h:49
void print_cost_matrix()
Print the cost matrix.
Definition: hungarian.cpp:123
void print_assignment()
Print the assignment matrix.
Definition: hungarian.cpp:113
int init(int **cost_matrix, int rows, int cols, int mode)
Initialize hungarian method.
Definition: hungarian.cpp:148
int * get_assignment(int &size)
Get assignment and size.
Definition: hungarian.cpp:592
void free()
Free space alloacted by method.
Definition: hungarian.cpp:225
HungarianMethod()
Constructor.
Definition: hungarian.cpp:52
int ** array_to_matrix(int *m, int rows, int cols)
Convert an array to a matrix.
Definition: hungarian.cpp:96