blog

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

prim-rlib.py (2939B)

      1 import pyray as pr
      2 import heapq
      3 import random
      4 import math
      5 import time
      6 
      7 VERTICES = 100000
      8 EDGES = 1000000
      9 RADIUS = 5
     10 
     11 pr.init_window(5120,1440, "prim")
     12 
     13 class Vertex():
     14     def __init__(self, x, y):
     15         self.x = x
     16         self.y = y
     17         self.visited = False
     18     def draw_vertex(self):
     19         if self.visited:
     20             pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.WHITE)
     21         else:
     22             pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.GRAY)
     23 class Edge():
     24     def __init__(self, v1, v2):
     25         self.v1 = v1
     26         self.v2 = v2
     27         self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2))
     28     def draw_edge(self, c):
     29         pr.draw_line(int(self.v1.x), int(self.v1.y), int(self.v2.x), int(self.v2.y), c)
     30 
     31     def __lt__(self,otr):
     32         return self.dist < otr.dist
     33 
     34 
     35 graph = {}
     36 
     37 for i in range(0,VERTICES):
     38     x = random.random() * 5120
     39     y = random.random() * 1440
     40     graph[Vertex(x,y)] = []
     41 
     42 
     43 edge_list = []
     44 keys = list(graph.keys())
     45 
     46 for i in range(0,EDGES):
     47     k1 = None
     48     k2 = None
     49     while k1 == k2:
     50         k1 = random.choice(keys)
     51         k2 = random.choice(keys)
     52 
     53     edge = Edge(k1,k2)
     54     graph[k1].append(edge)
     55     graph[k2].append(edge)
     56     edge_list.append(edge)
     57 
     58 
     59 edge_heap = []
     60 visited_vertices = set()
     61 
     62 
     63 start = random.choice(keys)
     64 start.visited = True
     65 visited_vertices.add(start)
     66 for edge in graph[start]:
     67     heapq.heappush(edge_heap, edge)
     68 
     69 
     70 first = True
     71 
     72 to_draw_vert = []
     73 to_draw_edge = []
     74 
     75 texture = pr.load_render_texture(5120,1440)
     76 
     77 while True:
     78     st = time.monotonic()
     79 
     80     pr.begin_texture_mode(texture)
     81 
     82     if first:
     83         pr.clear_background(pr.BLACK)
     84 
     85         for edge in edge_list:
     86             edge.draw_edge(pr.DARKGRAY)
     87         first = False
     88 
     89         for vertex in graph:
     90             vertex.draw_vertex()
     91 
     92     for edge in to_draw_edge:
     93         edge.draw_edge(pr.WHITE)
     94     for vert in to_draw_vert:
     95         vert.draw_vertex()
     96 
     97     to_draw_vert = []
     98     to_draw_edge = []
     99 
    100 
    101     item = None
    102     while edge_heap:
    103         candidate = heapq.heappop(edge_heap)
    104         if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices):
    105             item = candidate
    106             break
    107 
    108     if item is None:
    109         break
    110 
    111     new_vertex = item.v2 if item.v1 in visited_vertices else item.v1
    112     visited_vertices.add(new_vertex)
    113     new_vertex.visited = True
    114 
    115     to_draw_vert.append(new_vertex)
    116     to_draw_edge.append(item)
    117 
    118     for edge in graph[new_vertex]:
    119         if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices:
    120             heapq.heappush(edge_heap, edge)
    121 
    122     pr.end_texture_mode()
    123 
    124     source_rec = pr.Rectangle(0, 0, 5120, 1440)
    125     dest_rec = pr.Rectangle(0, 0, 5120,1440)
    126 
    127     pr.begin_drawing()
    128     pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE)
    129     pr.end_drawing()
    130 
    131     end = time.monotonic()
    132     print(end - st)
    133 
    134 pr.unload_render_texture(texture)
    135 pr.close_window()