From de2c4df728e62c5761edf7d58a30f3c59d7d4d20 Mon Sep 17 00:00:00 2001 From: Yidi Date: Sun, 8 Sep 2024 11:14:12 +0200 Subject: add remaining tests --- test/graph/hld.cpp | 83 ++++++++++++++++++++++++++++++++++++ test/graph/reroot.cpp | 59 ++++++++++++++++++++++++++ test/graph/reroot.cpp.awk | 7 ++++ test/graph/virtualTree.cpp | 95 ++++++++++++++++++++++++++++++++++++++++++ test/graph/virtualTree.cpp.awk | 7 ++++ 5 files changed, 251 insertions(+) create mode 100644 test/graph/hld.cpp create mode 100644 test/graph/reroot.cpp create mode 100644 test/graph/reroot.cpp.awk create mode 100644 test/graph/virtualTree.cpp create mode 100644 test/graph/virtualTree.cpp.awk diff --git a/test/graph/hld.cpp b/test/graph/hld.cpp new file mode 100644 index 0000000..bcd9c8c --- /dev/null +++ b/test/graph/hld.cpp @@ -0,0 +1,83 @@ +#include "../util.h" +#include + +struct Seg { // very real segment tree + vector a; + + Seg(int n) : a(n) {} + + void inc(int l, int r) { + for (int i=l; i(1, 50); + Graph g(n); + g.tree(); + + adj.assign(n, {}); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + init(Random::integer(0, n)); + + vector a(n); + auto dfs = [&](auto& self, int u, int p, int t) { + if (u == t) { + a[u]++; + return true; + } + for (int v : adj[u]) if (v != p) { + if (self(self, v, u, t)) { + a[u]++; + return true; + } + } + return false; + }; + + Seg seg(n); + + int Q = Random::integer(1, 50); + for (int q=0; q g(N); + g.tree(); + adj.assign(N, {}); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + vector> qu(N); + for (auto& [x, y] : qu) x = Random::integer(0, N), y = Random::integer(0, N); + + ll hash = 0; + t.start(); + init(0); + for (auto [x, y] : qu) for_intervals(x, y, [&](int l, int r){ hash += r-l; }); + t.stop(); + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/graph/reroot.cpp b/test/graph/reroot.cpp new file mode 100644 index 0000000..d5043b4 --- /dev/null +++ b/test/graph/reroot.cpp @@ -0,0 +1,59 @@ +#include "../util.h" +#include + +void stress_test() { + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer(1, 50); + Graph g(n); + g.tree(); + + adj.assign(n, {}); + g.forEdges([&](int a, int b){ + adj[a].emplace_back(b, Random::integer(0, 10)); + adj[b].emplace_back(a, Random::integer(0, 10)); + }); + + Reroot re; + auto ans = re.solve(); + + auto dfs = [&](auto& self, int u, int p) -> ll { + ll val = 0; + for (auto [v, w] : adj[u]) if (v != p) { + val ^= ((v ^ u) + self(self, v, u)) * w % MOD; + } + return u ^ val; + }; + for (int i=0; i g(N); + g.tree(); + adj.assign(N, {}); + g.forEdges([&](int a, int b){ + adj[a].emplace_back(b, Random::integer(0, (int)1e9)); + adj[b].emplace_back(a, Random::integer(0, (int)1e9)); + }); + + ll hash = 0; + t.start(); + Reroot re; + auto ans = re.solve(); + hash = accumulate(all(ans), 0LL); + t.stop(); + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/graph/reroot.cpp.awk b/test/graph/reroot.cpp.awk new file mode 100644 index 0000000..37ce8c3 --- /dev/null +++ b/test/graph/reroot.cpp.awk @@ -0,0 +1,7 @@ +BEGIN { print "constexpr ll MOD = 1e9 + 7;" } +{ + sub("W w, T x) {\\}", "W w, T x) { return ((v ^ c) + x) * w % MOD; }") + sub("T x, T y) {\\}", "T x, T y) { return x ^ y; }") + sub("int v, T x) {\\}", "int v, T x) { return v ^ x; }") +} +{ print } diff --git a/test/graph/virtualTree.cpp b/test/graph/virtualTree.cpp new file mode 100644 index 0000000..d256760 --- /dev/null +++ b/test/graph/virtualTree.cpp @@ -0,0 +1,95 @@ +#include "../util.h" +int lca(int u, int v); +#include + +vector d, par; +void dfs(int u, vector>& adj, int& counter) { + in[u] = counter++; + for (int v : adj[u]) if (v != par[u]) { + d[v] = d[u]+1; + par[v] = u; + dfs(v, adj, counter); + } + out[u] = counter; +} + +int lca(int u, int v) { + if (d[u] < d[v]) swap(u, v); + while (d[u] > d[v]) u = par[u]; + while (u != v) u = par[u], v = par[v]; + return u; +} + +void init(vector>& adj) { + int n = (int)sz(adj); + d.assign(n, 0); + in = par = out = d; + int counter = 0; + dfs(0, adj, counter); +} + +void stress_test() { + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer(1, 50); + Graph g(n); + g.tree(); + + vector> adj(n); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + init(adj); + vector ind = Random::distinct(Random::integer(1, n+1), 0, n); + auto [idk, tree] = virtualTree(ind); + vector> edges; + for (int i=0; i> edges2; + vector used(n); + for (int u : ind) for (int v : ind) used[lca(u, v)] = true; + auto dfs = [&](auto& self, int u, int p, int last) -> void { + if (used[u]) { + if (last != -1) edges2.emplace_back(last, u); + last = u; + } + for (int v : adj[u]) if (v != p) self(self, v, u, last); + }; + dfs(dfs, 0, -1, -1); + + sort(all(edges)), sort(all(edges2)); + if (edges != edges2) cerr << "WA edge list does not match" << FAIL; + } + cerr << "tested random 50'000 tests" << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + Graph g(N); + g.tree(); + vector> adj(N); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + init(adj); + vector ind = Random::distinct(N/2, 0, N); + + ll hash = 0; + t.start(); + auto [idk, tree] = virtualTree(ind); + hash = accumulate(all(idk), 0LL); + t.stop(); + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/graph/virtualTree.cpp.awk b/test/graph/virtualTree.cpp.awk new file mode 100644 index 0000000..fe4bc62 --- /dev/null +++ b/test/graph/virtualTree.cpp.awk @@ -0,0 +1,7 @@ +/\/\/ v/ { + print "return {ind, tree};" +} +{ + sub("void", "pair, vector>>") +} +{ print } -- cgit v1.2.3