00001 /* 00002 * Copyright (c) 2007 John Weaver 00003 * 00004 * This program is free software; you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation; either version 2 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program; if not, write to the Free Software 00016 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00017 */ 00018 00019 #if !defined(_MUNKRES_H_) 00020 #define _MUNKRES_H_ 00021 00022 #include "matrix.h" 00023 00024 #include <list> 00025 #include <utility> 00026 00027 00028 class Munkres { 00029 public: 00030 void solve(Matrix<double> &m); 00031 private: 00032 static const int NORMAL = 0; 00033 static const int STAR = 1; 00034 static const int PRIME = 2; 00035 inline bool find_uncovered_in_matrix(double, unsigned int&, unsigned int&) const; 00036 inline bool pair_in_list(const std::pair<int,int> &, const std::list<std::pair<int,int> > &); 00037 int step1(void); 00038 int step2(void); 00039 int step3(void); 00040 int step4(void); 00041 int step5(void); 00042 int step6(void); 00043 00044 Matrix<int> mask_matrix; 00045 Matrix<double> matrix; 00046 bool *row_mask; 00047 bool *col_mask; 00048 unsigned int saverow, savecol; 00049 }; 00050 00051 #endif /* !defined(_MUNKRES_H_) */