Mercurial > public > think_complexity

annotate GraphWorld.py @ 24:5c2c4ce095ef

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
A stab at the L(p)/L(0) plot. I still don't quite get how the graphs in the Watts and Strogatz paper were generated. My results have basically the same shape, but don't converge to 0. I'm not sure how this is possible if the rewire function does not remove edges.
author Brian Neal <bgneal@gmail.com>
date Thu, 03 Jan 2013 18:41:13 -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