00001 #ifndef vnl_hungarian_algorithm_h_ 00002 #define vnl_hungarian_algorithm_h_ 00003 //: 00004 // \file 00005 // \author Amitha Perera 00006 // \date Sep 2004 00007 // Refactored by Nicolas Rannou (Harvard), Oct 2010, such that the algorithm 00008 // presents itself in a templated and more object-oriented manner. 00009 00010 #include <vcl_vector.h> 00011 #include <vnl/vnl_matrix.h> 00012 00013 //: Find the best column to row assignment given a cost matrix. 00014 // 00015 // This is an implementation of the Hungarian algorithm (also known 00016 // as the Munkres algorithm). It finds the minimum cost assignment of 00017 // the rows of the cost matrix \a cost (workers) to the columns 00018 // (jobs). 00019 // 00020 // \param cost An N x M cost matrix. The costs cannot be -Infinity. 00021 // 00022 // \returns A vector v of size N such that v[i] = j means that row i 00023 // should be assigned to column j. \code v[i] = -1u \endcode (= \code 00024 // unsigned(-1) \endcode ) means that row i was not assigned to any 00025 // column. If N > M, then every column will be assigned to some 00026 // row. If N < M then every row will be assigned to some column. 00027 // 00028 // \relatesalso vnl_matrix 00029 template <class T> 00030 class vnl_hungarian_algorithm 00031 { 00032 public: 00033 00034 // The steps of the algorithm described below are taken from 00035 // http://www.cs.duke.edu/brd/Teaching/Bio/asmb/current/Handouts/munkres.html 00036 enum STEP_TYPE { 00037 STEP_0 = 0, 00038 STEP_1, 00039 STEP_2, 00040 STEP_3, 00041 STEP_4, 00042 STEP_5, 00043 STEP_6, 00044 STEP_done 00045 }; 00046 00047 enum STATE_TYPE { 00048 NORMAL=0, 00049 STAR, 00050 PRIME 00051 }; 00052 00053 typedef vnl_matrix< int > AssignmentMatrixType; 00054 typedef vcl_vector<unsigned> AssignmentVectorType; 00055 00056 vnl_hungarian_algorithm() : m_TotalCost(0) {} 00057 00058 ~vnl_hungarian_algorithm() {} 00059 00060 //: This constructor (and the following cast operator) is provided for backward compatibility with the original function implementation 00061 vnl_hungarian_algorithm(vnl_matrix<T> const& cost) { SetCostMatrix(cost); StartAssignment(); } 00062 operator vcl_vector<unsigned>() { return GetAssignmentVector(); } 00063 00064 //: Starts the assignment 00065 void SetCostMatrix( vnl_matrix< T > const& ); 00066 00067 //: Starts the assignment 00068 void StartAssignment(); 00069 00070 //: Returns the total cost of the assignment 00071 T GetTotalCost(); 00072 00073 //: Returns the assignment matrix 00074 AssignmentMatrixType GetAssignmentMatrix(); 00075 00076 //: Returns the assignment vector 00077 AssignmentVectorType GetAssignmentVector(); 00078 00079 protected: 00080 //: Step 0 - Make sure there are at least as many rows as columns in the cost matrix 00081 // The nxm cost matrix is a matrix in which each element represents 00082 // the cost of assigning one of n workers to one of m jobs. 00083 // \returns the next step to go to (which is Step 1). 00084 STEP_TYPE Step_0(); 00085 00086 //: Step 1 - For each row of the matrix, find the smallest element and subtract it from every element in its row. 00087 // \returns the next step to go to (which is Step 2). 00088 STEP_TYPE Step_1(); 00089 00090 //: Step 2 - Find a zero (Z) in the resulting matrix. 00091 // If there is no starred zero in its row or column, star Z. 00092 // Repeat for each element in the matrix. 00093 // \returns the next step to go to (which is Step 3) 00094 STEP_TYPE Step_2(); 00095 00096 //: Step 3 - Cover each column containing a starred zero. 00097 // If K columns are covered, the starred zeros describe a complete 00098 // set of unique assignments. 00099 // In this case, Go to DONE, otherwise, Go to Step 4. 00100 // \returns the next step to go to 00101 STEP_TYPE Step_3(); 00102 00103 //: Step 4: Find a noncovered zero and prime it. 00104 // If there is no starred zero in the row containing this primed zero, Go to Step 5. 00105 // Otherwise, cover this row and uncover the column containing the starred 00106 // zero. Continue in this manner until there are no uncovered zeros left. 00107 // Save the smallest uncovered value and Go to Step 6. 00108 // \returns the next step to go to 00109 STEP_TYPE Step_4(); 00110 00111 //: Step 5 - Construct a series of alternating primed and starred zeros as follows. 00112 // Let Z0 represent the uncovered primed zero found in Step 4. 00113 // Let Z1 denote the starred zero in the column of Z0 (if any). 00114 // Let Z2 denote the primed zero in the row of Z1 (there will always be 00115 // one). Continue until the series terminates at a primed zero that has 00116 // no starred zero in its column. Unstar each starred zero of the series, 00117 // star each primed zero of the series, erase all primes and uncover every 00118 // line in the matrix. Return to Step 3. 00119 // \returns the next step to go to 00120 STEP_TYPE Step_5(); 00121 00122 //: Step 6 - 00123 // Add the value found in Step 4 to every element of each covered row, 00124 // and subtract it from every element of each uncovered column. 00125 // Return to Step 4 without altering any stars, primes, or covered lines. 00126 // \returns the next step to go to 00127 STEP_TYPE Step_6(); 00128 00129 //: Step done - Returns a vector containing the result of the assignment. 00130 // Assignment pairs are indicated by the positions of the 00131 // starred zeros in the cost matrix. If C(i,j) is a starred zero, 00132 // then the element associated with row i is assigned to the element 00133 // associated with column j. 00134 void Step_done(); 00135 00136 //: Sets all the values in the input bool vector to false. 00137 void clear_vector( vcl_vector<bool>& ); 00138 00139 vnl_matrix<T> m_Cost; 00140 vnl_matrix<T> m_Cost_in; 00141 00142 //: Size of the input matrix 00143 unsigned m_N; 00144 00145 //: Row and col of the primed zero in step four to pass to step five. 00146 unsigned m_Z0_r, m_Z0_c; 00147 00148 //: 00149 // m_M(i,j) = 1 => m_Cost(i,j) is starred 00150 // m_M(i,j) = 2 => m_Cost(i,j) is primed 00151 AssignmentMatrixType m_M; 00152 00153 //: m_R_cov[i] = true => row i is covered 00154 vcl_vector<bool> m_R_cov; 00155 00156 //: m_C_cov[j] = true => column j is covered 00157 vcl_vector<bool> m_C_cov; 00158 00159 //: Total cost of the assignment 00160 T m_TotalCost; 00161 00162 //: m_C_cov[j] = true => column j is covered 00163 AssignmentVectorType m_AssignmentVector; 00164 }; 00165 00166 #define VNL_HUNGARIAN_ALGORITHM_INSTANTIATE(T) extern "please #include vnl/vnl_hungarian_algorithm.txx instead" 00167 00168 #endif // vnl_hungarian_algorithm_h_