vpMunkres Class Reference

#include <visp3/core/vpMunkres.h>

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

Public Member Functions
template<typename Type >
void	padCostMatrix (std::vector< std::vector< Type > > &costs)
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.

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

padCostMatrix()

template<typename Type >

void vpMunkres::padCostMatrix ( std::vector< std::vector< Type > > &  costs )

inline

Ensure that the cost matrix is square by the addition of dummy rows/columns.

Parameters

[in,out]

costs

Cost matrix.

Definition at line 128 of file vpMunkres.h.

References vpMath::equal().

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:

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

Definition at line 321 of file vpMunkres.h.

Referenced by std::operator<<().

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