commit 27a69afb31f1b2bbf19f6c9d7a715b52c41b7cd0
parent 4663bb33a71ecb5a188d89014ba66e89e0391ee1
Author: Andrew Laack <andrew@laack.co>
Date: Tue, 15 Sep 2026 02:43:34 -0500
Wrote tests for graph + prim's algorithm
Diffstat:
13 files changed, 436 insertions(+), 56 deletions(-)
diff --git a/background/Makefile b/background/Makefile
@@ -1,6 +1,13 @@
build:
- g++ -Ofast src/main.cpp src/graph.cpp src/edge.cpp src/utils.cpp src/vertex.cpp -lraylib -o background
+ g++ -Ofast src/main.cpp src/prim.cpp src/graph.cpp src/edge.cpp src/utils.cpp src/vertex.cpp -lraylib -o background
install: build
cp background /usr/local/bin
clean:
rm background
+test:
+ g++ tests/graph_test.cpp src/prim.cpp src/graph.cpp src/edge.cpp src/utils.cpp src/vertex.cpp -lCatch2Main -lCatch2 -lraylib -o graph_tests
+ ./graph_tests
+ rm graph_tests
+ g++ tests/algo_test.cpp src/prim.cpp src/graph.cpp src/edge.cpp src/utils.cpp src/vertex.cpp -lCatch2Main -lCatch2 -lraylib -o algo_tests
+ ./algo_tests
+ rm algo_tests
diff --git a/background/README b/background/README
@@ -0,0 +1,7 @@
+background
+==========
+
+
+dependencies
+============
+X11, feh, raylib, g++
diff --git a/background/headers/edge.hpp b/background/headers/edge.hpp
@@ -1,12 +1,12 @@
#pragma once
-#include <cstddef>
#include <string>
class Edge {
public:
// indices of v1 and v2
- Edge(std::size_t v1, std::size_t v2, float length2);
+ Edge(std::size_t v1, std::size_t v2, float length2, std::size_t identifier);
+ std::size_t identifier;
std::size_t v1Index;
std::size_t v2Index;
float length2;
diff --git a/background/headers/graph.hpp b/background/headers/graph.hpp
@@ -1,5 +1,7 @@
#pragma once
+#include <cstddef>
+#include <cstdint>
#include <string>
#include <unordered_map>
#include <vector>
@@ -12,10 +14,12 @@ class Graph {
std::vector<Vertex> vertices {};
public:
// based on the edgeCount and vertCount, random edges and vertices will be created.
- Graph(std::size_t edgeCount, std::size_t vertCount, float xMax, float yMax);
+ Graph(std::size_t edgeCount, std::size_t vertCount, uint32_t xMax, uint32_t yMax);
std::string toString();
void render();
void traverseVertexIdx(std::size_t idx);
std::vector<Edge> getEdgesOfVertexIdx(std::size_t idx);
void setEdgeTraversed(Edge e);
+ Vertex getVertex(std::size_t idx);
+ std::size_t getVertexCount();
};
diff --git a/background/headers/prim.hpp b/background/headers/prim.hpp
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <cstdlib>
+#include <unistd.h>
+#include <raylib.h>
+#include <queue>
+#include "../headers/graph.hpp"
+#include <unordered_set>
+
+void explore(
+ std::size_t cIdx,
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
+ Edge& current,
+ Graph& g
+ );
+void oneStepPrim(
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
+ std::unordered_set<std::size_t>& visitedIndices,
+ Graph& g
+ );
diff --git a/background/headers/utils.hpp b/background/headers/utils.hpp
@@ -1,9 +1,10 @@
#pragma once
+#include <cstdint>
#include <raylib.h>
#define DARKERGRAY CLITERAL(Color){ 40, 40, 40, 255 }
float square(float x);
-Vector2 randomPosition(float xMax, float yMax);
+Vector2 randomPosition(uint32_t xMax, uint32_t yMax);
float distanceSquared(Vector2 v1, Vector2 v2);
diff --git a/background/src/edge.cpp b/background/src/edge.cpp
@@ -1,7 +1,8 @@
#include "../headers/edge.hpp"
+#include <cstddef>
-Edge::Edge(std::size_t v1, std::size_t v2, float length2)
- : v1Index(v1), v2Index(v2), length2(length2) {}
+Edge::Edge(std::size_t v1, std::size_t v2, float length2, std::size_t identifier)
+ : v1Index(v1), v2Index(v2), length2(length2), identifier(identifier) {}
std::string Edge::toString() {
return "(" + std::to_string(this->v1Index) + ", " + std::to_string(this->v2Index) + ")";
diff --git a/background/src/graph.cpp b/background/src/graph.cpp
@@ -2,9 +2,20 @@
#include "../headers/vertex.hpp"
#include "../headers/utils.hpp"
#include <cstddef>
+#include <cstdint>
#include <raylib.h>
+#include <stdexcept>
+
+Graph::Graph(std::size_t edgeCount, std::size_t vertCount, uint32_t xMax, uint32_t yMax) {
+
+ if(edgeCount > 0 && vertCount <= 1) {
+ throw std::invalid_argument("This graph does not support self-loops.");
+ }
+ if(xMax <= 0 || yMax <= 0) {
+ throw std::invalid_argument("xMax and yMax must be > 0.");
+ }
+
-Graph::Graph(std::size_t edgeCount, std::size_t vertCount, float xMax, float yMax) {
for(std::size_t i = 0; i < vertCount; ++i) {
Vector2 rnd = randomPosition(xMax, yMax);
Vertex v {rnd,5};
@@ -19,7 +30,7 @@ Graph::Graph(std::size_t edgeCount, std::size_t vertCount, float xMax, float yMa
idx2 = std::rand() % vertCount;
}
- Edge e {idx1, idx2, distanceSquared(vertices[idx1].position, vertices[idx2].position)};
+ Edge e {idx1, idx2, distanceSquared(vertices[idx1].position, vertices[idx2].position), i};
this->edges[idx1].push_back(e);
this->edges[idx2].push_back(e);
}
@@ -117,3 +128,16 @@ void Graph::setEdgeTraversed(Edge e) {
}
}
+
+Vertex Graph::getVertex(std::size_t idx) {
+ // idx can't be negative bc size_t
+ if(idx >= vertices.size()) {
+ throw std::invalid_argument("idx out of bounds for vertex list");
+ }
+ return vertices[idx];
+}
+
+
+std::size_t Graph::getVertexCount() {
+ return vertices.size();
+}
diff --git a/background/src/main.cpp b/background/src/main.cpp
@@ -1,4 +1,5 @@
#include "../headers/graph.hpp"
+#include "../headers/prim.hpp"
#include <cstdlib>
#include <unistd.h>
#include <raylib.h>
@@ -13,19 +14,6 @@ void CustomTakeScreenshot(char* filePath){
ExportImage(screenshot, TextFormat(filePath, customParam));
UnloadImage(screenshot);
}
-void explore(
- std::size_t cIdx,
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
- Edge& current,
- Graph& g
- ) {
- g.traverseVertexIdx(cIdx);
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(cIdx);
- for(auto edge: edges) {
- toVisit.push(edge);
- }
- g.setEdgeTraversed(current);
-}
int main() {
@@ -55,7 +43,7 @@ int main() {
g.traverseVertexIdx(0);
visitedIndices.insert(0);
- while (!WindowShouldClose()) {
+ while (!WindowShouldClose() && toVisit.size() != 0) {
sleep(5);
BeginDrawing();
@@ -67,35 +55,7 @@ int main() {
CustomTakeScreenshot(path);
// TODO: Can this be done away with? It's not *that* slow...
system("/usr/bin/feh --no-fehbg --bg-tile /dev/shm/bg/out.png");
-
-
- bool found = false;
- if(toVisit.size() == 0) {
- break;
- }
- while(found == false) {
- if(toVisit.size() == 0) {
- break;
- }
-
- found = true;
- auto current = toVisit.top();
- toVisit.pop();
-
- if(visitedIndices.find(current.v2Index) == visitedIndices.end()) {
- auto cIdx = current.v2Index;
- visitedIndices.insert(current.v2Index);
- explore(cIdx, toVisit, current, g);
-
- } else if(visitedIndices.find(current.v1Index) == visitedIndices.end()) {
- auto cIdx = current.v1Index;
- visitedIndices.insert(current.v1Index);
- explore(cIdx, toVisit, current, g);
- } else {
- found = false;
- }
-
- }
+ oneStepPrim(toVisit, visitedIndices, g);
}
diff --git a/background/src/prim.cpp b/background/src/prim.cpp
@@ -0,0 +1,61 @@
+#include "../headers/graph.hpp"
+#include "../headers/prim.hpp"
+#include <cstdlib>
+#include <unistd.h>
+#include <raylib.h>
+#include <queue>
+#include <unordered_set>
+
+
+void explore(
+ std::size_t cIdx,
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
+ Edge& current,
+ Graph& g,
+ std::unordered_set<std::size_t>& visitedIndices
+ ) {
+
+ visitedIndices.insert(cIdx);
+ g.traverseVertexIdx(cIdx);
+
+ g.setEdgeTraversed(current);
+
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(cIdx);
+ for(auto edge: edges) {
+ toVisit.push(edge);
+ }
+}
+
+void oneStepPrim(
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
+ std::unordered_set<std::size_t>& visitedIndices,
+ Graph& g
+ ) {
+ bool found = false;
+ if(toVisit.size() == 0) {
+ return;
+ }
+ while(found == false) {
+ if(toVisit.size() == 0) {
+ return;
+ }
+
+ found = true;
+ auto current = toVisit.top();
+ toVisit.pop();
+
+ if(visitedIndices.find(current.v2Index) == visitedIndices.end()) {
+ auto cIdx = current.v2Index;
+ explore(cIdx, toVisit, current, g, visitedIndices);
+
+ } else if(visitedIndices.find(current.v1Index) == visitedIndices.end()) {
+ auto cIdx = current.v1Index;
+ explore(cIdx, toVisit, current, g, visitedIndices);
+ } else {
+ found = false;
+ }
+
+ }
+}
+
+
diff --git a/background/src/utils.cpp b/background/src/utils.cpp
@@ -1,4 +1,5 @@
#include "../headers/utils.hpp"
+#include <cstdint>
#include <cstdlib>
float square(float x) {
@@ -6,10 +7,10 @@ float square(float x) {
}
// call srand before invocation as this is a pure function.
-Vector2 randomPosition(float xMax, float yMax) {
- float r1 = static_cast <float> (rand()) / static_cast <float> (RAND_MAX) * xMax;
- float r2 = static_cast <float> (rand()) / static_cast <float> (RAND_MAX) * yMax;
- Vector2 v {r1,r2};
+Vector2 randomPosition(uint32_t xMax, uint32_t yMax) {
+ uint32_t r1 = rand() % xMax;
+ uint32_t r2 = rand() % yMax;
+ Vector2 v {(float)r1,(float)r2};
return v;
}
diff --git a/background/tests/algo_test.cpp b/background/tests/algo_test.cpp
@@ -0,0 +1,167 @@
+#include "../headers/prim.hpp"
+
+#include <catch2/catch_test_macros.hpp>
+#include <cstddef>
+
+TEST_CASE( "Small Prim algorithm", "[small prim algo]" ) {
+ std::size_t edgeCount = 1;
+ std::size_t vertCount = 2;
+
+ float xMax = 5120;
+ float yMax = 1440;
+
+ Graph g = Graph(edgeCount, vertCount, xMax,yMax);
+ std::unordered_set<std::size_t> visitedIndices {};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit {};
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+
+ for(auto edge: edges) {
+ toVisit.push(edge);
+ }
+
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
+
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
+ // this will be true bc 2 vertices 1 edge...
+ // our graph may have multi-edges.
+ REQUIRE(visitedIndices.size() == 2);
+}
+
+
+bool isConnected(Graph g) {
+
+ std::unordered_set<std::size_t> verticesFound {0};
+
+ std::vector<std::size_t> current {};
+
+ while(true) {
+ for(auto key: verticesFound) {
+ auto edges = g.getEdgesOfVertexIdx(key);
+ for(auto edge: edges) {
+ current.push_back(edge.v1Index);
+ current.push_back(edge.v2Index);
+ }
+ }
+ std::size_t len = verticesFound.size();
+ for(auto idx: current) {
+ verticesFound.insert(idx);
+ }
+ if (len == verticesFound.size()) {
+ break;
+ }
+ }
+
+ return verticesFound.size() == g.getVertexCount();
+}
+
+
+TEST_CASE( "Large Prim algorithm", "[Large prim algo]" ) {
+ std::size_t edgeCount = 3000;
+ std::size_t vertCount = 1000;
+
+ float xMax = 5120;
+ float yMax = 1440;
+
+ Graph g = Graph(edgeCount, vertCount, xMax,yMax);
+ std::unordered_set<std::size_t> visitedIndices {};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit {};
+
+ do {
+ g = Graph(edgeCount, vertCount, xMax,yMax);
+ }
+ while(!isConnected(g));
+
+
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
+
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+
+ for(auto edge: edges) {
+ toVisit.push(edge);
+ }
+
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
+
+ REQUIRE(visitedIndices.size() == vertCount);
+}
+
+TEST_CASE( "Medium Prim algorithm", "[Medium prim algo]" ) {
+ std::size_t edgeCount = 70;
+ std::size_t vertCount = 51;
+
+ float xMax = 5120;
+ float yMax = 1440;
+
+ Graph g = Graph(edgeCount, vertCount, xMax,yMax);
+ std::unordered_set<std::size_t> visitedIndices {};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit {};
+
+ do {
+ g = Graph(edgeCount, vertCount, xMax,yMax);
+ }
+ while(!isConnected(g));
+
+
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
+
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+
+ for(auto edge: edges) {
+ toVisit.push(edge);
+ }
+
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
+
+ REQUIRE(visitedIndices.size() == vertCount);
+}
+
+
+TEST_CASE( "Staircase Prim algorithm", "[Staircase prim algo]" ) {
+ for(int i = 2; i < 30; ++i) {
+ for(int x = i-1; x < 60; ++x) {
+ std::size_t edgeCount = x;
+ std::size_t vertCount = i;
+
+ float xMax = 5120;
+ float yMax = 1440;
+
+ Graph g = Graph(edgeCount, vertCount, xMax,yMax);
+ std::unordered_set<std::size_t> visitedIndices {};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit {};
+
+ do {
+ g = Graph(edgeCount, vertCount, xMax,yMax);
+ }
+ while(!isConnected(g));
+
+
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
+
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+
+ for(auto edge: edges) {
+ toVisit.push(edge);
+ }
+
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
+
+ REQUIRE(visitedIndices.size() == vertCount);
+
+
+ }
+ }
+}
+
+
diff --git a/background/tests/graph_test.cpp b/background/tests/graph_test.cpp
@@ -0,0 +1,127 @@
+#include "../headers/graph.hpp"
+
+#include <catch2/catch_test_macros.hpp>
+#include <cstdlib>
+#include <unordered_set>
+
+TEST_CASE( "Graph traversal invariants", "[graph traversal]" ) {
+ int vertCount = 10;
+ int edgeCount = 10;
+ float xMax = 10;
+ float yMax = 10;
+ auto g = Graph(edgeCount,vertCount,xMax,yMax);
+ int count = 0;
+ for(int i = 0; i < vertCount; ++i) {
+ g.traverseVertexIdx(i);
+ count += 1;
+ }
+ for(int i = 0; i < vertCount; ++i) {
+ REQUIRE(g.getVertex(i).visited);
+ }
+
+ bool error = false;
+
+ try {
+ g.getVertex(vertCount + 1);
+ } catch (std::invalid_argument e) {
+ error = true;
+ }
+
+ REQUIRE(error);
+}
+
+void createGraph(int vertCount, int edgeCount) {
+ auto g = Graph(edgeCount,vertCount,10,10);
+}
+
+TEST_CASE( "Graph gracefully handles stupid fucking inputs", "[graph bad inputs]" ) {
+ int vertCount = 0;
+ int edgeCount = 0; // some trivial and stupid graph
+
+ bool error = false;
+
+ try {
+ createGraph(vertCount, edgeCount);
+ } catch (std::invalid_argument e) {
+ error = true;
+ }
+ REQUIRE(!error);
+
+ vertCount = 0;
+ edgeCount = 1; // bad
+
+ error = false;
+ try {
+ createGraph(vertCount, edgeCount);
+ } catch (std::invalid_argument e) {
+ error = true;
+ }
+
+ REQUIRE(error);
+
+}
+
+TEST_CASE( "Graph respects max x and max y values", "[graph max values]" ) {
+ int vertCount = 10;
+ int edgeCount = 10;
+
+ for(int z = 2; z < 100; ++z) {
+
+ float xMax = 0;
+ float yMax = 0;
+
+ while (xMax == 0 || yMax == 0) {
+ xMax = rand() % z;
+ yMax = rand() % z;
+ }
+
+ auto g = Graph(edgeCount,vertCount,xMax,yMax);
+
+ for(int i = 0; i < vertCount; ++i) {
+ REQUIRE(g.getVertex(i).position.x <= xMax);
+ }
+ for(int i = 0; i < vertCount; ++i) {
+ REQUIRE(g.getVertex(i).position.y <= yMax);
+ }
+ }
+ auto g = Graph(edgeCount,vertCount,UINT32_MAX,UINT32_MAX);
+
+ for(int i = 0; i < vertCount; ++i) {
+ REQUIRE(g.getVertex(i).position.x <= UINT32_MAX);
+ }
+ for(int i = 0; i < vertCount; ++i) {
+ REQUIRE(g.getVertex(i).position.y <= UINT32_MAX);
+ }
+}
+
+
+std::size_t countEdges(Graph g) {
+ std::size_t vertexCount = g.getVertexCount();
+ std::unordered_set<std::size_t> unique {};
+
+ for(std::size_t i = 0; i < vertexCount; ++i) {
+ auto edges = g.getEdgesOfVertexIdx(i);
+ for(auto edge: edges) {
+ unique.insert(edge.identifier);
+ }
+ }
+ return unique.size();
+}
+
+TEST_CASE( "Graph vertex and edge counts", "[graph counts]" ) {
+
+ for(int i = 2; i < 100; ++i) {
+ for(int x = 1; x < 10; ++x) {
+ int vertCount = i;
+ int edgeCount = x;
+ float xMax = 10;
+ float yMax = 10;
+
+ auto g = Graph(edgeCount,vertCount,xMax,yMax);
+
+ REQUIRE(g.getVertexCount() == vertCount);
+ REQUIRE(countEdges(g) == edgeCount);
+ }
+ }
+
+}
