// Copyright (C) 2011 Davis E. King (davis@dlib.net) // License: Boost Software License See LICENSE.txt for the full license. #include #include #include #include #include #include #include "../rand.h" #include "tester.h" namespace { using namespace test; using namespace dlib; using namespace std; logger dlog("test.max_cost_assignment"); // ---------------------------------------------------------------------------------------- std::vector > permutations ( matrix vals ) { if (vals.size() == 0) { return std::vector >(); } else if (vals.size() == 1) { return std::vector >(1,std::vector(1,vals(0))); } std::vector > temp; for (long i = 0; i < vals.size(); ++i) { const std::vector >& res = permutations(remove_col(vals,i)); for (unsigned long j = 0; j < res.size(); ++j) { temp.resize(temp.size()+1); std::vector& part = temp.back(); part.push_back(vals(i)); part.insert(part.end(), res[j].begin(), res[j].end()); } } return temp; } // ---------------------------------------------------------------------------------------- template std::vector brute_force_max_cost_assignment ( matrix cost ) { if (cost.size() == 0) return std::vector(); const std::vector >& perms = permutations(range(0,cost.nc()-1)); T best_cost = std::numeric_limits::min(); unsigned long best_idx = 0; for (unsigned long i = 0; i < perms.size(); ++i) { const T temp = assignment_cost(cost, perms[i]); if (temp > best_cost) { best_idx = i; best_cost = temp; } } return perms[best_idx]; } // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- class test_max_cost_assignment : public tester { public: test_max_cost_assignment ( ) : tester ("test_max_cost_assignment", "Runs tests on the max_cost_assignment function.") {} dlib::rand rnd; template void test_hungarian() { long size = rnd.get_random_32bit_number()%7; long range = rnd.get_random_32bit_number()%100; matrix cost = matrix_cast(randm(size,size,rnd)*range) - range/2; // use a uniform cost matrix sometimes if ((rnd.get_random_32bit_number()%100) == 0) cost = rnd.get_random_32bit_number()%100; // negate the cost matrix every now and then if ((rnd.get_random_32bit_number()%100) == 0) cost = -cost; std::vector assign = brute_force_max_cost_assignment(cost); T true_eval = assignment_cost(cost, assign); assign = max_cost_assignment(cost); DLIB_TEST(assignment_cost(cost,assign) == true_eval); assign = max_cost_assignment(matrix_cast(cost)); DLIB_TEST(assignment_cost(cost,assign) == true_eval); cost = matrix_cast(randm(size,size,rnd)*range); assign = brute_force_max_cost_assignment(cost); true_eval = assignment_cost(cost, assign); assign = max_cost_assignment(cost); DLIB_TEST(assignment_cost(cost,assign) == true_eval); assign = max_cost_assignment(matrix_cast(cost)); DLIB_TEST(assignment_cost(cost,assign) == true_eval); assign = max_cost_assignment(matrix_cast::type>(cost)); DLIB_TEST(assignment_cost(cost,assign) == true_eval); } void perform_test ( ) { for (long i = 0; i < 1000; ++i) { if ((i%100) == 0) print_spinner(); test_hungarian(); test_hungarian(); test_hungarian(); test_hungarian(); } } } a; }