commit ed2744af6c27869af1aa4ed17745c10ec05d367a
parent e74e057ca3cdce2e435d25ca156e382e7212ac2c
Author: Andrew Laack <andrew@laack.co>
Date: Wed, 16 Sep 2026 23:05:59 -0500
Render with fixes
Diffstat:
3 files changed, 182 insertions(+), 79 deletions(-)
diff --git a/graph/benchmarking/render_fixed/bench.sh b/graph/benchmarking/render_fixed/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 v_10000_e_100000
+ sleep 1
+done
diff --git a/graph/benchmarking/render_fixed/prim.py b/graph/benchmarking/render_fixed/prim.py
@@ -0,0 +1,110 @@
+import pygame
+import heapq
+import random
+import math
+
+pygame.init()
+
+display = pygame.display.set_mode((5120,1440))
+
+
+VERTICES = 10000
+EDGES = 100000
+
+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
+ def draw_vertex(self,display):
+ if self.visited:
+ pygame.draw.circle(display, white, (self.x,self.y), 5)
+ else:
+ pygame.draw.circle(display, grey, (self.x,self.y), 5)
+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 draw_edge(self,display, c):
+ pygame.draw.line(display, c, (self.v1.x,self.v1.y), (self.v2.x,self.v2.y), 1)
+
+ 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:
+ for event in pygame.event.get():
+ if event.type == pygame.QUIT:
+ pygame.quit()
+ quit()
+
+
+ display.fill(black)
+ for edge in edge_list:
+ edge.draw_edge(display, light_grey)
+ for edge in mst:
+ edge.draw_edge(display, white)
+ for vertex in graph:
+ vertex.draw_vertex(display)
+
+ 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)
+ pygame.display.update()
diff --git a/graph/prim.py b/graph/prim.py
@@ -1,18 +1,15 @@
import pygame
-import os
-import time
import heapq
import random
import math
-os.environ["SDL_VIDEODRIVER"] = "dummy"
-
pygame.init()
display = pygame.display.set_mode((5120,1440))
-VERTICES = 100
-EDGES = 1000
+
+VERTICES = 1000
+EDGES = 10000
white = (255, 255, 255)
red = (255, 0, 0)
@@ -26,19 +23,16 @@ class Vertex():
self.x = x
self.y = y
self.visited = False
-
def draw_vertex(self,display):
if self.visited:
pygame.draw.circle(display, white, (self.x,self.y), 5)
else:
pygame.draw.circle(display, grey, (self.x,self.y), 5)
-
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 draw_edge(self,display, c):
pygame.draw.line(display, c, (self.v1.x,self.v1.y), (self.v2.x,self.v2.y), 1)
@@ -46,77 +40,71 @@ class Edge():
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:
- 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(keys)
- start.visited = True
- visited_vertices.add(start)
- for edge in graph[start]:
- heapq.heappush(edge_heap, edge)
-
- while True:
- for event in pygame.event.get():
- if event.type == pygame.QUIT:
- pygame.quit()
- quit()
-
- display.fill(black)
- for edge in edge_list:
- edge.draw_edge(display, light_grey)
- for edge in mst:
- edge.draw_edge(display, white)
- for vertex in graph:
- vertex.draw_vertex(display)
-
- 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:
- pygame.display.update()
+ for event in pygame.event.get():
+ if event.type == pygame.QUIT:
+ pygame.quit()
+ quit()
+
+
+ display.fill(black)
+ for edge in edge_list:
+ edge.draw_edge(display, light_grey)
+ for edge in mst:
+ edge.draw_edge(display, white)
+ for vertex in graph:
+ vertex.draw_vertex(display)
+
+ item = None
+ while edge_heap:
+ candidate = heapq.heappop(edge_heap)
+ if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices):
+ item = candidate
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)
+ if item is None:
+ break
- dir_name = "/dev/shm/bg/"
- if not os.path.exists(dir_name):
- os.mkdir(dir_name)
- pygame.image.save(display, dir_name + "out.png")
- os.system("/usr/bin/feh --no-fehbg --bg-tile '/dev/shm/bg/out.png' ")
- time.sleep(.1)
- pygame.display.update()
+ 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)
+ pygame.display.update()
