34 #include <visp3/core/vpMunkres.h>
37 #if ((__cplusplus >= 201703L) || (defined(_MSVC_LANG) && (_MSVC_LANG >= 201703L)))
47 std::optional<unsigned int> vpMunkres::findStarInRow(
const std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
48 const unsigned int &row)
50 const auto it = std::find(begin(mask.at(row)), end(mask.at(row)), vpMunkres::ZERO_T::STARRED);
51 return it != end(mask.at(row)) ? std::make_optional<unsigned int>(
static_cast<unsigned int>(std::distance(begin(mask.at(row)), it)))
62 std::optional<unsigned int> vpMunkres::findStarInCol(
const std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
63 const unsigned int &col)
65 const auto it = std::find_if(begin(mask), end(mask),
66 [&col](
const auto &row) {
return row.at(col) == vpMunkres::ZERO_T::STARRED; });
67 return it != end(mask) ? std::make_optional<unsigned int>(
static_cast<unsigned int>(std::distance(begin(mask), it)))
78 std::optional<unsigned int> vpMunkres::findPrimeInRow(
const std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
79 const unsigned int &row)
81 const auto it = std::find(begin(mask.at(row)), end(mask.at(row)), vpMunkres::ZERO_T::PRIMED);
82 return it != end(mask.at(row))
83 ? std::make_optional<unsigned int>(
static_cast<unsigned int>(std::distance(begin(mask.at(row)), it)))
93 void vpMunkres::augmentPath(std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
94 const std::vector<std::pair<unsigned int, unsigned int> > &path)
96 for (
const auto &[row, col] : path) {
97 mask.at(row).at(col) =
98 mask.at(row).at(col) == vpMunkres::ZERO_T::STARRED ? vpMunkres::ZERO_T::NA : vpMunkres::ZERO_T::STARRED;
108 void vpMunkres::clearCovers(std::vector<bool> &row_cover, std::vector<bool> &col_cover)
110 row_cover = std::vector<bool>(row_cover.size(),
false);
111 col_cover = std::vector<bool>(col_cover.size(),
false);
119 void vpMunkres::erasePrimes(std::vector<std::vector<vpMunkres::ZERO_T> > &mask)
121 std::for_each(begin(mask), end(mask), [](
auto &mask_row) {
122 std::for_each(begin(mask_row), end(mask_row), [](
auto &val) {
123 if (val == vpMunkres::ZERO_T::PRIMED)
124 val = vpMunkres::ZERO_T::NA;
138 vpMunkres::STEP_T vpMunkres::stepThree(
const std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
139 std::vector<bool> &col_cover)
141 for (
const auto &mask_row : mask) {
142 for (
auto col = 0u; col < mask_row.size(); col++) {
143 if (mask_row.at(col) == vpMunkres::ZERO_T::STARRED) {
144 col_cover.at(col) =
true;
149 const unsigned int col_count =
static_cast<unsigned int>(std::count(begin(col_cover), end(col_cover),
true));
150 return col_count >= mask.size() ? vpMunkres::STEP_T::DONE :
vpMunkres::STEP_T(4);
168 vpMunkres::STEP_T vpMunkres::stepFive(std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
169 const std::pair<unsigned int, unsigned int> &path_0, std::vector<bool> &row_cover,
170 std::vector<bool> &col_cover)
172 std::vector<std::pair<unsigned int, unsigned int> > path { path_0 };
175 if (
const auto star_in_col = findStarInCol(mask, path.back().second)) {
176 path.emplace_back(*star_in_col, path.back().second);
179 augmentPath(mask, path);
181 clearCovers(row_cover, col_cover);
186 if (
const auto prime_in_row = findPrimeInRow(mask, path.back().first)) {
187 path.emplace_back(path.back().first, *prime_in_row);