crash_test.cpp (2272B)
1 #include <catch2/catch_test_macros.hpp> 2 #include <cstddef> 3 #include <cstdint> 4 #include <random> 5 #include <thread> 6 #include <vector> 7 8 #include "../include/prim.hpp" 9 10 void run(size_t mv, size_t me, uint32_t iterations) { 11 uint32_t seed = std::random_device{}(); 12 std::mt19937 rng{seed}; 13 14 size_t vMax = mv; 15 size_t eMax = me; 16 17 size_t xMax = 60000; 18 size_t yMax = 60000; 19 20 std::uniform_int_distribution<std::size_t> pick1(2, vMax - 1); 21 std::uniform_int_distribution<std::size_t> pick2(0, eMax - 1); 22 23 std::uniform_int_distribution<uint> pick3(1, xMax - 1); 24 std::uniform_int_distribution<uint> pick4(1, yMax - 1); 25 26 for (uint32_t i = 0; i < iterations; ++i) { 27 std::size_t vertCount = pick1(rng); 28 std::size_t edgeCount = pick2(rng); 29 30 uint32_t xSel = pick3(rng); 31 uint32_t ySel = pick4(rng); 32 33 Graph g = Graph(edgeCount, vertCount, xSel, ySel); 34 std::unordered_set<std::size_t> visitedIndices{}; 35 std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> 36 toVisit{}; 37 std::vector<double> minEdgeToVertex(vertCount, -1); 38 39 g.traverseVertexIdx(0); 40 visitedIndices.insert(0); 41 42 std::vector<Edge> edges = g.getEdgesOfVertexIdx(0); 43 44 for (auto edge : edges) { 45 toVisit.push(edge); 46 } 47 48 while (toVisit.size() != 0) { 49 oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex); 50 } 51 REQUIRE(true); // just fuzzing for this one. 52 } 53 } 54 55 void runs() { run(100, 500, 10000); } 56 void runl() { run(100000, 1000000, 100); } 57 58 TEST_CASE("Small prim algorithm not guaranteed connected", "[Small prim]") { 59 std::vector<std::thread*> threads{}; 60 61 for (int i = 0; i < 10; ++i) { 62 std::thread* t1 = new std::thread{runs}; 63 threads.push_back(t1); 64 } 65 for (int i = 0; i < 10; ++i) { 66 threads[i]->join(); 67 delete threads[i]; 68 } 69 } 70 71 TEST_CASE("Large prim algorithm not guaranteed connected", "[Large prim]") { 72 std::vector<std::thread*> threads{}; 73 for (int i = 0; i < 10; ++i) { 74 std::thread* t1 = new std::thread{runl}; 75 threads.push_back(t1); 76 } 77 for (int i = 0; i < 10; ++i) { 78 threads[i]->join(); 79 delete threads[i]; 80 } 81 }