diff options
Diffstat (limited to 'test/graph')
32 files changed, 63 insertions, 51 deletions
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<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 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 <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 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 <graph/matching.cpp> #include <math/shortModInv.cpp> #include <math/lgsFp.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 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 <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/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 <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 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 <graph/matching.cpp> #include <math/shortModInv.cpp> #include <math/lgsFp.cpp> @@ -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(); } |