Mercurial > public > think_complexity

annotate GraphWorld.py @ 18:92e2879e2e33

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Rework the red-black tree based on Julienne Walker's tutorial. Insertion is implemented now. Deletion will come next.
author Brian Neal <bgneal@gmail.com>
date Wed, 26 Dec 2012 19:59:17 -0600
parents e87731ed81fc
children
rev   line source
bgneal@2 1 """ Code example from Complexity and Computation, a book about
bgneal@2 2 exploring complexity science with Python. Available free from
bgneal@2 3
bgneal@2 4 http://greenteapress.com/complexity
bgneal@2 5
bgneal@2 6 Copyright 2011 Allen B. Downey.
bgneal@2 7 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
bgneal@2 8 """
bgneal@2 9
bgneal@2 10 import string
bgneal@2 11 import random
bgneal@2 12 import math
bgneal@2 13
bgneal@2 14 from itertools import chain
bgneal@2 15
bgneal@2 16 try:
bgneal@2 17 from Gui import Gui, GuiCanvas
bgneal@2 18 except ImportError:
bgneal@2 19 from swampy.Gui import Gui, GuiCanvas
bgneal@2 20
bgneal@2 21 from Graph import Vertex
bgneal@2 22 from Graph import Edge
bgneal@2 23 from Graph import Graph
bgneal@2 24
bgneal@2 25
bgneal@2 26 class GraphCanvas(GuiCanvas):
bgneal@2 27 """a GraphCanvas is a canvas that knows how to draw Vertices
bgneal@2 28 and Edges"""
bgneal@2 29
bgneal@2 30 def draw_vertex(self, v, r=0.45):
bgneal@2 31 """draw a Vertex as a yellow circle with radius (r)
bgneal@2 32 and text (v.label)"""
bgneal@2 33 tag = 'v%d' % id(self)
bgneal@2 34
bgneal@2 35 try:
bgneal@2 36 color = v.color
bgneal@2 37 except:
bgneal@2 38 color = 'yellow'
bgneal@2 39
bgneal@2 40 self.circle(v.pos, r, color, tags=tag)
bgneal@2 41 self.text(v.pos, v.label, 'black', tags=tag)
bgneal@2 42 return tag
bgneal@2 43
bgneal@2 44 def draw_edge(self, e):
bgneal@2 45 """draw an Edge as a line between the positions of the
bgneal@2 46 Vertices it connects"""
bgneal@2 47 v, w = e
bgneal@2 48 tag = self.line([v.pos, w.pos])
bgneal@2 49 return tag
bgneal@2 50
bgneal@2 51
bgneal@2 52 class GraphWorld(Gui):
bgneal@2 53 """GraphWorld is a Gui that has a Graph Canvas and control buttons."""
bgneal@2 54
bgneal@2 55 def __init__(self):
bgneal@2 56 Gui.__init__(self)
bgneal@2 57 self.title('GraphWorld')
bgneal@2 58 self.setup()
bgneal@2 59
bgneal@2 60 def setup(self):
bgneal@2 61 """Create the widgets."""
bgneal@2 62 self.ca_width = 400
bgneal@2 63 self.ca_height = 400
bgneal@2 64 xscale = self.ca_width / 20
bgneal@2 65 yscale = self.ca_height / 20
bgneal@2 66
bgneal@2 67 # canvas
bgneal@2 68 self.col()
bgneal@2 69 self.canvas = self.widget(GraphCanvas, scale=[xscale, yscale],
bgneal@2 70 width=self.ca_width, height=self.ca_height,
bgneal@2 71 bg='white')
bgneal@2 72
bgneal@2 73 # buttons
bgneal@2 74 self.row()
bgneal@2 75 self.bu(text='Clear', command=self.clear)
bgneal@2 76 self.bu(text='Quit', command=self.quit)
bgneal@2 77 self.endrow()
bgneal@2 78
bgneal@2 79 def show_graph(self, g, layout):
bgneal@2 80 """Draws the Vertices and Edges of Graph (g) using the
bgneal@2 81 positions in Layout (layout).
bgneal@2 82 """
bgneal@2 83
bgneal@2 84 # copy the positions from the layout into the Vertex objects
bgneal@2 85 for v in g.vertices():
bgneal@2 86 v.pos = layout.pos(v)
bgneal@2 87
bgneal@2 88 # draw the edges and store the tags in self.etags, which maps
bgneal@2 89 # from Edges to their tags
bgneal@2 90 c = self.canvas
bgneal@2 91 self.etags = {}
bgneal@2 92 for v in g:
bgneal@2 93 self.etags[v] = [c.draw_edge(e) for e in g.out_edges(v)]
bgneal@2 94
bgneal@2 95 # draw the vertices and store their tags in a list
bgneal@2 96 self.vtags = [c.draw_vertex(v) for v in g]
bgneal@2 97
bgneal@2 98 def clear(self):
bgneal@2 99 """Delete all canvas items."""
bgneal@2 100 tags = chain(self.vtags, *self.etags.itervalues())
bgneal@2 101 for tag in tags:
bgneal@2 102 self.canvas.delete(tag)
bgneal@2 103
bgneal@2 104
bgneal@2 105 class Layout(dict):
bgneal@2 106 """A Layout is a mapping from vertices to positions in 2-D space."""
bgneal@2 107
bgneal@2 108 def __init__(self, g):
bgneal@2 109 for v in g.vertices():
bgneal@2 110 self[v] = (0, 0)
bgneal@2 111
bgneal@2 112 def pos(self, v):
bgneal@2 113 """Returns the position of this Vertex as a tuple."""
bgneal@2 114 return self[v]
bgneal@2 115
bgneal@2 116 def distance_between(self, v1, v2):
bgneal@2 117 """Computes the Euclidean distance between two vertices."""
bgneal@2 118 x1, y1 = self.pos(v1)
bgneal@2 119 x2, y2 = self.pos(v2)
bgneal@2 120 dx = x1 - x2
bgneal@2 121 dy = y1 - y2
bgneal@2 122 return math.sqrt(dx**2 + dy**2)
bgneal@2 123
bgneal@2 124 def sort_by_distance(self, v, others):
bgneal@2 125 """Returns a list of the vertices in others sorted in
bgneal@2 126 increasing order by their distance from v."""
bgneal@2 127 t = [(self.distance_between(v, w), w) for w in others]
bgneal@2 128 t.sort()
bgneal@2 129 return [w for (d, w) in t]
bgneal@2 130
bgneal@2 131
bgneal@2 132 class CircleLayout(Layout):
bgneal@2 133 """Creates a layout for a graph with the vertices equally
bgneal@2 134 spaced around the perimeter of a circle."""
bgneal@2 135
bgneal@2 136 def __init__(self, g, radius=9):
bgneal@2 137 """Creates a layout for Graph (g)"""
bgneal@2 138 vs = g.vertices()
bgneal@2 139 theta = math.pi * 2 / len(vs)
bgneal@2 140 for i, v in enumerate(vs):
bgneal@2 141 x = radius * math.cos(i * theta)
bgneal@2 142 y = radius * math.sin(i * theta)
bgneal@2 143 self[v] = (x, y)
bgneal@2 144
bgneal@2 145
bgneal@2 146 class RandomLayout(Layout):
bgneal@2 147 """Create a layout with each Vertex at a random position in
bgneal@2 148 [[-max, -max], [max, max]]."""
bgneal@2 149
bgneal@2 150 def __init__(self, g, max=10):
bgneal@2 151 """Creates a layout for Graph (g)"""
bgneal@2 152 self.max = max
bgneal@2 153 for v in g.vertices():
bgneal@2 154 self[v] = self.random_pos()
bgneal@2 155
bgneal@2 156 def random_pos(self):
bgneal@2 157 """choose a random position and return it as a tuple"""
bgneal@2 158 x = random.uniform(-self.max, self.max)
bgneal@2 159 y = random.uniform(-self.max, self.max)
bgneal@2 160 return x, y
bgneal@2 161
bgneal@2 162 def spread_vertex(self, v, others, min_dist=1.0):
bgneal@2 163 """Keep choosing random positions for v until it is at least
bgneal@2 164 min_dist units from the vertices in others.
bgneal@2 165
bgneal@2 166 Each time it fails, it relaxes min_dist by 10%.
bgneal@2 167 """
bgneal@2 168 while True:
bgneal@2 169 t = [(self.distance_between(v, w), w) for w in others]
bgneal@2 170 d, w = min(t)
bgneal@2 171 if d > min_dist:
bgneal@2 172 break
bgneal@2 173 min_dist *= 0.9
bgneal@2 174 self[v] = self.random_pos()
bgneal@2 175
bgneal@2 176 def spread_vertices(self):
bgneal@2 177 """Moves the vertices around until no two are closer together
bgneal@2 178 than a minimum distance."""
bgneal@2 179 vs = self.keys()
bgneal@2 180 others = vs[:]
bgneal@2 181 for v in vs:
bgneal@2 182 others.remove(v)
bgneal@2 183 self.spread_vertex(v, others)
bgneal@2 184 others.append(v)
bgneal@2 185
bgneal@2 186
bgneal@2 187
bgneal@2 188 def main(script, n='10', *args):
bgneal@2 189
bgneal@2 190 # create n Vertices
bgneal@2 191 n = int(n)
bgneal@2 192 labels = string.ascii_lowercase + string.ascii_uppercase
bgneal@2 193 vs = [Vertex(c) for c in labels[:n]]
bgneal@2 194
bgneal@2 195 # create a graph and a layout
bgneal@2 196 g = Graph(vs)
bgneal@2 197 g.add_all_edges()
bgneal@2 198 layout = CircleLayout(g)
bgneal@2 199
bgneal@2 200 # draw the graph
bgneal@2 201 gw = GraphWorld()
bgneal@2 202 gw.show_graph(g, layout)
bgneal@2 203 gw.mainloop()
bgneal@2 204
bgneal@2 205
bgneal@2 206 if __name__ == '__main__':
bgneal@2 207 import sys
bgneal@2 208 main(*sys.argv)
bgneal@2 209
bgneal@2 210