core/vnl/vnl_hungarian_algorithm.h
Go to the documentation of this file.
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_