SHOGUN
v2.0.0
|
00001 /* 00002 * Copyright (c) 2007 John Weaver 00003 * 00004 * 2012: Ported to shogun by Chiyuan Zhang 00005 * 00006 * This program is free software; you can redistribute it and/or modify 00007 * it under the terms of the GNU General Public License as published by 00008 * the Free Software Foundation; either version 2 of the License, or 00009 * (at your option) any later version. 00010 * 00011 * This program is distributed in the hope that it will be useful, 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 * GNU General Public License for more details. 00015 * 00016 * You should have received a copy of the GNU General Public License 00017 * along with this program; if not, write to the Free Software 00018 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00019 */ 00020 00021 #if !defined(_MUNKRES_H_) 00022 #define _MUNKRES_H_ 00023 00024 #include <shogun/lib/DataType.h> 00025 #include <shogun/lib/SGMatrix.h> 00026 00027 #include <list> 00028 #include <utility> 00029 00030 namespace shogun 00031 { 00032 00034 class Munkres 00035 { 00036 public: 00038 Munkres(SGMatrix<double> &m) 00039 :mask_matrix(m.num_rows, m.num_cols, true), matrix(m.num_rows, m.num_cols, true), ref_m(m) 00040 { 00041 } 00042 00044 void solve() 00045 { 00046 solve(ref_m); 00047 } 00048 00050 ~Munkres() 00051 { 00052 } 00053 00054 private: 00055 static const int NORMAL=0; 00056 static const int STAR=1; 00057 static const int PRIME=2; 00058 00059 void solve(SGMatrix<double> &m); 00060 00061 inline bool find_uncovered_in_matrix(double,int&,int&); 00062 inline bool pair_in_list(const std::pair<int,int> &, const std::list<std::pair<int,int> > &); 00063 int step1(void); 00064 int step2(void); 00065 int step3(void); 00066 int step4(void); 00067 int step5(void); 00068 int step6(void); 00069 SGMatrix<int> mask_matrix; 00070 SGMatrix<double> matrix; 00071 bool *row_mask; 00072 bool *col_mask; 00073 int saverow, savecol; 00074 00075 SGMatrix<double> &ref_m; 00076 }; 00077 00078 } // namespace shogun 00079 00080 #endif /* !defined(_MUNKRES_H_) */