summaryrefslogtreecommitdiff
path: root/test/graph
diff options
context:
space:
mode:
Diffstat (limited to 'test/graph')
-rw-r--r--test/graph/connect.cpp140
-rw-r--r--test/graph/connectMinLCT.h173
-rw-r--r--test/graph/dinic.cpp62
-rw-r--r--test/graph/hld.cpp83
-rw-r--r--test/graph/reroot.cpp59
-rw-r--r--test/graph/reroot.cpp.awk7
-rw-r--r--test/graph/scc.cpp12
-rw-r--r--test/graph/virtualTree.cpp95
-rw-r--r--test/graph/virtualTree.cpp.awk7
9 files changed, 626 insertions, 12 deletions
diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp
new file mode 100644
index 0000000..bba8104
--- /dev/null
+++ b/test/graph/connect.cpp
@@ -0,0 +1,140 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include "connectMinLCT.h"
+constexpr ll INF = 0x3FFF'FFFF;
+#include <graph/connect.cpp>
+
+struct Naive {
+ vector<multiset<int>> adj;
+ vector<int> seen;
+ int counter;
+ Naive(int n) : adj(n), seen(n), counter(0) {}
+
+ template<typename F>
+ void dfs(int x, F&& f) {
+ counter++;
+ vector<int> todo = {x};
+ seen[x] = counter;
+ while (!todo.empty()) {
+ x = todo.back();
+ todo.pop_back();
+ f(x);
+ for (ll y : adj[x]) {
+ if (seen[y] != counter) {
+ seen[y] = counter;
+ todo.push_back(y);
+ }
+ }
+ }
+ }
+
+ bool connected(int a, int b) {
+ bool res = false;
+ dfs(a, [&](int x){res |= x == b;});
+ return res;
+ }
+
+ void addEdge(int a, int b) {
+ adj[a].insert(b);
+ adj[b].insert(a);
+ }
+
+ void eraseEdge(int a, int b) {
+ adj[a].erase(adj[a].find(b));
+ adj[b].erase(adj[b].find(a));
+ }
+};
+
+void stress_test() {
+ ll queries = 0;
+ for (int tries = 0; tries < 2'000; tries++) {
+ int n = Random::integer<int>(2, 30);
+ int m = Random::integer<int>(30, 300);
+
+ vector<int> insertOrder(m);
+ iota(all(insertOrder), 0);
+ shuffle(all(insertOrder), Random::rng);
+ vector<pair<int, int>> edges(m, {-1, -1});
+
+ connect con(n, m);
+ Naive naive(n);
+
+ int deleted = 0;
+ for (int i = 0; i < m; i++) {
+ {
+ int a = Random::integer<int>(0, n);
+ int b = a;
+ while (b == a) b = Random::integer<int>(0, n);
+ edges[insertOrder[i]] = {a, b};
+
+ con.addEdge(a, b, insertOrder[i]);
+ naive.addEdge(a, b);
+ }
+
+ while (deleted < m && edges[deleted] != pair<int, int>{-1, -1} && Random::integer<int>(2) == 0) {
+ auto [a, b] = edges[deleted];
+
+ con.eraseEdge(deleted);
+ naive.eraseEdge(a, b);
+ deleted++;
+ }
+
+ for (int j = 0; j < n; j++) {
+ int a = Random::integer<int>(0, n);
+ int b = Random::integer<int>(0, n);
+
+ auto got = con.connected(a, b);
+ auto expected = naive.connected(a, b);
+
+ if (got != expected) cerr << "error" << FAIL;
+ }
+
+ queries += n;
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 100'000;
+constexpr int M = 500'000;
+void performance_test() {
+ timer t;
+ t.start();
+ connect con(N, M);
+ t.stop();
+
+ vector<int> insertOrder(M);
+ iota(all(insertOrder), 0);
+ shuffle(all(insertOrder), Random::rng);
+ vector<bool> inserted(M);
+
+ for (int i = 0, j = 0; i < N; i++) {
+ int a = Random::integer<int>(0, N);
+ int b = a;
+ while (b == a) b = Random::integer<int>(0, N);
+
+ t.start();
+ con.addEdge(a, b, insertOrder[i]);
+ t.stop();
+ inserted[i] = true;
+
+ while (j < M && inserted[j] && Random::integer<int>(2) == 0) {
+ t.start();
+ con.eraseEdge(j);
+ t.stop();
+ }
+ }
+ hash_t hash = 0;
+ for (int i = 1; i < N; i++) {
+ t.start();
+ hash += con.connected(i - 1, i);
+ 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/connectMinLCT.h b/test/graph/connectMinLCT.h
new file mode 100644
index 0000000..4d509f7
--- /dev/null
+++ b/test/graph/connectMinLCT.h
@@ -0,0 +1,173 @@
+constexpr ll queryDefault = 0x3FFF'FFFF;
+constexpr ll updateDefault = 0;
+//modifiable:
+ll _modify(ll x, ll y) {
+ return min(x, y);
+}
+ll _query(ll x, ll y) {
+ return min(x, y);
+}
+ll _update(ll delta, int /*length*/) {
+ return delta;
+}
+
+//generic:
+ll joinValueDelta(ll value, ll delta) {
+ if (delta == updateDefault) return value;
+ return _modify(value, delta);
+}
+
+ll joinDeltas(ll delta1, ll delta2) {
+ if (delta1 == updateDefault) return delta2;
+ if (delta2 == updateDefault) return delta1;
+ return _modify(delta1, delta2);
+}
+
+struct LCT {
+ struct Node {
+ ll nodeValue, subTreeValue, delta;
+ bool revert;
+ int id, size;
+ Node *left, *right, *parent;
+
+ Node(int id = 0, int val = queryDefault) :
+ nodeValue(val), subTreeValue(val), delta(updateDefault),
+ revert(false), id(id), size(1),
+ left(nullptr), right(nullptr), parent(nullptr) {}
+
+ bool isRoot() {
+ return !parent || (parent->left != this &&
+ parent->right != this);
+ }
+
+ void push() {
+ if (revert) {
+ revert = false;
+ swap(left, right);
+ if (left) left->revert ^= 1;
+ if (right) right->revert ^= 1;
+ }
+ nodeValue = joinValueDelta(nodeValue, delta);
+ subTreeValue = joinValueDelta(subTreeValue,
+ _update(delta, size));
+ if (left) left->delta = joinDeltas(left->delta, delta);
+ if (right) right->delta = joinDeltas(right->delta, delta);
+ delta = updateDefault;
+ }
+
+ ll getSubtreeValue() {
+ return joinValueDelta(subTreeValue, _update(delta, size));
+ }
+
+ void update() {
+ subTreeValue = joinValueDelta(nodeValue, delta);
+ size = 1;
+ if (left) {
+ subTreeValue = _query(subTreeValue,
+ left->getSubtreeValue());
+ size += left->size;
+ }
+ if (right) {
+ subTreeValue = _query(subTreeValue,
+ right->getSubtreeValue());
+ size += right->size;
+ }}
+ };
+
+ vector<Node> nodes;
+
+ LCT(int n) : nodes(n) {
+ for (int i = 0; i < n; i++) nodes[i].id = i;
+ }
+
+ void connect(Node* ch, Node* p, int isLeftChild) {
+ if (ch) ch->parent = p;
+ if (isLeftChild >= 0) {
+ if (isLeftChild) p->left = ch;
+ else p->right = ch;
+ }}
+
+ void rotate(Node* x) {
+ Node* p = x->parent;
+ Node* g = p->parent;
+ bool isRootP = p->isRoot();
+ bool leftChildX = (x == p->left);
+
+ connect(leftChildX ? x->right : x->left, p, leftChildX);
+ connect(p, x, !leftChildX);
+ connect(x, g, isRootP ? -1 : p == g->left);
+ p->update();
+ }
+
+ void splay(Node* x) {
+ while (!x->isRoot()) {
+ Node* p = x->parent;
+ Node* g = p->parent;
+ if (!p->isRoot()) g->push();
+ p->push();
+ x->push();
+ if (!p->isRoot()) rotate((x == p->left) ==
+ (p == g->left) ? p : x);
+ rotate(x);
+ }
+ x->push();
+ x->update();
+ }
+
+ Node* expose(Node* x) {
+ Node* last = nullptr;
+ for (Node* y = x; y; y = y->parent) {
+ splay(y);
+ y->left = last;
+ last = y;
+ }
+ splay(x);
+ return last;
+ }
+
+ void makeRoot(Node* x) {
+ expose(x);
+ x->revert ^= 1;
+ }
+
+ bool connected(Node* x, Node* y) {
+ if (x == y) return true;
+ expose(x);
+ expose(y);
+ return x->parent;
+ }
+
+ void link(Node* x, Node* y) {
+ assert(!connected(x, y)); // not yet connected!
+ makeRoot(x);
+ x->parent = y;
+ }
+
+ void cut(Node* x, Node* y) {
+ makeRoot(x);
+ expose(y);
+ //must be a tree edge!
+ assert(!(y->right != x || x->left != nullptr));
+ y->right->parent = nullptr;
+ y->right = nullptr;
+ }
+
+ Node* lca(Node* x, Node* y) {
+ assert(connected(x, y));
+ expose(x);
+ return expose(y);
+ }
+
+ ll query(Node* from, Node* to) {
+ makeRoot(from);
+ expose(to);
+ if (to) return to->getSubtreeValue();
+ return queryDefault;
+ }
+
+ void modify(Node* from, Node* to, ll delta) {
+ makeRoot(from);
+ expose(to);
+ to->delta = joinDeltas(to->delta, delta);
+ }
+};
diff --git a/test/graph/dinic.cpp b/test/graph/dinic.cpp
new file mode 100644
index 0000000..5af7c6f
--- /dev/null
+++ b/test/graph/dinic.cpp
@@ -0,0 +1,62 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+namespace dinic {
+#include <graph/dinic.cpp>
+}
+
+namespace pushRelabel {
+#include <graph/pushRelabel.cpp>
+}
+
+void stress_test() {
+ ll queries = 0;
+ for (int tries = 0; tries < 20'000; tries++) {
+ int n = Random::integer<int>(2, 30);
+ int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1)));
+
+ dinic::adj.assign(n, {});
+ pushRelabel::adj.assign(n, {});
+
+ Graph<NoData, true> g(n);
+ g.erdosRenyi(m);
+ g.forEdges([](int a, int b){
+ ll w = Random::integer<ll>(1, 1'000'000'000'000ll);
+ dinic::addEdge(a, b, w);
+ pushRelabel::addEdge(a, b, w);
+ });
+
+ ll got = dinic::maxFlow(0, n - 1);
+ ll expected = pushRelabel::maxFlow(0, n - 1);
+
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ queries += n;
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 50000;
+constexpr int M = 200000;
+void performance_test() {
+ using namespace dinic;
+ timer t;
+ Graph<NoData> g(N);
+ g.erdosRenyi(M);
+ adj.assign(N, {});
+ g.forEdges([](int a, int b){
+ ll w1 = Random::integer<ll>(1, 1'000'000'000'000ll);
+ ll w2 = Random::integer<ll>(1, 1'000'000'000'000ll);
+ addEdge(a, b, w1);
+ addEdge(b, a, w2);
+ });
+
+ t.start();
+ hash_t hash = maxFlow(0, N - 1);
+ t.stop();
+ if (t.time > 2000) 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/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 <graph/hld.cpp>
+
+struct Seg { // very real segment tree
+ vector<int> a;
+
+ Seg(int n) : a(n) {}
+
+ void inc(int l, int r) {
+ for (int i=l; i<r; i++) a[i]++;
+ }
+};
+
+void stress_test() {
+ for (int tries = 0; tries < 100'000; tries++) {
+ int n = Random::integer<int>(1, 50);
+ Graph<NoData> 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<int> 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<Q; q++) {
+ int u = Random::integer(0, n), v = Random::integer(0, n);
+ for_intervals(u, v, [&](int l, int r) { seg.inc(l, r); });
+ dfs(dfs, u, -1, v);
+ }
+ for (int i=0; i<n; i++) {
+ if (seg.a[in[i]] != a[i]) cerr << "WA: expected " << a[i] << " got " << seg.a[in[i]] << FAIL;
+ }
+ }
+ cerr << "tested random tests: " << 100'000 << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+ timer t;
+ Graph<NoData> g(N);
+ g.tree();
+ adj.assign(N, {});
+ g.forEdges([&](int a, int b){
+ adj[a].push_back(b);
+ adj[b].push_back(a);
+ });
+ vector<pair<int, int>> 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 <graph/reroot.cpp>
+
+void stress_test() {
+ for (int tries = 0; tries < 50'000; tries++) {
+ int n = Random::integer<int>(1, 50);
+ Graph<NoData> 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<n; i++) {
+ if (ans[i] != dfs(dfs, i, -1)) {
+ cerr << "WA expected " << dfs(dfs, i, -1) << " got " << ans[i] << FAIL;
+ }
+ }
+ }
+ cerr << "tested random 50'000 tests" << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+ timer t;
+ Graph<NoData> 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/scc.cpp b/test/graph/scc.cpp
index 123050f..9ab7051 100644
--- a/test/graph/scc.cpp
+++ b/test/graph/scc.cpp
@@ -16,18 +16,6 @@ void stress_test() {
});
scc();
- vector<bool> tmp(n);
- for (int i = 0; i < sz(sccs); i++) {
- for (int x : sccs[i]) {
- if (tmp[x]) cerr << "error: duclicate" << FAIL;
- if (idx[x] != i) cerr << "error: inconsistent" << FAIL;
- tmp[x] = true;
- }
- }
- for (int i = 0; i < n; i++) {
- if (!tmp[i]) cerr << "error: missing" << FAIL;
- }
-
init(n);
vector<ll> seen(n);
int tmpCounter = 0;
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 <graph/virtualTree.cpp>
+
+vector<int> d, par;
+void dfs(int u, vector<vector<int>>& 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<vector<int>>& 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<int>(1, 50);
+ Graph<NoData> g(n);
+ g.tree();
+
+ vector<vector<int>> adj(n);
+ g.forEdges([&](int a, int b){
+ adj[a].push_back(b);
+ adj[b].push_back(a);
+ });
+
+ init(adj);
+ vector<int> ind = Random::distinct(Random::integer(1, n+1), 0, n);
+ auto [idk, tree] = virtualTree(ind);
+ vector<pair<int, int>> edges;
+ for (int i=0; i<sz(idk); i++) for (int v : tree[i]) {
+ edges.emplace_back(idk[i], idk[v]);
+ }
+
+ vector<pair<int, int>> edges2;
+ vector<bool> 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<NoData> g(N);
+ g.tree();
+ vector<vector<int>> adj(N);
+ g.forEdges([&](int a, int b){
+ adj[a].push_back(b);
+ adj[b].push_back(a);
+ });
+
+ init(adj);
+ vector<int> 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<int>, vector<vector<int>>>")
+}
+{ print }
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 23:29:02 +0000