1 #include <gtest/gtest.h>
2 #include "munkres.h"
3 #include "matrixtest.h"
4 #include <iostream>
5 #include <iomanip>
6
7 class MunkresTest : public ::testing::Test
8 {
9 protected:
10 virtual void SetUp ();
11 virtual void TearDown ();
12
13 Matrix <double> generateRandomMatrix (const int, const int);
14 void isSingleSolution (Matrix <double> &);
15 void isValidOutput (Matrix <double> &);
16 };
17
18
19
SetUp()20 void MunkresTest::SetUp ()
21 {
22 }
23
24
25
TearDown()26 void MunkresTest::TearDown ()
27 {
28 }
29
30
31
generateRandomMatrix(const int nrows,const int ncols)32 Matrix<double> MunkresTest::generateRandomMatrix(const int nrows, const int ncols)
33 {
34 Matrix<double> matrix(nrows, ncols);
35
36 srandom(time(nullptr)); // Seed random number generator.
37
38 // Initialize matrix with random values.
39 for ( unsigned int row = 0 ; row < matrix.rows() ; row++ )
40 for ( unsigned int col = 0 ; col < matrix.columns() ; col++ )
41 matrix(row,col) = (double)random();
42
43 return matrix;
44 }
45
46
47
isSingleSolution(Matrix<double> & matrix)48 void MunkresTest::isSingleSolution (Matrix <double> & matrix)
49 {
50 for ( unsigned int row = 0 ; row < matrix.rows() ; row++ ) {
51 int columnsolutioncount = 0;
52 for ( unsigned int col = 0 ; col < matrix.columns() ; col++ )
53 if ( matrix(row,col) == 0 )
54 columnsolutioncount++;
55 EXPECT_EQ ( columnsolutioncount, 1 );
56 }
57
58 for ( unsigned int col = 0 ; col < matrix.columns() ; col++ ) {
59 int rowsolutioncount = 0;
60 for ( unsigned int row = 0 ; row < matrix.rows() ; row++ )
61 if ( matrix(row,col) == 0 )
62 rowsolutioncount++;
63 EXPECT_EQ ( rowsolutioncount, 1 );
64 }
65 }
66
67
68
isValidOutput(Matrix<double> & matrix)69 void MunkresTest::isValidOutput (Matrix <double> & matrix)
70 {
71 for ( unsigned int row = 0 ; row < matrix.rows() ; row++ )
72 for ( unsigned int col = 0 ; col < matrix.columns() ; col++ )
73 EXPECT_TRUE ( matrix(row,col) == 0 || matrix(row,col) == -1 );
74 }
75
76
77
TEST_F(MunkresTest,replace_infinites_4x4Case001_Success)78 TEST_F (MunkresTest, replace_infinites_4x4Case001_Success)
79 {
80 // Arrange.
81 const auto infinity = std::numeric_limits<double>::infinity();
82 Matrix<double> etalon_matrix{
83 { 1.0, 0.0, 3.0, 2.0},
84 { 3.0, -2.0, -1.0, 0.0},
85 {-1.0, 3.0, 2.0, 0.0},
86 {-1.0, 0.0, 2.0, 3.0}
87 };
88 Matrix<double> test_matrix{
89 { 1.0, 0.0, infinity, 2.0},
90 {infinity, -2.0, -1.0, 0.0},
91 {-1.0, infinity, 2.0, 0.0},
92 {-1.0, 0.0, 2.0, infinity}
93 };
94
95 // Act.
96 Munkres<double>::replace_infinites (test_matrix);
97
98 // Assert.
99 EXPECT_EQ (etalon_matrix, test_matrix);
100 }
101
102
103
TEST_F(MunkresTest,replace_infinites_4x4Case002_Success)104 TEST_F (MunkresTest, replace_infinites_4x4Case002_Success)
105 {
106 // Arrange.
107 const auto infinity = std::numeric_limits<double>::infinity();
108 Matrix<double> etalon_matrix{
109 { 3.0, 0.0, 3.0, 2.0},
110 { 3.0, -2.0, -1.0, 3.0},
111 {-1.0, 3.0, 2.0, 3.0},
112 {-1.0, 3.0, 2.0, 3.0}
113 };
114 Matrix<double> test_matrix{
115 {infinity, 0.0, infinity, 2.0},
116 {infinity, -2.0, -1.0, infinity},
117 {-1.0, infinity, 2.0, infinity},
118 {-1.0, infinity, 2.0, infinity}
119 };
120
121 // Act.
122 Munkres<double>::replace_infinites(test_matrix);
123
124 // Assert.
125 EXPECT_EQ (etalon_matrix, test_matrix);
126 }
127
128
129
TEST_F(MunkresTest,replace_infinites_4x4Case003_Success)130 TEST_F (MunkresTest, replace_infinites_4x4Case003_Success)
131 {
132 // Arrange.
133 const auto infinity = std::numeric_limits<double>::infinity();
134 Matrix<double> etalon_matrix{
135 {-5.0, -4.0, -1.0, -2.0},
136 {-1.0, -2.0, -5.0, -4.0},
137 {-5.0, -1.0, -2.0, -4.0},
138 {-5.0, -4.0, -2.0, -1.0}
139 };
140 Matrix<double> test_matrix{
141 {-5.0, -4.0, infinity, -2.0},
142 {infinity, -2.0, -5.0, -4.0},
143 {-5.0, infinity, -2.0, -4.0},
144 {-5.0, -4.0, -2.0, infinity}
145 };
146
147 // Act.
148 Munkres<double>::replace_infinites (test_matrix);
149
150 // Assert.
151 EXPECT_EQ (etalon_matrix, test_matrix);
152 }
153
154
155
TEST_F(MunkresTest,replace_infinites_4x4Case004_Success)156 TEST_F (MunkresTest, replace_infinites_4x4Case004_Success)
157 {
158 // Arrange.
159 const auto infinity = std::numeric_limits<double>::infinity();
160 Matrix<double> etalon_matrix{
161 { 1.0, 0.0, 3.0, 2.0},
162 { 3.0, -2.0, -1.0, 0.0},
163 {-1.0, 3.0, 0.0, 0.0},
164 {-1.0, 0.0, 0.0, 3.0}
165 };
166 Matrix<double> test_matrix{
167 { 1.0, 0.0, infinity, 2.0},
168 {infinity, -2.0, -1.0, 0.0},
169 {-1.0, infinity, 0.0, 0.0},
170 {-1.0, 0.0, 0.0, infinity}
171 };
172
173 // Act.
174 Munkres<double>::replace_infinites (test_matrix);
175
176 // Assert.
177 EXPECT_EQ (etalon_matrix, test_matrix);
178 }
179
180
181
TEST_F(MunkresTest,replace_infinites_4x4Case005_Success)182 TEST_F (MunkresTest, replace_infinites_4x4Case005_Success)
183 {
184 // Arrange.
185 const auto infinity = std::numeric_limits<double>::infinity();
186 Matrix<double> etalon_matrix{
187 { 0.0, 0.0, 0.0, 0.0},
188 { 0.0, 0.0, 0.0, 0.0},
189 { 0.0, 0.0, 0.0, 0.0},
190 { 0.0, 0.0, 0.0, 0.0}
191 };
192 Matrix<double> test_matrix{
193 {infinity, infinity, infinity, infinity},
194 {infinity, infinity, infinity, infinity},
195 {infinity, infinity, infinity, infinity},
196 {infinity, infinity, infinity, infinity}
197 };
198
199 // Act.
200 Munkres<double>::replace_infinites (test_matrix);
201
202 // Assert.
203 EXPECT_EQ (etalon_matrix, test_matrix);
204 }
205
206
207
TEST_F(MunkresTest,minimize_along_direction_5x5_OverRowsOnly_Success)208 TEST_F (MunkresTest, minimize_along_direction_5x5_OverRowsOnly_Success)
209 {
210 // Arrange.
211 Matrix<double> etalon_matrix{
212 { 1.0, 0.0, 3.0, 2.0, 4.0},
213 { 3.0, -2.0, -1.0, 0.0, 4.0},
214 {-1.0, 3.0, 2.0, 1.0, 2.0},
215 { 0.0, 2.0, 1.0, 0.0, 3.0},
216 { 0.0, 1.0, 1.0, 0.0, 2.0}
217 };
218 Matrix<double> test_matrix{
219 { 1.0, 0.0, 3.0, 2.0, 4.0},
220 { 3.0, -2.0, -1.0, 0.0, 4.0},
221 {-1.0, 3.0, 2.0, 1.0, 2.0},
222 { 1.0, 3.0, 2.0, 1.0, 4.0},
223 { 2.0, 3.0, 3.0, 2.0, 4.0}
224 };
225
226 // Act.
227 Munkres<double>::minimize_along_direction(test_matrix, false);
228
229 // Assert.
230 EXPECT_EQ (etalon_matrix, test_matrix);
231 }
232
233
234
TEST_F(MunkresTest,minimize_along_direction_5x5_OverColumnsOnly_Success)235 TEST_F (MunkresTest, minimize_along_direction_5x5_OverColumnsOnly_Success)
236 {
237 // Arrange.
238 Matrix<double> etalon_matrix{
239 { 1.0, 0.0, 3.0, 2.0, 2.0},
240 { 3.0, -2.0, -1.0, 0.0, 2.0},
241 {-1.0, 3.0, 2.0, 1.0, 0.0},
242 { 1.0, 3.0, 2.0, 1.0, 2.0},
243 { 2.0, 3.0, 3.0, 2.0, 2.0}
244 };
245 Matrix<double> test_matrix{
246 { 1.0, 0.0, 3.0, 2.0, 4.0},
247 { 3.0, -2.0, -1.0, 0.0, 4.0},
248 {-1.0, 3.0, 2.0, 1.0, 2.0},
249 { 1.0, 3.0, 2.0, 1.0, 4.0},
250 { 2.0, 3.0, 3.0, 2.0, 4.0}
251 };
252
253 // Act.
254 Munkres<double>::minimize_along_direction(test_matrix, true);
255
256 // Assert.
257 EXPECT_EQ (etalon_matrix, test_matrix);
258 }
259
260
261
TEST_F(MunkresTest,minimize_along_direction_5x5_OverRowsAndColumns_Success)262 TEST_F (MunkresTest, minimize_along_direction_5x5_OverRowsAndColumns_Success)
263 {
264 // Arrange.
265 Matrix<double> etalon_matrix{
266 { 1.0, 0.0, 3.0, 2.0, 2.0},
267 { 3.0, -2.0, -1.0, 0.0, 2.0},
268 {-1.0, 3.0, 2.0, 1.0, 0.0},
269 { 0.0, 2.0, 1.0, 0.0, 1.0},
270 { 0.0, 1.0, 1.0, 0.0, 0.0}
271 };
272 Matrix<double> test_matrix{
273 { 1.0, 0.0, 3.0, 2.0, 4.0},
274 { 3.0, -2.0, -1.0, 0.0, 4.0},
275 {-1.0, 3.0, 2.0, 1.0, 2.0},
276 { 1.0, 3.0, 2.0, 1.0, 4.0},
277 { 2.0, 3.0, 3.0, 2.0, 4.0}
278 };
279
280 // Act.
281 Munkres<double>::minimize_along_direction(test_matrix, false);
282 Munkres<double>::minimize_along_direction(test_matrix, true);
283
284 // Assert.
285 EXPECT_EQ (etalon_matrix, test_matrix);
286 }
287
288
289
TEST_F(MunkresTest,solve_5x5_IsSingleSolution_Success)290 TEST_F (MunkresTest, solve_5x5_IsSingleSolution_Success)
291 {
292 // Arrange.
293 Matrix<double> matrix = generateRandomMatrix(5, 5);
294 Munkres<double> munkres;
295
296 // Act.
297 munkres.solve(matrix);
298
299 // Assert.
300 isSingleSolution(matrix);
301 }
302
303
304
TEST_F(MunkresTest,solve_10x10_IsSingleSolution_Success)305 TEST_F (MunkresTest, solve_10x10_IsSingleSolution_Success)
306 {
307 // Arrange.
308 Matrix<double> matrix = generateRandomMatrix(10, 10);
309 Munkres<double> munkres;
310
311 // Act.
312 munkres.solve(matrix);
313
314 // Assert.
315 isSingleSolution(matrix);
316 }
317
318
319
TEST_F(MunkresTest,solve_50x50_IsSingleSolution_Success)320 TEST_F (MunkresTest, solve_50x50_IsSingleSolution_Success)
321 {
322 // Arrange.
323 Matrix<double> matrix = generateRandomMatrix(50, 50);
324 Munkres<double> munkres;
325
326 // Act.
327 munkres.solve(matrix);
328
329 // Assert.
330 isSingleSolution(matrix);
331 }
332
333
334
TEST_F(MunkresTest,solve_100x100_IsSingleSolution_Success)335 TEST_F (MunkresTest, solve_100x100_IsSingleSolution_Success)
336 {
337 // Arrange.
338 Matrix<double> matrix = generateRandomMatrix(100, 100);
339 Munkres<double> munkres;
340
341 // Act.
342 munkres.solve(matrix);
343
344 // Assert.
345 isSingleSolution(matrix);
346 }
347
348
349
TEST_F(MunkresTest,solve_200x200_IsSingleSolution_Success)350 TEST_F (MunkresTest, solve_200x200_IsSingleSolution_Success)
351 {
352 // Arrange.
353 Matrix<double> matrix = generateRandomMatrix(200, 200);
354 Munkres<double> munkres;
355
356 // Act.
357 munkres.solve(matrix);
358
359 // Assert.
360 isSingleSolution(matrix);
361 }
362
363
364
TEST_F(MunkresTest,solve_10x10_IsValideOutput_Success)365 TEST_F (MunkresTest, solve_10x10_IsValideOutput_Success)
366 {
367 // Arrange.
368 Matrix<double> matrix = generateRandomMatrix(10, 10);
369 Munkres<double> munkres;
370
371 // Act.
372 munkres.solve(matrix);
373
374 // Assert.
375 isValidOutput (matrix);
376 }
377
378
379
TEST_F(MunkresTest,solve_1x1_ObviousSolution_Success)380 TEST_F (MunkresTest, solve_1x1_ObviousSolution_Success)
381 {
382 // Arrange.
383 Matrix<double> etalon_matrix{
384 {0.0}
385 };
386 Matrix<double> test_matrix{
387 {0.0}
388 };
389
390 Munkres<double> munkres;
391
392 // Act.
393 munkres.solve(test_matrix);
394
395 // Assert.
396 EXPECT_EQ (etalon_matrix, test_matrix);
397 }
398
399
400
TEST_F(MunkresTest,solve_2x2_ObviousSolution_Success)401 TEST_F (MunkresTest, solve_2x2_ObviousSolution_Success)
402 {
403 // Arrange.
404 Matrix<double> etalon_matrix{
405 {-1.0, 0.0},
406 { 0.0, -1.0}
407 };
408 Matrix<double> test_matrix{
409 {1.0, 0.0},
410 {0.0, 1.0}
411 };
412
413 Munkres<double> munkres;
414
415 // Act.
416 munkres.solve(test_matrix);
417
418 // Assert.
419 EXPECT_EQ (etalon_matrix, test_matrix);
420 }
421
422
423
TEST_F(MunkresTest,solve_3x3_ObviousSolution_Success)424 TEST_F (MunkresTest, solve_3x3_ObviousSolution_Success)
425 {
426 // Arrange.
427 Matrix<double> etalon_matrix{
428 {-1.0, 0.0, -1.0},
429 { 0.0, -1.0, -1.0},
430 {-1.0, -1.0, 0.0}
431 };
432 Matrix<double> test_matrix{
433 {1.0, 0.0, 1.0},
434 {0.0, 1.0, 1.0},
435 {1.0, 1.0, 0.0}
436 };
437
438 Munkres<double> munkres;
439
440 // Act.
441 munkres.solve(test_matrix);
442
443 // Assert.
444 EXPECT_EQ (etalon_matrix, test_matrix);
445 }
446
447
448
TEST_F(MunkresTest,solve_3x2_NonObviousSolutionCase001_Success)449 TEST_F (MunkresTest, solve_3x2_NonObviousSolutionCase001_Success)
450 {
451 // Arrange.
452 Matrix<double> etalon_matrix{
453 {-1.0, 0.0},
454 { 0.0, -1.0},
455 {-1.0, -1.0}
456 };
457 Matrix<double> test_matrix{
458 {1.0, 2.0},
459 {0.0, 9.0},
460 {9.0, 9.0}
461 };
462
463 Munkres<double> munkres;
464
465 // Act.
466 munkres.solve(test_matrix);
467
468 // Assert.
469 EXPECT_EQ (etalon_matrix, test_matrix);
470 }
471
472
473
474 // This is simplified version of test case #008.
TEST_F(MunkresTest,solve_3x2_NonObviousSolutionCase002_Success)475 TEST_F (MunkresTest, solve_3x2_NonObviousSolutionCase002_Success)
476 {
477 // Arrange.
478 Matrix<double> etalon_matrix{
479 {-1.0, -1.0},
480 { 0.0, -1.0},
481 {-1.0, 0.0}
482 };
483 Matrix<double> test_matrix{
484 {1.0e+17, 3},
485 {2, 1.0e+17},
486 {4, 1}
487 };
488
489 Munkres<double> munkres;
490
491 // Act.
492 munkres.solve(test_matrix);
493
494 // Assert.
495 EXPECT_EQ (etalon_matrix, test_matrix);
496 }
497
498
499
500 // This is simplified version of test case #009 (transposed version of test case 002).
TEST_F(MunkresTest,solve_2x3_NonObviousSolutionCase003_Success)501 TEST_F (MunkresTest, solve_2x3_NonObviousSolutionCase003_Success)
502 {
503 // Arrange.
504 Matrix<double> etalon_matrix{
505 {-1.0, 0.0, -1.0},
506 {-1.0, -1.0, 0.0}
507 };
508 Matrix<double> test_matrix{
509 {1.0e+17, 2, 4},
510 {3, 1.0e+17, 1}
511 };
512
513 Munkres<double> munkres;
514
515 // Act.
516 munkres.solve(test_matrix);
517
518 // Assert.
519 EXPECT_EQ (etalon_matrix, test_matrix);
520 }
521
522
523
524 // This is test case based on test case #002, but extended by one "impossible" task and one "lazy" worker.
TEST_F(MunkresTest,solve_4x3_NonObviousSolutionCase004_Success)525 TEST_F (MunkresTest, solve_4x3_NonObviousSolutionCase004_Success)
526 {
527 // Arrange.
528 Matrix<double> etalon_matrix{
529 {-1.0, -1.0, -1.0},
530 { 0.0, -1.0, -1.0},
531 {-1.0, -1.0, 0.0},
532 {-1.0, 0.0, -1.0}
533 };
534 Matrix<double> test_matrix{
535 {1.0e+17, 3, 1.0e+17},
536 {2, 1.0e+17, 1.0e+17},
537 {1.0e+17, 1.0e+17, 1.0e+17},
538 {4, 1, 1.0e+17}
539 };
540
541 Munkres<double> munkres;
542
543 // Act.
544 munkres.solve(test_matrix);
545
546 // Assert.
547 EXPECT_EQ (etalon_matrix (1, 0), test_matrix (1, 0) );
548 EXPECT_EQ (etalon_matrix (3, 1), test_matrix (3, 1) );
549 }
550
551
552
553 // This is test case based on test case #003, but extended by one "impossible" task and one "lazy" worker.
TEST_F(MunkresTest,solve_3x4_NonObviousSolutionCase005_Success)554 TEST_F (MunkresTest, solve_3x4_NonObviousSolutionCase005_Success)
555 {
556 // Arrange.
557 Matrix<double> etalon_matrix{
558 {-1.0, 0.0, -1.0, -1.0},
559 {-1.0, -1.0, -1.0, 0.0},
560 {-1.0, -1.0, 0.0, -1.0}
561 };
562 Matrix<double> test_matrix{
563 {1.0e+17, 2, 1.0e17, 4},
564 {3, 1.0e+17, 1.0e17, 1},
565 {1.0e+17, 1.0e+17, 1.0e17, 1.0e+17}
566 };
567
568 Munkres<double> munkres;
569
570 // Act.
571 munkres.solve(test_matrix);
572
573 // Assert.
574 EXPECT_EQ (etalon_matrix (0, 1), test_matrix (0, 1) );
575 EXPECT_EQ (etalon_matrix (1, 3), test_matrix (1, 3) );
576 }
577
578
579
TEST_F(MunkresTest,solve_3x3_NonObviousSolutionCase006_Success)580 TEST_F (MunkresTest, solve_3x3_NonObviousSolutionCase006_Success)
581 {
582 // Arrange.
583 Matrix<double> etalon_matrix{
584 {-1.0, 0.0, -1.0},
585 { 0.0, -1.0, -1.0},
586 {-1.0, -1.0, 0.0}
587 };
588 Matrix<double> test_matrix{
589 {1.0, 2.0, 1.0},
590 {0.0, 9.0, 9.0},
591 {9.0, 9.0, 0.0}
592 };
593
594 Munkres<double> munkres;
595
596 // Act.
597 munkres.solve(test_matrix);
598
599 // Assert.
600 EXPECT_EQ (etalon_matrix, test_matrix);
601 }
602
603
604
TEST_F(MunkresTest,solve_3x3_NonObviousSolutionCase007_Success)605 TEST_F (MunkresTest, solve_3x3_NonObviousSolutionCase007_Success)
606 {
607 // Arrange.
608 Matrix<double> etalon_matrix{
609 {-1.0, -1.0, 0.0},
610 {-1.0, 0.0, -1.0},
611 { 0.0, -1.0, -1.0}
612 };
613 Matrix<double> test_matrix{
614 {0.0, 0.0, 4.0},
615 {4.0, 3.0, 9.0},
616 {3.0, 4.0, 9.0}
617 };
618
619 Munkres<double> munkres;
620
621 // Act.
622 munkres.solve(test_matrix);
623
624 // Assert.
625 EXPECT_EQ (etalon_matrix, test_matrix);
626 }
627
628
629
TEST_F(MunkresTest,solve_6x4_NonObviousSolutionCase008_Success)630 TEST_F (MunkresTest, solve_6x4_NonObviousSolutionCase008_Success)
631 {
632 // Arrange.
633 Matrix<double> etalon_matrix{
634 {-1.0, -1.0, -1.0, -1.0},
635 { 0.0, -1.0, -1.0, -1.0},
636 {-1.0, 0.0, -1.0, -1.0},
637 {-1.0, -1.0, -1.0, -1.0},
638 {-1.0, -1.0, -1.0, 0.0},
639 {-1.0, -1.0, 0.0, -1.0}
640 };
641 Matrix<double> test_matrix{
642 {1.79769e+308, 7.33184e+08, 9.41561e+08, 2.79247e+08},
643 {3.06449e+08, 1.79769e+308, 3.3464e+08, 7.06878e+08},
644 {9.93296e+08, 1.9414e+08, 1.79769e+308, 1.14174e+08},
645 {3.51623e+08, 2.48635e+08, 7.81242e+08, 1.79769e+308},
646 {7.02639e+08, 8.51663e+08, 9.37382e+08, 4.96945e+07},
647 {7.58851e+08, 8.58445e+08, 8.7235e+07, 5.47076e+08}
648 };
649
650 Munkres<double> munkres;
651
652 // Act.
653 munkres.solve(test_matrix);
654
655 // Assert.
656 EXPECT_EQ (etalon_matrix, test_matrix);
657 }
658
659
660
TEST_F(MunkresTest,solve_4x6_NonObviousSolutionCase009_Success)661 TEST_F (MunkresTest, solve_4x6_NonObviousSolutionCase009_Success)
662 {
663 // Arrange.
664 Matrix<double> etalon_matrix{
665 {-1.0, 0.0, -1.0, -1.0, -1.0, -1.0},
666 {-1.0, -1.0, 0.0, -1.0, -1.0, -1.0},
667 {-1.0, -1.0, -1.0, -1.0, -1.0, 0.0},
668 {-1.0, -1.0, -1.0, -1.0, 0.0, -1.0}
669 };
670 Matrix<double> test_matrix{
671 {1.79769e+308, 3.06449e+08, 9.93296e+08, 3.51623e+08, 7.02639e+08, 7.58851e+08},
672 {7.33184e+08, 1.79769e+308, 1.9414e+08, 2.48635e+08, 8.51663e+08, 8.58445e+08},
673 {9.41561e+08, 3.3464e+08, 1.79769e+308, 7.81242e+08, 9.37382e+08, 8.7235e+07},
674 {2.79247e+08, 7.06878e+08, 1.14174e+08, 1.79769e+308, 4.96945e+07, 5.47076e+08}
675 };
676
677 Munkres<double> munkres;
678
679 // Act.
680 munkres.solve(test_matrix);
681
682 // Assert.
683 EXPECT_EQ (etalon_matrix, test_matrix);
684 }
685
686
687
TEST_F(MunkresTest,solve_3x3_IsValide_Fail)688 TEST_F (MunkresTest, solve_3x3_IsValide_Fail)
689 {
690 // Arrange.
691 Matrix<double> etalon_matrix{
692 { 0.0, -1.0, -1.0},
693 // ^ ^
694 // | |
695 // Wrong Wrong
696 { 0.0, -1.0, -1.0},
697 {-1.0, -1.0, 0.0}
698 };
699 Matrix<double> test_matrix{
700 {1.0, 0.0, 1.0},
701 {0.0, 1.0, 1.0},
702 {1.0, 1.0, 0.0}
703 };
704
705 Munkres<double> munkres;
706
707 // Act.
708 munkres.solve(test_matrix);
709
710 // Assert.
711 EXPECT_NE (etalon_matrix, test_matrix);
712 }
713