Visual Servoing Platform  version 3.5.1 under development (2022-11-26)

#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]costsCost matrix.

Definition at line 128 of file vpMunkres.h.

◆ 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]costsCost 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.

◆ 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]costsCost matrix.
[in,out]maskMask matrix.
[in,out]row_coverRow coverage array.
[in,out]col_coverCol 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]costsCost matrix.
[in]maskMask matrix.
[in,out]row_coverRow coverage array.
[in,out]col_coverCol coverage array.
Returns
Next step.

Definition at line 232 of file vpMunkres.h.

References vpMath::equal().