1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#pragma GCC diagnostic ignored "-Wunused-macros"
#define CATCH_CONFIG_ENABLE_PAIR_STRINGMAKER
#include "cata_catch.h"
#include <algorithm>
#include <unordered_map>
#include <vector>
#include "cata_algo.h"
static void check_cycle_finding( std::unordered_map<int, std::vector<int>> &g,
std::vector<std::vector<int>> &expected )
{
CAPTURE( g );
std::vector<std::vector<int>> loops = cata::find_cycles( g );
// Canonicalize the list of loops by rotating each to be lexicographically
// least and then sorting.
for( std::vector<int> &loop : loops ) {
auto min = std::min_element( loop.begin(), loop.end() );
std::rotate( loop.begin(), min, loop.end() );
}
std::sort( loops.begin(), loops.end() );
CHECK( loops == expected );
}
TEST_CASE( "find_cycles_small" )
{
std::unordered_map<int, std::vector<int>> g = {
{ 0, { 1 } },
{ 1, { 0 } },
};
std::vector<std::vector<int>> expected = {
{ 0, 1 },
};
check_cycle_finding( g, expected );
}
TEST_CASE( "find_cycles" )
{
std::unordered_map<int, std::vector<int>> g = {
{ 0, { 0, 1 } },
{ 1, { 0, 2, 3, 17 } },
{ 2, { 1 } },
{ 3, {} },
};
std::vector<std::vector<int>> expected = {
{ 0 },
{ 0, 1 },
{ 1, 2 },
};
check_cycle_finding( g, expected );
}
|
