41 #include <visp3/core/vpMunkres.h>
44 #if ((__cplusplus >= 201703L) || (defined(_MSVC_LANG) && (_MSVC_LANG >= 201703L)))
49 #ifndef DOXYGEN_SHOULD_SKIP_THIS
54 ostream &operator<<(ostream &os,
const pair<unsigned int, unsigned int> &val)
56 os <<
"[" << val.first <<
"," << val.second <<
"]";
62 #ifdef VISP_HAVE_CATCH2
63 #define CATCH_CONFIG_RUNNER
66 TEST_CASE(
"Check Munkres-based assignment",
"[visp_munkres]")
68 auto testMunkres = [](
const std::vector<std::vector<double> > &cost_matrix,
69 const std::vector<std::pair<unsigned int, unsigned int> > &expected_pairs) {
70 const auto munkres_pairs = vpMunkres::run(cost_matrix);
71 REQUIRE(expected_pairs.size() == munkres_pairs.size());
72 for (
auto i = 0u; i < munkres_pairs.size(); i++) {
73 REQUIRE(expected_pairs.at(i) == munkres_pairs.at(i));
77 SECTION(
"Square cost matrix")
79 std::vector<std::vector<double> > costs {};
80 costs.push_back(std::vector<double>{3, 1, 2});
81 costs.push_back(std::vector<double>{2, 3, 1});
82 costs.push_back(std::vector<double>{1, 2, 3});
84 std::vector<std::pair<unsigned int, unsigned int> > expected_pairs {};
85 expected_pairs.emplace_back(0, 1);
86 expected_pairs.emplace_back(1, 2);
87 expected_pairs.emplace_back(2, 0);
89 testMunkres(costs, expected_pairs);
92 SECTION(
"Horizontal cost matrix")
94 std::vector<std::vector<double> > costs {};
95 costs.push_back(std::vector<double>{4, 1, 2, 3});
96 costs.push_back(std::vector<double>{3, 4, 1, 2});
97 costs.push_back(std::vector<double>{2, 3, 4, 1});
99 std::vector<std::pair<unsigned int, unsigned int> > expected_pairs {};
100 expected_pairs.emplace_back(0, 1);
101 expected_pairs.emplace_back(1, 2);
102 expected_pairs.emplace_back(2, 3);
104 testMunkres(costs, expected_pairs);
107 SECTION(
"Vertical cost matrix")
109 std::vector<std::vector<double> > costs {};
110 costs.push_back(std::vector<double>{4, 1, 2});
111 costs.push_back(std::vector<double>{3, 4, 1});
112 costs.push_back(std::vector<double>{2, 3, 4});
113 costs.push_back(std::vector<double>{1, 2, 3});
115 std::vector<std::pair<unsigned int, unsigned int> > expected_pairs {};
116 expected_pairs.emplace_back(0, 1);
117 expected_pairs.emplace_back(1, 2);
118 expected_pairs.emplace_back(3, 0);
120 testMunkres(costs, expected_pairs);
124 int main(
int argc,
char *argv[])
126 Catch::Session session;
127 session.applyCommandLine(argc, argv);
129 return session.run();
134 bool testMunkres(
const std::vector<std::vector<double> > &costs_matrix,
135 const std::vector<std::pair<unsigned int, unsigned int> > &expected_pairs)
137 const auto pairs = vpMunkres::run(costs_matrix);
139 if (pairs.size() != expected_pairs.size()) {
141 std::cerr <<
"Expected nb of association | Munkres nb of association: "
142 << expected_pairs.size() <<
" | " << pairs.size()
148 for (
auto i = 0u; i < pairs.size(); i++) {
149 if (expected_pairs.at(i) != pairs.at(i)) {
152 std::cout <<
"Cost matrix:" << std::endl;
153 for (
const auto &cost_row : costs_matrix) {
155 for (
const auto &cost : cost_row) {
156 std::cout << cost <<
" | ";
158 std::cout << std::endl;
160 std::cout << std::endl;
163 std::cerr <<
"FAIL: "
164 <<
"Expected association | Munkres association: " << expected_pairs.at(i) <<
" | " << pairs.at(i)
176 std::vector<std::vector<double> > costs {};
177 costs.push_back(std::vector<double>{3, 4, 1, 2});
178 costs.push_back(std::vector<double>{3, 4, 2, 1});
179 costs.push_back(std::vector<double>{1, 2, 3, 4});
180 costs.push_back(std::vector<double>{2, 1, 4, 3});
182 std::vector<std::pair<unsigned int, unsigned int> > pairs {};
183 pairs.emplace_back(0, 2);
184 pairs.emplace_back(1, 3);
185 pairs.emplace_back(2, 0);
186 pairs.emplace_back(3, 1);
188 return testMunkres(costs, pairs);
193 std::vector<std::vector<double> > costs {};
194 costs.push_back(std::vector<double>{3, 2, 1});
195 costs.push_back(std::vector<double>{4, 3, 2});
196 costs.push_back(std::vector<double>{1, 4, 3});
197 costs.push_back(std::vector<double>{2, 1, 4});
199 std::vector<std::pair<unsigned int, unsigned int> > pairs {};
200 pairs.emplace_back(0, 2);
201 pairs.emplace_back(2, 0);
202 pairs.emplace_back(3, 1);
204 return testMunkres(costs, pairs);
209 std::vector<std::vector<double> > costs {};
210 costs.push_back(std::vector<double>{2, 3, 4, 1});
211 costs.push_back(std::vector<double>{4, 1, 2, 3});
212 costs.push_back(std::vector<double>{1, 2, 3, 4});
214 std::vector<std::pair<unsigned int, unsigned int> > pairs {};
215 pairs.emplace_back(0, 3);
216 pairs.emplace_back(1, 1);
217 pairs.emplace_back(2, 0);
219 return testMunkres(costs, pairs);
224 if (not testSquareMat()) {
228 if (not testVertMat()) {
232 if (not testHorMat()) {
241 int main() {
return EXIT_SUCCESS; }