commit ae29e29635cccbd2ec4392876c3f226519a35285
parent dd6e54bcea818804df685213e9635a989a2ab3be
Author: Andrew Laack <andrew@laack.co>
Date: Wed, 16 Sep 2026 22:16:02 -0500
Performance optimizations. Replace uo_map with vector, only call line render once per edge, only fetch edges with vertices that haven't been traversed (facilitated by edge rule where v_1 is the current vertex for an edge in the edge vector)
Diffstat:
10 files changed, 78 insertions(+), 62 deletions(-)
diff --git a/Makefile b/Makefile
@@ -5,8 +5,11 @@ include config.mk
debug-build:
${DCOMMAND_P} src/main.cpp ${DCOMMAND_S} -o abg.out
-release-build:
+build:
${COMMAND_P} src/main.cpp ${COMMAND_S} -o abg.out
+
+release-build: build
+
man:
mkdir -p ${MANPREFIX}/man1
sed "s/VERSION/${VERSION}/g" < abg.1 > ${DESTDIR}${MANPREFIX}/man1/abg.1
diff --git a/include/graph.hpp b/include/graph.hpp
@@ -4,24 +4,25 @@
#include "vertex.hpp"
#include <cstddef>
#include <cstdint>
+#include <random>
#include <string>
-#include <unordered_map>
#include <vector>
class Graph {
private:
- std::unordered_map<std::size_t, std::vector<Edge>> edges{};
- std::vector<Vertex> vertices{};
+ std::vector<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);
+ uint32_t yMax, std::uint32_t seed = std::random_device{}());
std::string toString() noexcept;
void render() noexcept;
void traverseVertexIdx(std::size_t idx);
std::vector<Edge> getEdgesOfVertexIdx(std::size_t idx);
+ std::vector<Edge>* getEdgesWithUnvisitedVertices(std::size_t idx);
void setEdgeTraversed(Edge e);
Vertex getVertex(std::size_t idx);
std::size_t getVertexCount() const noexcept;
diff --git a/include/utils.hpp b/include/utils.hpp
@@ -1,8 +1,6 @@
#pragma once
-#include <cstdint>
#include <raylib.h>
float square(float x);
-Vector2 randomPosition(uint32_t xMax, uint32_t yMax);
float distanceSquared(Vector2 v1, Vector2 v2);
diff --git a/src/graph.cpp b/src/graph.cpp
@@ -5,14 +5,13 @@
#include <cstddef>
#include <cstdint>
#include <stdexcept>
-#include <unordered_map>
#include "../include/constants.hpp"
#include "../include/utils.hpp"
#include "../include/vertex.hpp"
Graph::Graph(std::size_t edgeCount, std::size_t vertCount, uint32_t xMax,
- uint32_t yMax) {
+ uint32_t yMax, std::uint32_t seed) {
if (edgeCount > 0 && vertCount <= 1) {
throw std::invalid_argument("This graph does not support self-loops.");
}
@@ -20,8 +19,17 @@ Graph::Graph(std::size_t edgeCount, std::size_t vertCount, uint32_t xMax,
throw std::invalid_argument("xMax and yMax must be > 0.");
}
+ std::mt19937 rng{seed};
+ std::uniform_int_distribution<std::size_t> pick1(0, vertCount - 1);
+
+ std::uniform_int_distribution<std::uint32_t> pick2(0, xMax - 1);
+ std::uniform_int_distribution<std::uint32_t> pick3(0, yMax - 1);
+
+ vertices.reserve(vertCount);
+ edges.resize(vertCount);
+
for (std::size_t i = 0; i < vertCount; ++i) {
- Vector2 rnd = randomPosition(xMax, yMax);
+ Vector2 rnd = Vector2{(float)pick2(rng), (float)pick3(rng)};
Vertex v{rnd, VERTEX_RENDER_SIZE};
this->vertices.push_back(v);
}
@@ -30,25 +38,27 @@ Graph::Graph(std::size_t edgeCount, std::size_t vertCount, uint32_t xMax,
std::size_t idx2 = 0;
// no self-edges
while (idx1 == idx2) {
- idx1 = std::rand() % vertCount;
- idx2 = std::rand() % vertCount;
+ idx1 = pick1(rng);
+ idx2 = pick1(rng);
}
- Edge e{
- idx1, idx2,
- distanceSquared(vertices[idx1].position, vertices[idx2].position),
- i};
- this->edges[idx1].push_back(e);
- this->edges[idx2].push_back(e);
+ double distance =
+ distanceSquared(vertices[idx1].position, vertices[idx2].position);
+
+ // this maintains the invariant that the first vertex of the edge is the
+ // current one.
+ Edge e1{idx1, idx2, distance, i};
+ Edge e2{idx2, idx1, distance, i};
+ this->edges[idx1].push_back(e1);
+ this->edges[idx2].push_back(e2);
}
}
std::string Graph::toString() noexcept {
std::string result = "edges: {";
- for (auto pair : this->edges) {
- auto key = pair.first;
- for (auto edge : edges[key]) {
+ for (auto edgesV : this->edges) {
+ for (auto edge : edgesV) {
result += edge.toString();
}
}
@@ -66,14 +76,13 @@ std::string Graph::toString() noexcept {
}
void Graph::render() noexcept {
- // yes, this will double draw because we track 0 -> 1 and 1 -> 0
- // this is faster than tracking which have and haven't been rendered though
- // with a to_string + unordered set.
-
std::vector<Edge> visited{};
- for (auto pair : this->edges) {
- auto edges = this->edges[pair.first];
- for (auto edge : edges) {
+ for (auto& edgesT : this->edges) {
+ for (auto& edge : edgesT) {
+ if (edge.v1Index < edge.v2Index) {
+ continue; // since edges are tracked twice with v1
+ // it's safe to skip one of them.
+ }
std::size_t idx1 = edge.v1Index;
std::size_t idx2 = edge.v2Index;
auto v1 = vertices[idx1].position;
@@ -86,12 +95,16 @@ void Graph::render() noexcept {
}
}
- for (auto vertex : this->vertices) {
+ for (auto& vertex : this->vertices) {
vertex.render();
}
// ensure we draw visited over unvisited for better looks
- for (auto edge : visited) {
+ for (auto& edge : visited) {
+ if (edge.v1Index < edge.v2Index) {
+ continue; // since edges are tracked twice with v1
+ // it's safe to skip one of them.
+ }
std::size_t idx1 = edge.v1Index;
std::size_t idx2 = edge.v2Index;
auto v1 = vertices[idx1].position;
@@ -104,6 +117,18 @@ void Graph::traverseVertexIdx(std::size_t idx) {
this->vertices[idx].visited = true;
}
+// we assume the current vertex is already marked as traversed so we check to
+// see if the other is here.
+std::vector<Edge>* Graph::getEdgesWithUnvisitedVertices(std::size_t idx) {
+ std::vector<Edge>* result = new std::vector<Edge>{};
+ for (auto edge : edges[idx]) {
+ if (!vertices[edge.v2Index].visited && !edge.traversed) {
+ result->push_back(edge);
+ }
+ }
+ return result;
+}
+
std::vector<Edge> Graph::getEdgesOfVertexIdx(std::size_t idx) {
return this->edges[idx];
}
diff --git a/src/prim.cpp b/src/prim.cpp
@@ -15,19 +15,22 @@ void explore(
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);
+ g.setEdgeTraversed(
+ current); // this must happen before the next line below.
+ std::vector<Edge>* edges = g.getEdgesWithUnvisitedVertices(
+ cIdx); // this gets edges with two unvisited vertices connected to
+ // cIdx.
+ for (auto& edge : *edges) {
+ toVisit.push(std::move(edge));
}
+ delete edges;
}
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;
}
diff --git a/src/utils.cpp b/src/utils.cpp
@@ -1,23 +1,12 @@
#include "../include/utils.hpp"
#include <cassert>
-#include <cstdint>
-#include <cstdlib>
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;
-}
-
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;
}
diff --git a/tests/snapshot/basicGraph.out b/tests/snapshot/basicGraph.out
@@ -1,2 +1,2 @@
-edges: {(v1: 5, v2: 7, traversed: 0)(v1: 1, v2: 0, traversed: 0)(v1: 1, v2: 6, traversed: 0)(v1: 6, v2: 4, traversed: 0)(v1: 1, v2: 6, traversed: 0)(v1: 4, v2: 1, traversed: 0)(v1: 1, v2: 0, traversed: 0)(v1: 9, v2: 4, traversed: 0)(v1: 6, v2: 4, traversed: 0)(v1: 4, v2: 1, traversed: 0)(v1: 9, v2: 3, traversed: 0)(v1: 3, v2: 7, traversed: 0)(v1: 9, v2: 3, traversed: 0)(v1: 7, v2: 9, traversed: 0)(v1: 9, v2: 4, traversed: 0)(v1: 7, v2: 2, traversed: 0)(v1: 7, v2: 2, traversed: 0)(v1: 7, v2: 9, traversed: 0)(v1: 3, v2: 7, traversed: 0)(v1: 5, v2: 7, traversed: 0)}
-vertices: {(x: 6.000000, y: 0.000000, visited: 0)(x: 1.000000, y: 1.000000, visited: 0)(x: 2.000000, y: 8.000000, visited: 0)(x: 1.000000, y: 0.000000, visited: 0)(x: 5.000000, y: 3.000000, visited: 0)(x: 4.000000, y: 3.000000, visited: 0)(x: 7.000000, y: 4.000000, visited: 0)(x: 6.000000, y: 2.000000, visited: 0)(x: 2.000000, y: 8.000000, visited: 0)(x: 8.000000, y: 9.000000, visited: 0)}-
\ No newline at end of file
+edges: {(v1: 0, v2: 2, traversed: 0)(v1: 0, v2: 5, traversed: 0)(v1: 0, v2: 4, traversed: 0)(v1: 1, v2: 9, traversed: 0)(v1: 1, v2: 6, traversed: 0)(v1: 2, v2: 0, traversed: 0)(v1: 2, v2: 5, traversed: 0)(v1: 3, v2: 6, traversed: 0)(v1: 3, v2: 6, traversed: 0)(v1: 4, v2: 0, traversed: 0)(v1: 5, v2: 0, traversed: 0)(v1: 5, v2: 2, traversed: 0)(v1: 6, v2: 1, traversed: 0)(v1: 6, v2: 3, traversed: 0)(v1: 6, v2: 3, traversed: 0)(v1: 7, v2: 9, traversed: 0)(v1: 8, v2: 9, traversed: 0)(v1: 9, v2: 7, traversed: 0)(v1: 9, v2: 8, traversed: 0)(v1: 9, v2: 1, traversed: 0)}
+vertices: {(x: 3.000000, y: 7.000000, visited: 0)(x: 9.000000, y: 1.000000, visited: 0)(x: 7.000000, y: 7.000000, visited: 0)(x: 5.000000, y: 5.000000, visited: 0)(x: 1.000000, y: 4.000000, visited: 0)(x: 1.000000, y: 0.000000, visited: 0)(x: 0.000000, y: 4.000000, visited: 0)(x: 8.000000, y: 3.000000, visited: 0)(x: 6.000000, y: 1.000000, visited: 0)(x: 7.000000, y: 6.000000, visited: 0)}+
\ No newline at end of file
diff --git a/tests/snapshot/traversedGraph.out b/tests/snapshot/traversedGraph.out
@@ -1,2 +1,2 @@
-edges: {(v1: 1, v2: 0, traversed: 1)(v1: 1, v2: 0, traversed: 1)}
-vertices: {(x: 1606.000000, y: 420.000000, visited: 1)(x: 3121.000000, y: 1161.000000, visited: 1)}-
\ No newline at end of file
+edges: {(v1: 0, v2: 1, traversed: 1)(v1: 1, v2: 0, traversed: 1)}
+vertices: {(x: 4214.000000, y: 1185.000000, visited: 1)(x: 133.000000, y: 210.000000, visited: 1)}+
\ No newline at end of file
diff --git a/tests/snapshot/traversedLargerGraph.out b/tests/snapshot/traversedLargerGraph.out
@@ -1,2 +1,2 @@
-edges: {(v1: 6, v2: 4, traversed: 1)(v1: 8, v2: 6, traversed: 0)(v1: 8, v2: 2, traversed: 1)(v1: 3, v2: 8, traversed: 1)(v1: 10, v2: 8, traversed: 0)(v1: 8, v2: 6, traversed: 0)(v1: 3, v2: 8, traversed: 1)(v1: 8, v2: 2, traversed: 1)(v1: 2, v2: 13, traversed: 1)(v1: 0, v2: 2, traversed: 0)(v1: 12, v2: 2, traversed: 1)(v1: 11, v2: 4, traversed: 1)(v1: 11, v2: 0, traversed: 1)(v1: 11, v2: 4, traversed: 1)(v1: 6, v2: 4, traversed: 1)(v1: 0, v2: 10, traversed: 0)(v1: 11, v2: 0, traversed: 1)(v1: 0, v2: 14, traversed: 1)(v1: 0, v2: 2, traversed: 0)(v1: 2, v2: 13, traversed: 1)(v1: 10, v2: 13, traversed: 1)(v1: 0, v2: 10, traversed: 0)(v1: 10, v2: 12, traversed: 0)(v1: 10, v2: 12, traversed: 0)(v1: 10, v2: 13, traversed: 1)(v1: 5, v2: 10, traversed: 1)(v1: 5, v2: 10, traversed: 1)(v1: 10, v2: 8, traversed: 0)(v1: 10, v2: 5, traversed: 1)(v1: 9, v2: 10, traversed: 1)(v1: 14, v2: 10, traversed: 0)(v1: 9, v2: 1, traversed: 1)(v1: 9, v2: 14, traversed: 1)(v1: 9, v2: 10, traversed: 1)(v1: 9, v2: 1, traversed: 1)(v1: 1, v2: 5, traversed: 0)(v1: 0, v2: 14, traversed: 1)(v1: 9, v2: 14, traversed: 1)(v1: 14, v2: 10, traversed: 0)(v1: 10, v2: 12, traversed: 0)(v1: 10, v2: 12, traversed: 0)(v1: 12, v2: 2, traversed: 1)(v1: 12, v2: 3, traversed: 0)(v1: 5, v2: 10, traversed: 1)(v1: 5, v2: 10, traversed: 1)(v1: 10, v2: 5, traversed: 1)(v1: 1, v2: 5, traversed: 0)(v1: 3, v2: 8, traversed: 1)(v1: 12, v2: 3, traversed: 0)(v1: 3, v2: 8, traversed: 1)}
-vertices: {(x: 1606.000000, y: 420.000000, visited: 1)(x: 3121.000000, y: 1161.000000, visited: 1)(x: 4452.000000, y: 838.000000, visited: 1)(x: 5101.000000, y: 60.000000, visited: 1)(x: 2775.000000, y: 383.000000, visited: 1)(x: 194.000000, y: 1223.000000, visited: 1)(x: 1317.000000, y: 1224.000000, visited: 1)(x: 1056.000000, y: 962.000000, visited: 0)(x: 4292.000000, y: 648.000000, visited: 1)(x: 858.000000, y: 459.000000, visited: 1)(x: 267.000000, y: 672.000000, visited: 1)(x: 2369.000000, y: 1353.000000, visited: 1)(x: 3407.000000, y: 779.000000, visited: 1)(x: 2289.000000, y: 1144.000000, visited: 1)(x: 1741.000000, y: 176.000000, visited: 1)}-
\ No newline at end of file
+edges: {(v1: 0, v2: 14, traversed: 1)(v1: 0, v2: 12, traversed: 0)(v1: 0, v2: 14, traversed: 1)(v1: 0, v2: 6, traversed: 1)(v1: 1, v2: 4, traversed: 0)(v1: 1, v2: 10, traversed: 1)(v1: 1, v2: 2, traversed: 0)(v1: 1, v2: 14, traversed: 1)(v1: 2, v2: 8, traversed: 0)(v1: 2, v2: 1, traversed: 0)(v1: 2, v2: 3, traversed: 1)(v1: 2, v2: 6, traversed: 1)(v1: 3, v2: 2, traversed: 1)(v1: 4, v2: 1, traversed: 0)(v1: 4, v2: 10, traversed: 0)(v1: 4, v2: 5, traversed: 1)(v1: 4, v2: 8, traversed: 1)(v1: 5, v2: 4, traversed: 1)(v1: 6, v2: 13, traversed: 0)(v1: 6, v2: 12, traversed: 1)(v1: 6, v2: 10, traversed: 0)(v1: 6, v2: 0, traversed: 1)(v1: 6, v2: 2, traversed: 1)(v1: 6, v2: 9, traversed: 0)(v1: 7, v2: 10, traversed: 1)(v1: 8, v2: 2, traversed: 0)(v1: 8, v2: 13, traversed: 1)(v1: 8, v2: 4, traversed: 1)(v1: 9, v2: 10, traversed: 1)(v1: 9, v2: 12, traversed: 0)(v1: 9, v2: 6, traversed: 0)(v1: 10, v2: 9, traversed: 1)(v1: 10, v2: 1, traversed: 1)(v1: 10, v2: 11, traversed: 1)(v1: 10, v2: 7, traversed: 1)(v1: 10, v2: 4, traversed: 0)(v1: 10, v2: 6, traversed: 0)(v1: 10, v2: 11, traversed: 1)(v1: 11, v2: 10, traversed: 1)(v1: 11, v2: 10, traversed: 1)(v1: 11, v2: 13, traversed: 1)(v1: 12, v2: 0, traversed: 0)(v1: 12, v2: 6, traversed: 1)(v1: 12, v2: 9, traversed: 0)(v1: 13, v2: 6, traversed: 0)(v1: 13, v2: 8, traversed: 1)(v1: 13, v2: 11, traversed: 1)(v1: 14, v2: 0, traversed: 1)(v1: 14, v2: 0, traversed: 1)(v1: 14, v2: 1, traversed: 1)}
+vertices: {(x: 4221.000000, y: 1241.000000, visited: 1)(x: 928.000000, y: 99.000000, visited: 1)(x: 4491.000000, y: 780.000000, visited: 1)(x: 2557.000000, y: 707.000000, visited: 1)(x: 4940.000000, y: 798.000000, visited: 1)(x: 18.000000, y: 341.000000, visited: 1)(x: 4729.000000, y: 987.000000, visited: 1)(x: 3222.000000, y: 1350.000000, visited: 1)(x: 1558.000000, y: 673.000000, visited: 1)(x: 1745.000000, y: 1343.000000, visited: 1)(x: 720.000000, y: 295.000000, visited: 1)(x: 2493.000000, y: 1277.000000, visited: 1)(x: 4510.000000, y: 76.000000, visited: 1)(x: 2319.000000, y: 841.000000, visited: 1)(x: 2431.000000, y: 765.000000, visited: 1)}+
\ No newline at end of file
diff --git a/tests/snapshot_shared.cpp b/tests/snapshot_shared.cpp
@@ -6,24 +6,22 @@
#include "../include/prim.hpp"
Graph basicGraphSerialization() {
- srand(42);
int vertCount = 10;
int edgeCount = 10;
float xMax = 10;
float yMax = 10;
- auto g = Graph(edgeCount, vertCount, xMax, yMax);
+ auto g = Graph(edgeCount, vertCount, xMax, yMax, 42);
return g;
}
Graph fullTraversalSerialization() {
- srand(42);
std::size_t edgeCount = 1;
std::size_t vertCount = 2;
float xMax = 5120;
float yMax = 1440;
- Graph g = Graph(edgeCount, vertCount, xMax, yMax);
+ Graph g = Graph(edgeCount, vertCount, xMax, yMax, 52);
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);
@@ -43,14 +41,13 @@ Graph fullTraversalSerialization() {
}
Graph fullTraversalLargerSerialization() {
- srand(42);
std::size_t edgeCount = 25;
std::size_t vertCount = 15;
float xMax = 5120;
float yMax = 1440;
- Graph g = Graph(edgeCount, vertCount, xMax, yMax);
+ Graph g = Graph(edgeCount, vertCount, xMax, yMax, 61);
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);
