commit e62b7193b1fcea31c57f91f9a25c736b543477cf
parent 17119798c5c2dd71a7eebecbee66905371bb5a26
Author: Andrew Laack <andrew@laack.co>
Date: Wed, 16 Sep 2026 01:23:24 -0500
Formatted
Diffstat:
17 files changed, 639 insertions(+), 662 deletions(-)
diff --git a/include/constants.hpp b/include/constants.hpp
@@ -1,7 +1,7 @@
#include <cstddef>
#include <raylib.h>
-const CLITERAL(Color) DARKERGRAY { 40, 40, 40, 255 };
+const CLITERAL(Color) DARKERGRAY{40, 40, 40, 255};
const float VERTEX_RENDER_SIZE = 4;
const float EDGE_REDNER_SIZE = 1;
diff --git a/include/edge.hpp b/include/edge.hpp
@@ -3,15 +3,15 @@
#include <string>
class Edge {
- public:
- // indices of v1 and v2
- Edge(std::size_t v1, std::size_t v2, double length2, std::size_t identifier);
- std::size_t identifier;
- std::size_t v1Index;
- std::size_t v2Index;
- double length2;
- bool traversed = false;
- std::string toString() const noexcept;
- bool operator<(const Edge& other) const;
- bool operator>(const Edge& other) const;
+public:
+ // indices of v1 and v2
+ Edge(std::size_t v1, std::size_t v2, double length2, std::size_t identifier);
+ std::size_t identifier;
+ std::size_t v1Index;
+ std::size_t v2Index;
+ double length2;
+ bool traversed = false;
+ std::string toString() const noexcept;
+ bool operator<(const Edge &other) const;
+ bool operator>(const Edge &other) const;
};
diff --git a/include/graph.hpp b/include/graph.hpp
@@ -1,25 +1,28 @@
#pragma once
+#include "edge.hpp"
+#include "vertex.hpp"
#include <cstddef>
#include <cstdint>
#include <string>
#include <unordered_map>
#include <vector>
-#include "edge.hpp"
-#include "vertex.hpp"
class Graph {
- private:
- std::unordered_map<std::size_t, std::vector<Edge>> edges {};
- 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, uint32_t xMax, uint32_t yMax);
- std::string toString() noexcept;
- void render() noexcept;
- 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() const noexcept;
+private:
+ std::unordered_map<std::size_t, std::vector<Edge>> edges{};
+ 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, uint32_t xMax,
+ uint32_t yMax);
+ std::string toString() noexcept;
+ void render() noexcept;
+ 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() const noexcept;
};
diff --git a/include/prim.hpp b/include/prim.hpp
@@ -1,20 +1,16 @@
#pragma once
+#include "../include/graph.hpp"
#include <cstdlib>
-#include <unistd.h>
-#include <raylib.h>
#include <queue>
-#include "../include/graph.hpp"
+#include <raylib.h>
+#include <unistd.h>
#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::size_t cIdx,
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> &toVisit,
+ Edge ¤t, Graph &g);
void oneStepPrim(
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
- std::unordered_set<std::size_t>& visitedIndices,
- Graph& g
- );
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> &toVisit,
+ std::unordered_set<std::size_t> &visitedIndices, Graph &g);
diff --git a/include/vertex.hpp b/include/vertex.hpp
@@ -4,11 +4,11 @@
#include <string>
class Vertex {
- public:
- Vertex(Vector2 position, float drawSize);
- Vector2 position;
- float drawSize;
- std::string toString();
- void render();
- bool visited = false;
+public:
+ Vertex(Vector2 position, float drawSize);
+ Vector2 position;
+ float drawSize;
+ std::string toString();
+ void render();
+ bool visited = false;
};
diff --git a/src/background.cpp b/src/background.cpp
@@ -1,61 +1,60 @@
+#include <X11/Xatom.h>
+#include <X11/Xlib.h>
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <string>
-#include <vector>
-#include <X11/Xlib.h>
-#include <X11/Xatom.h>
#include <unistd.h>
+#include <vector>
std::vector<uint32_t> getScreenSize() {
- Display* dpy;
- Screen* screen;
- dpy = XOpenDisplay(NULL);
- int count = ScreenCount(dpy);
- if(count == 0) {
- throw std::runtime_error{"Unable to find screens."};
- }
- screen = ScreenOfDisplay(dpy, 0);
- std::vector<uint32_t> res {(uint32_t)screen->width, (uint32_t)screen->height};
- return res;
+ Display *dpy;
+ Screen *screen;
+ dpy = XOpenDisplay(NULL);
+ int count = ScreenCount(dpy);
+ if (count == 0) {
+ throw std::runtime_error{"Unable to find screens."};
+ }
+ screen = ScreenOfDisplay(dpy, 0);
+ std::vector<uint32_t> res{(uint32_t)screen->width, (uint32_t)screen->height};
+ return res;
}
-void sendToBg(std::string name)
-{
- Display* d = XOpenDisplay(nullptr);
- Window root = DefaultRootWindow(d), r, p, *kids;
- uint32_t n;
+void sendToBg(std::string name) {
+ Display *d = XOpenDisplay(nullptr);
+ Window root = DefaultRootWindow(d), r, p, *kids;
+ uint32_t n;
- XQueryTree(d, root, &r, &p, &kids, &n);
- for (unsigned i = 0; i < n; i++) {
+ XQueryTree(d, root, &r, &p, &kids, &n);
+ for (unsigned i = 0; i < n; i++) {
- char* wn = nullptr;
- XFetchName(d, kids[i], &wn);
+ char *wn = nullptr;
+ XFetchName(d, kids[i], &wn);
- if (wn == nullptr) {
- continue;
- }
+ if (wn == nullptr) {
+ continue;
+ }
- bool hit = name == wn;
- XFree(wn);
+ bool hit = name == wn;
+ XFree(wn);
- if (!hit) {
- continue;
- }
+ if (!hit) {
+ continue;
+ }
- XSetWindowAttributes a;
+ XSetWindowAttributes a;
- a.override_redirect = True;
- XChangeWindowAttributes(d, kids[i], CWOverrideRedirect, &a);
+ a.override_redirect = True;
+ XChangeWindowAttributes(d, kids[i], CWOverrideRedirect, &a);
- // have to do unmap / map to make it bg for all tags
- XUnmapWindow(d, kids[i]);
- XMapWindow(d, kids[i]);
+ // have to do unmap / map to make it bg for all tags
+ XUnmapWindow(d, kids[i]);
+ XMapWindow(d, kids[i]);
- XLowerWindow(d, kids[i]);
- break;
- }
+ XLowerWindow(d, kids[i]);
+ break;
+ }
- XFree(kids);
- XCloseDisplay(d);
+ XFree(kids);
+ XCloseDisplay(d);
}
diff --git a/src/edge.cpp b/src/edge.cpp
@@ -2,17 +2,20 @@
#include <cstddef>
#include <string>
-Edge::Edge(std::size_t v1, std::size_t v2, double length2, std::size_t identifier)
+Edge::Edge(std::size_t v1, std::size_t v2, double length2,
+ std::size_t identifier)
: v1Index(v1), v2Index(v2), length2(length2), identifier(identifier) {}
std::string Edge::toString() const noexcept {
- return "(v1: " + std::to_string(this->v1Index) + ", v2: " + std::to_string(this->v2Index) + + ", traversed: " + std::to_string(this->traversed) + ")";
+ return "(v1: " + std::to_string(this->v1Index) +
+ ", v2: " + std::to_string(this->v2Index) +
+ +", traversed: " + std::to_string(this->traversed) + ")";
}
-bool Edge::operator<(const Edge& other) const {
- return length2 < other.length2;
+bool Edge::operator<(const Edge &other) const {
+ return length2 < other.length2;
}
-bool Edge::operator>(const Edge& other) const {
- return length2 > other.length2;
+bool Edge::operator>(const Edge &other) const {
+ return length2 > other.length2;
}
diff --git a/src/graph.cpp b/src/graph.cpp
@@ -1,144 +1,141 @@
#include "../include/graph.hpp"
#include "../include/constants.hpp"
-#include "../include/vertex.hpp"
#include "../include/utils.hpp"
+#include "../include/vertex.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.");
+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.");
+ }
+
+ for (std::size_t i = 0; i < vertCount; ++i) {
+ Vector2 rnd = randomPosition(xMax, yMax);
+ Vertex v{rnd, VERTEX_RENDER_SIZE};
+ this->vertices.push_back(v);
+ }
+ for (std::size_t i = 0; i < edgeCount; ++i) {
+ std::size_t idx1 = 0;
+ std::size_t idx2 = 0;
+ // no self-edges
+ while (idx1 == idx2) {
+ idx1 = std::rand() % vertCount;
+ idx2 = std::rand() % vertCount;
}
- if(xMax <= 0 || yMax <= 0) {
- throw std::invalid_argument("xMax and yMax must be > 0.");
- }
-
- for(std::size_t i = 0; i < vertCount; ++i) {
- Vector2 rnd = randomPosition(xMax, yMax);
- Vertex v {rnd,VERTEX_RENDER_SIZE};
- this->vertices.push_back(v);
- }
- for(std::size_t i = 0; i < edgeCount; ++i) {
- std::size_t idx1 = 0;
- std::size_t idx2 = 0;
- // no self-edges
- while (idx1 == idx2) {
- idx1 = std::rand() % vertCount;
- idx2 = std::rand() % vertCount;
- }
-
- Edge e {idx1, idx2, distanceSquared(vertices[idx1].position, vertices[idx2].position), i};
- this->edges[idx1].push_back(e);
- this->edges[idx2].push_back(e);
- }
+ Edge e{idx1, idx2,
+ distanceSquared(vertices[idx1].position, vertices[idx2].position),
+ i};
+ this->edges[idx1].push_back(e);
+ this->edges[idx2].push_back(e);
+ }
}
std::string Graph::toString() noexcept {
- std::string result = "edges: {";
+ std::string result = "edges: {";
- for(auto pair: this->edges) {
- auto key = pair.first;
- for(auto edge: edges[key]) {
- result += edge.toString();
- }
+ for (auto pair : this->edges) {
+ auto key = pair.first;
+ for (auto edge : edges[key]) {
+ result += edge.toString();
}
-
- result += "}";
+ }
- result += "\nvertices: {";
+ result += "}";
- for(auto vertex: this->vertices) {
- result += vertex.toString();
- }
+ result += "\nvertices: {";
- result += "}";
- return result;
-}
+ for (auto vertex : this->vertices) {
+ result += vertex.toString();
+ }
+ result += "}";
+ return result;
+}
void Graph::render() noexcept {
-
- // yes, this will double draw because we track 0 -> 1 and 1 -> 0
-
- std::vector<Edge> visited {};
- for(auto pair: this->edges) {
- auto edges = this->edges[pair.first];
- for(auto edge: edges) {
- std::size_t idx1 = edge.v1Index;
- std::size_t idx2 = edge.v2Index;
- auto v1 = vertices[idx1].position;
- auto v2 = vertices[idx2].position;
- if(edge.traversed) {
- visited.push_back(edge);
- } else {
- DrawLineEx(v1, v2, EDGE_REDNER_SIZE,DARKERGRAY);
- }
- }
- }
-
- for(auto vertex: this->vertices) {
- vertex.render();
- }
- // ensure we draw visited over unvisited for better looks
- for(auto edge: visited) {
- std::size_t idx1 = edge.v1Index;
- std::size_t idx2 = edge.v2Index;
- auto v1 = vertices[idx1].position;
- auto v2 = vertices[idx2].position;
- DrawLineEx(v1, v2, EDGE_REDNER_SIZE, WHITE);
+ // yes, this will double draw because we track 0 -> 1 and 1 -> 0
+
+ std::vector<Edge> visited{};
+ for (auto pair : this->edges) {
+ auto edges = this->edges[pair.first];
+ for (auto edge : edges) {
+ std::size_t idx1 = edge.v1Index;
+ std::size_t idx2 = edge.v2Index;
+ auto v1 = vertices[idx1].position;
+ auto v2 = vertices[idx2].position;
+ if (edge.traversed) {
+ visited.push_back(edge);
+ } else {
+ DrawLineEx(v1, v2, EDGE_REDNER_SIZE, DARKERGRAY);
+ }
}
+ }
+
+ for (auto vertex : this->vertices) {
+ vertex.render();
+ }
+
+ // ensure we draw visited over unvisited for better looks
+ for (auto edge : visited) {
+ std::size_t idx1 = edge.v1Index;
+ std::size_t idx2 = edge.v2Index;
+ auto v1 = vertices[idx1].position;
+ auto v2 = vertices[idx2].position;
+ DrawLineEx(v1, v2, EDGE_REDNER_SIZE, WHITE);
+ }
}
void Graph::traverseVertexIdx(std::size_t idx) {
- this->vertices[idx].visited = true;
+ this->vertices[idx].visited = true;
}
std::vector<Edge> Graph::getEdgesOfVertexIdx(std::size_t idx) {
- return this->edges[idx];
+ return this->edges[idx];
}
void Graph::setEdgeTraversed(Edge e) {
- std::size_t source = e.v1Index;
- std::size_t destination = e.v2Index;
+ std::size_t source = e.v1Index;
+ std::size_t destination = e.v2Index;
- if(source == destination) {
- return;
- }
+ if (source == destination) {
+ return;
+ }
- auto& cEdges = edges[source];
+ auto &cEdges = edges[source];
- for(auto& edge : cEdges) {
- if(edge.v2Index == destination || edge.v1Index == destination) {
- edge.traversed = true;
- }
+ for (auto &edge : cEdges) {
+ if (edge.v2Index == destination || edge.v1Index == destination) {
+ edge.traversed = true;
}
+ }
- auto& oEdges = edges[destination];
+ auto &oEdges = edges[destination];
- for(auto& edge : oEdges) {
- if(edge.v2Index == source || edge.v1Index == source) {
- edge.traversed = true;
- }
+ for (auto &edge : oEdges) {
+ if (edge.v2Index == source || edge.v1Index == source) {
+ edge.traversed = true;
}
-
+ }
}
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];
+ // 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() const noexcept {
- return vertices.size();
-}
+std::size_t Graph::getVertexCount() const noexcept { return vertices.size(); }
diff --git a/src/main.cpp b/src/main.cpp
@@ -1,91 +1,93 @@
-#include "../include/graph.hpp"
-#include "../include/prim.hpp"
#include "../include/background.hpp"
#include "../include/constants.hpp"
+#include "../include/graph.hpp"
+#include "../include/prim.hpp"
#include "../vendor/argparse.hpp"
#include <cstddef>
#include <cstdint>
#include <cstdlib>
-#include <iostream>
-#include <unistd.h>
-#include <raylib.h>
#include <ctime>
+#include <iostream>
#include <queue>
+#include <raylib.h>
+#include <unistd.h>
#include <unordered_set>
-int main(int argc, char** argv) {
+int main(int argc, char **argv) {
- srand(clock());
- // reverse semver
- argparse::ArgumentParser program("abg", "10.0.0");
+ srand(clock());
- program.add_argument("--vertices")
- .help("number of vertices in the graph")
- .default_value(DEFAULT_VERTEX_COUNT)
- .scan<'i', std::size_t>();
+ // reverse semver
+ // software does get completed at some point, and for me that's at 1.0.0.
- program.add_argument("--sleep", "-s")
- .help("amount of time to sleep between traversals")
- .default_value(DEFAULT_SLEEP_TIME)
- .scan<'g', float>();
+ argparse::ArgumentParser program("abg", "10.0.0");
+ program.add_argument("--vertices")
+ .help("number of vertices in the graph")
+ .default_value(DEFAULT_VERTEX_COUNT)
+ .scan<'i', std::size_t>();
- // edges != total number of unique edges where uniqueness is defined by vertices
- // this is because we allow multiple edges between two vertices (though they aren't rendered differently)
- // we don't allow self-edges though.
+ program.add_argument("--sleep", "-s")
+ .help("amount of time to sleep between traversals")
+ .default_value(DEFAULT_SLEEP_TIME)
+ .scan<'g', float>();
- program.add_argument("--edges", "-e")
- .help("number of edges in the graph")
- .default_value(DEFAULT_EDGE_COUNT)
- .scan<'i', std::size_t>();
+ // edges != total number of unique edges where uniqueness is defined by
+ // vertices this is because we allow multiple edges between two vertices
+ // (though they aren't rendered differently) we don't allow self-edges though.
- try {
- program.parse_args(argc, argv);
- }
- catch (const std::exception& err) {
- std::cerr << err.what() << std::endl;
- std::cerr << program;
- std::exit(1);
- }
+ program.add_argument("--edges", "-e")
+ .help("number of edges in the graph")
+ .default_value(DEFAULT_EDGE_COUNT)
+ .scan<'i', std::size_t>();
+
+ try {
+ program.parse_args(argc, argv);
+ } catch (const std::exception &err) {
+ std::cerr << err.what() << std::endl;
+ std::cerr << program;
+ std::exit(1);
+ }
+
+ std::size_t vertexCount = program.get<std::size_t>("--vertices");
+ std::size_t edgeCount = program.get<std::size_t>("--edges");
+ float sleepTime = program.get<float>("--sleep");
+
+ SetTraceLogLevel(LOG_ERROR);
+
+ auto ss = getScreenSize();
- std::size_t vertexCount = program.get<std::size_t>("--vertices");
- std::size_t edgeCount = program.get<std::size_t>("--edges");
- float sleepTime = program.get<float>("--sleep");
-
- SetTraceLogLevel(LOG_ERROR);
-
- auto ss = getScreenSize();
-
- uint32_t xMax = ss[0];
- uint32_t yMax = ss[1];
-
- // would be nice to do this all in background.cpp, but raylib and x11 can't both be imported
- // by the same file because of some dependency chain thing with Font.
-
- InitWindow(xMax, yMax, "abg");
- sendToBg("abg");
-
- int count = 0;
- while (!WindowShouldClose()) {
- count += 1;
-
- Graph g = Graph(edgeCount, vertexCount, 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 (!WindowShouldClose() && toVisit.size() != 0) {
- BeginDrawing();
- ClearBackground(BLACK);
- g.render();
- EndDrawing();
- usleep((int)(sleepTime * 1000000));
- oneStepPrim(toVisit, visitedIndices, g);
- }
+ uint32_t xMax = ss[0];
+ uint32_t yMax = ss[1];
+
+ // would be nice to do this all in background.cpp, but raylib and x11 can't
+ // both be imported by the same file because of some dependency chain thing
+ // with Font.
+
+ InitWindow(xMax, yMax, "abg");
+ sendToBg("abg");
+
+ int count = 0;
+ while (!WindowShouldClose()) {
+ count += 1;
+
+ Graph g = Graph(edgeCount, vertexCount, 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 (!WindowShouldClose() && toVisit.size() != 0) {
+ BeginDrawing();
+ ClearBackground(BLACK);
+ g.render();
+ EndDrawing();
+ usleep((int)(sleepTime * 1000000));
+ oneStepPrim(toVisit, visitedIndices, g);
}
+ }
}
diff --git a/src/prim.cpp b/src/prim.cpp
@@ -1,61 +1,52 @@
-#include "../include/graph.hpp"
#include "../include/prim.hpp"
+#include "../include/graph.hpp"
#include <cstdlib>
-#include <unistd.h>
-#include <raylib.h>
#include <queue>
+#include <raylib.h>
+#include <unistd.h>
#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
- ) {
+ std::size_t cIdx,
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> &toVisit,
+ Edge ¤t, Graph &g, std::unordered_set<std::size_t> &visitedIndices) {
- visitedIndices.insert(cIdx);
- g.traverseVertexIdx(cIdx);
+ visitedIndices.insert(cIdx);
+ g.traverseVertexIdx(cIdx);
- g.setEdgeTraversed(current);
+ g.setEdgeTraversed(current);
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(cIdx);
- for(auto edge: edges) {
- toVisit.push(edge);
- }
+ 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;
+ 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;
}
- 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;
- }
- }
-}
+ 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/src/utils.cpp b/src/utils.cpp
@@ -1,24 +1,22 @@
#include "../include/utils.hpp"
-#include <cstdint>
#include <cassert>
+#include <cstdint>
#include <cstdlib>
-float square(float x) {
- return x * x;
-}
+float square(float x) { return x * x; }
// call srand before invocation as this is a pure function.
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;
+ uint32_t r1 = rand() % xMax;
+ uint32_t r2 = rand() % yMax;
+ Vector2 v{(float)r1, (float)r2};
+ return v;
}
float distanceSquared(Vector2 v1, Vector2 v2) {
- float xSquare = square(v1.x - v2.x);
- float ySquare = square(v1.y - v2.y);
- float result = xSquare + ySquare;
- assert(result >= 0);
- return result;
+ float xSquare = square(v1.x - v2.x);
+ float ySquare = square(v1.y - v2.y);
+ float result = xSquare + ySquare;
+ assert(result >= 0);
+ return result;
}
diff --git a/src/vertex.cpp b/src/vertex.cpp
@@ -1,21 +1,21 @@
#include "../include/vertex.hpp"
-#include <string>
#include <raylib.h>
+#include <string>
-Vertex::Vertex(Vector2 position, float drawSize)
+Vertex::Vertex(Vector2 position, float drawSize)
: position(position), drawSize(drawSize) {}
-
std::string Vertex::toString() {
- std::string result = "(x: " + std::to_string(this->position.x) + ", y: " + std::to_string(this->position.y) + ", visited: "+ std::to_string(this->visited) + ")";
- return result;
+ std::string result = "(x: " + std::to_string(this->position.x) +
+ ", y: " + std::to_string(this->position.y) +
+ ", visited: " + std::to_string(this->visited) + ")";
+ return result;
}
-
void Vertex::render() {
- if(visited) {
- DrawCircle(position.x, position.y, drawSize, WHITE);
- } else {
- DrawCircle(position.x, position.y, drawSize, DARKGRAY);
- }
+ if (visited) {
+ DrawCircle(position.x, position.y, drawSize, WHITE);
+ } else {
+ DrawCircle(position.x, position.y, drawSize, DARKGRAY);
+ }
}
diff --git a/tests/algo_test.cpp b/tests/algo_test.cpp
@@ -3,213 +3,203 @@
#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);
+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::unordered_set<std::size_t> verticesFound{0};
- std::vector<std::size_t> current {};
+ 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;
- }
+ 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();
+ return verticesFound.size() == g.getVertexCount();
}
+TEST_CASE("Large Prim algorithm", "[Large prim algo]") {
+ std::size_t edgeCount = 3000;
+ std::size_t vertCount = 1000;
-TEST_CASE( "Large Prim algorithm", "[Large prim algo]" ) {
- std::size_t edgeCount = 3000;
- std::size_t vertCount = 1000;
+ float xMax = 5120;
+ float yMax = 1440;
- 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{};
- 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));
+ do {
+ g = Graph(edgeCount, vertCount, xMax, yMax);
+ } while (!isConnected(g));
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+ for (auto edge : edges) {
+ toVisit.push(edge);
+ }
- for(auto edge: edges) {
- toVisit.push(edge);
- }
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
- while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
- }
-
- REQUIRE(visitedIndices.size() == vertCount);
+ 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;
+TEST_CASE("Medium Prim algorithm", "[Medium prim algo]") {
+ std::size_t edgeCount = 70;
+ std::size_t vertCount = 51;
- 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 {};
+ float xMax = 5120;
+ float yMax = 1440;
- do {
- g = Graph(edgeCount, vertCount, xMax,yMax);
- }
- while(!isConnected(g));
+ 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);
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
- for(auto edge: edges) {
- toVisit.push(edge);
- }
+ for (auto edge : edges) {
+ toVisit.push(edge);
+ }
- while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
- }
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
- REQUIRE(visitedIndices.size() == vertCount);
+ 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;
-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;
- 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{};
- 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));
- do {
- g = Graph(edgeCount, vertCount, xMax,yMax);
- }
- while(!isConnected(g));
+ 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);
+ }
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
- for(auto edge: edges) {
- toVisit.push(edge);
- }
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
+ REQUIRE(visitedIndices.size() == vertCount);
+ }
+ }
+}
- while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
- }
+TEST_CASE("Small Prim Test", "[Small full validation]") {
+ for (int i = 0; i < 100; ++i) {
+ std::size_t edgeCount = 10;
+ std::size_t vertCount = 5;
- REQUIRE(visitedIndices.size() == vertCount);
+ float xMax = 5120;
+ float yMax = 1440;
+ Graph g = Graph(edgeCount, vertCount, xMax, yMax);
+ do {
+ g = Graph(edgeCount, vertCount, xMax, yMax);
+ } while (!isConnected(g));
- }
- }
-}
+ std::unordered_set<std::size_t> visitedIndices{};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
-TEST_CASE( "Small Prim Test", "[Small full validation]" ) {
- for(int i = 0; i < 100; ++i) {
- std::size_t edgeCount = 10;
- std::size_t vertCount = 5;
+ for (auto edge : g.getEdgesOfVertexIdx(0))
+ toVisit.push(edge);
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
- float xMax = 5120;
- float yMax = 1440;
+ std::unordered_set<std::size_t> vBefore = visitedIndices;
- Graph g = Graph(edgeCount, vertCount, xMax,yMax);
- do {
- g = Graph(edgeCount, vertCount, xMax,yMax);
- }
- while(!isConnected(g));
-
- std::unordered_set<std::size_t> visitedIndices {};
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit {};
-
- for (auto edge : g.getEdgesOfVertexIdx(0)) toVisit.push(edge);
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
-
- std::unordered_set<std::size_t> vBefore = visitedIndices;
-
- bool havePrior = false;
- Edge prior = toVisit.top();
- std::unordered_set<std::size_t> visibleAtPrior;
-
- while (toVisit.size() != 0) {
- auto current = toVisit.top();
- if (havePrior) {
- bool wasPresent = visibleAtPrior.count(current.v1Index) > 0
- || visibleAtPrior.count(current.v2Index) > 0;
- // anytime we use the same source node two steps in a row, the second
- // weight must be smaller.
- if (wasPresent) {
- REQUIRE(current.length2 >= prior.length2);
- }
- }
-
- prior = current;
- visibleAtPrior = visitedIndices;
- havePrior = true;
- oneStepPrim(toVisit, visitedIndices, g);
- bool valid = vBefore.size() + 1 == visitedIndices.size()
- || vBefore.size() == vertCount;
- REQUIRE(valid);
- vBefore = visitedIndices;
+ bool havePrior = false;
+ Edge prior = toVisit.top();
+ std::unordered_set<std::size_t> visibleAtPrior;
+
+ while (toVisit.size() != 0) {
+ auto current = toVisit.top();
+ if (havePrior) {
+ bool wasPresent = visibleAtPrior.count(current.v1Index) > 0 ||
+ visibleAtPrior.count(current.v2Index) > 0;
+ // anytime we use the same source node two steps in a row, the second
+ // weight must be smaller.
+ if (wasPresent) {
+ REQUIRE(current.length2 >= prior.length2);
}
- REQUIRE(visitedIndices.size() == vertCount);
+ }
+
+ prior = current;
+ visibleAtPrior = visitedIndices;
+ havePrior = true;
+ oneStepPrim(toVisit, visitedIndices, g);
+ bool valid = vBefore.size() + 1 == visitedIndices.size() ||
+ vBefore.size() == vertCount;
+ REQUIRE(valid);
+ vBefore = visitedIndices;
}
+ REQUIRE(visitedIndices.size() == vertCount);
+ }
}
diff --git a/tests/graph_test.cpp b/tests/graph_test.cpp
@@ -4,124 +4,122 @@
#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);
+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);
+ 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;
+TEST_CASE("Graph gracefully handles stupid fucking inputs",
+ "[graph bad inputs]") {
+ int vertCount = 0;
+ int edgeCount = 0; // some trivial and stupid graph
- try {
- createGraph(vertCount, edgeCount);
- } catch (std::invalid_argument e) {
- error = true;
- }
- REQUIRE(!error);
+ bool error = false;
- vertCount = 0;
- edgeCount = 1; // bad
+ try {
+ createGraph(vertCount, edgeCount);
+ } catch (std::invalid_argument e) {
+ error = true;
+ }
+ REQUIRE(!error);
- error = false;
- try {
- createGraph(vertCount, edgeCount);
- } catch (std::invalid_argument e) {
- error = true;
- }
+ vertCount = 0;
+ edgeCount = 1; // bad
- REQUIRE(error);
+ 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;
+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) {
+ for (int z = 2; z < 100; ++z) {
- float xMax = 0;
- float yMax = 0;
+ float xMax = 0;
+ float yMax = 0;
- while (xMax == 0 || yMax == 0) {
- xMax = rand() % z;
- yMax = rand() % z;
- }
+ while (xMax == 0 || yMax == 0) {
+ xMax = rand() % z;
+ yMax = rand() % z;
+ }
- auto g = Graph(edgeCount,vertCount,xMax,yMax);
+ 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);
- }
+ 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);
- }
+ }
+ 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);
- }
+ 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();
+ }
+ return unique.size();
}
-TEST_CASE( "Graph vertex and edge counts", "[graph counts]" ) {
+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;
+ 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);
+ auto g = Graph(edgeCount, vertCount, xMax, yMax);
- REQUIRE(g.getVertexCount() == vertCount);
- REQUIRE(countEdges(g) == edgeCount);
- }
+ REQUIRE(g.getVertexCount() == vertCount);
+ REQUIRE(countEdges(g) == edgeCount);
}
-
+ }
}
diff --git a/tests/snapshot_shared.cpp b/tests/snapshot_shared.cpp
@@ -1,70 +1,69 @@
#include "../include/graph.hpp"
-#include <catch2/catch_test_macros.hpp>
#include "../include/prim.hpp"
+#include <catch2/catch_test_macros.hpp>
#include <queue>
#include <unordered_set>
Graph basicGraphSerialization() {
- srand(42);
- int vertCount = 10;
- int edgeCount = 10;
- float xMax = 10;
- float yMax = 10;
- auto g = Graph(edgeCount,vertCount,xMax,yMax);
- return g;
+ srand(42);
+ int vertCount = 10;
+ int edgeCount = 10;
+ float xMax = 10;
+ float yMax = 10;
+ auto g = Graph(edgeCount, vertCount, xMax, yMax);
+ return g;
}
Graph fullTraversalSerialization() {
- srand(42);
- std::size_t edgeCount = 1;
- std::size_t vertCount = 2;
+ srand(42);
+ std::size_t edgeCount = 1;
+ std::size_t vertCount = 2;
+
+ float xMax = 5120;
+ float yMax = 1440;
- 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);
- 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);
+ }
- for(auto edge: edges) {
- toVisit.push(edge);
- }
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
- while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
- }
-
- return g;
+ return g;
}
Graph fullTraversalLargerSerialization() {
- srand(42);
- std::size_t edgeCount = 25;
- std::size_t vertCount = 15;
+ srand(42);
+ std::size_t edgeCount = 25;
+ std::size_t vertCount = 15;
- float xMax = 5120;
- float yMax = 1440;
+ 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);
+ 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);
- }
+ for (auto edge : edges) {
+ toVisit.push(edge);
+ }
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
- while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
- }
-
- return g;
-}
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
+ return g;
+}
diff --git a/tests/snapshot_test.cpp b/tests/snapshot_test.cpp
@@ -1,28 +1,31 @@
#include "../include/graph.hpp"
+#include "snapshot_shared.cpp"
#include <catch2/catch_test_macros.hpp>
#include <fstream>
#include <iostream>
#include <sstream>
-#include "snapshot_shared.cpp"
std::string readFileToString(std::string filename) {
- auto in = std::ifstream ("tests/snapshot/" + filename + ".out");
- std::ostringstream sstr;
- sstr << in.rdbuf();
- return sstr.str();
+ auto in = std::ifstream("tests/snapshot/" + filename + ".out");
+ std::ostringstream sstr;
+ sstr << in.rdbuf();
+ return sstr.str();
}
-TEST_CASE( "Basic graph serialization snapshot", "[basic graph serialization snapshot]" ) {
- Graph g = basicGraphSerialization();
- REQUIRE(readFileToString("basicGraph") == g.toString());
+TEST_CASE("Basic graph serialization snapshot",
+ "[basic graph serialization snapshot]") {
+ Graph g = basicGraphSerialization();
+ REQUIRE(readFileToString("basicGraph") == g.toString());
}
-TEST_CASE( "Traversed graph serialization snapshot", "[traversed graph serialization snapshot]" ) {
- Graph g = fullTraversalSerialization();
- REQUIRE(readFileToString("traversedGraph") == g.toString());
+TEST_CASE("Traversed graph serialization snapshot",
+ "[traversed graph serialization snapshot]") {
+ Graph g = fullTraversalSerialization();
+ REQUIRE(readFileToString("traversedGraph") == g.toString());
}
-TEST_CASE( "Traversed graph serialization snapshot larger", "[traversed graph serialization snapshot larger]" ) {
- Graph g = fullTraversalLargerSerialization();
- REQUIRE(readFileToString("traversedLargerGraph") == g.toString());
+TEST_CASE("Traversed graph serialization snapshot larger",
+ "[traversed graph serialization snapshot larger]") {
+ Graph g = fullTraversalLargerSerialization();
+ REQUIRE(readFileToString("traversedLargerGraph") == g.toString());
}
diff --git a/tests/snapshot_update.cpp b/tests/snapshot_update.cpp
@@ -1,23 +1,21 @@
#include "../include/graph.hpp"
#include "snapshot_shared.cpp"
-#include <fstream>
#include <filesystem>
+#include <fstream>
void snapshotGraph(std::string testName, Graph g) {
- std::filesystem::path path{ "tests/snapshot" };
- path /= testName + ".out";
- std::filesystem::create_directories(path.parent_path());
- std::ofstream ofs(path);
- ofs << g.toString();
-
+ std::filesystem::path path{"tests/snapshot"};
+ path /= testName + ".out";
+ std::filesystem::create_directories(path.parent_path());
+ std::ofstream ofs(path);
+ ofs << g.toString();
}
int main() {
- Graph g1 = basicGraphSerialization();
- snapshotGraph("basicGraph", g1);
- Graph g2 = fullTraversalSerialization();
- snapshotGraph("traversedGraph", g2);
- Graph g3 = fullTraversalLargerSerialization();
- snapshotGraph("traversedLargerGraph", g3);
-
+ Graph g1 = basicGraphSerialization();
+ snapshotGraph("basicGraph", g1);
+ Graph g2 = fullTraversalSerialization();
+ snapshotGraph("traversedGraph", g2);
+ Graph g3 = fullTraversalLargerSerialization();
+ snapshotGraph("traversedLargerGraph", g3);
}
