Mercurial > public > think_complexity

comparison GraphWorld.py @ 2:e87731ed81fc

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