Find the best column to row assignment given a cost matrix. More...
#include <vnl_hungarian_algorithm.h>
Public Types | |
| enum | STEP_TYPE { STEP_0 = 0, STEP_1, STEP_2, STEP_3, STEP_4, STEP_5, STEP_6, STEP_done } |
| enum | STATE_TYPE { NORMAL = 0, STAR, PRIME } |
| typedef vnl_matrix< int > | AssignmentMatrixType |
| typedef vcl_vector< unsigned > | AssignmentVectorType |
Public Member Functions | |
| vnl_hungarian_algorithm () | |
| ~vnl_hungarian_algorithm () | |
| vnl_hungarian_algorithm (vnl_matrix< T > const &cost) | |
| This constructor (and the following cast operator) is provided for backward compatibility with the original function implementation. | |
| operator vcl_vector< unsigned > () | |
| void | SetCostMatrix (vnl_matrix< T > const &) |
| Starts the assignment. | |
| void | StartAssignment () |
| Starts the assignment. | |
| T | GetTotalCost () |
| Returns the total cost of the assignment. | |
| AssignmentMatrixType | GetAssignmentMatrix () |
| Returns the assignment matrix. | |
| AssignmentVectorType | GetAssignmentVector () |
| Returns the assignment vector. | |
Protected Member Functions | |
| STEP_TYPE | Step_0 () |
| Step 0 - Make sure there are at least as many rows as columns in the cost matrix. | |
| STEP_TYPE | Step_1 () |
| Step 1 - For each row of the matrix, find the smallest element and subtract it from every element in its row. | |
| STEP_TYPE | Step_2 () |
| Step 2 - Find a zero (Z) in the resulting matrix. | |
| STEP_TYPE | Step_3 () |
| Step 3 - Cover each column containing a starred zero. | |
| STEP_TYPE | Step_4 () |
| Step 4: Find a noncovered zero and prime it. | |
| STEP_TYPE | Step_5 () |
| Step 5 - Construct a series of alternating primed and starred zeros as follows. | |
| STEP_TYPE | Step_6 () |
| Step 6 -. | |
| void | Step_done () |
| Step done - Returns a vector containing the result of the assignment. | |
| void | clear_vector (vcl_vector< bool > &) |
| Sets all the values in the input bool vector to false. | |
Protected Attributes | |
| vnl_matrix< T > | m_Cost |
| vnl_matrix< T > | m_Cost_in |
| unsigned | m_N |
| Size of the input matrix. | |
| unsigned | m_Z0_r |
| Row and col of the primed zero in step four to pass to step five. | |
| unsigned | m_Z0_c |
| AssignmentMatrixType | m_M |
| m_M(i,j) = 1 => m_Cost(i,j) is starred m_M(i,j) = 2 => m_Cost(i,j) is primed | |
| vcl_vector< bool > | m_R_cov |
| m_R_cov[i] = true => row i is covered. | |
| vcl_vector< bool > | m_C_cov |
| m_C_cov[j] = true => column j is covered. | |
| T | m_TotalCost |
| Total cost of the assignment. | |
| AssignmentVectorType | m_AssignmentVector |
| m_C_cov[j] = true => column j is covered. | |
Find the best column to row assignment given a cost matrix.
This is an implementation of the Hungarian algorithm (also known as the Munkres algorithm). It finds the minimum cost assignment of the rows of the cost matrix cost (workers) to the columns (jobs).
| cost | An N x M cost matrix. The costs cannot be -Infinity. |
v[i] = -1u
unsigned(-1)
Definition at line 30 of file vnl_hungarian_algorithm.h.
| typedef vnl_matrix< int > vnl_hungarian_algorithm< T >::AssignmentMatrixType |
Definition at line 53 of file vnl_hungarian_algorithm.h.
| typedef vcl_vector<unsigned> vnl_hungarian_algorithm< T >::AssignmentVectorType |
Definition at line 54 of file vnl_hungarian_algorithm.h.
| enum vnl_hungarian_algorithm::STATE_TYPE |
Definition at line 47 of file vnl_hungarian_algorithm.h.
| enum vnl_hungarian_algorithm::STEP_TYPE |
Definition at line 36 of file vnl_hungarian_algorithm.h.
| vnl_hungarian_algorithm< T >::vnl_hungarian_algorithm | ( | ) | [inline] |
Definition at line 56 of file vnl_hungarian_algorithm.h.
| vnl_hungarian_algorithm< T >::~vnl_hungarian_algorithm | ( | ) | [inline] |
Definition at line 58 of file vnl_hungarian_algorithm.h.
| vnl_hungarian_algorithm< T >::vnl_hungarian_algorithm | ( | vnl_matrix< T > const & | cost | ) | [inline] |
This constructor (and the following cast operator) is provided for backward compatibility with the original function implementation.
Definition at line 61 of file vnl_hungarian_algorithm.h.
| void vnl_hungarian_algorithm< T >::clear_vector | ( | vcl_vector< bool > & | v | ) | [protected] |
Sets all the values in the input bool vector to false.
Definition at line 48 of file vnl_hungarian_algorithm.txx.
| vnl_hungarian_algorithm< T >::AssignmentMatrixType vnl_hungarian_algorithm< T >::GetAssignmentMatrix | ( | ) |
Returns the assignment matrix.
Definition at line 512 of file vnl_hungarian_algorithm.txx.
| vnl_hungarian_algorithm< T >::AssignmentVectorType vnl_hungarian_algorithm< T >::GetAssignmentVector | ( | ) |
Returns the assignment vector.
Definition at line 522 of file vnl_hungarian_algorithm.txx.
| T vnl_hungarian_algorithm< T >::GetTotalCost | ( | ) |
Returns the total cost of the assignment.
Definition at line 502 of file vnl_hungarian_algorithm.txx.
| vnl_hungarian_algorithm< T >::operator vcl_vector< unsigned > | ( | ) | [inline] |
Definition at line 62 of file vnl_hungarian_algorithm.h.
| void vnl_hungarian_algorithm< T >::SetCostMatrix | ( | vnl_matrix< T > const & | cost_in | ) |
Starts the assignment.
Definition at line 22 of file vnl_hungarian_algorithm.txx.
| void vnl_hungarian_algorithm< T >::StartAssignment | ( | ) |
Starts the assignment.
Definition at line 64 of file vnl_hungarian_algorithm.txx.
| vnl_hungarian_algorithm< T >::STEP_TYPE vnl_hungarian_algorithm< T >::Step_0 | ( | ) | [protected] |
Step 0 - Make sure there are at least as many rows as columns in the cost matrix.
The nxm cost matrix is a matrix in which each element represents the cost of assigning one of n workers to one of m jobs.
Definition at line 153 of file vnl_hungarian_algorithm.txx.
| vnl_hungarian_algorithm< T >::STEP_TYPE vnl_hungarian_algorithm< T >::Step_1 | ( | ) | [protected] |
Step 1 - For each row of the matrix, find the smallest element and subtract it from every element in its row.
Definition at line 177 of file vnl_hungarian_algorithm.txx.
| vnl_hungarian_algorithm< T >::STEP_TYPE vnl_hungarian_algorithm< T >::Step_2 | ( | ) | [protected] |
Step 2 - Find a zero (Z) in the resulting matrix.
If there is no starred zero in its row or column, star Z. Repeat for each element in the matrix.
Definition at line 208 of file vnl_hungarian_algorithm.txx.
| vnl_hungarian_algorithm< T >::STEP_TYPE vnl_hungarian_algorithm< T >::Step_3 | ( | ) | [protected] |
Step 3 - Cover each column containing a starred zero.
If K columns are covered, the starred zeros describe a complete set of unique assignments. In this case, Go to DONE, otherwise, Go to Step 4.
Definition at line 241 of file vnl_hungarian_algorithm.txx.
| vnl_hungarian_algorithm< T >::STEP_TYPE vnl_hungarian_algorithm< T >::Step_4 | ( | ) | [protected] |
Step 4: Find a noncovered zero and prime it.
If there is no starred zero in the row containing this primed zero, Go to Step 5. Otherwise, cover this row and uncover the column containing the starred zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered value and Go to Step 6.
Definition at line 277 of file vnl_hungarian_algorithm.txx.
| vnl_hungarian_algorithm< T >::STEP_TYPE vnl_hungarian_algorithm< T >::Step_5 | ( | ) | [protected] |
Step 5 - Construct a series of alternating primed and starred zeros as follows.
Let Z0 represent the uncovered primed zero found in Step 4. Let Z1 denote the starred zero in the column of Z0 (if any). Let Z2 denote the primed zero in the row of Z1 (there will always be one). Continue until the series terminates at a primed zero that has no starred zero in its column. Unstar each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line in the matrix. Return to Step 3.
Definition at line 341 of file vnl_hungarian_algorithm.txx.
| vnl_hungarian_algorithm< T >::STEP_TYPE vnl_hungarian_algorithm< T >::Step_6 | ( | ) | [protected] |
Step 6 -.
Add the value found in Step 4 to every element of each covered row, and subtract it from every element of each uncovered column. Return to Step 4 without altering any stars, primes, or covered lines.
Definition at line 430 of file vnl_hungarian_algorithm.txx.
| void vnl_hungarian_algorithm< T >::Step_done | ( | ) | [protected] |
Step done - Returns a vector containing the result of the assignment.
Assignment pairs are indicated by the positions of the starred zeros in the cost matrix. If C(i,j) is a starred zero, then the element associated with row i is assigned to the element associated with column j.
Definition at line 476 of file vnl_hungarian_algorithm.txx.
AssignmentVectorType vnl_hungarian_algorithm< T >::m_AssignmentVector [protected] |
m_C_cov[j] = true => column j is covered.
Definition at line 163 of file vnl_hungarian_algorithm.h.
vcl_vector<bool> vnl_hungarian_algorithm< T >::m_C_cov [protected] |
m_C_cov[j] = true => column j is covered.
Definition at line 157 of file vnl_hungarian_algorithm.h.
vnl_matrix<T> vnl_hungarian_algorithm< T >::m_Cost [protected] |
Definition at line 139 of file vnl_hungarian_algorithm.h.
vnl_matrix<T> vnl_hungarian_algorithm< T >::m_Cost_in [protected] |
Definition at line 140 of file vnl_hungarian_algorithm.h.
AssignmentMatrixType vnl_hungarian_algorithm< T >::m_M [protected] |
m_M(i,j) = 1 => m_Cost(i,j) is starred m_M(i,j) = 2 => m_Cost(i,j) is primed
Definition at line 151 of file vnl_hungarian_algorithm.h.
unsigned vnl_hungarian_algorithm< T >::m_N [protected] |
Size of the input matrix.
Definition at line 143 of file vnl_hungarian_algorithm.h.
vcl_vector<bool> vnl_hungarian_algorithm< T >::m_R_cov [protected] |
m_R_cov[i] = true => row i is covered.
Definition at line 154 of file vnl_hungarian_algorithm.h.
T vnl_hungarian_algorithm< T >::m_TotalCost [protected] |
Total cost of the assignment.
Definition at line 160 of file vnl_hungarian_algorithm.h.
unsigned vnl_hungarian_algorithm< T >::m_Z0_c [protected] |
Definition at line 146 of file vnl_hungarian_algorithm.h.
unsigned vnl_hungarian_algorithm< T >::m_Z0_r [protected] |
Row and col of the primed zero in step four to pass to step five.
Definition at line 146 of file vnl_hungarian_algorithm.h.
1.7.5.1