abg

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

algo_test.cpp (6316B)

      1 #include <catch2/catch_test_macros.hpp>
      2 #include <cstddef>
      3 
      4 #include "../include/prim.hpp"
      5 
      6 TEST_CASE("Small Prim algorithm", "[small prim algo]") {
      7     std::size_t edgeCount = 1;
      8     std::size_t vertCount = 2;
      9 
     10     float xMax = 5120;
     11     float yMax = 1440;
     12 
     13     Graph g = Graph(edgeCount, vertCount, xMax, yMax);
     14     std::unordered_set<std::size_t> visitedIndices{};
     15     std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
     16     std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
     17     std::vector<double> minEdgeToVertex(vertCount, -1);
     18 
     19     for (auto edge : edges) {
     20         toVisit.push(edge);
     21     }
     22 
     23     g.traverseVertexIdx(0);
     24     visitedIndices.insert(0);
     25 
     26     while (toVisit.size() != 0) {
     27         oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
     28     }
     29     // this will be true bc 2 vertices 1 edge...
     30     // our graph may have multi-edges.
     31     REQUIRE(visitedIndices.size() == 2);
     32 }
     33 
     34 bool isConnected(Graph g) {
     35     std::unordered_set<std::size_t> verticesFound{0};
     36 
     37     std::vector<std::size_t> current{};
     38 
     39     while (true) {
     40         for (auto key : verticesFound) {
     41             auto edges = g.getEdgesOfVertexIdx(key);
     42             for (auto edge : edges) {
     43                 current.push_back(edge.v1Index);
     44                 current.push_back(edge.v2Index);
     45             }
     46         }
     47         std::size_t len = verticesFound.size();
     48         for (auto idx : current) {
     49             verticesFound.insert(idx);
     50         }
     51         if (len == verticesFound.size()) {
     52             break;
     53         }
     54     }
     55 
     56     return verticesFound.size() == g.getVertexCount();
     57 }
     58 
     59 TEST_CASE("Large Prim algorithm", "[Large prim algo]") {
     60     std::size_t edgeCount = 3000;
     61     std::size_t vertCount = 1000;
     62 
     63     float xMax = 5120;
     64     float yMax = 1440;
     65 
     66     Graph g = Graph(edgeCount, vertCount, xMax, yMax);
     67     std::unordered_set<std::size_t> visitedIndices{};
     68     std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
     69     std::vector<double> minEdgeToVertex(vertCount, -1);
     70 
     71     do {
     72         g = Graph(edgeCount, vertCount, xMax, yMax);
     73     } while (!isConnected(g));
     74 
     75     g.traverseVertexIdx(0);
     76     visitedIndices.insert(0);
     77 
     78     std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
     79 
     80     for (auto edge : edges) {
     81         toVisit.push(edge);
     82     }
     83 
     84     while (toVisit.size() != 0) {
     85         oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
     86     }
     87 
     88     REQUIRE(visitedIndices.size() == vertCount);
     89 }
     90 
     91 TEST_CASE("Medium Prim algorithm", "[Medium prim algo]") {
     92     std::size_t edgeCount = 70;
     93     std::size_t vertCount = 51;
     94 
     95     float xMax = 5120;
     96     float yMax = 1440;
     97 
     98     Graph g = Graph(edgeCount, vertCount, xMax, yMax);
     99     std::unordered_set<std::size_t> visitedIndices{};
    100     std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
    101     std::vector<double> minEdgeToVertex(vertCount, -1);
    102 
    103     do {
    104         g = Graph(edgeCount, vertCount, xMax, yMax);
    105     } while (!isConnected(g));
    106 
    107     g.traverseVertexIdx(0);
    108     visitedIndices.insert(0);
    109 
    110     std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
    111 
    112     for (auto edge : edges) {
    113         toVisit.push(edge);
    114     }
    115 
    116     while (toVisit.size() != 0) {
    117         oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
    118     }
    119 
    120     REQUIRE(visitedIndices.size() == vertCount);
    121 }
    122 
    123 TEST_CASE("Staircase Prim algorithm", "[Staircase prim algo]") {
    124     for (int i = 2; i < 30; ++i) {
    125         for (int x = i - 1; x < 60; ++x) {
    126             std::size_t edgeCount = x;
    127             std::size_t vertCount = i;
    128 
    129             float xMax = 5120;
    130             float yMax = 1440;
    131 
    132             std::vector<double> minEdgeToVertex(vertCount, -1);
    133             Graph g = Graph(edgeCount, vertCount, xMax, yMax);
    134             std::unordered_set<std::size_t> visitedIndices{};
    135             std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>
    136                 toVisit{};
    137 
    138             do {
    139                 g = Graph(edgeCount, vertCount, xMax, yMax);
    140             } while (!isConnected(g));
    141 
    142             std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
    143             for (auto edge : edges) {
    144                 toVisit.push(edge);
    145             }
    146             g.traverseVertexIdx(0);
    147             visitedIndices.insert(0);
    148 
    149             while (toVisit.size() != 0) {
    150                 oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
    151             }
    152 
    153             REQUIRE(visitedIndices.size() == vertCount);
    154         }
    155     }
    156 }
    157 
    158 TEST_CASE("Small Prim Test", "[Small full validation]") {
    159     for (int i = 0; i < 100; ++i) {
    160         std::size_t edgeCount = 10;
    161         std::size_t vertCount = 5;
    162 
    163         float xMax = 5120;
    164         float yMax = 1440;
    165 
    166         Graph g = Graph(edgeCount, vertCount, xMax, yMax);
    167         do {
    168             g = Graph(edgeCount, vertCount, xMax, yMax);
    169         } while (!isConnected(g));
    170 
    171         std::unordered_set<std::size_t> visitedIndices{};
    172         std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>
    173             toVisit{};
    174 
    175         for (auto edge : g.getEdgesOfVertexIdx(0)) toVisit.push(edge);
    176         g.traverseVertexIdx(0);
    177         visitedIndices.insert(0);
    178 
    179         std::unordered_set<std::size_t> vBefore = visitedIndices;
    180 
    181         bool havePrior = false;
    182         Edge prior = toVisit.top();
    183         std::unordered_set<std::size_t> visibleAtPrior;
    184         std::vector<double> minEdgeToVertex(vertCount, -1);
    185 
    186         while (toVisit.size() != 0) {
    187             auto current = toVisit.top();
    188             if (havePrior) {
    189                 bool wasPresent = visibleAtPrior.count(current.v1Index) > 0 ||
    190                                   visibleAtPrior.count(current.v2Index) > 0;
    191                 // anytime we use the same source node two steps in a row, the
    192                 // second weight must be smaller.
    193                 if (wasPresent) {
    194                     REQUIRE(current.length2 >= prior.length2);
    195                 }
    196             }
    197 
    198             prior = current;
    199             visibleAtPrior = visitedIndices;
    200             havePrior = true;
    201             oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
    202             bool valid = vBefore.size() + 1 == visitedIndices.size() ||
    203                          vBefore.size() == vertCount;
    204             REQUIRE(valid);
    205             vBefore = visitedIndices;
    206         }
    207         REQUIRE(visitedIndices.size() == vertCount);
    208     }
    209 }