algo_test.cpp (9699B)
1 #include <catch2/catch_test_macros.hpp> 2 #include <cstddef> 3 #include <iostream> 4 #include <random> 5 6 #include "../include/prim.hpp" 7 8 TEST_CASE("Small Prim algorithm", "[small prim algo]") { 9 std::size_t edgeCount = 1; 10 std::size_t vertCount = 2; 11 12 float xMax = 5120; 13 float yMax = 1440; 14 15 Graph g = Graph(edgeCount, vertCount, xMax, yMax); 16 std::unordered_set<std::size_t> visitedIndices{}; 17 std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{}; 18 std::vector<Edge> edges = g.getEdgesOfVertexIdx(0); 19 std::vector<double> minEdgeToVertex(vertCount, -1); 20 21 for (auto edge : edges) { 22 toVisit.push(edge); 23 } 24 25 g.traverseVertexIdx(0); 26 visitedIndices.insert(0); 27 28 while (toVisit.size() != 0) { 29 oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex); 30 } 31 // this will be true bc 2 vertices 1 edge... 32 // our graph may have multi-edges. 33 REQUIRE(visitedIndices.size() == 2); 34 } 35 36 bool isConnected(Graph g) { 37 std::unordered_set<std::size_t> verticesFound{0}; 38 39 std::vector<std::size_t> current{}; 40 41 while (true) { 42 for (auto key : verticesFound) { 43 auto edges = g.getEdgesOfVertexIdx(key); 44 for (auto edge : edges) { 45 current.push_back(edge.v1Index); 46 current.push_back(edge.v2Index); 47 } 48 } 49 std::size_t len = verticesFound.size(); 50 for (auto idx : current) { 51 verticesFound.insert(idx); 52 } 53 if (len == verticesFound.size()) { 54 break; 55 } 56 } 57 58 return verticesFound.size() == g.getVertexCount(); 59 } 60 61 TEST_CASE("Large Prim algorithm", "[Large prim algo]") { 62 std::size_t edgeCount = 3000; 63 std::size_t vertCount = 1000; 64 65 float xMax = 5120; 66 float yMax = 1440; 67 68 Graph g = Graph(edgeCount, vertCount, xMax, yMax); 69 std::unordered_set<std::size_t> visitedIndices{}; 70 std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{}; 71 std::vector<double> minEdgeToVertex(vertCount, -1); 72 73 do { 74 g = Graph(edgeCount, vertCount, xMax, yMax); 75 } while (!isConnected(g)); 76 77 g.traverseVertexIdx(0); 78 visitedIndices.insert(0); 79 80 std::vector<Edge> edges = g.getEdgesOfVertexIdx(0); 81 82 for (auto edge : edges) { 83 toVisit.push(edge); 84 } 85 86 while (toVisit.size() != 0) { 87 oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex); 88 } 89 90 REQUIRE(visitedIndices.size() == vertCount); 91 } 92 93 TEST_CASE("Medium Prim algorithm", "[Medium prim algo]") { 94 std::size_t edgeCount = 70; 95 std::size_t vertCount = 51; 96 97 float xMax = 5120; 98 float yMax = 1440; 99 100 Graph g = Graph(edgeCount, vertCount, xMax, yMax); 101 std::unordered_set<std::size_t> visitedIndices{}; 102 std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{}; 103 std::vector<double> minEdgeToVertex(vertCount, -1); 104 105 do { 106 g = Graph(edgeCount, vertCount, xMax, yMax); 107 } while (!isConnected(g)); 108 109 g.traverseVertexIdx(0); 110 visitedIndices.insert(0); 111 112 std::vector<Edge> edges = g.getEdgesOfVertexIdx(0); 113 114 for (auto edge : edges) { 115 toVisit.push(edge); 116 } 117 118 while (toVisit.size() != 0) { 119 oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex); 120 } 121 122 REQUIRE(visitedIndices.size() == vertCount); 123 } 124 125 TEST_CASE("Staircase Prim algorithm", "[Staircase prim algo]") { 126 for (int i = 2; i < 30; ++i) { 127 for (int x = i - 1; x < 60; ++x) { 128 std::size_t edgeCount = x; 129 std::size_t vertCount = i; 130 131 float xMax = 5120; 132 float yMax = 1440; 133 134 std::vector<double> minEdgeToVertex(vertCount, -1); 135 Graph g = Graph(edgeCount, vertCount, xMax, yMax); 136 std::unordered_set<std::size_t> visitedIndices{}; 137 std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> 138 toVisit{}; 139 140 do { 141 g = Graph(edgeCount, vertCount, xMax, yMax); 142 } while (!isConnected(g)); 143 144 std::vector<Edge> edges = g.getEdgesOfVertexIdx(0); 145 for (auto edge : edges) { 146 toVisit.push(edge); 147 } 148 g.traverseVertexIdx(0); 149 visitedIndices.insert(0); 150 151 while (toVisit.size() != 0) { 152 oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex); 153 } 154 155 REQUIRE(visitedIndices.size() == vertCount); 156 } 157 } 158 } 159 160 TEST_CASE("Small Prim Test", "[Small full validation]") { 161 for (int i = 0; i < 100; ++i) { 162 std::size_t edgeCount = 10; 163 std::size_t vertCount = 5; 164 165 float xMax = 5120; 166 float yMax = 1440; 167 168 Graph g = Graph(edgeCount, vertCount, xMax, yMax); 169 do { 170 g = Graph(edgeCount, vertCount, xMax, yMax); 171 } while (!isConnected(g)); 172 173 std::unordered_set<std::size_t> visitedIndices{}; 174 std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> 175 toVisit{}; 176 177 for (auto edge : g.getEdgesOfVertexIdx(0)) toVisit.push(edge); 178 g.traverseVertexIdx(0); 179 visitedIndices.insert(0); 180 181 std::unordered_set<std::size_t> vBefore = visitedIndices; 182 183 bool havePrior = false; 184 Edge prior = toVisit.top(); 185 std::unordered_set<std::size_t> visibleAtPrior; 186 std::vector<double> minEdgeToVertex(vertCount, -1); 187 188 while (toVisit.size() != 0) { 189 auto current = toVisit.top(); 190 if (havePrior) { 191 bool wasPresent = visibleAtPrior.count(current.v1Index) > 0 || 192 visibleAtPrior.count(current.v2Index) > 0; 193 // anytime we use the same source node two steps in a row, the 194 // second weight must be smaller. 195 if (wasPresent) { 196 REQUIRE(current.length2 >= prior.length2); 197 } 198 } 199 200 prior = current; 201 visibleAtPrior = visitedIndices; 202 havePrior = true; 203 oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex); 204 bool valid = vBefore.size() + 1 == visitedIndices.size() || 205 vBefore.size() == vertCount; 206 REQUIRE(valid); 207 vBefore = visitedIndices; 208 } 209 REQUIRE(visitedIndices.size() == vertCount); 210 } 211 } 212 213 // traverse the graph randomly, ensuring we visit all vertices then return edge 214 // weight sum. This ensures our admissible heuristic always beats or is on par 215 // with an inadmissible one (this one). 216 217 double randomTraversalCost(Graph g) { 218 std::uint32_t seed = std::random_device{}(); 219 std::mt19937 rng{seed}; 220 221 std::size_t count = g.getVertexCount(); 222 std::uniform_int_distribution<std::size_t> pick1(0, count - 1); 223 224 std::size_t traversed = 0; 225 double cost = 0; 226 227 g.traverseVertexIdx(pick1(rng)); // start 228 traversed += 1; 229 230 while (traversed < g.getVertexCount()) { 231 std::size_t idx = pick1(rng); 232 if (g.getVertex(idx).visited) { 233 std::vector<Edge> edges = g.getEdgesOfVertexIdx(idx); 234 std::uniform_int_distribution<std::size_t> pick2(0, 235 edges.size() - 1); 236 std::size_t selection = pick2(rng); 237 if (!g.getVertex(edges[selection].v2Index).visited) { 238 cost += edges[selection].length2; 239 g.setEdgeTraversed(edges[selection]); 240 g.traverseVertexIdx(edges[selection].v2Index); 241 traversed += 1; 242 } 243 } 244 } 245 return cost; 246 } 247 248 TEST_CASE("Prim Correctness Test", "[Correctness test for MST]") { 249 for (int i = 0; i < 100; ++i) { 250 std::size_t edgeCount = 10; 251 std::size_t vertCount = 5; 252 253 float xMax = 5120; 254 float yMax = 1440; 255 256 Graph g = Graph(edgeCount, vertCount, xMax, yMax); 257 do { 258 g = Graph(edgeCount, vertCount, xMax, yMax); 259 } while (!isConnected(g)); // this passes by value 260 261 double rndCost = randomTraversalCost(g); // this passes by value 262 263 std::unordered_set<std::size_t> visitedIndices{}; 264 std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> 265 toVisit{}; 266 267 for (auto edge : g.getEdgesOfVertexIdx(0)) toVisit.push(edge); 268 g.traverseVertexIdx(0); 269 visitedIndices.insert(0); 270 271 std::unordered_set<std::size_t> vBefore = visitedIndices; 272 273 bool havePrior = false; 274 Edge prior = toVisit.top(); 275 std::unordered_set<std::size_t> visibleAtPrior; 276 std::vector<double> minEdgeToVertex(vertCount, -1); 277 278 double primCost = 0; 279 280 while (toVisit.size() != 0) { 281 auto current = toVisit.top(); 282 if (havePrior) { 283 bool wasPresent = visibleAtPrior.count(current.v1Index) > 0 || 284 visibleAtPrior.count(current.v2Index) > 0; 285 // anytime we use the same source node two steps in a row, the 286 // second weight must be smaller. 287 if (wasPresent) { 288 REQUIRE(current.length2 >= prior.length2); 289 } 290 } 291 292 prior = current; 293 visibleAtPrior = visitedIndices; 294 havePrior = true; 295 296 primCost += 297 oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex); 298 bool valid = vBefore.size() + 1 == visitedIndices.size() || 299 vBefore.size() == vertCount; 300 REQUIRE(valid); 301 vBefore = visitedIndices; 302 } 303 REQUIRE(visitedIndices.size() == vertCount); 304 REQUIRE(primCost <= rndCost); 305 } 306 }