blog

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

prim.py (3180B)


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