visualizations

commit e74e057ca3cdce2e435d25ca156e382e7212ac2c
parent 03d8d43a469e29226ae89b494a8ce23ac032afeb
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 16 Sep 2026 20:11:04 -0500

Another heap optimization

Diffstat:
A
graph/benchmarking/no_render_3_fixed_itr_fixed_check/bench.sh
 | 
5
+++++
A
graph/benchmarking/no_render_3_fixed_itr_fixed_check/out
 | 
1
+
A
graph/benchmarking/no_render_3_fixed_itr_fixed_check/prim.py
 | 
83
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
graph/benchmarking/no_render_3_fixed_itr_fixed_check/v100000e1000000nosc
 | 
6
++++++

4 files changed, 95 insertions(+), 0 deletions(-)
diff --git a/graph/benchmarking/no_render_3_fixed_itr_fixed_check/bench.sh b/graph/benchmarking/no_render_3_fixed_itr_fixed_check/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 1
+done
diff --git a/graph/benchmarking/no_render_3_fixed_itr_fixed_check/out b/graph/benchmarking/no_render_3_fixed_itr_fixed_check/out
@@ -0,0 +1 @@
+0.06,8.36,8.48
diff --git a/graph/benchmarking/no_render_3_fixed_itr_fixed_check/prim.py b/graph/benchmarking/no_render_3_fixed_itr_fixed_check/prim.py
@@ -0,0 +1,83 @@
+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 = []
+keys = list(graph.keys())
+
+for i in range(0,EDGES):
+    k1 = None
+    k2 = None
+    while k1 == k2:
+        k1 = random.choice(keys)
+        k2 = random.choice(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]:
+        if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices:
+            heapq.heappush(edge_heap, edge)
diff --git a/graph/benchmarking/no_render_3_fixed_itr_fixed_check/v100000e1000000nosc b/graph/benchmarking/no_render_3_fixed_itr_fixed_check/v100000e1000000nosc
@@ -0,0 +1,6 @@
+0.06,8.38,8.47
+0.06,8.39,8.48
+0.06,8.47,8.60
+0.07,8.52,8.63
+0.06,8.35,8.44
+0.06,8.36,8.48