vpMunkres Class Reference

#include <vpMunkres.h>

Public Types
enum	ZERO_T : unsigned int
enum	STEP_T : unsigned int

Public Member Functions
template<typename Type>
vpMunkres::STEP_T	stepTwo (std::vector< std::vector< Type > > &costs, std::vector< std::vector< vpMunkres::ZERO_T > > &mask, std::vector< bool > &row_cover, std::vector< bool > &col_cover)
template<typename Type>
std::tuple< vpMunkres::STEP_T, std::optional< std::pair< unsigned int, unsigned int > > >	stepFour (const std::vector< std::vector< Type > > &costs, std::vector< std::vector< vpMunkres::ZERO_T > > &mask, std::vector< bool > &row_cover, std::vector< bool > &col_cover)

Static Public Member Functions
template<typename Type>
static std::vector< std::pair< unsigned int, unsigned int > >	run (std::vector< std::vector< Type > > costs)

Detailed Description

Implements the Munkres Assignment Algorithm described here.

Note

This class is only available with c++17 enabled.

Tutorials & Examples

Tutorials
If you are interested in using using the Munkres algorithm, you may have a look at:

• Tutorial: Munkres Assignment Algorithm

Definition at line 65 of file vpMunkres.h.

Member Enumeration Documentation

STEP_T

enum vpMunkres::STEP_T : unsigned int

Definition at line 121 of file vpMunkres.h.

ZERO_T

enum vpMunkres::ZERO_T : unsigned int

Definition at line 119 of file vpMunkres.h.

Member Function Documentation

run()

template<typename Type>

std::vector< std::pair< unsigned int, unsigned int > > vpMunkres::run ( std::vector< std::vector< Type > > costs )

inlinestatic

Munkres FSM.

Parameters

[in]

costs

: Cost matrix.

Returns

List of associated pairs [<row_idx,col_idx>].

Examples

catchMunkres.cpp, and tutorial-munkres-assignment.cpp.

Definition at line 323 of file vpMunkres.h.

stepFour()

template<typename Type>

std::tuple< vpMunkres::STEP_T, std::optional< std::pair< unsigned int, unsigned int > > > vpMunkres::stepFour ( const std::vector< std::vector< Type > > & costs, std::vector< std::vector< vpMunkres::ZERO_T > > & mask, std::vector< bool > & row_cover, std::vector< bool > & col_cover )

inline

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. Go to Step 6.

Parameters

[in]	costs	: Cost matrix.
[in,out]	mask	: Mask matrix.
[in,out]	row_cover	: Row coverage array.
[in,out]	col_cover	: Col coverage array.

Returns

Tuple(Next step, pair(path_row_0 path_col_0)).

Definition at line 266 of file vpMunkres.h.

stepTwo()

template<typename Type>

vpMunkres::STEP_T vpMunkres::stepTwo ( std::vector< std::vector< Type > > & costs, std::vector< std::vector< vpMunkres::ZERO_T > > & mask, std::vector< bool > & row_cover, std::vector< bool > & col_cover )

inline

Find a zero (Z) in the cost matrix. If there is no starred zero in its row or column, star Z. Repeat for each element in the cost matrix. When finished, Go to Step 3.

Parameters

[in,out]	costs	: Cost matrix.
[in]	mask	: Mask matrix.
[in,out]	row_cover	: Row coverage array.
[in,out]	col_cover	: Col coverage array.

Returns

Next step.

Definition at line 232 of file vpMunkres.h.

References vpMath::equal().