diff options
Diffstat (limited to 'test/graph')
28 files changed, 201 insertions, 209 deletions
diff --git a/test/graph/2sat.cpp b/test/graph/2sat.cpp index 4635086..fd6326c 100644 --- a/test/graph/2sat.cpp +++ b/test/graph/2sat.cpp @@ -25,7 +25,7 @@ struct RandomClause { return false; } - void add(sat2& sat) const { + void add(SAT2& sat) const { int va = a; int vb = b; if (type == 0) sat.addImpl(va, vb); @@ -80,9 +80,8 @@ void stress_test() { vector<RandomClause> clauses; for (int i = 0; i < m; i++) clauses.emplace_back(n); - sat2 sat(n); + SAT2 sat(n); for (auto& c : clauses) c.add(sat); - adj = sat.adj; bool got = sat.solve(); bool expected = naive(n, clauses); @@ -113,11 +112,8 @@ void performance_test() { vector<RandomClause> clauses; for (int i = 0; i < M; i++) clauses.emplace_back(N); t.start(); - sat2 sat(N); + 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; diff --git a/test/graph/2sat.cpp.awk b/test/graph/2sat.cpp.awk deleted file mode 100644 index d0215d8..0000000 --- a/test/graph/2sat.cpp.awk +++ /dev/null @@ -1,6 +0,0 @@ -/scc variablen/ { - print; - print "\tvector<vector<int>> adj;"; - next -} -{ print } diff --git a/test/graph/TSP.cpp b/test/graph/TSP.cpp index 930ec88..3b1ce94 100644 --- a/test/graph/TSP.cpp +++ b/test/graph/TSP.cpp @@ -7,9 +7,9 @@ constexpr ll INF = LL::INF; #include <graph/TSP.cpp> vector<int> naive() { - int n = sz(dist); + int n = ssize(dist); vector<int> todo(n - 1); - iota(all(todo), 1); + iota(begin(todo), end(todo), 1); vector<int> res; ll best = LL::INF; do { @@ -26,7 +26,7 @@ vector<int> naive() { res.insert(res.begin(), 0); res.push_back(0); } - } while (next_permutation(all(todo))); + } while (ranges::next_permutation(todo).found); return res; } @@ -39,7 +39,7 @@ void stress_test() { auto expected = naive(); auto got = TSP(); - + if (got != expected) cerr << "error" << FAIL; queries += n; } diff --git a/test/graph/articulationPoints.bcc.cpp b/test/graph/articulationPoints.bcc.cpp index e9fc32f..927ceb4 100644 --- a/test/graph/articulationPoints.bcc.cpp +++ b/test/graph/articulationPoints.bcc.cpp @@ -8,11 +8,11 @@ struct edge { #include <datastructures/unionFind.cpp> vector<vector<int>> naiveBCC(int m) { - init(m); + UnionFind uf(m); - vector<int> seen(sz(adj), -1); + vector<int> seen(ssize(adj), -1); int run = 0; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { for (auto e : adj[i]) { run++; seen[i] = run; @@ -28,17 +28,17 @@ vector<vector<int>> naiveBCC(int m) { } } for (auto ee : adj[i]) { - if (seen[ee.to] == run) unionSets(ee.id, e.id); + if (seen[ee.to] == run) uf.link(ee.id, e.id); } } } vector<vector<int>> res(m); for (int i = 0; i < m; i++) { - res[findSet(i)].push_back(i); + res[uf.find(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)); + for (auto& v : res) ranges::sort(v); + res.erase(begin(ranges::remove_if(res, [](const vector<int>& v){return ssize(v) <= 1;})), end(res)); + ranges::sort(res); return res; } @@ -60,12 +60,12 @@ void stress_test_bcc(int LIM) { auto expected = naiveBCC(nextId); find(); - vector<vector<int>> got(sz(bcc)); - for (int i = 0; i < sz(bcc); i++) { + vector<vector<int>> got(ssize(bcc)); + for (int i = 0; i < ssize(bcc); i++) { for (auto e : bcc[i]) got[i].push_back(e.id); - sort(all(got[i])); + ranges::sort(got[i]); } - sort(all(got)); + ranges::sort(got); if (got != expected) cerr << "error" << FAIL; queries += n; diff --git a/test/graph/articulationPoints.bridges.cpp b/test/graph/articulationPoints.bridges.cpp index a1b89d2..15408ea 100644 --- a/test/graph/articulationPoints.bridges.cpp +++ b/test/graph/articulationPoints.bridges.cpp @@ -7,10 +7,10 @@ struct edge { #undef Edge vector<bool> naiveBridges(const vector<pair<int, int>>& edges) { - vector<bool> res(sz(edges)); + vector<bool> res(ssize(edges)); - vector<int> seen(sz(adj), -1); - for (int i = 0; i < sz(edges); i++) { + vector<int> seen(ssize(adj), -1); + for (int i = 0; i < ssize(edges); i++) { auto [a, b] = edges[i]; vector<int> todo = {a}; seen[a] = i; @@ -40,14 +40,14 @@ void stress_test_bridges() { 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)}); + adj[a].push_back({a, b, ssize(edges)}); + adj[b].push_back({b, a, ssize(edges)}); edges.emplace_back(a, b); }); auto expected = naiveBridges(edges); find(); - vector<bool> got(sz(edges)); + vector<bool> got(ssize(edges)); for (auto e : bridges) { if (got[e.id]) cerr << "error: duclicate" << FAIL; got[e.id] = true; diff --git a/test/graph/articulationPoints.cpp b/test/graph/articulationPoints.cpp index 8ee6bc4..6960f73 100644 --- a/test/graph/articulationPoints.cpp +++ b/test/graph/articulationPoints.cpp @@ -7,10 +7,10 @@ struct edge { #undef Edge vector<bool> naiveArt() { - vector<bool> res(sz(adj)); + vector<bool> res(ssize(adj)); - vector<int> seen(sz(adj), -1); - for (int i = 0; i < sz(adj); i++) { + vector<int> seen(ssize(adj), -1); + for (int i = 0; i < ssize(adj); i++) { if (adj[i].empty()) continue; seen[i] = i; vector<ll> todo = {adj[i][0].to}; @@ -72,9 +72,9 @@ void performance_test() { }); t.start(); - find(); + find(); t.stop(); - hash_t hash = sz(bridges) + sz(bcc); + hash_t hash = ssize(bridges) + ssize(bcc); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/binary_lifting.cpp b/test/graph/binary_lifting.cpp new file mode 100644 index 0000000..20318da --- /dev/null +++ b/test/graph/binary_lifting.cpp @@ -0,0 +1,60 @@ +#include "../util.h" +#include <graph/binary_lifting.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); + }); + + Lift lift(adj, 0); + + expected::adj = adj; + expected::init(); + + for (int i = 0; i < n; i++) { + for (int j = 0; j <= i; j++) { + auto got = lift.lca(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(); + Lift lift(adj, 0); + for (int i = 1; i < N; i++) hash += lift.lca(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/blossom.cpp b/test/graph/blossom.cpp index f44f815..56d3132 100644 --- a/test/graph/blossom.cpp +++ b/test/graph/blossom.cpp @@ -1,6 +1,6 @@ #include "../util.h" namespace tutte { -void gauss(int n, int m); +vector<int> gauss(vector<vector<ll>> &mat); #include <graph/matching.cpp> #include <math/shortModInv.cpp> #include <math/lgsFp.cpp> @@ -15,20 +15,20 @@ void stress_test() { GM blossom(n); srand(Random::rng()); - tutte::adj.assign(n, {}); + vector<vector<int>> adj(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); + adj[a].push_back(b); + 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(); + ll expected = tutte::max_matching(adj); vector<bool> seen(n); ll got2 = 0; diff --git a/test/graph/bronKerbosch.cpp b/test/graph/bronKerbosch.cpp index 1a90c06..8c0a200 100644 --- a/test/graph/bronKerbosch.cpp +++ b/test/graph/bronKerbosch.cpp @@ -9,7 +9,7 @@ void naive(bits mask = {}, int l = 0) { if (mask[i]) continue; if ((adj[i] & mask) == mask) maximal = false; } - for (; l < sz(adj); l++) { + for (; l < ssize(adj); l++) { if ((adj[l] & mask) == mask) { maximal = false; mask[l] = 1; @@ -37,10 +37,10 @@ void stress_test() { 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();}); + ranges::sort(cliques, {}, [](bits x) { return x.to_ullong(); }); + ranges::sort(naiveCliques, {}, [](bits x) { return x.to_ullong(); }); - if (cliques != naiveCliques) cerr << "got: " << sz(cliques) << ", expected: " << sz(naiveCliques) << FAIL; + if (cliques != naiveCliques) cerr << "got: " << ssize(cliques) << ", expected: " << ssize(naiveCliques) << FAIL; queries += n; } cerr << "tested random queries: " << queries << endl; @@ -62,7 +62,7 @@ void performance_test() { bronKerbosch(); t.stop(); - hash_t hash = sz(cliques); + hash_t hash = ssize(cliques); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/centroid.cpp b/test/graph/centroid.cpp index c3f1d3f..d231c3e 100644 --- a/test/graph/centroid.cpp +++ b/test/graph/centroid.cpp @@ -13,9 +13,9 @@ int subtreeSize(int c, int p) { vector<int> naive() { vector<int> res; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { bool isCentroid = true; - for (int j : adj[i]) isCentroid &= 2*subtreeSize(j, i) <= sz(adj); + for (int j : adj[i]) isCentroid &= 2*subtreeSize(j, i) <= ssize(adj); if (isCentroid) res.push_back(i); } return res; @@ -33,16 +33,16 @@ void stress_test() { adj[a].push_back(b); adj[b].push_back(a); }); - + auto expected = naive(); - sort(all(expected)); + ranges::sort(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)); + ranges::sort(got); if (got != expected) cerr << "error" << FAIL; } @@ -63,7 +63,7 @@ void performance_test() { adj[b].push_back(a); }); - t.start(); + t.start(); auto [gotA, gotB] = find_centroid(); t.stop(); hash_t hash = gotA + gotB; diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp index 8114339..ef087e3 100644 --- a/test/graph/connect.cpp +++ b/test/graph/connect.cpp @@ -52,8 +52,8 @@ void stress_test(int lim) { int m = Random::integer<int>(30, 300); vector<int> insertOrder(m); - iota(all(insertOrder), 0); - shuffle(all(insertOrder), Random::rng); + iota(begin(insertOrder), end(insertOrder), 0); + ranges::shuffle(insertOrder, Random::rng); vector<pair<int, int>> edges(m, {-1, -1}); connect con(n, m); @@ -104,15 +104,15 @@ void performance_test() { t.stop(); vector<int> insertOrder(M); - iota(all(insertOrder), 0); - shuffle(all(insertOrder), Random::rng); + iota(begin(insertOrder), end(insertOrder), 0); + ranges::shuffle(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(); diff --git a/test/graph/cycleCounting.cpp b/test/graph/cycleCounting.cpp index 6459162..bfe313e 100644 --- a/test/graph/cycleCounting.cpp +++ b/test/graph/cycleCounting.cpp @@ -4,20 +4,16 @@ int naive(const vector<pair<int, int>>& edges, int n) { int res = 0; - for (int i = 1; i < (1ll << sz(edges)); i++) { + for (int i = 1; i < (1ll << ssize(edges)); i++) { vector<int> deg(n); - init(n); + UnionFind uf(n); int cycles = 0; - for (int j = 0; j < sz(edges); j++) { + for (int j = 0; j < ssize(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++; - } + if (!uf.link(a, b)) cycles++; } } bool ok = cycles == 1; @@ -66,7 +62,7 @@ void performance_test() { t.start(); hash_t hash = cyc.count(); - cerr << sz(cyc.base) << endl; + cerr << ssize(cyc.base) << endl; t.stop(); if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; diff --git a/test/graph/dijkstra.cpp b/test/graph/dijkstra.cpp index dd5b826..d79e700 100644 --- a/test/graph/dijkstra.cpp +++ b/test/graph/dijkstra.cpp @@ -13,21 +13,21 @@ void stress_test(int LIM) { 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<vector<pair<int, ll>>> 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}); + adj[a].emplace_back(b, w); 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; } @@ -41,12 +41,12 @@ void performance_test() { timer t; Graph<NoData> g(N); g.erdosRenyi(M); - vector<vector<path>> adj(N); + vector<vector<pair<int, ll>>> 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}); + adj[a].emplace_back(b, w1); + adj[b].emplace_back(a, w2); }); t.start(); diff --git a/test/graph/dinic.cpp b/test/graph/dinic.cpp deleted file mode 100644 index bd270be..0000000 --- a/test/graph/dinic.cpp +++ /dev/null @@ -1,62 +0,0 @@ -#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(); - if (!sanitize) performance_test(); -} diff --git a/test/graph/dinicScaling.cpp b/test/graph/dinitzScaling.cpp index 065dd9e..0ab9718 100644 --- a/test/graph/dinicScaling.cpp +++ b/test/graph/dinitzScaling.cpp @@ -1,6 +1,6 @@ #include "../util.h" -namespace dinic { -#include <graph/dinicScaling.cpp> +namespace dinitz { +#include <graph/dinitzScaling.cpp> } namespace pushRelabel { @@ -13,20 +13,20 @@ void stress_test() { 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, {}); + dinitz::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); + dinitz::addEdge(a, b, w); pushRelabel::addEdge(a, b, w); }); - ll got = dinic::maxFlow(0, n - 1); + ll got = dinitz::maxFlow(0, n - 1); ll expected = pushRelabel::maxFlow(0, n - 1); - + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries += n; } @@ -36,7 +36,7 @@ void stress_test() { constexpr int N = 50000; constexpr int M = 200000; void performance_test() { - using namespace dinic; + using namespace dinitz; timer t; Graph<NoData> g(N); g.erdosRenyi(M); diff --git a/test/graph/euler.cpp b/test/graph/euler.cpp index b26add1..5314123 100644 --- a/test/graph/euler.cpp +++ b/test/graph/euler.cpp @@ -20,7 +20,7 @@ Euler eulerGraph(int n, int m) { } int last = -1; for (int i = 0; i < n; i++) { - if (sz(res.adj[i]) % 2 != 0) { + if (ssize(res.adj[i]) % 2 != 0) { if (last >= 0) { res.addEdge(last, i); last = -1; @@ -41,25 +41,25 @@ void stress_test() { 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 (auto [j, rev] : g.adj[i]) { expected[i].push_back(j); } - sort(all(expected[i])); + ranges::sort(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++) { + for (int i = 1; i < ssize(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)); + for (auto& v : got) ranges::sort(v); if (got != expected) cerr << "error" << FAIL; queries += n; diff --git a/test/graph/floydWarshall.cpp b/test/graph/floydWarshall.cpp index 5926449..819af39 100644 --- a/test/graph/floydWarshall.cpp +++ b/test/graph/floydWarshall.cpp @@ -40,7 +40,7 @@ void stress_test(int LIM) { 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++) { + for (int l = 1; l < ssize(path); l++) { if (floydWarshall::dist[i][path[l-1]] + orig[path[l-1]][path[l]] + floydWarshall::dist[path[l]][k] != @@ -52,7 +52,7 @@ void stress_test(int LIM) { 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; } diff --git a/test/graph/havelHakimi.cpp b/test/graph/havelHakimi.cpp index f0b6fd9..0752b85 100644 --- a/test/graph/havelHakimi.cpp +++ b/test/graph/havelHakimi.cpp @@ -13,11 +13,11 @@ void stress_test() { 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; + if (ssize(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]); + got[i] = ssize(res[i]); for (int j : res[i]) { if (j < 0 || j >= n) cerr << "error: invalid edge" << FAIL; rev[j].push_back(i); @@ -25,11 +25,11 @@ void stress_test() { } for (int i = 0; i < n; i++) { - sort(all(res[i])); - sort(all(rev[i])); + ranges::sort(res[i]); + ranges::sort(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++) { + for (int j = 1; j < ssize(res[i]); j++) { if (res[i][j] == res[i][j-1]) cerr << "error: multiedge" << FAIL; } } @@ -54,7 +54,7 @@ void performance_test() { auto res = havelHakimi(expected); t.stop(); hash_t hash = 0; - for (auto& v : res) hash += sz(v); + for (auto& v : res) hash += ssize(v); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/hopcroftKarp.cpp b/test/graph/hopcroftKarp.cpp index a6306b6..c446c99 100644 --- a/test/graph/hopcroftKarp.cpp +++ b/test/graph/hopcroftKarp.cpp @@ -1,6 +1,6 @@ #include "../util.h" namespace kuhn { -#include <graph/maxCarBiMatch.cpp> +#include <graph/kuhn.cpp> } namespace hk { #include <graph/hopcroftKarp.cpp> diff --git a/test/graph/kruskal.cpp b/test/graph/kruskal.cpp index d80376f..157a2f4 100644 --- a/test/graph/kruskal.cpp +++ b/test/graph/kruskal.cpp @@ -1,22 +1,19 @@ #include "../util.h" #include <datastructures/unionFind.cpp> -struct edge { +#define Edge Edge_ // we have a struct named Edge in util.h + +struct Edge { int from, to; ll cost; - bool operator<(const edge& o) const { + 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) { +#include <graph/kruskal.cpp> + +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); @@ -51,13 +48,14 @@ void stress_test() { Graph<NoData> g(n); g.erdosRenyi(m); - vector<edge> edges; + 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); + vector<Edge> mst; + ll got = kruskal(n, edges, mst); ll expected = prim(edges, n); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; @@ -72,14 +70,15 @@ void performance_test() { timer t; Graph<NoData> g(N); g.erdosRenyi(M); - vector<edge> edges; + 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); + vector<Edge> mst; + hash_t hash = kruskal(N, edges, mst); t.stop(); if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/graph/maxCarBiMatch.cpp b/test/graph/kuhn.cpp index 6672d30..0a6a9a4 100644 --- a/test/graph/maxCarBiMatch.cpp +++ b/test/graph/kuhn.cpp @@ -1,6 +1,6 @@ #include "../util.h" namespace kuhn { -#include <graph/maxCarBiMatch.cpp> +#include <graph/kuhn.cpp> } namespace hk { #include <graph/hopcroftKarp.cpp> diff --git a/test/graph/matching.cpp b/test/graph/matching.cpp index ccd98e6..d737954 100644 --- a/test/graph/matching.cpp +++ b/test/graph/matching.cpp @@ -1,6 +1,6 @@ #include "../util.h" namespace tutte { -void gauss(int n, int m); +vector<int> gauss(vector<vector<ll>> &mat); #include <graph/matching.cpp> #include <math/shortModInv.cpp> #include <math/lgsFp.cpp> @@ -15,19 +15,19 @@ void stress_test() { GM blossom(n); srand(Random::rng()); - tutte::adj.assign(n, {}); + vector<vector<int>> adj(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); + adj[a].push_back(b); + adj[b].push_back(a); blossom.adj[a].push_back(b); blossom.adj[b].push_back(a); }); - ll got = tutte::max_matching(); + ll got = tutte::max_matching(adj); ll expected = blossom.match(); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; @@ -43,14 +43,14 @@ void performance_test() { Graph<NoData> g(N); g.erdosRenyi(M); srand(Random::rng()); - tutte::adj.assign(N, {}); + vector<vector<int>> adj(N); g.forEdges([&](int a, int b){ - tutte::adj[a].push_back(b); - tutte::adj[b].push_back(a); + adj[a].push_back(b); + adj[b].push_back(a); }); t.start(); - hash_t hash = tutte::max_matching(); + hash_t hash = tutte::max_matching(adj); t.stop(); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/graph/pushRelabel.cpp b/test/graph/pushRelabel.cpp index 00a73d1..ca50860 100644 --- a/test/graph/pushRelabel.cpp +++ b/test/graph/pushRelabel.cpp @@ -1,6 +1,6 @@ #include "../util.h" -namespace dinic { -#include <graph/dinicScaling.cpp> +namespace dinitz { +#include <graph/dinitzScaling.cpp> } namespace pushRelabel { @@ -13,20 +13,20 @@ void stress_test() { 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, {}); + dinitz::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); + dinitz::addEdge(a, b, w); pushRelabel::addEdge(a, b, w); }); ll got = pushRelabel::maxFlow(0, n - 1); - ll expected = dinic::maxFlow(0, n - 1); - + ll expected = dinitz::maxFlow(0, n - 1); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries += n; } diff --git a/test/graph/reroot.cpp b/test/graph/reroot.cpp index 6fc2f4d..c7c4608 100644 --- a/test/graph/reroot.cpp +++ b/test/graph/reroot.cpp @@ -47,7 +47,7 @@ void performance_test() { t.start(); Reroot re; auto ans = re.solve(); - hash = accumulate(all(ans), 0LL); + hash = accumulate(begin(ans), end(ans), 0LL); t.stop(); if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp index 7c1261f..ebd3af0 100644 --- a/test/graph/scc.cpp +++ b/test/graph/scc.cpp @@ -9,11 +9,11 @@ void stress_test() { Graph<NoData, true> g(n); g.erdosRenyi(m); - adj.assign(n, {}); - g.forEdges([](int a, int b){ + vector<vector<int>> adj(n); + g.forEdges([&](int a, int b){ adj[a].push_back(b); }); - scc(); + SCC scc(adj); auto reach = [&](int a) -> vector<bool> { vector<bool> seen(n); @@ -28,12 +28,21 @@ void stress_test() { return seen; }; + vector<int> seen(n); + for (int i = 0; i < ssize(scc.sccs); i++) { + for (int v: scc.sccs[i]) { + if (scc.idx[v] != i) cerr << v << " is in scc " << i << ", but idx[" << v << "] = " << scc.idx[v] << FAIL; + seen[v]++; + } + } + for (int a = 0; a < n; a++) { + if (seen[a] != 1) cerr << a << " occurs " << seen[a] << " times in sccs" << FAIL; vector<bool> reacha = reach(a); for (int b = 0; b < n; b++) { - if (idx[a] == idx[b]) { + if (scc.idx[a] == scc.idx[b]) { if (!reacha[b]) cerr << a << " and " << b << " should be in different SCCs" << FAIL; - } else if (idx[a] < idx[b]) { + } else if (scc.idx[a] < scc.idx[b]) { if (reacha[b]) cerr << a << " should come before " << b << " in topological order" << FAIL; } } @@ -49,16 +58,16 @@ void performance_test() { timer t; Graph<NoData, true> g(N); g.erdosRenyi(M); - adj.assign(N, {}); - g.forEdges([](int a, int b){ + vector<vector<int>> adj(N); + g.forEdges([&](int a, int b){ adj[a].push_back(b); }); t.start(); - scc(); + SCC scc(adj); t.stop(); hash_t hash = 0; - for (int x : idx) hash += x; + for (int x : scc.idx) hash += x; if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/graph/stoerWagner.cpp b/test/graph/stoerWagner.cpp index cc01a7d..3b67aac 100644 --- a/test/graph/stoerWagner.cpp +++ b/test/graph/stoerWagner.cpp @@ -13,7 +13,7 @@ namespace pushRelabel { #include <graph/pushRelabel.cpp> ll minCut() { ll res = INF; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { for (int j = 0; j < i; j++) { if (i == j) continue; res = min(res, maxFlow(i, j)); @@ -48,7 +48,7 @@ void stress_test() { ll got = stoerWagner::stoer_wagner(); ll expected = pushRelabel::minCut(); - + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries += n; } diff --git a/test/graph/treeIsomorphism.cpp b/test/graph/treeIsomorphism.cpp index e5fd817..1594016 100644 --- a/test/graph/treeIsomorphism.cpp +++ b/test/graph/treeIsomorphism.cpp @@ -45,7 +45,7 @@ void stress_test_eq() { void test_tiny() { vector<int> expected = {1,1,1,1,2,3,6,11,23}; //#A000055 - for (int i = 1; i < sz(expected); i++) { + for (int i = 1; i < ssize(expected); i++) { set<pair<int, int>> got; tree t(i); @@ -63,9 +63,9 @@ void test_tiny() { got.insert(t.treeLabel()); } - if (sz(got) != expected[i]) cerr << i << ", got: " << sz(got) << ", expected: " << expected[i] << FAIL; + if (ssize(got) != expected[i]) cerr << i << ", got: " << ssize(got) << ", expected: " << expected[i] << FAIL; } - cerr << "tested tiny: " << sz(expected) << endl; + cerr << "tested tiny: " << ssize(expected) << endl; } void stress_test_neq() { @@ -110,7 +110,7 @@ void performance_test() { tt.adj[b].push_back(a); }); - t.start(); + t.start(); auto [gotA, gotB] = tt.treeLabel(); t.stop(); hash_t hash = gotA + gotB; diff --git a/test/graph/virtualTree.cpp b/test/graph/virtualTree.cpp index af57619..556ba7b 100644 --- a/test/graph/virtualTree.cpp +++ b/test/graph/virtualTree.cpp @@ -21,7 +21,7 @@ int lca(int u, int v) { } void init(vector<vector<int>>& adj) { - int n = (int)sz(adj); + int n = (int)ssize(adj); d.assign(n, 0); in = par = out = d; int counter = 0; @@ -44,7 +44,7 @@ void stress_test() { 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]) { + for (int i=0; i<ssize(idk); i++) for (int v : tree[i]) { edges.emplace_back(idk[i], idk[v]); } @@ -60,7 +60,7 @@ void stress_test() { }; dfs(dfs, 0, -1, -1); - sort(all(edges)), sort(all(edges2)); + ranges::sort(edges), ranges::sort(edges2); if (edges != edges2) cerr << "WA edge list does not match" << FAIL; } cerr << "tested random 50'000 tests" << endl; @@ -83,7 +83,7 @@ void performance_test() { ll hash = 0; t.start(); auto [idk, tree] = virtualTree(ind); - hash = accumulate(all(idk), 0LL); + hash = accumulate(begin(idk), end(idk), 0LL); t.stop(); if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; |