diff options
Diffstat (limited to 'test/graph')
28 files changed, 2118 insertions, 0 deletions
diff --git a/test/graph/2sat.cpp b/test/graph/2sat.cpp new file mode 100644 index 0000000..fc3186e --- /dev/null +++ b/test/graph/2sat.cpp @@ -0,0 +1,133 @@ +#include "../util.h" +#include <graph/scc.cpp> +#define static vector<vector<int>> adj; static // hacky... +#include <graph/2sat.cpp> +#undef static +#undef adj + +struct RandomClause { + int a, b; + int type; + RandomClause(int n) : + a(Random::integer<int>(0, 2*n)), + b(Random::integer<int>(0, 2*n)), + type(Random::integer<int>(0, 8)) {} + + bool eval(vector<int>& sol) const { + bool ba = sol[a]; + bool bb = sol[b]; + if (type == 0) return !ba || bb; + if (type == 1) return ba == bb; + if (type == 2) return ba || bb; + if (type == 3) return ba != bb; + if (type == 4) return ba && bb; + if (type == 5) return !(ba && bb); + + if (type == 6) return ba; + if (type == 7) return !ba; + return false; + } + + void add(sat2& sat) const { + int va = a; + int vb = b; + if (type == 0) sat.addImpl(va, vb); + if (type == 1) sat.addEquiv(va, vb); + if (type == 2) sat.addOr(va, vb); + if (type == 3) sat.addXor(va, vb); + if (type == 4) sat.addAnd(va, vb); + if (type == 5) sat.addNand(va, vb); + + if (type == 6) sat.addTrue(va); + if (type == 7) sat.addFalse(va); + } + + friend ostream& operator<<(ostream& os, const RandomClause& c) { + if (c.a & 1) os << "-"; + os << (c.a >> 1); + if (c.type == 0) os << "=>"; + if (c.type == 1) os << "=="; + if (c.type == 2) os << "or"; + if (c.type == 3) os << "xor"; + if (c.type == 4) os << "and"; + if (c.type == 5) os << "nand"; + + if (c.type == 6) return os; + if (c.type == 7) return os << "==F"; + + if (c.b & 1) os << "-"; + os << (c.b >> 1); + return os; + } +}; + +bool naive(int n, const vector<RandomClause>& clauses) { + for (ll i = 0; i < (1ll << n); i++) { + vector<int> tmp(2*n); + for (ll j = 0; j < n; j++) { + tmp[(2*j) + ((i >> j) & 1)] = 1; + } + bool ok = true; + for (auto& c : clauses) ok &= c.eval(tmp); + if (ok) return true; + } + return false; +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(1, 12); + int m = Random::integer<int>(0, 30); + + vector<RandomClause> clauses; + for (int i = 0; i < m; i++) clauses.emplace_back(n); + + sat2 sat(n); + for (auto& c : clauses) c.add(sat); + adj = sat.adj; + + bool got = sat.solve(); + bool expected = naive(n, clauses); + + if (got) { + for (int i = 0; i < 2*n; i+=2) { + if (sat.sol[i] < 0) cerr << "error: invalid vars" << FAIL; + if (sat.sol[i+1] < 0) cerr << "error: invalid vars" << FAIL; + if (sat.sol[i] == sat.sol[i+1]) cerr << "error: inconsistent vars" << FAIL; + } + for (auto& c : clauses) { + if (!c.eval(sat.sol)) { + cerr << "error: inconsistent" << FAIL; + } + } + } + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 200'000; +constexpr int M = 500'000; +void performance_test() { + timer t; + vector<RandomClause> clauses; + for (int i = 0; i < M; i++) clauses.emplace_back(N); + t.start(); + sat2 sat(N); + for (auto& c : clauses) c.add(sat); + t.stop(); + adj = sat.adj; + t.start(); + hash_t hash = sat.solve(); + t.stop(); + if (t.time > 500) 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/LCA_sparse.cpp b/test/graph/LCA_sparse.cpp new file mode 100644 index 0000000..f6eb345 --- /dev/null +++ b/test/graph/LCA_sparse.cpp @@ -0,0 +1,63 @@ +#include "../util.h" +#include <datastructures/sparseTable.cpp> +#include <graph/LCA_sparse.cpp> +namespace expected { +#include <graph/hld.cpp> +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(2, 30); + 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); + }); + + LCA lca; + lca.init(adj, 0); + + expected::adj = adj; + expected::init(); + + for (int i = 0; i < n; i++) { + for (int j = 0; j <= i; j++) { + auto got = lca.getLCA(i, j); + auto expected = expected::get_lca(i, j); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + queries += n; + } + cerr << "tested random queries: " << queries << 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); + }); + + hash_t hash = 0; + t.start(); + LCA lca; + lca.init(adj, 0); + for (int i = 1; i < N; i++) hash += lca.getLCA(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/TSP.cpp b/test/graph/TSP.cpp new file mode 100644 index 0000000..f9aab2e --- /dev/null +++ b/test/graph/TSP.cpp @@ -0,0 +1,67 @@ +#include "../util.h" +struct edge { + ll dist; + int to; +}; +constexpr ll INF = LL::INF; +#include <graph/TSP.cpp> + +vector<int> naive() { + int n = sz(dist); + vector<int> todo(n - 1); + iota(all(todo), 1); + vector<int> res; + ll best = LL::INF; + do { + int last = 0; + ll cur = 0; + for (int x : todo) { + cur += dist[last][x]; + last = x; + } + cur += dist[last][0]; + if (cur < best) { + best = cur; + res = todo; + res.insert(res.begin(), 0); + res.push_back(0); + } + } while (next_permutation(all(todo))); + return res; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 100'000; i++) { + int n = Random::integer<int>(1, 9); + dist.assign(n, {}); + for (auto& v : dist) v = Random::integers<ll>(n, 0, 1000'000'000); + + auto expected = naive(); + auto got = TSP(); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 19; +void performance_test() { + timer t; + dist.assign(N, {}); + for (auto& v : dist) v = Random::integers<ll>(N, 0, 1000'000'000); + t.start(); + auto got = TSP(); + t.stop(); + + hash_t hash = 0; + for (int x : got) hash += x; + 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/articulationPoints.bcc.cpp b/test/graph/articulationPoints.bcc.cpp new file mode 100644 index 0000000..15f5cf2 --- /dev/null +++ b/test/graph/articulationPoints.bcc.cpp @@ -0,0 +1,78 @@ +#include "../util.h" +struct edge { + ll from, to, id; +}; +#define Edge edge +#include <graph/articulationPoints.cpp> +#undef Edge +#include <datastructures/unionFind.cpp> + +vector<vector<int>> naiveBCC(int m) { + init(m); + + vector<int> seen(sz(adj), -1); + int run = 0; + for (int i = 0; i < sz(adj); i++) { + for (auto e : adj[i]) { + run++; + seen[i] = run; + vector<ll> todo = {e.to}; + seen[e.to] = run; + while (!todo.empty()) { + int c = todo.back(); + todo.pop_back(); + for (auto ee : adj[c]) { + if (seen[ee.to] == run) continue; + seen[ee.to] = run; + todo.push_back(ee.to); + } + } + for (auto ee : adj[i]) { + if (seen[ee.to] == run) unionSets(ee.id, e.id); + } + } + } + vector<vector<int>> res(m); + for (int i = 0; i < m; i++) { + res[findSet(i)].push_back(i); + } + for (auto& v : res) sort(all(v)); + res.erase(remove_if(all(res), [](const vector<int>& v){return sz(v) <= 1;}), res.end()); + sort(all(res)); + return res; +} + +void stress_test_bcc() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(0, max<int>(1, min<int>(300, n*(n-1) / 2 + 1))); + Graph<NoData, 0, 1> g(n); + g.erdosRenyi(m); + + adj.assign(n, {}); + int nextId = 0; + g.forEdges([&](int a, int b){ + adj[a].push_back({a, b, nextId}); + adj[b].push_back({b, a, nextId}); + nextId++; + }); + + auto expected = naiveBCC(nextId); + find(); + vector<vector<int>> got(sz(bcc)); + for (int i = 0; i < sz(bcc); i++) { + for (auto e : bcc[i]) got[i].push_back(e.id); + sort(all(got[i])); + } + sort(all(got)); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test_bcc(); +} diff --git a/test/graph/articulationPoints.bridges.cpp b/test/graph/articulationPoints.bridges.cpp new file mode 100644 index 0000000..a1b89d2 --- /dev/null +++ b/test/graph/articulationPoints.bridges.cpp @@ -0,0 +1,64 @@ +#include "../util.h" +struct edge { + ll from, to, id; +}; +#define Edge edge +#include <graph/articulationPoints.cpp> +#undef Edge + +vector<bool> naiveBridges(const vector<pair<int, int>>& edges) { + vector<bool> res(sz(edges)); + + vector<int> seen(sz(adj), -1); + for (int i = 0; i < sz(edges); i++) { + auto [a, b] = edges[i]; + vector<int> todo = {a}; + seen[a] = i; + while (!todo.empty() && seen[b] != i) { + int c = todo.back(); + todo.pop_back(); + for (auto e : adj[c]) { + if (e.id == i) continue; + if (seen[e.to] == i) continue; + seen[e.to] = i; + todo.push_back(e.to); + } + } + res[i] = seen[b] != i; + } + return res; +} + +void stress_test_bridges() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(0, max<int>(1, min<int>(300, n*(n-1) / 2 + 1))); + Graph<NoData, 0, 1> g(n); + g.erdosRenyi(m); + + adj.assign(n, {}); + vector<pair<int, int>> edges; + g.forEdges([&](int a, int b){ + adj[a].push_back({a, b, sz(edges)}); + adj[b].push_back({b, a, sz(edges)}); + edges.emplace_back(a, b); + }); + + auto expected = naiveBridges(edges); + find(); + vector<bool> got(sz(edges)); + for (auto e : bridges) { + if (got[e.id]) cerr << "error: duclicate" << FAIL; + got[e.id] = true; + } + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test_bridges(); +} diff --git a/test/graph/articulationPoints.cpp b/test/graph/articulationPoints.cpp new file mode 100644 index 0000000..2567a09 --- /dev/null +++ b/test/graph/articulationPoints.cpp @@ -0,0 +1,85 @@ +#include "../util.h" +struct edge { + ll from, to, id; +}; +#define Edge edge +#include <graph/articulationPoints.cpp> +#undef Edge + +vector<bool> naiveArt() { + vector<bool> res(sz(adj)); + + vector<int> seen(sz(adj), -1); + for (int i = 0; i < sz(adj); i++) { + if (adj[i].empty()) continue; + seen[i] = i; + vector<ll> todo = {adj[i][0].to}; + seen[todo[0]] = i; + while (!todo.empty()) { + int c = todo.back(); + todo.pop_back(); + for (auto e : adj[c]) { + if (seen[e.to] == i) continue; + seen[e.to] = i; + todo.push_back(e.to); + } + } + for (auto e : adj[i]) { + if (seen[e.to] != i) res[i] = true; + } + } + return res; +} + +void stress_test_art() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(0, max<int>(1, min<int>(300, n*(n-1) / 2 + 1))); + Graph<NoData, 0, 1> g(n); + g.erdosRenyi(m); + + adj.assign(n, {}); + int nextId = 0; + g.forEdges([&](int a, int b){ + adj[a].push_back({a, b, nextId}); + adj[b].push_back({b, a, nextId}); + nextId++; + }); + + auto expected = naiveArt(); + find(); + vector<bool> got = isArt; + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +constexpr int M = 2'000'000; +void performance_test() { + timer t; + Graph<NoData, 0, 1> g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + int nextId = 0; + g.forEdges([&](int a, int b){ + adj[a].push_back({a, b, nextId}); + adj[b].push_back({b, a, nextId}); + nextId++; + }); + + t.start(); + find(); + t.stop(); + hash_t hash = sz(bridges) + sz(bcc); + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test_art(); + performance_test(); +} diff --git a/test/graph/bellmannFord.cpp b/test/graph/bellmannFord.cpp new file mode 100644 index 0000000..92f1fef --- /dev/null +++ b/test/graph/bellmannFord.cpp @@ -0,0 +1,70 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +struct edge { + int from, to; + ll cost; +}; +#include <graph/bellmannFord.cpp> +namespace floydWarshall { +#include <graph/floydWarshall.cpp> +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'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))); + vector<ll> potential = Random::integers<ll>(n, 0, 1'000'000'000'000ll); + + vector<edge> edges; + floydWarshall::dist.assign(n, vector<ll>(n, INF)); + for (int i = 0; i < n; i++) floydWarshall::dist[i][i] = 0; + + Graph<NoData, true> g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + ll w = Random::integer<ll>(1, 100'000'000'000ll); + w = potential[b] + w - potential[a]; + edges.push_back({a, b, w}); + floydWarshall::dist[a][b] = min(floydWarshall::dist[a][b], w); + }); + + floydWarshall::floydWarshall(); + for (int i = 0; i < n; i++) { + auto got = bellmannFord(n, edges, i); + auto expected = floydWarshall::dist[i]; + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 5'000; +constexpr int M = 20'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + vector<edge> edges; + 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); + edges.push_back({a, b, w1}); + edges.push_back({b, a, w2}); + }); + + t.start(); + auto got = bellmannFord(N, edges, 0); + t.stop(); + hash_t hash = 0; + for (auto x : got) hash += x; + if (t.time > 500) 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/bitonicTSP.cpp b/test/graph/bitonicTSP.cpp new file mode 100644 index 0000000..7c448a2 --- /dev/null +++ b/test/graph/bitonicTSP.cpp @@ -0,0 +1,49 @@ +#include "../util.h" +namespace got { +#include <graph/bitonicTSP.cpp> +} +namespace expected { +#include <graph/bitonicTSPsimple.cpp> +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(1, 30); + + vector<vector<double>> dist(n); + for (auto& v : dist) v = Random::reals<double>(n, 0, 1e18); + + got::dist = dist; + expected::dist = dist; + + auto got = got::bitonicTSP(); + auto expected = got::bitonicTSP(); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +//this is an easy graph... +constexpr int N = 5'000; +void performance_test() { + timer t; + got::dist = vector<vector<double>>(N); + for (auto& v : got::dist) v = Random::reals<double>(N, 0, 1e18); + + + t.start(); + auto got = got::bitonicTSP(); + t.stop(); + hash_t hash = 0; + for (auto x : got) hash += x; + if (t.time > 500) 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/bitonicTSPsimple.cpp b/test/graph/bitonicTSPsimple.cpp new file mode 100644 index 0000000..c79a0ef --- /dev/null +++ b/test/graph/bitonicTSPsimple.cpp @@ -0,0 +1,49 @@ +#include "../util.h" +namespace got { +#include <graph/bitonicTSPsimple.cpp> +} +namespace expected { +#include <graph/bitonicTSP.cpp> +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(1, 30); + + vector<vector<double>> dist(n); + for (auto& v : dist) v = Random::reals<double>(n, 0, 1e18); + + got::dist = dist; + expected::dist = dist; + + auto got = got::bitonicTSP(); + auto expected = got::bitonicTSP(); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +//this is an easy graph... +constexpr int N = 2'000; +void performance_test() { + timer t; + got::dist = vector<vector<double>>(N); + for (auto& v : got::dist) v = Random::reals<double>(N, 0, 1e18); + + + t.start(); + auto got = got::bitonicTSP(); + t.stop(); + hash_t hash = 0; + for (auto x : got) hash += x; + if (t.time > 500) 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/blossom.cpp b/test/graph/blossom.cpp new file mode 100644 index 0000000..714b029 --- /dev/null +++ b/test/graph/blossom.cpp @@ -0,0 +1,76 @@ +#include "../util.h" +namespace tutte { +void gauss(int n, ll mod); +#include <graph/matching.cpp> +#include <math/shortModInv.cpp> +#include <math/lgsFp.cpp> +} +#include <graph/blossom.cpp> + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 5'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(0, max<int>(1, n*(n-1) / 2 + 1)); + + GM blossom(n); + srand(Random::rng()); + tutte::adj.assign(n, {}); + + Graph<NoData> g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + tutte::adj[a].push_back(b); + tutte::adj[b].push_back(a); + + blossom.adj[a].push_back(b); + blossom.adj[b].push_back(a); + }); + + ll got = blossom.match(); + ll expected = tutte::max_matching(); + + vector<bool> seen(n); + ll got2 = 0; + for (int i = 0; i < n; i++) { + int j = blossom.pairs[i]; + if (j >= n) continue; + if (blossom.pairs[j] != i) cerr << "error: inconsitent" << FAIL; + if (j == i) cerr << "error: invalid" << FAIL; + if (j < i) continue; + if (seen[i] || seen[j]) cerr << "error: invalid" << FAIL; + seen[i] = seen[j] = true; + got2++; + } + + if (got != got2) cerr << "got: " << got << ", got2: " << got2 << FAIL; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +//this is an easy graph... +constexpr int N = 100'000; +constexpr int M = 500'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + GM blossom(N); + g.forEdges([&](int a, int b){ + blossom.adj[a].push_back(b); + blossom.adj[b].push_back(a); + }); + + t.start(); + hash_t hash = blossom.match(); + t.stop(); + if (t.time > 200) 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/bronKerbosch.cpp b/test/graph/bronKerbosch.cpp new file mode 100644 index 0000000..1ccd493 --- /dev/null +++ b/test/graph/bronKerbosch.cpp @@ -0,0 +1,73 @@ +#include "../util.h" +#include <graph/bronKerbosch.cpp> + +vector<bits> naiveCliques; + +void naive(bits mask = {}, int l = 0) { + bool maximal = true; + for (ll i = 0; i < l; i++) { + if (mask[i]) continue; + if ((adj[i] & mask) == mask) maximal = false; + } + for (; l < sz(adj); l++) { + if ((adj[l] & mask) == mask) { + maximal = false; + mask[l] = 1; + naive(mask, l + 1); + mask[l] = 0; + } + } + if (maximal and mask.any()) naiveCliques.push_back(mask); +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(2, 15); + int m = Random::integer<int>(0, max<int>(n, min<int>(500, n*(n-1) / 2 + 1))); + + Graph<NoData> g(n); + g.erdosRenyi(m); + adj.assign(n, {}); + g.forEdges([&](int a, int b){ + addEdge(a, b); + }); + + bronKerbosch(); + naiveCliques.clear(); + naive(); + + sort(all(cliques), [](bits a, bits b){return a.to_ullong() < b.to_ullong();}); + sort(all(naiveCliques), [](bits a, bits b){return a.to_ullong() < b.to_ullong();}); + + if (cliques != naiveCliques) cerr << "got: " << sz(cliques) << ", expected: " << sz(naiveCliques) << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 55; +constexpr int M = N*(N-1) / 2 - 2*N; +void performance_test() { + timer t; + + Graph<NoData> g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([&](int a, int b){ + addEdge(a, b); + }); + + t.start(); + bronKerbosch(); + t.stop(); + + hash_t hash = sz(cliques); + if (t.time > 500) 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/centroid.cpp b/test/graph/centroid.cpp new file mode 100644 index 0000000..41d9d0f --- /dev/null +++ b/test/graph/centroid.cpp @@ -0,0 +1,77 @@ +#include "../util.h" +vector<vector<int>> adj; +#include <graph/centroid.cpp> + +int subtreeSize(int c, int p) { + int res = 1; + for (int x : adj[c]) { + if (x == p) continue; + res += subtreeSize(x, c); + } + return res; +} + +vector<int> naive() { + vector<int> res; + for (int i = 0; i < sz(adj); i++) { + bool isCentroid = true; + for (int j : adj[i]) isCentroid &= 2*subtreeSize(j, i) <= sz(adj); + if (isCentroid) res.push_back(i); + } + return res; +} + +void stress_test() { + ll queries = 0; + 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); + }); + + auto expected = naive(); + sort(all(expected)); + + for (int i = 0; i < n; i++) { + auto [a, b] = find_centroid(i); + vector<int> got; + if (a >= 0) got.push_back(a); + if (b >= 0) got.push_back(b); + sort(all(got)); + + if (got != expected) cerr << "error" << FAIL; + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 2'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); + }); + + t.start(); + auto [gotA, gotB] = find_centroid(); + t.stop(); + hash_t hash = gotA + gotB; + if (t.time > 500) 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/cycleCounting.cpp b/test/graph/cycleCounting.cpp new file mode 100644 index 0000000..8e53aec --- /dev/null +++ b/test/graph/cycleCounting.cpp @@ -0,0 +1,79 @@ +#include "../util.h" +#include <datastructures/unionFind.cpp> +#include <graph/cycleCounting.cpp> + +int naive(const vector<pair<int, int>>& edges, int n) { + int res = 0; + for (int i = 1; i < (1ll << sz(edges)); i++) { + vector<int> deg(n); + init(n); + int cycles = 0; + for (int j = 0; j < sz(edges); j++) { + if (((i >> j) & 1) != 0) { + auto [a, b] = edges[j]; + deg[a]++; + deg[b]++; + if (findSet(a) != findSet(b)) { + unionSets(a, b); + } else { + cycles++; + } + } + } + bool ok = cycles == 1; + for (auto d : deg) ok &= d == 0 || d == 2; + if (ok) res++; + } + return res; +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer<int>(1, 8); + int m = Random::integer<int>(0, min<int>(15, n*(n-1) / 2 + 1)); + + Graph<NoData, 0, 1, 1> g(n); + g.erdosRenyi(m); + vector<pair<int, int>> edges; + cycles cyc(n); + g.forEdges([&](int a, int b){ + edges.emplace_back(a, b); + cyc.addEdge(a, b); + }); + + int expected = naive(edges, n); + int got = cyc.count(); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100; +constexpr int M = 20; +void performance_test() { + timer t; + + Graph<NoData> g(N); + g.tree(); + g.erdosRenyi(M); + cycles cyc(N); + g.forEdges([&](int a, int b){ + cyc.addEdge(a, b); + }); + + t.start(); + hash_t hash = cyc.count(); + cerr << sz(cyc.base) << endl; + 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/dijkstra.cpp b/test/graph/dijkstra.cpp new file mode 100644 index 0000000..c0cfb7e --- /dev/null +++ b/test/graph/dijkstra.cpp @@ -0,0 +1,64 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +#include <graph/dijkstra.cpp> +struct edge { + int from, to; + ll cost; +}; +#include <graph/bellmannFord.cpp> + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'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))); + + vector<vector<path>> adj(n); + vector<edge> edges; + + 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); + adj[a].push_back({w, b}); + edges.push_back({a, b, w}); + }); + + for (int i = 0; i < n; i++) { + auto got = dijkstra(adj, i); + auto expected = bellmannFord(n, edges, i); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +constexpr int M = 3'000'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + vector<vector<path>> adj(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); + adj[a].push_back({w1, b}); + adj[b].push_back({w2, a}); + }); + + t.start(); + auto got = dijkstra(adj, 0); + t.stop(); + hash_t hash = 0; + for (auto x : got) hash += x; + 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/dinicScaling.cpp b/test/graph/dinicScaling.cpp new file mode 100644 index 0000000..967d6b1 --- /dev/null +++ b/test/graph/dinicScaling.cpp @@ -0,0 +1,61 @@ +#include "../util.h" +namespace dinic { +#include <graph/dinicScaling.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/euler.cpp b/test/graph/euler.cpp new file mode 100644 index 0000000..6666040 --- /dev/null +++ b/test/graph/euler.cpp @@ -0,0 +1,87 @@ +#include "../util.h" +struct Euler { + Euler(int n) : idx(n), validIdx(n) {} +#include <graph/euler.cpp> +}; + +Euler eulerGraph(int n, int m) { + Euler res(n); + + Graph<NoData> g(n); + g.tree(); + g.forEdges([&](int a, int b) { + res.addEdge(a, b); + }); + + for (int i = n-1; i < m; i++) { + int a = Random::integer<int>(0, n); + int b = Random::integer<int>(0, n); + res.addEdge(a, b); + } + int last = -1; + for (int i = 0; i < n; i++) { + if (sz(res.idx[i]) % 2 != 0) { + if (last >= 0) { + res.addEdge(last, i); + last = -1; + } else { + last = i; + } + } + } + if (last >= 0) cerr << "FAIL" << FAIL; + + return res; +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(n-1, 200); + + auto g = eulerGraph(n, m); + + vector<vector<int>> expected(n); + for (int i = 0; i < n; i++) { + for (int j : g.idx[i]) { + expected[i].push_back(g.to[j]); + } + sort(all(expected[i])); + } + + g.euler(0); + vector<vector<int>> got(n); + if (g.cycle.front() != g.cycle.back()) cerr << "error: not cyclic" << FAIL; + for (int i = 1; i < sz(g.cycle); i++) { + int a = g.cycle[i-1]; + int b = g.cycle[i]; + got[a].push_back(b); + got[b].push_back(a); + } + for (auto& v : got) sort(all(v)); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100'000; +constexpr int M = 1'000'000; +void performance_test() { + timer t; + auto g = eulerGraph(N, M); + t.start(); + g.euler(0); + t.stop(); + hash_t hash = 0; + for (int x : g.cycle) hash += x; + if (t.time > 500) 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/floydWarshall.cpp b/test/graph/floydWarshall.cpp new file mode 100644 index 0000000..a93a9ea --- /dev/null +++ b/test/graph/floydWarshall.cpp @@ -0,0 +1,90 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +struct edge { + int from, to; + ll cost; +}; +#include <graph/bellmannFord.cpp> +namespace floydWarshall { +#include <graph/floydWarshall.cpp> +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'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))); + vector<ll> potential = Random::integers<ll>(n, 0, 1'000'000'000'000ll); + + vector<edge> edges; + floydWarshall::dist.assign(n, vector<ll>(n, INF)); + for (int i = 0; i < n; i++) floydWarshall::dist[i][i] = 0; + + Graph<NoData, true> g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + ll w = Random::integer<ll>(1, 100'000'000'000ll); + w = potential[b] + w - potential[a]; + edges.push_back({a, b, w}); + floydWarshall::dist[a][b] = min(floydWarshall::dist[a][b], w); + }); + + vector<vector<ll>> orig = floydWarshall::dist; + + floydWarshall::floydWarshall(); + for (int i = 0; i < n; i++) { + for (int j = 0; j < 10; j++) { + int k = Random::integer<int>(0, n); + auto path = floydWarshall::getPath(i, k); + if (path.empty() != (floydWarshall::dist[i][k] == INF)) cerr << "error: reconstruction" << FAIL; + if (path.empty()) continue; + if (path.front() != i) cerr << "error: start" << FAIL; + if (path.back() != k) cerr << "error: end" << FAIL; + for (int l = 1; l < sz(path); l++) { + if (floydWarshall::dist[i][path[l-1]] + + orig[path[l-1]][path[l]] + + floydWarshall::dist[path[l]][k] != + floydWarshall::dist[i][k]) cerr << "error: edge" << FAIL; + } + } + } + + for (int i = 0; i < n; i++) { + auto got = floydWarshall::dist[i]; + auto expected = bellmannFord(n, edges, i); + + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500; +constexpr int M = 20'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + floydWarshall::dist.assign(N, vector<ll>(N, INF)); + for (int i = 0; i < N; i++) floydWarshall::dist[i][i] = 0; + 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); + floydWarshall::dist[a][b] = w1; + floydWarshall::dist[b][a] = w2; + }); + + t.start(); + floydWarshall::floydWarshall(); + t.stop(); + hash_t hash = 0; + for (auto x : floydWarshall::dist[42]) hash += x; + if (t.time > 500) 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/havelHakimi.cpp b/test/graph/havelHakimi.cpp new file mode 100644 index 0000000..71476ec --- /dev/null +++ b/test/graph/havelHakimi.cpp @@ -0,0 +1,65 @@ +#include "../util.h" +#include <graph/havelHakimi.cpp> + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(0, n*(n-1) / 2 + 1); + Graph g(n); + g.erdosRenyi(m); + + vector<int> expected(n); + for (int i = 0; i < n; i++) expected[i] = g.deg(i); + + auto res = havelHakimi(expected); + if (sz(res) != n) cerr << "error: wrong number of nodes" << FAIL; + vector<vector<int>> rev(n); + vector<int> got(n); + for (int i = 0; i < n; i++) { + got[i] = sz(res[i]); + for (int j : res[i]) { + if (j < 0 || j >= n) cerr << "error: invalid edge" << FAIL; + rev[j].push_back(i); + } + } + + for (int i = 0; i < n; i++) { + sort(all(res[i])); + sort(all(rev[i])); + if (res[i] != rev[i]) cerr << "error: graph is directed" << FAIL; + for (int j : res[i]) if (j == i) cerr << "error: graph has loop" << FAIL; + for (int j = 1; j < sz(res[i]); j++) { + if (res[i][j] == res[i][j-1]) cerr << "error: multiedge" << FAIL; + } + } + + if (expected != got) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 200'000; +constexpr int M = 1'000'000; +void performance_test() { + timer t; + Graph g(N); + g.erdosRenyi(M); + + vector<int> expected(N); + for (int i = 0; i < N; i++) expected[i] = g.deg(i); + + t.start(); + auto res = havelHakimi(expected); + t.stop(); + hash_t hash = 0; + for (auto& v : res) hash += sz(v); + if (t.time > 500) 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/hopcroftKarp.cpp b/test/graph/hopcroftKarp.cpp new file mode 100644 index 0000000..05599dd --- /dev/null +++ b/test/graph/hopcroftKarp.cpp @@ -0,0 +1,74 @@ +#include "../util.h" +namespace kuhn { +#include <graph/maxCarBiMatch.cpp> +} +namespace hk { +#include <graph/hopcroftKarp.cpp> +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(0, max<int>(1, n*(n-1) / 2 + 1)); + + kuhn::adj.assign(2*n, {}); + hk::adj.assign(2*n, {}); + + Graph<NoData> g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + kuhn::adj[a].push_back(n+b); + kuhn::adj[b+n].push_back(a); + + hk::adj[a].push_back(n+b); + hk::adj[b+n].push_back(a); + }); + + ll got = hk::hopcroft_karp(n); + ll expected = kuhn::kuhn(n); + + vector<bool> seen(2*n); + ll got2 = 0; + for (int i = 0; i < n; i++) { + int j = hk::pairs[i]; + if (j < 0) continue; + if (hk::pairs[j] != i) cerr << "error: inconsitent" << FAIL; + if (j == i) cerr << "error: invalid" << FAIL; + if (j < i) continue; + if (seen[i] || seen[j]) cerr << "error: invalid" << FAIL; + seen[i] = seen[j] = true; + got2++; + } + + if (got != got2) cerr << "got: " << got << ", got2: " << got2 << FAIL; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +//this is an easy graph... +constexpr int N = 100'000; +constexpr int M = 500'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + hk::adj.assign(2*N, {}); + g.forEdges([&](int a, int b){ + hk::adj[a].push_back(N+b); + hk::adj[b+N].push_back(a); + }); + + t.start(); + hash_t hash = hk::hopcroft_karp(N); + t.stop(); + if (t.time > 300) 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/kruskal.cpp b/test/graph/kruskal.cpp new file mode 100644 index 0000000..f6245b9 --- /dev/null +++ b/test/graph/kruskal.cpp @@ -0,0 +1,91 @@ +#include "../util.h" +#include <datastructures/unionFind.cpp> + +struct edge { + int from, to; + ll cost; + bool operator<(const edge& o) const { + return cost > o.cost; + } +}; +ll kruskal(vector<edge>& edges, int n) { + init(n); + #define Edge edge + #include <graph/kruskal.cpp> + #undef Edge + return cost; +} + +ll prim(vector<edge>& edges, int n) { + vector<vector<pair<ll, int>>> adj(n); + for (auto [a, b, d] : edges) { + adj[a].emplace_back(d, b); + adj[b].emplace_back(d, a); + } + priority_queue<pair<ll, int>> todo; + vector<bool> seen(n); + ll res = 0; + for (ll i = 0; i < n; i++) { + if (seen[i]) continue; + todo.push({0, i}); + while (!todo.empty()) { + auto [d, c] = todo.top(); + todo.pop(); + if (seen[c]) continue; + seen[c] = true; + res += d; + for (auto e : adj[c]) { + todo.push(e); + } + } + } + return res; +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer<int>(2, 30); + int m = Random::integer<int>(0, max<int>(n, min<int>(500, n*(n-1) / 2 + 1))); + + + Graph<NoData> g(n); + g.erdosRenyi(m); + vector<edge> edges; + g.forEdges([&](int a, int b){ + ll w = Random::integer<ll>(-1'000'000'000ll, 1'000'000'000ll); + edges.push_back({a, b, w}); + }); + + ll got = kruskal(edges, n); + ll expected = prim(edges, n); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +constexpr int M = 3'000'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + vector<edge> edges; + g.forEdges([&](int a, int b){ + ll w = Random::integer<ll>(-1'000'000'000ll, 1'000'000'000ll); + edges.push_back({a, b, w}); + }); + + t.start(); + hash_t hash = kruskal(edges, N); + 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/matching.cpp b/test/graph/matching.cpp new file mode 100644 index 0000000..b8fbc6c --- /dev/null +++ b/test/graph/matching.cpp @@ -0,0 +1,62 @@ +#include "../util.h" +namespace tutte { +void gauss(int n, ll mod); +#include <graph/matching.cpp> +#include <math/shortModInv.cpp> +#include <math/lgsFp.cpp> +} +#include <graph/blossom.cpp> + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 5'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(0, max<int>(1, n*(n-1) / 2 + 1)); + + GM blossom(n); + srand(Random::rng()); + tutte::adj.assign(n, {}); + + Graph<NoData> g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + tutte::adj[a].push_back(b); + tutte::adj[b].push_back(a); + + blossom.adj[a].push_back(b); + blossom.adj[b].push_back(a); + }); + + ll got = tutte::max_matching(); + ll expected = blossom.match(); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 125; +constexpr int M = 5'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + srand(Random::rng()); + tutte::adj.assign(N, {}); + g.forEdges([&](int a, int b){ + tutte::adj[a].push_back(b); + tutte::adj[b].push_back(a); + }); + + t.start(); + hash_t hash = tutte::max_matching(); + t.stop(); + if (t.time > 500) 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/maxCarBiMatch.cpp b/test/graph/maxCarBiMatch.cpp new file mode 100644 index 0000000..6d7fad0 --- /dev/null +++ b/test/graph/maxCarBiMatch.cpp @@ -0,0 +1,74 @@ +#include "../util.h" +namespace kuhn { +#include <graph/maxCarBiMatch.cpp> +} +namespace hk { +#include <graph/hopcroftKarp.cpp> +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(0, max<int>(1, n*(n-1) / 2 + 1)); + + kuhn::adj.assign(2*n, {}); + hk::adj.assign(2*n, {}); + + Graph<NoData> g(n); + g.erdosRenyi(m); + g.forEdges([&](int a, int b){ + kuhn::adj[a].push_back(n+b); + kuhn::adj[b+n].push_back(a); + + hk::adj[a].push_back(n+b); + hk::adj[b+n].push_back(a); + }); + + ll got = kuhn::kuhn(n); + ll expected = hk::hopcroft_karp(n); + + vector<bool> seen(2*n); + ll got2 = 0; + for (int i = 0; i < n; i++) { + int j = kuhn::pairs[i]; + if (j < 0) continue; + if (kuhn::pairs[j] != i) cerr << "error: inconsitent" << FAIL; + if (j == i) cerr << "error: invalid" << FAIL; + if (j < i) continue; + if (seen[i] || seen[j]) cerr << "error: invalid" << FAIL; + seen[i] = seen[j] = true; + got2++; + } + + if (got != got2) cerr << "got: " << got << ", got2: " << got2 << FAIL; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +//this is an easy graph... +constexpr int N = 10'000; +constexpr int M = 100'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + kuhn::adj.assign(2*N, {}); + g.forEdges([&](int a, int b){ + kuhn::adj[a].push_back(N+b); + kuhn::adj[b+N].push_back(a); + }); + + t.start(); + hash_t hash = kuhn::kuhn(N); + t.stop(); + if (t.time > 200) 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/maxWeightBipartiteMatching.cpp b/test/graph/maxWeightBipartiteMatching.cpp new file mode 100644 index 0000000..d245405 --- /dev/null +++ b/test/graph/maxWeightBipartiteMatching.cpp @@ -0,0 +1,59 @@ +#include "../util.h" +#pragma GCC diagnostic ignored "-Wshadow" +namespace matching { + constexpr int N_LEFT = 1000; + constexpr int N_RIGHT = 1000; + constexpr double INF = LD::INF; + #include <graph/maxWeightBipartiteMatching.cpp> +} +namespace mcmf { + #include <graph/minCostMaxFlow.cpp> +} + + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + auto [l, r] = Random::pair<int>(1, 30); + mcmf::MinCostFlow mcmf(l+r+2, 0, 1); + + for (int i = 0; i < l; i++) mcmf.addEdge(0, 2 + i, 1, 0); + for (int i = 0; i < r; i++) mcmf.addEdge(2 + l + i, 1, 1, 0); + for (int i = 0; i < l; i++) { + for (int j = 0; j < r; j++) { + matching::costs[i][j] = Random::integer<int>(-100, 100); + mcmf.addEdge(2 + i, 2 + l + j, 1, -matching::costs[i][j]); + } + } + + double got = matching::match(l, r); + mcmf.mincostflow(); + ll expected = -mcmf.mincost; + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += l + r; + } + cerr << "tested random queries: " << queries << endl; +} + +void performance_test() { + using namespace matching; + timer t; + + for (int i = 0; i < N_LEFT; i++) { + for (int j = 0; j < N_RIGHT; j++) { + costs[i][j] = Random::integer<int>(-100, 100); + } + } + + t.start(); + hash_t hash = match(N_LEFT, N_RIGHT); + 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/minCostMaxFlow.cpp b/test/graph/minCostMaxFlow.cpp new file mode 100644 index 0000000..8c92aa7 --- /dev/null +++ b/test/graph/minCostMaxFlow.cpp @@ -0,0 +1,68 @@ +#include "../util.h" +#pragma GCC diagnostic ignored "-Wshadow" +namespace matching { + constexpr int N_LEFT = 1000; + constexpr int N_RIGHT = 1000; + constexpr double INF = LD::INF; + #include <graph/maxWeightBipartiteMatching.cpp> +} +namespace mcmf { + #include <graph/minCostMaxFlow.cpp> +} + + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + auto [l, r] = Random::pair<int>(1, 30); + mcmf::MinCostFlow mcmf(l+r+2, 0, 1); + + for (int i = 0; i < l; i++) mcmf.addEdge(0, 2 + i, 1, 0); + for (int i = 0; i < r; i++) mcmf.addEdge(2 + l + i, 1, 1, 0); + for (int i = 0; i < l; i++) { + for (int j = 0; j < r; j++) { + matching::costs[i][j] = Random::integer<int>(-100, 100); + mcmf.addEdge(2 + i, 2 + l + j, 1, -matching::costs[i][j]); + } + } + + mcmf.mincostflow(); + ll got = -mcmf.mincost; + double expected = matching::match(l, r); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += l + r; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000; +constexpr int M = 10'000; +void performance_test() { + using namespace mcmf; + timer t; + + Graph<NoData> g(N); + g.erdosRenyi(M); + MinCostFlow mcmf(N, 0, 1); + vector<ll> potential = Random::integers<ll>(N, 0, 1'000'000ll); + g.forEdges([&](int a, int b){ + ll c = Random::integer<ll>(1, 1000'000); + ll cost = Random::integer<ll>(0, 1000'000); + mcmf.addEdge(a, b, c, potential[b] + cost - potential[a]); + mcmf.addEdge(b, a, c, potential[a] + cost - potential[b]); + }); + + t.start(); + mcmf.mincostflow(); + t.stop(); + + hash_t hash = mcmf.mincost; + if (t.time > 500) 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/pushRelabel.cpp b/test/graph/pushRelabel.cpp new file mode 100644 index 0000000..ac3b079 --- /dev/null +++ b/test/graph/pushRelabel.cpp @@ -0,0 +1,61 @@ +#include "../util.h" +namespace dinic { +#include <graph/dinicScaling.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 = pushRelabel::maxFlow(0, n - 1); + ll expected = dinic::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 pushRelabel; + 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 > 300) 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/scc.cpp b/test/graph/scc.cpp new file mode 100644 index 0000000..123050f --- /dev/null +++ b/test/graph/scc.cpp @@ -0,0 +1,92 @@ +#include "../util.h" +#include <graph/scc.cpp> +#include <datastructures/unionFind.cpp> + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(0, max<int>(1, min<int>(100, n*(n-1) / 2 + 1))); + Graph<NoData, true> g(n); + g.erdosRenyi(m); + + adj.assign(n, {}); + g.forEdges([](int a, int b){ + adj[a].push_back(b); + }); + 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; + auto reach = [&](int a, int b) { + tmpCounter++; + seen[a] = tmpCounter; + vector<int> todo = {a}; + while (seen[b] != tmpCounter && !todo.empty()) { + a = todo.back(); + todo.pop_back(); + g.forOut(a, [&](int /**/, int x){ + if (seen[x] != tmpCounter) { + seen[x] = tmpCounter; + todo.push_back(x); + } + }); + } + return seen[b] == tmpCounter; + }; + for (int a = 0; a < n; a++) { + for (int b = 0; b < a; b++) { + if (findSet(a) == findSet(b)) continue; + if (reach(a, b) && reach(b, a)) unionSets(a, b); + } + } + + for (int a = 0; a < n; a++) { + for (int b = 0; b <= a; b++) { + bool got = idx[a] == idx[b]; + bool expected = findSet(a) == findSet(b); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +constexpr int M = 2'000'000; +void performance_test() { + timer t; + Graph<NoData, true> g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + adj[a].push_back(b); + }); + + t.start(); + scc(); + t.stop(); + hash_t hash = 0; + for (int x : idx) hash += x; + if (t.time > 500) 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/stoerWagner.cpp b/test/graph/stoerWagner.cpp new file mode 100644 index 0000000..2003f09 --- /dev/null +++ b/test/graph/stoerWagner.cpp @@ -0,0 +1,81 @@ +#include "../util.h" +constexpr ll INF = LL::INF; + +namespace stoerWagner { +#include <graph/stoerWagner.cpp> + void addEdge(int u, int v, ll c) { + adj[u].push_back({u, v, c}); + adj[v].push_back({v, u, c}); + } +} + +namespace pushRelabel { +#include <graph/pushRelabel.cpp> + ll minCut() { + ll res = INF; + for (int i = 0; i < sz(adj); i++) { + for (int j = 0; j < i; j++) { + if (i == j) continue; + res = min(res, maxFlow(i, j)); + for (auto& v : adj) { + for (auto& e : v) { + e.f = 0; + } + } + } + } + return res; + } +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 5'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))); + + stoerWagner::adj.assign(n, {}); + pushRelabel::adj.assign(n, {}); + + Graph<NoData> g(n); + g.erdosRenyi(m); + g.forEdges([](int a, int b){ + ll w = Random::integer<ll>(1, 1'000'000'000'000ll); + stoerWagner::addEdge(a, b, w); + pushRelabel::addEdge(a, b, w); + pushRelabel::addEdge(b, a, w); + }); + + ll got = stoerWagner::stoer_wagner(); + ll expected = pushRelabel::minCut(); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 200; +constexpr int M = 10000; +void performance_test() { + using namespace stoerWagner; + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + ll w = Random::integer<ll>(1, 1'000'000'000'000ll); + addEdge(a, b, w); + }); + + t.start(); + hash_t hash = stoer_wagner(); + 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/treeIsomorphism.cpp b/test/graph/treeIsomorphism.cpp new file mode 100644 index 0000000..97f4df4 --- /dev/null +++ b/test/graph/treeIsomorphism.cpp @@ -0,0 +1,126 @@ +#include "../util.h" +struct tree { + tree(int n) : adj(n) {} + #include <graph/treeIsomorphism.cpp> + #include <graph/centroid.cpp> + + pair<int, int> treeLabel() { + auto [a, b] = find_centroid(0); + if (a >= 0) a = treeLabel(a); + if (b >= 0) b = treeLabel(b); + if (a > b) swap(a, b); + return {a, b}; + } +}; + +void stress_test_eq() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer<int>(1, 50); + Graph<NoData> g(n); + g.tree(); + + tree t(n); + + g.forEdges([&](int a, int b){ + t.adj[a].push_back(b); + t.adj[b].push_back(a); + }); + auto [gotA, gotB] = t.treeLabel(); + + g.permutate(); + t.adj.assign(n, {}); + g.forEdges([&](int a, int b){ + t.adj[a].push_back(b); + t.adj[b].push_back(a); + }); + auto [expectedA, expectedB] = t.treeLabel(); + + if (gotA != expectedA) cerr << "got: " << gotA << ", expected: " << expectedA << FAIL; + if (gotB != expectedB) cerr << "got: " << gotB << ", expected: " << expectedB << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +void test_tiny() { + vector<int> expected = {1,1,1,1,2,3,6,11,23}; //#A000055 + for (int i = 1; i < sz(expected); i++) { + set<pair<int, int>> got; + tree t(i); + + int labeled = 1; + for (int j = 3; j < i; j++) labeled *= i; + for (int j = 0; j < 10 * labeled; j++) { + Graph<NoData> g(i); + g.tree(); + + t.adj.assign(i, {}); + g.forEdges([&](int a, int b){ + t.adj[a].push_back(b); + t.adj[b].push_back(a); + }); + + got.insert(t.treeLabel()); + } + if (sz(got) != expected[i]) cerr << i << ", got: " << sz(got) << ", expected: " << expected[i] << FAIL; + } + cerr << "tested tiny: " << sz(expected) << endl; +} + +void stress_test_neq() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer<int>(20, 50); + Graph<NoData> g(n); + g.tree(); + + tree t(n); + + g.forEdges([&](int a, int b){ + t.adj[a].push_back(b); + t.adj[b].push_back(a); + }); + auto [gotA, gotB] = t.treeLabel(); + + g.clear().tree(); + t.adj.assign(n, {}); + g.forEdges([&](int a, int b){ + t.adj[a].push_back(b); + t.adj[b].push_back(a); + }); + auto [expectedA, expectedB] = t.treeLabel(); + + if (gotA == expectedA && gotA >= 0) cerr << "error: " << n << ", " << tries << FAIL; + if (gotB == expectedB) cerr << "error: " << n << ", " << tries << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 500'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.tree(); + + tree tt(N); + g.forEdges([&](int a, int b){ + tt.adj[a].push_back(b); + tt.adj[b].push_back(a); + }); + + t.start(); + auto [gotA, gotB] = tt.treeLabel(); + t.stop(); + hash_t hash = gotA + gotB; + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test_eq(); + test_tiny(); + stress_test_neq(); + performance_test(); +} |