commit 8902403ef922e56940d622e0d146739edb339a85
parent edc5f44246df080f7ded88bf50bb9e15ecf1ea5e
Author: Andrew Laack <andrew@laack.co>
Date: Mon, 14 Sep 2026 21:22:00 -0500
Refactored c++ approach with raylib
Diffstat:
27 files changed, 602 insertions(+), 140 deletions(-)
diff --git a/background/Makefile b/background/Makefile
@@ -1,4 +1,2 @@
-clean:
- rm a.out
build:
- g++ main.c draw.c vert.c edge.c util.c -lraylib
+ g++ main.cpp graph.cpp edge.cpp utils.cpp vertex.cpp -lraylib
diff --git a/background/draw.c b/background/draw.c
@@ -1,31 +0,0 @@
-#include "raylib.h"
-#include "edge.h"
-#include <stdio.h>
-
-#define VERTEX_SIZE 5
-
-void draw_edges(Edge* edges, int length) {
- for(int i = 0; i < length; ++i) {
- Edge e = edges[i];
-
- Vertex v1 = *e.v1;
- Vertex v2 = *e.v2;
-
- // TODO: Convert this to a function.
- Vector2 v1_p;
- v1_p.x = v1.x;
- v1_p.y = v1.y;
- Vector2 v2_p;
- v2_p.x = (float)v2.x;
- v2_p.y = (float)v2.y;
- DrawLineEx(v1_p, v2_p, 1,DARKGRAY);
- }
-}
-
-void draw_vertices(Vertex* vertices, int length) {
- for(int i = 0; i < length; ++i) {
- Vertex v = vertices[i];
- DrawCircle(v.x,v.y,VERTEX_SIZE, WHITE);
- }
-}
-
diff --git a/background/draw.h b/background/draw.h
@@ -1,4 +0,0 @@
-#include "edge.h"
-
-void draw_vertices(Vertex* vertices, int length);
-void draw_edges(Edge* edges, int length);
diff --git a/background/edge.c b/background/edge.c
@@ -1,27 +0,0 @@
-#include "edge.h"
-#include "util.h"
-#include <stdlib.h>
-#include <stdio.h>
-
-void print_edge(Edge *e) {
- printf("v1.x = %i, v1.y = %i\nv2.x = %i, v2.y = %i", e->v1->x, e->v1->y, e->v2->x, e->v2->y);
-}
-
-Edge gen_edge(int idx1, int idx2, Vertex* vertices) {
- Edge e;
- e.v1 = &vertices[idx1];
- e.v2 = &vertices[idx2];
- return e;
-}
-
-Edge* gen_edges(Vertex* vertices, int vtCount, int edgeCount) {
- Edge* edges = (Edge*)malloc(sizeof(Edge) * edgeCount);
- for(int i = 0; i < edgeCount; ++i) {
- int idx1 = choose_random(vtCount);
- int idx2 = choose_random(vtCount);
- Edge e = gen_edge(idx1,idx2, vertices);
- edges[i] = e;
- }
- return edges;
-
-}
diff --git a/background/edge.cpp b/background/edge.cpp
@@ -0,0 +1,16 @@
+#include "edge.hpp"
+
+Edge::Edge(std::size_t v1, std::size_t v2, float length2)
+ : v1Index(v1), v2Index(v2), length2(length2) {}
+
+std::string Edge::toString() {
+ return "(" + std::to_string(this->v1Index) + ", " + std::to_string(this->v2Index) + ")";
+}
+
+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/background/edge.h b/background/edge.h
@@ -1,11 +0,0 @@
-#include "vert.h"
-
-typedef struct Edge {
- Vertex* v1;
- Vertex* v2;
-
-} Edge;
-
-Edge gen_edge(int idx1, int idx2, Vertex* vertices);
-Edge* gen_edges(Vertex* vertices, int vtCount, int edgeCount);
-void print_edge(Edge* e);
diff --git a/background/edge.hpp b/background/edge.hpp
@@ -0,0 +1,17 @@
+#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);
+ std::size_t v1Index;
+ std::size_t v2Index;
+ float length2;
+ bool traversed = false;
+ std::string toString();
+ bool operator<(const Edge& other) const;
+ bool operator>(const Edge& other) const;
+};
diff --git a/background/graph.cpp b/background/graph.cpp
@@ -0,0 +1,119 @@
+#include "graph.hpp"
+#include "vertex.hpp"
+#include "utils.hpp"
+#include <cstddef>
+#include <raylib.h>
+#include <iostream>
+
+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};
+ 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)};
+ this->edges[idx1].push_back(e);
+ this->edges[idx2].push_back(e);
+ }
+}
+
+std::string Graph::toString() {
+
+ std::string result = "edges: {";
+
+ for(auto pair: this->edges) {
+ auto key = pair.first;
+ for(auto edge: edges[key]) {
+ result += edge.toString();
+ }
+ }
+
+ result += "}";
+
+ result += "\nvertices: {";
+
+ for(auto vertex: this->vertices) {
+ result += vertex.toString();
+ }
+
+ result += "}";
+ return result;
+}
+
+
+void Graph::render() {
+ // 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, 1,DARKERGRAY);
+ }
+ }
+ }
+
+ // 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, 1, WHITE);
+ }
+
+ for(auto vertex: this->vertices) {
+ vertex.render();
+ }
+}
+
+void Graph::traverseVertexIdx(std::size_t idx) {
+ this->vertices[idx].visited = true;
+}
+
+std::vector<Edge> Graph::getEdgesOfVertexIdx(std::size_t idx) {
+ return this->edges[idx];
+}
+
+void Graph::setEdgeTraversed(Edge e) {
+
+ std::size_t source = e.v1Index;
+ std::size_t destination = e.v2Index;
+
+ if(source == destination) {
+ return;
+ }
+
+ auto& cEdges = edges[source];
+
+ for(auto& edge : cEdges) {
+ if(edge.v2Index == destination || edge.v1Index == destination) {
+ edge.traversed = true;
+ }
+ }
+
+ auto& oEdges = edges[destination];
+
+ for(auto& edge : oEdges) {
+ if(edge.v2Index == source || edge.v1Index == source) {
+ edge.traversed = true;
+ }
+ }
+
+}
diff --git a/background/graph.hpp b/background/graph.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+#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, float xMax, float yMax);
+ std::string toString();
+ void render();
+ void traverseVertexIdx(std::size_t idx);
+ std::vector<Edge> getEdgesOfVertexIdx(std::size_t idx);
+ void setEdgeTraversed(Edge e);
+};
diff --git a/background/main.c b/background/main.c
@@ -1,30 +0,0 @@
-#include "raylib.h"
-#include <stdlib.h>
-#include <time.h>
-#include "draw.h"
-
-#define VERTICES 100
-#define EDGES 1000
-
-int main(void)
-{
-
- srand(time(0));
- InitWindow(5120, 1440, "Raylib background animation window");
-
- while (!WindowShouldClose())
- {
- Vertex* vertices = gen_vertices(VERTICES);
- Edge* edges = gen_edges(vertices, VERTICES, EDGES);
- BeginDrawing();
- ClearBackground(BLACK);
- draw_edges(edges,EDGES);
- draw_vertices(vertices,VERTICES);
- EndDrawing();
- free(vertices);
- free(edges);
- }
-
- CloseWindow();
- return 0;
-}
diff --git a/background/main.cpp b/background/main.cpp
@@ -0,0 +1,87 @@
+#include "graph.hpp"
+#include <unistd.h>
+#include <raylib.h>
+#include <ctime>
+#include <queue>
+#include <unordered_set>
+
+int main() {
+ srand(clock());
+
+ std::size_t edgeCount = 2000;
+ std::size_t vertCount = 200;
+
+ float xMax = 5120;
+ float yMax = 1440;
+
+
+ InitWindow(xMax, yMax, "Raylib animation window");
+
+ while (!WindowShouldClose()) {
+
+ 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 (!WindowShouldClose()) {
+
+ BeginDrawing();
+ ClearBackground(BLACK);
+ g.render();
+ EndDrawing();
+
+ 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);
+ g.traverseVertexIdx(cIdx);
+ // TODO: Make this a function.
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(cIdx);
+ for(auto edge: edges) {
+ toVisit.push(edge);
+ }
+ g.setEdgeTraversed(current);
+
+ } else if(visitedIndices.find(current.v1Index) == visitedIndices.end()) {
+ auto cIdx = current.v1Index;
+ visitedIndices.insert(current.v1Index);
+ g.traverseVertexIdx(cIdx);
+ // TODO: Make this a function.
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(cIdx);
+ for(auto edge: edges) {
+ toVisit.push(edge);
+ }
+ g.setEdgeTraversed(current);
+ } else {
+ found = false;
+ }
+
+ }
+
+ }
+
+ }
+
+}
diff --git a/background/old/Makefile b/background/old/Makefile
@@ -0,0 +1,4 @@
+clean:
+ rm a.out
+build:
+ g++ main.cpp draw.c vert.c edge.cpp util.c -lraylib
diff --git a/background/old/draw.c b/background/old/draw.c
@@ -0,0 +1,38 @@
+#include "raylib.h"
+#include "edge.hpp"
+
+#define VERTEX_SIZE 5
+
+void draw_edges(Edge* edges, int length) {
+ for(int i = 0; i < length; ++i) {
+ Edge e = edges[i];
+
+ Vertex v1 = *e.v1;
+ Vertex v2 = *e.v2;
+
+ // TODO: Convert this to a function.
+ Vector2 v1_p;
+ v1_p.x = v1.x;
+ v1_p.y = v1.y;
+ Vector2 v2_p;
+ v2_p.x = (float)v2.x;
+ v2_p.y = (float)v2.y;
+ if(e.traversed == true) {
+ DrawLineEx(v1_p, v2_p, 1,WHITE);
+ } else {
+ DrawLineEx(v1_p, v2_p, 1,DARKGRAY);
+ }
+ }
+}
+
+void draw_vertices(Vertex* vertices, int length) {
+ for(int i = 0; i < length; ++i) {
+ Vertex v = vertices[i];
+ if(v.visited) {
+ DrawCircle(v.x,v.y,VERTEX_SIZE, WHITE);
+ } else {
+ DrawCircle(v.x,v.y,VERTEX_SIZE, GRAY);
+ }
+ }
+}
+
diff --git a/background/old/draw.h b/background/old/draw.h
@@ -0,0 +1,4 @@
+#include "edge.hpp"
+
+void draw_vertices(Vertex* vertices, int length);
+void draw_edges(Edge* edges, int length);
diff --git a/background/old/edge.cpp b/background/old/edge.cpp
@@ -0,0 +1,28 @@
+#include "edge.hpp"
+#include "util.h"
+#include <stdlib.h>
+#include <stdio.h>
+
+void print_edge(Edge *e) {
+ printf("v1.x = %i, v1.y = %i\nv2.x = %i, v2.y = %i", e->v1->x, e->v1->y, e->v2->x, e->v2->y);
+}
+
+Edge gen_edge(int idx1, int idx2, Vertex* vertices) {
+ Edge e;
+ e.v1 = &vertices[idx1];
+ e.v2 = &vertices[idx2];
+ e.weight = vert_dist(e.v1, e.v2);
+ return e;
+}
+
+Edge* gen_edges(Vertex* vertices, int vtCount, int edgeCount) {
+ Edge* edges = (Edge*)malloc(sizeof(Edge) * edgeCount);
+ for(int i = 0; i < edgeCount; ++i) {
+ int idx1 = choose_random(vtCount);
+ int idx2 = choose_random(vtCount);
+ Edge e = gen_edge(idx1,idx2, vertices);
+ edges[i] = e;
+ }
+ return edges;
+
+}
diff --git a/background/old/edge.hpp b/background/old/edge.hpp
@@ -0,0 +1,21 @@
+#ifndef EDGE
+#define EDGE
+
+#include "vert.h"
+
+typedef struct Edge {
+ Vertex* v1;
+ Vertex* v2;
+ float weight;
+ bool traversed;
+ bool operator<(const Edge& other) const {
+ return weight < other.weight;
+ }
+
+} Edge;
+
+Edge gen_edge(int idx1, int idx2, Vertex* vertices);
+Edge* gen_edges(Vertex* vertices, int vtCount, int edgeCount);
+void print_edge(Edge* e);
+
+#endif
diff --git a/background/old/main.cpp b/background/old/main.cpp
@@ -0,0 +1,135 @@
+#include <algorithm>
+#include <thread>
+#include <chrono>
+#include <ctime>
+#include <time.h>
+#include <iostream>
+#include <cstdint>
+#include <raylib.h>
+#include <stdlib.h>
+#include <time.h>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+#include "draw.h"
+
+#define VERTICES 100
+#define EDGES 1000
+
+std::unordered_map<std::uintptr_t, std::vector<Edge*>> getMap(Vertex* verts, Edge* edges, int edgeCount, int vertCount) {
+
+ std::unordered_map<std::uintptr_t, std::vector<Edge*>> res {};
+
+ for(int i = 0; i < vertCount; ++i) {
+ Vertex* vert = &verts[i];
+ res[std::uintptr_t(vert)] = std::vector<Edge*>{};
+ }
+
+
+ for (int i = 0; i < edgeCount; ++i) {
+ Edge& e = edges[i];
+ res[std::uintptr_t(e.v1)].push_back(&e);
+ res[std::uintptr_t(e.v2)].push_back(&e);
+ }
+
+ return res;
+}
+
+void visit_vertex(
+ Vertex* v,
+ const std::vector<Edge*>& edges,
+ std::vector<Edge*>& visitHeap,
+ std::unordered_set<std::uintptr_t>& visited
+) {
+
+ v->visited = true;
+
+ visited.insert(uintptr_t(v));
+ for(Edge* edge: edges) {
+ visitHeap.push_back(edge);
+
+ auto cmp = [](Edge* a, Edge* b) {
+ // this makes it a min heap bc <
+ return a->weight < b->weight;
+ };
+
+ std::push_heap(visitHeap.begin(), visitHeap.end(), cmp);
+ }
+ return;
+}
+
+// create vertices
+// create weighted edge list
+// associated edges with both vertices
+ // undirected graph
+// start with arbitrary element
+ // push edges into an array
+ // search array for smallest element
+ // explore
+int main(void)
+{
+
+ srand(time(0));
+ InitWindow(5120, 1440, "Raylib background animation window");
+
+ while (!WindowShouldClose())
+ {
+ Vertex* vertices = gen_vertices(VERTICES);
+ Edge* edges = gen_edges(vertices, VERTICES, EDGES);
+ auto mp = getMap(vertices,edges,EDGES,VERTICES);
+
+ std::unordered_set<std::uintptr_t> visited {};
+ std::vector<Edge*> visitHeap;
+
+ visit_vertex(&vertices[0], mp[uintptr_t(&vertices[0])], visitHeap, visited);
+ bool done = false;
+
+ while(!done) {
+
+ BeginDrawing();
+ ClearBackground(BLACK);
+ draw_edges(edges,EDGES);
+ draw_vertices(vertices,VERTICES);
+ EndDrawing();
+ std::this_thread::sleep_for(std::chrono::seconds(1));
+
+ std::vector<Edge*> currentHeap = visitHeap;
+ visitHeap.clear();
+
+ auto cmp = [](Edge* a, Edge* b) {
+ return a->weight < b->weight;
+ };
+ std::pop_heap(visitHeap.begin(), visitHeap.end(), cmp);
+
+ Edge* vis = visitHeap.back();
+ visitHeap.pop_back();
+
+ if(visited.find(uintptr_t(vis->v1)) == visited.end() && visited.find(uintptr_t(vis->v2)) == visited.end()) {
+ continue;
+ }
+
+ if(visited.find(uintptr_t(vis->v1)) != visited.end() && visited.find(uintptr_t(vis->v2)) != visited.end()) {
+ continue;
+ }
+
+
+ Vertex* visiting = nullptr;
+
+ if(visited.find(uintptr_t(vis->v1)) == visited.end()){
+ visited.insert(uintptr_t(vis->v1));
+ visiting = vis->v1;
+ } else {
+ visited.insert(uintptr_t(vis->v2));
+ visiting = vis->v2;
+ }
+ vis->traversed = true;
+ visit_vertex(visiting, mp[uintptr_t(visiting)], visitHeap, visited);
+ }
+
+ free(vertices);
+ free(edges);
+ }
+
+ CloseWindow();
+ return 0;
+}
diff --git a/background/util.c b/background/old/util.c
diff --git a/background/util.h b/background/old/util.h
diff --git a/background/old/vert.c b/background/old/vert.c
@@ -0,0 +1,33 @@
+#include "vert.h"
+#include <math.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+Vertex gen_vertex() {
+ int y = rand() % 1440;
+ int x = rand() % 5120;
+ Vertex v;
+ v.x = x;
+ v.y = y;
+ return v;
+}
+
+void print_vertex(Vertex* v) {
+ printf("x: %i, y: %i", v->x, v->y);
+}
+
+Vertex* gen_vertices(int vtCount) {
+ Vertex* vertices = (Vertex*)malloc(sizeof(Vertex) * vtCount);
+ for(int i = 0; i < vtCount; ++i) {
+ Vertex v = gen_vertex();
+ vertices[i] = v;
+ }
+ return vertices;
+
+}
+
+float vert_dist(Vertex* v1, Vertex* v2) {
+ float dx = (float)v1->x - (float)v2->x;
+ float dy = (float)v1->y - (float)v2->y;
+ return sqrt(dx*dx + dy*dy);
+}
diff --git a/background/old/vert.h b/background/old/vert.h
@@ -0,0 +1,14 @@
+#ifndef VERT
+#define VERT
+
+typedef struct Vert {
+ int x;
+ int y;
+ bool visited;
+
+} Vertex;
+Vertex gen_vertex();
+Vertex* gen_vertices(int vtCount);
+Vertex* choose_random(Vertex* vertices, int length);
+float vert_dist(Vertex* v1, Vertex* v2);
+#endif
diff --git a/background/utils.cpp b/background/utils.cpp
@@ -0,0 +1,20 @@
+#include "utils.hpp"
+#include <cstdlib>
+
+float square(float x) {
+ return x * 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};
+ return v;
+}
+
+float distanceSquared(Vector2 v1, Vector2 v2) {
+ float xSquare = square(v1.x - v2.x);
+ float ySquare = square(v1.y - v2.y);
+ return xSquare + ySquare;
+}
diff --git a/background/utils.hpp b/background/utils.hpp
@@ -0,0 +1,9 @@
+#pragma once
+
+#include <raylib.h>
+
+#define DARKERGRAY CLITERAL(Color){ 40, 40, 40, 255 }
+
+float square(float x);
+Vector2 randomPosition(float xMax, float yMax);
+float distanceSquared(Vector2 v1, Vector2 v2);
diff --git a/background/vert.c b/background/vert.c
@@ -1,26 +0,0 @@
-#include "vert.h"
-#include <stdlib.h>
-#include <stdio.h>
-
-Vertex gen_vertex() {
- int y = rand() % 1440;
- int x = rand() % 5120;
- Vertex v;
- v.x = x;
- v.y = y;
- return v;
-}
-
-void print_vertex(Vertex* v) {
- printf("x: %i, y: %i", v->x, v->y);
-}
-
-Vertex* gen_vertices(int vtCount) {
- Vertex* vertices = (Vertex*)malloc(sizeof(Vertex) * vtCount);
- for(int i = 0; i < vtCount; ++i) {
- Vertex v = gen_vertex();
- vertices[i] = v;
- }
- return vertices;
-
-}
diff --git a/background/vert.h b/background/vert.h
@@ -1,8 +0,0 @@
-typedef struct Vert {
- int x;
- int y;
-
-} Vertex;
-Vertex gen_vertex();
-Vertex* gen_vertices(int vtCount);
-Vertex* choose_random(Vertex* vertices, int length);
diff --git a/background/vertex.cpp b/background/vertex.cpp
@@ -0,0 +1,21 @@
+#include "vertex.hpp"
+#include <string>
+#include <raylib.h>
+
+Vertex::Vertex(Vector2 position, float drawSize)
+ : position(position), drawSize(drawSize) {}
+
+
+std::string Vertex::toString() {
+ std::string result = "(" + std::to_string(this->position.x) + ", " + std::to_string(this->position.y) + ")";
+ return result;
+}
+
+
+void Vertex::render() {
+ if(visited) {
+ DrawCircle(position.x, position.y, drawSize, WHITE);
+ } else {
+ DrawCircle(position.x, position.y, drawSize, DARKGRAY);
+ }
+}
diff --git a/background/vertex.hpp b/background/vertex.hpp
@@ -0,0 +1,14 @@
+#pragma once
+
+#include <raylib.h>
+#include <string>
+
+class Vertex {
+ public:
+ Vertex(Vector2 position, float drawSize);
+ Vector2 position;
+ float drawSize;
+ std::string toString();
+ void render();
+ bool visited = false;
+};
