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 std::vector< unsigned >	AssignmentVectorType

Public Member Functions
	vnl_hungarian_algorithm ()

	~vnl_hungarian_algorithm ()=default

	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. More...

	operator std::vector< unsigned > ()

void	SetCostMatrix (vnl_matrix< T > const &)
	Starts the assignment. More...

void	StartAssignment ()
	Starts the assignment. More...

T	GetTotalCost ()
	Returns the total cost of the assignment. More...

AssignmentMatrixType	GetAssignmentMatrix ()
	Returns the assignment matrix. More...

AssignmentVectorType	GetAssignmentVector ()
	Returns the assignment vector. More...

Protected Member Functions
STEP_TYPE	Step_0 ()
	Step 0 - Make sure there are at least as many rows as columns in the cost matrix. More...

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. More...

STEP_TYPE	Step_2 ()
	Step 2 - Find a zero (Z) in the resulting matrix. More...

STEP_TYPE	Step_3 ()
	Step 3 - Cover each column containing a starred zero. More...

STEP_TYPE	Step_4 ()
	Step 4: Find a noncovered zero and prime it. More...

STEP_TYPE	Step_5 ()
	Step 5 - Construct a series of alternating primed and starred zeros as follows. More...

STEP_TYPE	Step_6 ()
	Step 6 -. More...

void	Step_done ()
	Step done - Returns a vector containing the result of the assignment. More...

void	clear_vector (std::vector< bool > &)
	Sets all the values in the input bool vector to false. More...

Protected Attributes
vnl_matrix< T >	m_Cost

vnl_matrix< T >	m_Cost_in

unsigned	m_N
	Size of the input matrix. More...

unsigned	m_Z0_r
	Row and col of the primed zero in step four to pass to step five. More...

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 More...

std::vector< bool >	m_R_cov
	m_R_cov[i] = true => row i is covered. More...

std::vector< bool >	m_C_cov
	m_C_cov[j] = true => column j is covered. More...

T	m_TotalCost
	Total cost of the assignment. More...

AssignmentVectorType	m_AssignmentVector
	m_C_cov[j] = true => column j is covered. More...

Detailed Description

template<class T>
class vnl_hungarian_algorithm< T >

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).

Parameters

cost	An N x M cost matrix. The costs cannot be -Infinity.

Returns: A vector v of size N such that v[i] = j means that row i should be assigned to column j.
v[i] = -1u
(=
unsigned(-1)
) means that row i was not assigned to any column. If N > M, then every column will be assigned to some row. If N < M then every row will be assigned to some column.

Definition at line 34 of file vnl_hungarian_algorithm.h.

Member Typedef Documentation

◆ AssignmentMatrixType

template<class T>

typedef vnl_matrix< int > vnl_hungarian_algorithm< T >::AssignmentMatrixType

Definition at line 57 of file vnl_hungarian_algorithm.h.

◆ AssignmentVectorType

template<class T>

typedef std::vector<unsigned> vnl_hungarian_algorithm< T >::AssignmentVectorType

Definition at line 58 of file vnl_hungarian_algorithm.h.

Member Enumeration Documentation

◆ STATE_TYPE

template<class T>

enum vnl_hungarian_algorithm::STATE_TYPE

Enumerator
NORMAL
STAR
PRIME

Definition at line 51 of file vnl_hungarian_algorithm.h.

◆ STEP_TYPE

template<class T>

enum vnl_hungarian_algorithm::STEP_TYPE

Enumerator
STEP_0
STEP_1
STEP_2
STEP_3
STEP_4
STEP_5
STEP_6
STEP_done

Definition at line 40 of file vnl_hungarian_algorithm.h.

Constructor & Destructor Documentation

◆ vnl_hungarian_algorithm() [1/2]

template<class T>

vnl_hungarian_algorithm< T >::vnl_hungarian_algorithm ( )

inline

Definition at line 60 of file vnl_hungarian_algorithm.h.

◆ ~vnl_hungarian_algorithm()

template<class T>

vnl_hungarian_algorithm< T >::~vnl_hungarian_algorithm ( )

default

◆ vnl_hungarian_algorithm() [2/2]

template<class T>

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 65 of file vnl_hungarian_algorithm.h.

Member Function Documentation

◆ clear_vector()

template<class T >

void vnl_hungarian_algorithm< T >::clear_vector ( std::vector< bool > & v )

protected

Sets all the values in the input bool vector to false.

Definition at line 51 of file vnl_hungarian_algorithm.hxx.

◆ GetAssignmentMatrix()

template<class T >

vnl_hungarian_algorithm< T >::AssignmentMatrixType vnl_hungarian_algorithm< T >::GetAssignmentMatrix ( )

Returns the assignment matrix.

Definition at line 515 of file vnl_hungarian_algorithm.hxx.

◆ GetAssignmentVector()

template<class T >

vnl_hungarian_algorithm< T >::AssignmentVectorType vnl_hungarian_algorithm< T >::GetAssignmentVector ( )

Returns the assignment vector.

Definition at line 525 of file vnl_hungarian_algorithm.hxx.

◆ GetTotalCost()

template<class T >

T vnl_hungarian_algorithm< T >::GetTotalCost ( )

Returns the total cost of the assignment.

