visualizations

Programmatic visualizations
git clone git://git.laack.co/visualizations.git
Log | Files | Refs | README

prim-rlib.py (2886B)

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