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)))