commit 06a1d1f835eb30e1b93036e72264b0e902dc3153
parent 75cb1a79c75c998f73a2bb8e0fac226aeddd374d
Author: Andrew Laack <andrew@laack.co>
Date: Thu, 17 Sep 2026 13:30:20 -0500
Benchmark with smarter pushing
Diffstat:
7 files changed, 54 insertions(+), 17 deletions(-)
diff --git a/benchmarking/bench.sh b/benchmarking/bench.sh
@@ -1,5 +1,5 @@
while [ 1 ]; do
- /usr/bin/time -o out -f '%S,%U,%e' ./abg.out -s 0 --edges 2000000 --vertices 200000 >/dev/null 2>&1
- cat out | tee -a benchmarking/final_no_render_v_200000_e_2000000_s_0/out1.csv
+ /usr/bin/time -o out -f '%S,%U,%e' ./abg.out -s 0 --edges 100000 --vertices 10000 >/dev/null 2>&1
+ cat out | tee -a benchmarking/render_smart_push_v_10000_e_100000_s_0/out.csv
sleep 1
done
diff --git a/benchmarking/final_min_no_render_v_200000_e_2000000_s_0/out.csv b/benchmarking/final_min_no_render_v_200000_e_2000000_s_0/out.csv
@@ -0,0 +1,20 @@
+0.06,0.97,1.04
+0.06,0.93,1.00
+0.07,0.95,1.03
+0.09,0.92,1.02
+0.08,0.94,1.02
+0.08,0.94,1.03
+0.08,0.94,1.03
+0.06,0.95,1.02
+0.08,0.93,1.02
+0.07,0.95,1.02
+0.07,0.95,1.03
+0.07,0.95,1.03
+0.08,0.95,1.04
+0.09,0.93,1.03
+0.07,0.98,1.06
+0.07,0.95,1.04
+0.08,0.94,1.03
+0.07,0.96,1.04
+0.07,0.95,1.04
+0.07,1.00,1.08
diff --git a/include/prim.hpp b/include/prim.hpp
@@ -10,7 +10,7 @@
void explore(
std::size_t cIdx,
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> &toVisit,
- Edge ¤t, Graph &g);
+ Edge ¤t, Graph &g, std::vector<double>& minVertWeight);
void oneStepPrim(
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> &toVisit,
- std::unordered_set<std::size_t> &visitedIndices, Graph &g);
+ std::unordered_set<std::size_t> &visitedIndices, Graph &g, std::vector<double>& minVertWeight);
diff --git a/src/main.cpp b/src/main.cpp
@@ -91,13 +91,17 @@ int main(int argc, char** argv) {
while (!WindowShouldClose()) {
Graph g = Graph(edgeCount, vertexCount, xMax, yMax);
+ std::vector<double> minEdgeToVertex(vertexCount, -1);
+
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);
@@ -123,7 +127,7 @@ int main(int argc, char** argv) {
usleep((int)(sleepTime * 1000000));
- oneStepPrim(toVisit, visitedIndices, g);
+ oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
}
UnloadRenderTexture(blankGraph);
}
diff --git a/src/prim.cpp b/src/prim.cpp
@@ -11,7 +11,8 @@
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) {
+ Edge& current, Graph& g, std::unordered_set<std::size_t>& visitedIndices,
+ std::vector<double>& minVertWeight) {
visitedIndices.insert(cIdx);
g.traverseVertexIdx(cIdx);
g.setEdgeTraversed(
@@ -20,14 +21,19 @@ void explore(
cIdx); // this gets edges with two unvisited vertices connected to
// cIdx.
for (auto& edge : *edges) {
- toVisit.push(std::move(edge));
+ if (edge.length2 < minVertWeight[edge.v2Index] ||
+ minVertWeight[edge.v2Index] == -1) {
+ toVisit.push(std::move(edge));
+ minVertWeight[edge.v2Index] = edge.length2;
+ }
}
delete edges;
}
void oneStepPrim(
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
- std::unordered_set<std::size_t>& visitedIndices, Graph& g) {
+ std::unordered_set<std::size_t>& visitedIndices, Graph& g,
+ std::vector<double>& minVertWeight) {
bool found = false;
if (toVisit.size() == 0) {
@@ -44,12 +50,12 @@ void oneStepPrim(
if (visitedIndices.find(current.v2Index) == visitedIndices.end()) {
auto cIdx = current.v2Index;
- explore(cIdx, toVisit, current, g, visitedIndices);
+ explore(cIdx, toVisit, current, g, visitedIndices, minVertWeight);
} else if (visitedIndices.find(current.v1Index) ==
visitedIndices.end()) {
auto cIdx = current.v1Index;
- explore(cIdx, toVisit, current, g, visitedIndices);
+ explore(cIdx, toVisit, current, g, visitedIndices, minVertWeight);
} else {
found = false;
}
diff --git a/tests/algo_test.cpp b/tests/algo_test.cpp
@@ -14,6 +14,7 @@ TEST_CASE("Small Prim algorithm", "[small prim algo]") {
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);
+ std::vector<double> minEdgeToVertex(vertCount, -1);
for (auto edge : edges) {
toVisit.push(edge);
@@ -23,7 +24,7 @@ TEST_CASE("Small Prim algorithm", "[small prim algo]") {
visitedIndices.insert(0);
while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
+ oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
}
// this will be true bc 2 vertices 1 edge...
// our graph may have multi-edges.
@@ -65,6 +66,7 @@ TEST_CASE("Large Prim algorithm", "[Large prim algo]") {
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<double> minEdgeToVertex(vertCount, -1);
do {
g = Graph(edgeCount, vertCount, xMax, yMax);
@@ -80,7 +82,7 @@ TEST_CASE("Large Prim algorithm", "[Large prim algo]") {
}
while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
+ oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
}
REQUIRE(visitedIndices.size() == vertCount);
@@ -96,6 +98,7 @@ TEST_CASE("Medium Prim algorithm", "[Medium prim algo]") {
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<double> minEdgeToVertex(vertCount, -1);
do {
g = Graph(edgeCount, vertCount, xMax, yMax);
@@ -111,7 +114,7 @@ TEST_CASE("Medium Prim algorithm", "[Medium prim algo]") {
}
while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
+ oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
}
REQUIRE(visitedIndices.size() == vertCount);
@@ -126,6 +129,7 @@ TEST_CASE("Staircase Prim algorithm", "[Staircase prim algo]") {
float xMax = 5120;
float yMax = 1440;
+ std::vector<double> minEdgeToVertex(vertCount, -1);
Graph g = Graph(edgeCount, vertCount, xMax, yMax);
std::unordered_set<std::size_t> visitedIndices{};
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>
@@ -143,7 +147,7 @@ TEST_CASE("Staircase Prim algorithm", "[Staircase prim algo]") {
visitedIndices.insert(0);
while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
+ oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
}
REQUIRE(visitedIndices.size() == vertCount);
@@ -177,6 +181,7 @@ TEST_CASE("Small Prim Test", "[Small full validation]") {
bool havePrior = false;
Edge prior = toVisit.top();
std::unordered_set<std::size_t> visibleAtPrior;
+ std::vector<double> minEdgeToVertex(vertCount, -1);
while (toVisit.size() != 0) {
auto current = toVisit.top();
@@ -193,7 +198,7 @@ TEST_CASE("Small Prim Test", "[Small full validation]") {
prior = current;
visibleAtPrior = visitedIndices;
havePrior = true;
- oneStepPrim(toVisit, visitedIndices, g);
+ oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
bool valid = vBefore.size() + 1 == visitedIndices.size() ||
vBefore.size() == vertCount;
REQUIRE(valid);
diff --git a/tests/snapshot_shared.cpp b/tests/snapshot_shared.cpp
@@ -25,6 +25,7 @@ Graph fullTraversalSerialization() {
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);
+ std::vector<double> minEdgeToVertex(vertCount, -1);
for (auto edge : edges) {
toVisit.push(edge);
@@ -34,7 +35,7 @@ Graph fullTraversalSerialization() {
visitedIndices.insert(0);
while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
+ oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
}
return g;
@@ -51,6 +52,7 @@ Graph fullTraversalLargerSerialization() {
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);
+ std::vector<double> minEdgeToVertex(vertCount, -1);
for (auto edge : edges) {
toVisit.push(edge);
@@ -60,7 +62,7 @@ Graph fullTraversalLargerSerialization() {
visitedIndices.insert(0);
while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
+ oneStepPrim(toVisit, visitedIndices, g, minEdgeToVertex);
}
return g;
