blog

Personal blog
git clone git://git.laack.co/blog.git
Log | Files | Refs

prim.py (4132B)

      1 import pygame
      2 import time
      3 import heapq
      4 import random
      5 import statistics
      6 import math
      7 
      8 pygame.init()
      9 display = pygame.display.set_mode((5120,1440))
     10 
     11 fts = []
     12 first_time = []
     13 
     14 VERTICES = 2500
     15 EDGES = 25000
     16 
     17 white = (255, 255, 255)
     18 red = (255, 0, 0)
     19 black = (0, 0, 0)
     20 grey = (100,100,100)
     21 light_grey = (50,50,50)
     22 
     23 
     24 class Vertex():
     25     def __init__(self, x, y):
     26         self.x = x
     27         self.y = y
     28         self.visited = False
     29     def draw_vertex(self,display):
     30         if self.visited:
     31             pygame.draw.circle(display, white, (self.x,self.y), 5)
     32         else:
     33             pygame.draw.circle(display, grey, (self.x,self.y), 5)
     34 class Edge():
     35     def __init__(self, v1, v2):
     36         self.v1 = v1
     37         self.v2 = v2
     38         self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2))
     39     def draw_edge(self,display, c):
     40         pygame.draw.line(display, c, (self.v1.x,self.v1.y), (self.v2.x,self.v2.y), 1)
     41 
     42     def __lt__(self,otr):
     43         return self.dist < otr.dist
     44 
     45 for _ in range(0,10):
     46 
     47     graph = {}
     48 
     49     for i in range(0,VERTICES):
     50         x = random.random() * 5120
     51         y = random.random() * 1440
     52         graph[Vertex(x,y)] = []
     53 
     54 
     55     edge_list = []
     56     keys = list(graph.keys())
     57 
     58     for i in range(0,EDGES):
     59         k1 = None
     60         k2 = None
     61         while k1 == k2:
     62             k1 = random.choice(keys)
     63             k2 = random.choice(keys)
     64 
     65         edge = Edge(k1,k2)
     66         graph[k1].append(edge)
     67         graph[k2].append(edge)
     68         edge_list.append(edge)
     69 
     70 
     71     edge_heap = []
     72     visited_vertices = set()
     73 
     74 
     75     start = random.choice(keys)
     76     start.visited = True
     77     visited_vertices.add(start)
     78     for edge in graph[start]:
     79         heapq.heappush(edge_heap, edge)
     80 
     81 
     82     first = True
     83 
     84     to_draw_vert = []
     85     to_draw_edge = []
     86 
     87     while True:
     88         for event in pygame.event.get():
     89             if event.type == pygame.QUIT:
     90                 pygame.quit()
     91                 quit()
     92 
     93         if first:
     94             start = time.monotonic_ns()
     95             display.fill(black)
     96 
     97             edge_times = []
     98             vertex_times = []
     99 
    100             for edge in edge_list:
    101                 se = time.monotonic_ns()
    102                 edge.draw_edge(display, light_grey)
    103                 ee = time.monotonic_ns()
    104                 edge_times.append(ee - se)
    105 
    106             for vertex in graph:
    107                 sv = time.monotonic_ns()
    108                 vertex.draw_vertex(display)
    109                 ev = time.monotonic_ns()
    110                 vertex_times.append(ev - sv)
    111 
    112             pygame.display.update()
    113             end = time.monotonic_ns()
    114             first_time.append(end - start)
    115             first = False
    116             print("Edge time avg: " + str(sum(edge_times) / len(edge_times)))
    117             print("Vertex time avg: " + str(sum(vertex_times) / len(vertex_times)))
    118             continue
    119 
    120         item = None
    121         while edge_heap:
    122             candidate = heapq.heappop(edge_heap)
    123             if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices):
    124                 item = candidate
    125                 break
    126 
    127         if item is None:
    128             break
    129 
    130         new_vertex = item.v2 if item.v1 in visited_vertices else item.v1
    131         visited_vertices.add(new_vertex)
    132         new_vertex.visited = True
    133 
    134         to_draw_vert.append(new_vertex)
    135         to_draw_edge.append(item)
    136 
    137         for edge in graph[new_vertex]:
    138             if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices:
    139                 heapq.heappush(edge_heap, edge)
    140 
    141         start = time.monotonic_ns()
    142         for edge in to_draw_edge:
    143             edge.draw_edge(display, white)
    144         for vert in to_draw_vert:
    145             vert.draw_vertex(display)
    146         pygame.display.update()
    147         end = time.monotonic_ns()
    148 
    149         fts.append(end - start)
    150 
    151         to_draw_vert = []
    152         to_draw_edge = []
    153 
    154 
    155 
    156 
    157 print("Average frame time (ns): " + str(sum(fts) / len(fts)))
    158 print("Std. deviation frame time (ns): " + str(statistics.stdev(fts)))
    159 
    160 print("Average first frame time (ns): " + str(sum(first_time) / len(first_time)))
    161 print("Std. deviation first frame time (ns): " + str(statistics.stdev(first_time)))
    162