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
52
53
54
55
56
57
58
59
60
|
#include <gtest/gtest.h>
#include "test_util.h"
#include "nomnigraph/Graph/Graph.h"
TEST(Tarjans, Simple) {
TestClass t1;
TestClass t2;
nom::Graph<TestClass> g;
nom::Graph<TestClass>::NodeRef n1 = g.createNode(std::move(t1));
nom::Graph<TestClass>::NodeRef n2 = g.createNode(std::move(t2));
g.createEdge(n1, n2);
g.createEdge(n2, n1);
auto sccs = nom::algorithm::tarjans(&g);
EXPECT_EQ(sccs.size(), 1);
}
TEST(Tarjans, WithEdgeStorage) {
TestClass t1;
TestClass t2;
nom::Graph<TestClass, TestClass> g;
nom::Graph<TestClass, TestClass>::NodeRef n1 = g.createNode(std::move(t1));
nom::Graph<TestClass, TestClass>::NodeRef n2 = g.createNode(std::move(t2));
g.createEdge(n1, n2, TestClass());
g.createEdge(n2, n1, TestClass());
auto sccs = nom::algorithm::tarjans(&g);
EXPECT_EQ(sccs.size(), 1);
}
TEST(Tarjans, DAG) {
auto graph = createGraph();
auto sccs = nom::algorithm::tarjans(&graph);
EXPECT_EQ(sccs.size(), 9);
}
TEST(Tarjans, Cycle) {
auto graph = createGraphWithCycle();
auto sccs = nom::algorithm::tarjans(&graph);
EXPECT_EQ(sccs.size(), 8);
}
TEST(Tarjans, Random) {
nom::Graph<TestClass> g;
std::vector<nom::Graph<TestClass>::NodeRef> nodes;
for (auto i = 0; i < 10; ++i) {
TestClass t;
nodes.emplace_back(g.createNode(std::move(t)));
}
for (auto i = 0; i < 30; ++i) {
// NOLINTNEXTLINE(bugprone-narrowing-conversions,cppcoreguidelines-narrowing-conversions,clang-analyzer-security.insecureAPI.rand)
int ri1 = rand() % nodes.size();
// NOLINTNEXTLINE(bugprone-narrowing-conversions,cppcoreguidelines-narrowing-conversions,clang-analyzer-security.insecureAPI.rand)
int ri2 = rand() % nodes.size();
g.createEdge(nodes[ri1], nodes[ri2]);
}
auto sccs = nom::algorithm::tarjans(&g);
EXPECT_GE(sccs.size(), 1);
}
|
