diff options
Diffstat (limited to 'test/graph')
31 files changed, 63 insertions, 51 deletions
diff --git a/test/graph/2sat.cpp b/test/graph/2sat.cpp index e969364..fd6326c 100644 --- a/test/graph/2sat.cpp +++ b/test/graph/2sat.cpp @@ -122,5 +122,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 8a67409..3b1ce94 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 f112338..927ceb4 100644 --- a/test/graph/articulationPoints.bcc.cpp +++ b/test/graph/articulationPoints.bcc.cpp @@ -42,9 +42,9 @@ vector<vector<int>> 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<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); @@ -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 c06f3a3..6960f73 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 <graph/floydWarshall.cpp> } -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<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); @@ -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.todo index 7c448a2..9d6b77d 100644 --- a/test/graph/bitonicTSP.cpp +++ b/test/graph/bitonicTSP.cpp.todo @@ -9,17 +9,25 @@ namespace expected { void stress_test() { ll queries = 0; for (int tries = 0; tries < 200'000; tries++) { - int n = Random::integer<int>(1, 30); + int n = Random::integer<int>(2, 30); vector<vector<double>> dist(n); for (auto& v : dist) v = Random::reals<double>(n, 0, 1e18); + auto eval = [&](const vector<int>& 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 = got::bitonicTSP(); - auto expected = got::bitonicTSP(); + 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; } @@ -45,5 +53,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/bitonicTSPsimple.cpp b/test/graph/bitonicTSPsimple.cpp.todo index c79a0ef..7e0a80b 100644 --- a/test/graph/bitonicTSPsimple.cpp +++ b/test/graph/bitonicTSPsimple.cpp.todo @@ -9,7 +9,7 @@ namespace expected { void stress_test() { ll queries = 0; for (int tries = 0; tries < 200'000; tries++) { - int n = Random::integer<int>(1, 30); + int n = Random::integer<int>(2, 30); vector<vector<double>> dist(n); for (auto& v : dist) v = Random::reals<double>(n, 0, 1e18); @@ -18,7 +18,7 @@ void stress_test() { expected::dist = dist; auto got = got::bitonicTSP(); - auto expected = got::bitonicTSP(); + auto expected = expected::bitonicTSP(); if (got != expected) cerr << "error" << FAIL; queries += n; @@ -45,5 +45,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/blossom.cpp b/test/graph/blossom.cpp index 0add7e1..56d3132 100644 --- a/test/graph/blossom.cpp +++ b/test/graph/blossom.cpp @@ -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 e0cac22..8c0a200 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 633c3f1..d231c3e 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 96dc4be..ef087e3 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<int>(2, 30); int m = Random::integer<int>(30, 300); @@ -135,6 +135,6 @@ void performance_test() { } int main() { - stress_test(); - performance_test(); + stress_test(sanitize ? 1'000 : 2'000); + if (!sanitize) performance_test(); } diff --git a/test/graph/cycleCounting.cpp b/test/graph/cycleCounting.cpp index 82caf16..bfe313e 100644 --- a/test/graph/cycleCounting.cpp +++ b/test/graph/cycleCounting.cpp @@ -71,5 +71,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 18420ac..d79e700 100644 --- a/test/graph/dijkstra.cpp +++ b/test/graph/dijkstra.cpp @@ -7,9 +7,9 @@ struct edge { }; #include <graph/bellmannFord.cpp> -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<int>(2, 30); int m = Random::integer<int>(n-1, max<int>(n, min<int>(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/dinitzScaling.cpp b/test/graph/dinitzScaling.cpp index c06d486..0ab9718 100644 --- a/test/graph/dinitzScaling.cpp +++ b/test/graph/dinitzScaling.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 353cff2..5314123 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 182b99b..819af39 100644 --- a/test/graph/floydWarshall.cpp +++ b/test/graph/floydWarshall.cpp @@ -9,9 +9,9 @@ namespace floydWarshall { #include <graph/floydWarshall.cpp> } -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<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); @@ -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 9491db2..0752b85 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 df2cec2..c446c99 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 bc1cce5..157a2f4 100644 --- a/test/graph/kruskal.cpp +++ b/test/graph/kruskal.cpp @@ -86,5 +86,5 @@ void performance_test() { int main() { stress_test(); - performance_test(); + if (!sanitize) performance_test(); } diff --git a/test/graph/kuhn.cpp b/test/graph/kuhn.cpp index 8b7e13b..0a6a9a4 100644 --- a/test/graph/kuhn.cpp +++ b/test/graph/kuhn.cpp @@ -70,5 +70,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 9e3ad85..d737954 100644 --- a/test/graph/matching.cpp +++ b/test/graph/matching.cpp @@ -58,5 +58,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 42c2e57..ca50860 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 93f946b..c7c4608 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 bc52d7e..ebd3af0 100644 --- a/test/graph/scc.cpp +++ b/test/graph/scc.cpp @@ -74,5 +74,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 e7a1075..3b67aac 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 4daa373..1594016 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 0bd71d9..556ba7b 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(); } |