OR-Tools  8.2
hungarian_test.cc
Go to the documentation of this file.
1// Test file for hungarian.h
2
4
5#include "absl/container/flat_hash_map.h"
6#include "gtest/gtest.h"
10#include "ortools/base/random.h"
11
12namespace operations_research {
13
14// Generic check function that checks consistency of a linear assignment
15// result as well as whether the result is the expected one.
16
17void GenericCheck(const int expected_assignment_size,
18 const absl::flat_hash_map<int, int>& direct_assignment,
19 const absl::flat_hash_map<int, int>& reverse_assignment,
20 const int expected_agents[], const int expected_tasks[]) {
21 EXPECT_EQ(expected_assignment_size, direct_assignment.size());
22 EXPECT_EQ(expected_assignment_size, reverse_assignment.size());
23 for (int i = 0; i < expected_assignment_size; ++i) {
24 EXPECT_EQ(gtl::FindOrDie(direct_assignment, expected_agents[i]),
25 expected_tasks[i]);
26 EXPECT_EQ(gtl::FindOrDie(reverse_assignment, expected_tasks[i]),
27 expected_agents[i]);
28 }
29 for (const auto& direct_iter : direct_assignment) {
30 EXPECT_EQ(gtl::FindOrDie(reverse_assignment, direct_iter.second),
31 direct_iter.first)
32 << direct_iter.first << " -> " << direct_iter.second;
33 }
34}
35
36void TestMinimization(const std::vector<std::vector<double> >& cost,
37 const int expected_assignment_size,
38 const int expected_agents[], const int expected_tasks[]) {
39 absl::flat_hash_map<int, int> direct_assignment;
40 absl::flat_hash_map<int, int> reverse_assignment;
41 MinimizeLinearAssignment(cost, &direct_assignment, &reverse_assignment);
42 SCOPED_TRACE("Minimization");
43 GenericCheck(expected_assignment_size, direct_assignment, reverse_assignment,
44 expected_agents, expected_tasks);
45}
46
47void TestMaximization(const std::vector<std::vector<double> >& cost,
48 const int expected_assignment_size,
49 const int expected_agents[], const int expected_tasks[]) {
50 absl::flat_hash_map<int, int> direct_assignment;
51 absl::flat_hash_map<int, int> reverse_assignment;
52 MaximizeLinearAssignment(cost, &direct_assignment, &reverse_assignment);
53 SCOPED_TRACE("Maximization");
54 GenericCheck(expected_assignment_size, direct_assignment, reverse_assignment,
55 expected_agents, expected_tasks);
56}
57
58// Test on an empty matrix
59
60TEST(LinearAssignmentTest, NullMatrix) {
61 std::vector<std::vector<double> > cost;
62 const int* expected_agents = NULL;
63 const int* expected_tasks = NULL;
64 TestMinimization(cost, 0, expected_agents, expected_tasks);
65 TestMaximization(cost, 0, expected_agents, expected_tasks);
66}
67
68#define MATRIX_TEST \
69 { \
70 std::vector<std::vector<double> > cost(kMatrixHeight); \
71 for (int row = 0; row < kMatrixHeight; ++row) { \
72 cost[row].resize(kMatrixWidth); \
73 for (int col = 0; col < kMatrixWidth; ++col) { \
74 cost[row][col] = kCost[row][col]; \
75 } \
76 } \
77 EXPECT_EQ(arraysize(expected_agents_for_min), \
78 arraysize(expected_tasks_for_min)); \
79 EXPECT_EQ(arraysize(expected_agents_for_max), \
80 arraysize(expected_tasks_for_max)); \
81 const int assignment_size = arraysize(expected_agents_for_max); \
82 TestMinimization(cost, assignment_size, expected_agents_for_min, \
83 expected_tasks_for_min); \
84 TestMaximization(cost, assignment_size, expected_agents_for_max, \
85 expected_tasks_for_max); \
86 }
87
88// Test on a 1x1 matrix
89
90TEST(LinearAssignmentTest, SizeOneMatrix) {
91 const int kMatrixHeight = 1;
92 const int kMatrixWidth = 1;
93 const double kCost[kMatrixHeight][kMatrixWidth] = {{4}};
94 const int expected_agents_for_min[] = {0};
95 const int expected_tasks_for_min[] = {0};
96 const int expected_agents_for_max[] = {0};
97 const int expected_tasks_for_max[] = {0};
99}
100
101// Test on a 4x4 matrix. Example taken at
102// http://www.ee.oulu.fi/~mpa/matreng/eem1_2-1.htm
103TEST(LinearAssignmentTest, Small4x4Matrix) {
104 const int kMatrixHeight = 4;
105 const int kMatrixWidth = 4;
106 const double kCost[kMatrixHeight][kMatrixWidth] = {{90, 75, 75, 80},
107 {35, 85, 55, 65},
108 {125, 95, 90, 105},
109 {45, 110, 95, 115}};
110 const int expected_agents_for_min[] = {0, 1, 2, 3};
111 const int expected_tasks_for_min[] = {3, 2, 1, 0};
112 const int expected_agents_for_max[] = {0, 1, 2, 3};
113 const int expected_tasks_for_max[] = {2, 1, 0, 3};
115}
116
117// Test on a 3x4 matrix. Sub-problem of Small4x4Matrix
118TEST(LinearAssignmentTest, Small3x4Matrix) {
119 const int kMatrixHeight = 3;
120 const int kMatrixWidth = 4;
121 const double kCost[kMatrixHeight][kMatrixWidth] = {
122 {90, 75, 75, 80}, {35, 85, 55, 65}, {125, 95, 90, 105}};
123 const int expected_agents_for_min[] = {0, 1, 2};
124 const int expected_tasks_for_min[] = {1, 0, 2};
125 const int expected_agents_for_max[] = {0, 1, 2};
126 const int expected_tasks_for_max[] = {3, 1, 0};
128}
129
130// Test on a 4x3 matrix. Sub-problem of Small4x4Matrix
131TEST(LinearAssignmentTest, Small4x3Matrix) {
132 const int kMatrixHeight = 4;
133 const int kMatrixWidth = 3;
134 const double kCost[kMatrixHeight][kMatrixWidth] = {
135 {90, 75, 75}, {35, 85, 55}, {125, 95, 90}, {45, 110, 95}};
136 const int expected_agents_for_min[] = {0, 1, 3};
137 const int expected_tasks_for_min[] = {1, 2, 0};
138 const int expected_agents_for_max[] = {0, 2, 3};
139 const int expected_tasks_for_max[] = {2, 0, 1};
141}
142
143#undef MATRIX_TEST
144
145} // namespace operations_research
#define MATRIX_TEST
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:176
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void TestMinimization(const std::vector< std::vector< double > > &cost, const int expected_assignment_size, const int expected_agents[], const int expected_tasks[])
void MinimizeLinearAssignment(const std::vector< std::vector< double > > &cost, absl::flat_hash_map< int, int > *direct_assignment, absl::flat_hash_map< int, int > *reverse_assignment)
Definition: hungarian.cc:657
void GenericCheck(const int expected_assignment_size, const absl::flat_hash_map< int, int > &direct_assignment, const absl::flat_hash_map< int, int > &reverse_assignment, const int expected_agents[], const int expected_tasks[])
void TestMaximization(const std::vector< std::vector< double > > &cost, const int expected_assignment_size, const int expected_agents[], const int expected_tasks[])
TEST(LinearAssignmentTest, NullMatrix)
void MaximizeLinearAssignment(const std::vector< std::vector< double > > &cost, absl::flat_hash_map< int, int > *direct_assignment, absl::flat_hash_map< int, int > *reverse_assignment)
Definition: hungarian.cc:675
int64 cost