40 #include <visp3/core/vpMunkres.h>
43 #if ((__cplusplus >= 201703L) || (defined(_MSVC_LANG) && (_MSVC_LANG >= 201703L)))
52 std::optional<unsigned int> vpMunkres::findStarInRow(
const std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
53 const unsigned int &row)
55 const auto it = std::find(begin(mask.at(row)), end(mask.at(row)), vpMunkres::ZERO_T::STARRED);
56 return it != end(mask.at(row)) ? std::make_optional<unsigned int>(std::distance(begin(mask.at(row)), it))
67 std::optional<unsigned int> vpMunkres::findStarInCol(
const std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
68 const unsigned int &col)
70 const auto it = std::find_if(begin(mask), end(mask),
71 [&col](
const auto &row) {
return row.at(col) == vpMunkres::ZERO_T::STARRED; });
72 return it != end(mask) ? std::make_optional<unsigned int>(std::distance(begin(mask), it)) : std::nullopt;
82 std::optional<unsigned int> vpMunkres::findPrimeInRow(
const std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
83 const unsigned int &row)
85 const auto it = std::find(begin(mask.at(row)), end(mask.at(row)), vpMunkres::ZERO_T::PRIMED);
86 return it != end(mask.at(row)) ? std::make_optional<unsigned int>(std::distance(begin(mask.at(row)), it))
96 void vpMunkres::augmentPath(std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
97 const std::vector<std::pair<unsigned int, unsigned int> > &path)
99 for (
const auto &[row, col] : path) {
100 mask.at(row).at(col) =
101 mask.at(row).at(col) == vpMunkres::ZERO_T::STARRED ? vpMunkres::ZERO_T::NA : vpMunkres::ZERO_T::STARRED;
111 void vpMunkres::clearCovers(std::vector<bool> &row_cover, std::vector<bool> &col_cover)
113 row_cover = std::vector<bool>(row_cover.size(),
false);
114 col_cover = std::vector<bool>(col_cover.size(),
false);
122 void vpMunkres::erasePrimes(std::vector<std::vector<vpMunkres::ZERO_T> > &mask)
124 std::for_each(begin(mask), end(mask), [](
auto &mask_row) {
125 std::for_each(begin(mask_row), end(mask_row), [](
auto &val) {
126 if (val == vpMunkres::ZERO_T::PRIMED)
127 val = vpMunkres::ZERO_T::NA;
141 vpMunkres::STEP_T vpMunkres::stepThree(
const std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
142 std::vector<bool> &col_cover)
144 for (
const auto &mask_row : mask) {
145 for (
auto col = 0u; col < mask_row.size(); col++) {
146 if (mask_row.at(col) == vpMunkres::ZERO_T::STARRED) {
147 col_cover.at(col) =
true;
152 const unsigned int col_count =
static_cast<unsigned int>(std::count(begin(col_cover), end(col_cover),
true));
153 return col_count >= mask.size() ? vpMunkres::STEP_T::DONE : vpMunkres::STEP_T(4);
171 vpMunkres::STEP_T vpMunkres::stepFive(std::vector<std::vector<vpMunkres::ZERO_T> > &mask,
172 const std::pair<unsigned int, unsigned int> &path_0, std::vector<bool> &row_cover,
173 std::vector<bool> &col_cover)
175 std::vector<std::pair<unsigned int, unsigned int> > path { path_0 };
178 if (
const auto star_in_col = findStarInCol(mask, path.back().second)) {
179 path.emplace_back(*star_in_col, path.back().second);
182 augmentPath(mask, path);
184 clearCovers(row_cover, col_cover);
186 return vpMunkres::STEP_T(3);
189 if (
const auto prime_in_row = findPrimeInRow(mask, path.back().first)) {
190 path.emplace_back(path.back().first, *prime_in_row);