abg

Animated background for X11
git clone git://git.laack.co/abg.git
Log | Files | Refs | README | LICENSE

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 }