summaryrefslogtreecommitdiff
path: root/test/graph
diff options
context:
space:
mode:
Diffstat (limited to 'test/graph')
-rw-r--r--test/graph/TSP.cpp8
-rw-r--r--test/graph/articulationPoints.bcc.cpp18
-rw-r--r--test/graph/articulationPoints.bridges.cpp12
-rw-r--r--test/graph/articulationPoints.cpp10
-rw-r--r--test/graph/bronKerbosch.cpp10
-rw-r--r--test/graph/centroid.cpp12
-rw-r--r--test/graph/connect.cpp10
-rw-r--r--test/graph/cycleCounting.cpp6
-rw-r--r--test/graph/euler.cpp10
-rw-r--r--test/graph/floydWarshall.cpp4
-rw-r--r--test/graph/havelHakimi.cpp12
-rw-r--r--test/graph/reroot.cpp2
-rw-r--r--test/graph/stoerWagner.cpp4
-rw-r--r--test/graph/treeIsomorphism.cpp8
-rw-r--r--test/graph/virtualTree.cpp8
15 files changed, 67 insertions, 67 deletions
diff --git a/test/graph/TSP.cpp b/test/graph/TSP.cpp
index f9aab2e..8a67409 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 15f5cf2..cee2d0b 100644
--- a/test/graph/articulationPoints.bcc.cpp
+++ b/test/graph/articulationPoints.bcc.cpp
@@ -10,9 +10,9 @@ struct edge {
vector<vector<int>> naiveBCC(int m) {
init(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;
@@ -36,9 +36,9 @@ vector<vector<int>> naiveBCC(int 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));
+ 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() {
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 2567a09..c06f3a3 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/bronKerbosch.cpp b/test/graph/bronKerbosch.cpp
index 1ccd493..e0cac22 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 41d9d0f..633c3f1 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 bba8104..96dc4be 100644
--- a/test/graph/connect.cpp
+++ b/test/graph/connect.cpp
@@ -52,8 +52,8 @@ void stress_test() {
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 8e53aec..9c7bf0c 100644
--- a/test/graph/cycleCounting.cpp
+++ b/test/graph/cycleCounting.cpp
@@ -4,11 +4,11 @@
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);
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]++;
@@ -66,7 +66,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/euler.cpp b/test/graph/euler.cpp
index 6666040..e468e05 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.idx[i]) % 2 != 0) {
+ if (ssize(res.idx[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 (int j : g.idx[i]) {
expected[i].push_back(g.to[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 a93a9ea..182b99b 100644
--- a/test/graph/floydWarshall.cpp
+++ b/test/graph/floydWarshall.cpp
@@ -40,7 +40,7 @@ void stress_test() {
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() {
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 71476ec..9491db2 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/reroot.cpp b/test/graph/reroot.cpp
index d5043b4..93f946b 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/stoerWagner.cpp b/test/graph/stoerWagner.cpp
index 2003f09..e7a1075 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 97f4df4..4daa373 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 d256760..0bd71d9 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;
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 16:38:04 +0000