Definition at line 505 of file vnl_hungarian_algorithm.hxx.

◆ operator std::vector< unsigned >()

template<class T>

vnl_hungarian_algorithm< T >::operator std::vector< unsigned > ( )

inline

Definition at line 66 of file vnl_hungarian_algorithm.h.

◆ SetCostMatrix()

template<class T>

void vnl_hungarian_algorithm< T >::SetCostMatrix ( vnl_matrix< T > const & cost_in )

Starts the assignment.

Definition at line 25 of file vnl_hungarian_algorithm.hxx.

◆ StartAssignment()

template<class T >

void vnl_hungarian_algorithm< T >::StartAssignment ( )

Starts the assignment.

Definition at line 67 of file vnl_hungarian_algorithm.hxx.

◆ Step_0()

template<class T >

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.

Returns: the next step to go to (which is Step 1).

Definition at line 156 of file vnl_hungarian_algorithm.hxx.

◆ Step_1()

template<class T >

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.

Returns: the next step to go to (which is Step 2).

Definition at line 180 of file vnl_hungarian_algorithm.hxx.

◆ Step_2()

template<class T >

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.

Returns: the next step to go to (which is Step 3)

Definition at line 211 of file vnl_hungarian_algorithm.hxx.

◆ Step_3()

template<class T >

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.

Returns: the next step to go to

Definition at line 244 of file vnl_hungarian_algorithm.hxx.

◆ Step_4()

template<class T >

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.

Returns: the next step to go to

Definition at line 280 of file vnl_hungarian_algorithm.hxx.

◆ Step_5()

template<class T >

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.

Returns: the next step to go to

Definition at line 344 of file vnl_hungarian_algorithm.hxx.

◆ Step_6()

template<class T >

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.

Returns: the next step to go to

Definition at line 433 of file vnl_hungarian_algorithm.hxx.

◆ Step_done()

template<class T >

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 479 of file vnl_hungarian_algorithm.hxx.

Member Data Documentation

◆ m_AssignmentVector

template<class T>

AssignmentVectorType vnl_hungarian_algorithm< T >::m_AssignmentVector

protected

m_C_cov[j] = true => column j is covered.

Definition at line 167 of file vnl_hungarian_algorithm.h.

◆ m_C_cov

template<class T>

std::vector<bool> vnl_hungarian_algorithm< T >::m_C_cov

protected

m_C_cov[j] = true => column j is covered.

Definition at line 161 of file vnl_hungarian_algorithm.h.

◆ m_Cost

template<class T>

vnl_matrix<T> vnl_hungarian_algorithm< T >::m_Cost

protected

Definition at line 143 of file vnl_hungarian_algorithm.h.

◆ m_Cost_in

template<class T>

vnl_matrix<T> vnl_hungarian_algorithm< T >::m_Cost_in

protected

Definition at line 144 of file vnl_hungarian_algorithm.h.

◆ m_M

template<class T>

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 155 of file vnl_hungarian_algorithm.h.

◆ m_N

template<class T>

unsigned vnl_hungarian_algorithm< T >::m_N

protected

Size of the input matrix.

Definition at line 147 of file vnl_hungarian_algorithm.h.

◆ m_R_cov

template<class T>

std::vector<bool> vnl_hungarian_algorithm< T >::m_R_cov

protected

m_R_cov[i] = true => row i is covered.

Definition at line 158 of file vnl_hungarian_algorithm.h.

◆ m_TotalCost

template<class T>

T vnl_hungarian_algorithm< T >::m_TotalCost

protected

Total cost of the assignment.

Definition at line 164 of file vnl_hungarian_algorithm.h.

◆ m_Z0_c

template<class T>

unsigned vnl_hungarian_algorithm< T >::m_Z0_c

protected

Definition at line 150 of file vnl_hungarian_algorithm.h.

◆ m_Z0_r

template<class T>

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 150 of file vnl_hungarian_algorithm.h.

The documentation for this class was generated from the following files:

core/vnl/vnl_hungarian_algorithm.h
core/vnl/vnl_hungarian_algorithm.hxx

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class T> class vnl_hungarian_algorithm< T >

Member Typedef Documentation

◆ AssignmentMatrixType

◆ AssignmentVectorType

Member Enumeration Documentation

◆ STATE_TYPE

◆ STEP_TYPE

Constructor & Destructor Documentation

◆ vnl_hungarian_algorithm() [1/2]

◆ ~vnl_hungarian_algorithm()

◆ vnl_hungarian_algorithm() [2/2]

Member Function Documentation

◆ clear_vector()

◆ GetAssignmentMatrix()

◆ GetAssignmentVector()

◆ GetTotalCost()

◆ operator std::vector< unsigned >()

◆ SetCostMatrix()

◆ StartAssignment()

◆ Step_0()

◆ Step_1()

◆ Step_2()

◆ Step_3()

◆ Step_4()

◆ Step_5()

◆ Step_6()

◆ Step_done()

Member Data Documentation

◆ m_AssignmentVector

◆ m_C_cov

◆ m_Cost

◆ m_Cost_in

◆ m_M

◆ m_N

◆ m_R_cov

◆ m_TotalCost

◆ m_Z0_c

◆ m_Z0_r

template<class T>
class vnl_hungarian_algorithm< T >