visualizations

commit e21c8d96e525812e09085f21692a3e308d016940
parent 3560585db8e6f9d6dd29753b28ff26fb1e05c9a2
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 16 Sep 2026 17:39:22 -0500

Benchmarking code, larger graph, no render

Diffstat:
A
graph/benchmarking/no_render_2_itr/bench.sh
 | 
5
+++++
A
graph/benchmarking/no_render_2_itr/prim.py
 | 
80
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 85 insertions(+), 0 deletions(-)
diff --git a/graph/benchmarking/no_render_2_itr/bench.sh b/graph/benchmarking/no_render_2_itr/bench.sh
@@ -0,0 +1,5 @@
+while [ 1 ]; do
+    /usr/bin/time -o out -f '%S,%U,%e' python3 prim.py >/dev/null 2>&1
+    cat out | tee -a v100000e1000000nosc
+    sleep 10
+done
diff --git a/graph/benchmarking/no_render_2_itr/prim.py b/graph/benchmarking/no_render_2_itr/prim.py
@@ -0,0 +1,80 @@
+import heapq
+import random
+import math
+
+VERTICES = 100000
+EDGES = 1000000
+
+white = (255, 255, 255)
+red = (255, 0, 0)
+black = (0, 0, 0)
+grey = (100,100,100)
+light_grey = (50,50,50)
+
+
+class Vertex():
+    def __init__(self, x, y):
+        self.x = x
+        self.y = y
+        self.visited = False
+
+class Edge():
+    def __init__(self, v1, v2):
+        self.v1 = v1
+        self.v2 = v2
+        self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2))
+
+    def __lt__(self,otr):
+        return self.dist < otr.dist
+
+
+graph = {}
+
+for i in range(0,VERTICES):
+    x = random.random() * 5120
+    y = random.random() * 1440
+    graph[Vertex(x,y)] = []
+
+
+edge_list = []
+for i in range(0,EDGES):
+    k1 = None
+    k2 = None
+    while k1 == k2:
+        k1 = random.choice(list(graph.keys()))
+        k2 = random.choice(list(graph.keys()))
+
+    edge = Edge(k1,k2)
+    graph[k1].append(edge)
+    graph[k2].append(edge)
+    edge_list.append(edge)
+
+
+edge_heap = []
+visited_vertices = set()
+
+mst = []
+
+start = random.choice(list(graph.keys()))
+start.visited = True
+visited_vertices.add(start)
+for edge in graph[start]:
+    heapq.heappush(edge_heap, edge)
+
+while True:
+    item = None
+    while edge_heap:
+        candidate = heapq.heappop(edge_heap)
+        if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices):
+            item = candidate
+            break
+
+    if item is None:
+        break
+
+    new_vertex = item.v2 if item.v1 in visited_vertices else item.v1
+    visited_vertices.add(new_vertex)
+    new_vertex.visited = True
+    mst.append(item)
+    for edge in graph[new_vertex]:
+        heapq.heappush(edge_heap, edge)