From 630a5bdf06d59b8340fb4bfc0e692cbcf094026a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Thu, 10 Jul 2025 17:40:18 +0200 Subject: run with sanitizer --- test/graph/2sat.cpp | 2 +- test/graph/LCA_sparse.cpp | 2 +- test/graph/TSP.cpp | 4 +-- test/graph/articulationPoints.bcc.cpp | 7 ++-- test/graph/articulationPoints.cpp | 2 +- test/graph/bellmannFord.cpp | 9 ++--- test/graph/bitonicTSP.cpp | 49 -------------------------- test/graph/bitonicTSP.cpp.todo | 57 +++++++++++++++++++++++++++++++ test/graph/bitonicTSPsimple.cpp | 49 -------------------------- test/graph/bitonicTSPsimple.cpp.todo | 49 ++++++++++++++++++++++++++ test/graph/blossom.cpp | 4 +-- test/graph/bronKerbosch.cpp | 2 +- test/graph/centroid.cpp | 2 +- test/graph/connect.cpp | 2 +- test/graph/cycleCounting.cpp | 2 +- test/graph/dijkstra.cpp | 9 ++--- test/graph/dinic.cpp | 2 +- test/graph/dinicScaling.cpp | 2 +- test/graph/euler.cpp | 2 +- test/graph/floydWarshall.cpp | 9 ++--- test/graph/havelHakimi.cpp | 2 +- test/graph/hld.cpp | 2 +- test/graph/hopcroftKarp.cpp | 2 +- test/graph/kruskal.cpp | 2 +- test/graph/matching.cpp | 4 +-- test/graph/maxCarBiMatch.cpp | 2 +- test/graph/maxWeightBipartiteMatching.cpp | 2 +- test/graph/minCostMaxFlow.cpp | 2 +- test/graph/pushRelabel.cpp | 2 +- test/graph/reroot.cpp | 2 +- test/graph/scc.cpp | 2 +- test/graph/stoerWagner.cpp | 2 +- test/graph/treeIsomorphism.cpp | 2 +- test/graph/virtualTree.cpp | 2 +- 34 files changed, 154 insertions(+), 142 deletions(-) delete mode 100644 test/graph/bitonicTSP.cpp create mode 100644 test/graph/bitonicTSP.cpp.todo delete mode 100644 test/graph/bitonicTSPsimple.cpp create mode 100644 test/graph/bitonicTSPsimple.cpp.todo (limited to 'test/graph') diff --git a/test/graph/2sat.cpp b/test/graph/2sat.cpp index cf37131..4635086 100644 --- a/test/graph/2sat.cpp +++ b/test/graph/2sat.cpp @@ -126,5 +126,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/LCA_sparse.cpp b/test/graph/LCA_sparse.cpp index f6eb345..f5b023f 100644 --- a/test/graph/LCA_sparse.cpp +++ b/test/graph/LCA_sparse.cpp @@ -59,5 +59,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/TSP.cpp b/test/graph/TSP.cpp index f9aab2e..930ec88 100644 --- a/test/graph/TSP.cpp +++ b/test/graph/TSP.cpp @@ -57,11 +57,11 @@ void performance_test() { hash_t hash = 0; for (int x : got) hash += x; - if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + if (t.time > 1500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/articulationPoints.bcc.cpp b/test/graph/articulationPoints.bcc.cpp index 15f5cf2..e9fc32f 100644 --- a/test/graph/articulationPoints.bcc.cpp +++ b/test/graph/articulationPoints.bcc.cpp @@ -42,9 +42,9 @@ vector> naiveBCC(int m) { return res; } -void stress_test_bcc() { +void stress_test_bcc(int LIM) { ll queries = 0; - for (int tries = 0; tries < 200'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(1, 30); int m = Random::integer(0, max(1, min(300, n*(n-1) / 2 + 1))); Graph g(n); @@ -74,5 +74,6 @@ void stress_test_bcc() { } int main() { - stress_test_bcc(); + stress_test_bcc(20'000); + if (!sanitize) stress_test_bcc(200'000); } diff --git a/test/graph/articulationPoints.cpp b/test/graph/articulationPoints.cpp index 2567a09..8ee6bc4 100644 --- a/test/graph/articulationPoints.cpp +++ b/test/graph/articulationPoints.cpp @@ -81,5 +81,5 @@ void performance_test() { int main() { stress_test_art(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/bellmannFord.cpp b/test/graph/bellmannFord.cpp index 92f1fef..dd697f7 100644 --- a/test/graph/bellmannFord.cpp +++ b/test/graph/bellmannFord.cpp @@ -9,9 +9,9 @@ namespace floydWarshall { #include } -void stress_test() { +void stress_test(int LIM) { ll queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(2, 30); int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); vector potential = Random::integers(n, 0, 1'000'000'000'000ll); @@ -65,6 +65,7 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(10'000); + if (!sanitize) stress_test(100'000); + if (!sanitize) performance_test(); } diff --git a/test/graph/bitonicTSP.cpp b/test/graph/bitonicTSP.cpp deleted file mode 100644 index 7c448a2..0000000 --- a/test/graph/bitonicTSP.cpp +++ /dev/null @@ -1,49 +0,0 @@ -#include "../util.h" -namespace got { -#include -} -namespace expected { -#include -} - -void stress_test() { - ll queries = 0; - for (int tries = 0; tries < 200'000; tries++) { - int n = Random::integer(1, 30); - - vector> dist(n); - for (auto& v : dist) v = Random::reals(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>(N); - for (auto& v : got::dist) v = Random::reals(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/bitonicTSP.cpp.todo b/test/graph/bitonicTSP.cpp.todo new file mode 100644 index 0000000..9d6b77d --- /dev/null +++ b/test/graph/bitonicTSP.cpp.todo @@ -0,0 +1,57 @@ +#include "../util.h" +namespace got { +#include +} +namespace expected { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(2, 30); + + vector> dist(n); + for (auto& v : dist) v = Random::reals(n, 0, 1e18); + auto eval = [&](const vector& order) { + double res = 0; + for (int i = 0; i < n; i++) res += dist[order[i]][order[i+1]]; + return res; + }; + + + got::dist = dist; + expected::dist = dist; + + auto got = eval(got::bitonicTSP()); + auto expected = eval(expected::bitonicTSP()); + + std::cout << got << std::endl; + std::cout << expected << std::endl; + 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>(N); + for (auto& v : got::dist) v = Random::reals(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(); + if (!sanitize) performance_test(); +} diff --git a/test/graph/bitonicTSPsimple.cpp b/test/graph/bitonicTSPsimple.cpp deleted file mode 100644 index c79a0ef..0000000 --- a/test/graph/bitonicTSPsimple.cpp +++ /dev/null @@ -1,49 +0,0 @@ -#include "../util.h" -namespace got { -#include -} -namespace expected { -#include -} - -void stress_test() { - ll queries = 0; - for (int tries = 0; tries < 200'000; tries++) { - int n = Random::integer(1, 30); - - vector> dist(n); - for (auto& v : dist) v = Random::reals(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>(N); - for (auto& v : got::dist) v = Random::reals(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.todo b/test/graph/bitonicTSPsimple.cpp.todo new file mode 100644 index 0000000..7e0a80b --- /dev/null +++ b/test/graph/bitonicTSPsimple.cpp.todo @@ -0,0 +1,49 @@ +#include "../util.h" +namespace got { +#include +} +namespace expected { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 200'000; tries++) { + int n = Random::integer(2, 30); + + vector> dist(n); + for (auto& v : dist) v = Random::reals(n, 0, 1e18); + + got::dist = dist; + expected::dist = dist; + + auto got = got::bitonicTSP(); + auto expected = expected::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>(N); + for (auto& v : got::dist) v = Random::reals(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(); + if (!sanitize) performance_test(); +} diff --git a/test/graph/blossom.cpp b/test/graph/blossom.cpp index 714b029..f44f815 100644 --- a/test/graph/blossom.cpp +++ b/test/graph/blossom.cpp @@ -1,6 +1,6 @@ #include "../util.h" namespace tutte { -void gauss(int n, ll mod); +void gauss(int n, int m); #include #include #include @@ -72,5 +72,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/bronKerbosch.cpp b/test/graph/bronKerbosch.cpp index 1ccd493..1a90c06 100644 --- a/test/graph/bronKerbosch.cpp +++ b/test/graph/bronKerbosch.cpp @@ -69,5 +69,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/centroid.cpp b/test/graph/centroid.cpp index 41d9d0f..c3f1d3f 100644 --- a/test/graph/centroid.cpp +++ b/test/graph/centroid.cpp @@ -73,5 +73,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp index bba8104..9580a4b 100644 --- a/test/graph/connect.cpp +++ b/test/graph/connect.cpp @@ -136,5 +136,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/cycleCounting.cpp b/test/graph/cycleCounting.cpp index 8e53aec..6459162 100644 --- a/test/graph/cycleCounting.cpp +++ b/test/graph/cycleCounting.cpp @@ -75,5 +75,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/dijkstra.cpp b/test/graph/dijkstra.cpp index c0cfb7e..dd5b826 100644 --- a/test/graph/dijkstra.cpp +++ b/test/graph/dijkstra.cpp @@ -7,9 +7,9 @@ struct edge { }; #include -void stress_test() { +void stress_test(int LIM) { ll queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(2, 30); int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); @@ -59,6 +59,7 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(10'000); + if (!sanitize) stress_test(100'000); + if (!sanitize) performance_test(); } diff --git a/test/graph/dinic.cpp b/test/graph/dinic.cpp index 5af7c6f..bd270be 100644 --- a/test/graph/dinic.cpp +++ b/test/graph/dinic.cpp @@ -58,5 +58,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/dinicScaling.cpp b/test/graph/dinicScaling.cpp index 967d6b1..065dd9e 100644 --- a/test/graph/dinicScaling.cpp +++ b/test/graph/dinicScaling.cpp @@ -57,5 +57,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/euler.cpp b/test/graph/euler.cpp index 457ca99..b26add1 100644 --- a/test/graph/euler.cpp +++ b/test/graph/euler.cpp @@ -83,5 +83,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/floydWarshall.cpp b/test/graph/floydWarshall.cpp index a93a9ea..5926449 100644 --- a/test/graph/floydWarshall.cpp +++ b/test/graph/floydWarshall.cpp @@ -9,9 +9,9 @@ namespace floydWarshall { #include } -void stress_test() { +void stress_test(int LIM) { ll queries = 0; - for (int tries = 0; tries < 100'000; tries++) { + for (int tries = 0; tries < LIM; tries++) { int n = Random::integer(2, 30); int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); vector potential = Random::integers(n, 0, 1'000'000'000'000ll); @@ -85,6 +85,7 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(10'000); + if (!sanitize) stress_test(100'000); + if (!sanitize) performance_test(); } diff --git a/test/graph/havelHakimi.cpp b/test/graph/havelHakimi.cpp index 71476ec..f0b6fd9 100644 --- a/test/graph/havelHakimi.cpp +++ b/test/graph/havelHakimi.cpp @@ -61,5 +61,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/hld.cpp b/test/graph/hld.cpp index bcd9c8c..bf055f7 100644 --- a/test/graph/hld.cpp +++ b/test/graph/hld.cpp @@ -79,5 +79,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/hopcroftKarp.cpp b/test/graph/hopcroftKarp.cpp index 05599dd..a6306b6 100644 --- a/test/graph/hopcroftKarp.cpp +++ b/test/graph/hopcroftKarp.cpp @@ -70,5 +70,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/kruskal.cpp b/test/graph/kruskal.cpp index f6245b9..d80376f 100644 --- a/test/graph/kruskal.cpp +++ b/test/graph/kruskal.cpp @@ -87,5 +87,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/matching.cpp b/test/graph/matching.cpp index b8fbc6c..ccd98e6 100644 --- a/test/graph/matching.cpp +++ b/test/graph/matching.cpp @@ -1,6 +1,6 @@ #include "../util.h" namespace tutte { -void gauss(int n, ll mod); +void gauss(int n, int m); #include #include #include @@ -58,5 +58,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/maxCarBiMatch.cpp b/test/graph/maxCarBiMatch.cpp index 6d7fad0..6672d30 100644 --- a/test/graph/maxCarBiMatch.cpp +++ b/test/graph/maxCarBiMatch.cpp @@ -70,5 +70,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/maxWeightBipartiteMatching.cpp b/test/graph/maxWeightBipartiteMatching.cpp index d245405..be38d8c 100644 --- a/test/graph/maxWeightBipartiteMatching.cpp +++ b/test/graph/maxWeightBipartiteMatching.cpp @@ -55,5 +55,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/minCostMaxFlow.cpp b/test/graph/minCostMaxFlow.cpp index 8c92aa7..a070f51 100644 --- a/test/graph/minCostMaxFlow.cpp +++ b/test/graph/minCostMaxFlow.cpp @@ -64,5 +64,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/pushRelabel.cpp b/test/graph/pushRelabel.cpp index ac3b079..00a73d1 100644 --- a/test/graph/pushRelabel.cpp +++ b/test/graph/pushRelabel.cpp @@ -57,5 +57,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/reroot.cpp b/test/graph/reroot.cpp index d5043b4..6fc2f4d 100644 --- a/test/graph/reroot.cpp +++ b/test/graph/reroot.cpp @@ -55,5 +55,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp index cf4efc7..7c1261f 100644 --- a/test/graph/scc.cpp +++ b/test/graph/scc.cpp @@ -65,5 +65,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/stoerWagner.cpp b/test/graph/stoerWagner.cpp index 2003f09..cc01a7d 100644 --- a/test/graph/stoerWagner.cpp +++ b/test/graph/stoerWagner.cpp @@ -77,5 +77,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/treeIsomorphism.cpp b/test/graph/treeIsomorphism.cpp index 97f4df4..e5fd817 100644 --- a/test/graph/treeIsomorphism.cpp +++ b/test/graph/treeIsomorphism.cpp @@ -122,5 +122,5 @@ int main() { stress_test_eq(); test_tiny(); stress_test_neq(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/virtualTree.cpp b/test/graph/virtualTree.cpp index d256760..af57619 100644 --- a/test/graph/virtualTree.cpp +++ b/test/graph/virtualTree.cpp @@ -91,5 +91,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } -- cgit v1.2.3 From cdeded176c18240579168ee8461c5101abb47e78 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 22 Sep 2025 19:32:21 +0200 Subject: reduce bounds for test --- test/graph/connect.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'test/graph') diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp index 9580a4b..8114339 100644 --- a/test/graph/connect.cpp +++ b/test/graph/connect.cpp @@ -45,9 +45,9 @@ struct Naive { } }; -void stress_test() { +void stress_test(int lim) { ll queries = 0; - for (int tries = 0; tries < 2'000; tries++) { + for (int tries = 0; tries < lim; tries++) { int n = Random::integer(2, 30); int m = Random::integer(30, 300); @@ -135,6 +135,6 @@ void performance_test() { } int main() { - stress_test(); + stress_test(sanitize ? 1'000 : 2'000); if (!sanitize) performance_test(); } -- cgit v1.2.3