bgneal@2: """ Code example from Complexity and Computation, a book about
bgneal@2: exploring complexity science with Python. Available free from
bgneal@2:
bgneal@2: http://greenteapress.com/complexity
bgneal@2:
bgneal@2: Copyright 2011 Allen B. Downey.
bgneal@2: Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
bgneal@2: """
bgneal@2:
bgneal@2: import string
bgneal@2: import random
bgneal@2: import math
bgneal@2:
bgneal@2: from itertools import chain
bgneal@2:
bgneal@2: try:
bgneal@2: from Gui import Gui, GuiCanvas
bgneal@2: except ImportError:
bgneal@2: from swampy.Gui import Gui, GuiCanvas
bgneal@2:
bgneal@2: from Graph import Vertex
bgneal@2: from Graph import Edge
bgneal@2: from Graph import Graph
bgneal@2:
bgneal@2:
bgneal@2: class GraphCanvas(GuiCanvas):
bgneal@2: """a GraphCanvas is a canvas that knows how to draw Vertices
bgneal@2: and Edges"""
bgneal@2:
bgneal@2: def draw_vertex(self, v, r=0.45):
bgneal@2: """draw a Vertex as a yellow circle with radius (r)
bgneal@2: and text (v.label)"""
bgneal@2: tag = 'v%d' % id(self)
bgneal@2:
bgneal@2: try:
bgneal@2: color = v.color
bgneal@2: except:
bgneal@2: color = 'yellow'
bgneal@2:
bgneal@2: self.circle(v.pos, r, color, tags=tag)
bgneal@2: self.text(v.pos, v.label, 'black', tags=tag)
bgneal@2: return tag
bgneal@2:
bgneal@2: def draw_edge(self, e):
bgneal@2: """draw an Edge as a line between the positions of the
bgneal@2: Vertices it connects"""
bgneal@2: v, w = e
bgneal@2: tag = self.line([v.pos, w.pos])
bgneal@2: return tag
bgneal@2:
bgneal@2:
bgneal@2: class GraphWorld(Gui):
bgneal@2: """GraphWorld is a Gui that has a Graph Canvas and control buttons."""
bgneal@2:
bgneal@2: def __init__(self):
bgneal@2: Gui.__init__(self)
bgneal@2: self.title('GraphWorld')
bgneal@2: self.setup()
bgneal@2:
bgneal@2: def setup(self):
bgneal@2: """Create the widgets."""
bgneal@2: self.ca_width = 400
bgneal@2: self.ca_height = 400
bgneal@2: xscale = self.ca_width / 20
bgneal@2: yscale = self.ca_height / 20
bgneal@2:
bgneal@2: # canvas
bgneal@2: self.col()
bgneal@2: self.canvas = self.widget(GraphCanvas, scale=[xscale, yscale],
bgneal@2: width=self.ca_width, height=self.ca_height,
bgneal@2: bg='white')
bgneal@2:
bgneal@2: # buttons
bgneal@2: self.row()
bgneal@2: self.bu(text='Clear', command=self.clear)
bgneal@2: self.bu(text='Quit', command=self.quit)
bgneal@2: self.endrow()
bgneal@2:
bgneal@2: def show_graph(self, g, layout):
bgneal@2: """Draws the Vertices and Edges of Graph (g) using the
bgneal@2: positions in Layout (layout).
bgneal@2: """
bgneal@2:
bgneal@2: # copy the positions from the layout into the Vertex objects
bgneal@2: for v in g.vertices():
bgneal@2: v.pos = layout.pos(v)
bgneal@2:
bgneal@2: # draw the edges and store the tags in self.etags, which maps
bgneal@2: # from Edges to their tags
bgneal@2: c = self.canvas
bgneal@2: self.etags = {}
bgneal@2: for v in g:
bgneal@2: self.etags[v] = [c.draw_edge(e) for e in g.out_edges(v)]
bgneal@2:
bgneal@2: # draw the vertices and store their tags in a list
bgneal@2: self.vtags = [c.draw_vertex(v) for v in g]
bgneal@2:
bgneal@2: def clear(self):
bgneal@2: """Delete all canvas items."""
bgneal@2: tags = chain(self.vtags, *self.etags.itervalues())
bgneal@2: for tag in tags:
bgneal@2: self.canvas.delete(tag)
bgneal@2:
bgneal@2:
bgneal@2: class Layout(dict):
bgneal@2: """A Layout is a mapping from vertices to positions in 2-D space."""
bgneal@2:
bgneal@2: def __init__(self, g):
bgneal@2: for v in g.vertices():
bgneal@2: self[v] = (0, 0)
bgneal@2:
bgneal@2: def pos(self, v):
bgneal@2: """Returns the position of this Vertex as a tuple."""
bgneal@2: return self[v]
bgneal@2:
bgneal@2: def distance_between(self, v1, v2):
bgneal@2: """Computes the Euclidean distance between two vertices."""
bgneal@2: x1, y1 = self.pos(v1)
bgneal@2: x2, y2 = self.pos(v2)
bgneal@2: dx = x1 - x2
bgneal@2: dy = y1 - y2
bgneal@2: return math.sqrt(dx**2 + dy**2)
bgneal@2:
bgneal@2: def sort_by_distance(self, v, others):
bgneal@2: """Returns a list of the vertices in others sorted in
bgneal@2: increasing order by their distance from v."""
bgneal@2: t = [(self.distance_between(v, w), w) for w in others]
bgneal@2: t.sort()
bgneal@2: return [w for (d, w) in t]
bgneal@2:
bgneal@2:
bgneal@2: class CircleLayout(Layout):
bgneal@2: """Creates a layout for a graph with the vertices equally
bgneal@2: spaced around the perimeter of a circle."""
bgneal@2:
bgneal@2: def __init__(self, g, radius=9):
bgneal@2: """Creates a layout for Graph (g)"""
bgneal@2: vs = g.vertices()
bgneal@2: theta = math.pi * 2 / len(vs)
bgneal@2: for i, v in enumerate(vs):
bgneal@2: x = radius * math.cos(i * theta)
bgneal@2: y = radius * math.sin(i * theta)
bgneal@2: self[v] = (x, y)
bgneal@2:
bgneal@2:
bgneal@2: class RandomLayout(Layout):
bgneal@2: """Create a layout with each Vertex at a random position in
bgneal@2: [[-max, -max], [max, max]]."""
bgneal@2:
bgneal@2: def __init__(self, g, max=10):
bgneal@2: """Creates a layout for Graph (g)"""
bgneal@2: self.max = max
bgneal@2: for v in g.vertices():
bgneal@2: self[v] = self.random_pos()
bgneal@2:
bgneal@2: def random_pos(self):
bgneal@2: """choose a random position and return it as a tuple"""
bgneal@2: x = random.uniform(-self.max, self.max)
bgneal@2: y = random.uniform(-self.max, self.max)
bgneal@2: return x, y
bgneal@2:
bgneal@2: def spread_vertex(self, v, others, min_dist=1.0):
bgneal@2: """Keep choosing random positions for v until it is at least
bgneal@2: min_dist units from the vertices in others.
bgneal@2:
bgneal@2: Each time it fails, it relaxes min_dist by 10%.
bgneal@2: """
bgneal@2: while True:
bgneal@2: t = [(self.distance_between(v, w), w) for w in others]
bgneal@2: d, w = min(t)
bgneal@2: if d > min_dist:
bgneal@2: break
bgneal@2: min_dist *= 0.9
bgneal@2: self[v] = self.random_pos()
bgneal@2:
bgneal@2: def spread_vertices(self):
bgneal@2: """Moves the vertices around until no two are closer together
bgneal@2: than a minimum distance."""
bgneal@2: vs = self.keys()
bgneal@2: others = vs[:]
bgneal@2: for v in vs:
bgneal@2: others.remove(v)
bgneal@2: self.spread_vertex(v, others)
bgneal@2: others.append(v)
bgneal@2:
bgneal@2:
bgneal@2:
bgneal@2: def main(script, n='10', *args):
bgneal@2:
bgneal@2: # create n Vertices
bgneal@2: n = int(n)
bgneal@2: labels = string.ascii_lowercase + string.ascii_uppercase
bgneal@2: vs = [Vertex(c) for c in labels[:n]]
bgneal@2:
bgneal@2: # create a graph and a layout
bgneal@2: g = Graph(vs)
bgneal@2: g.add_all_edges()
bgneal@2: layout = CircleLayout(g)
bgneal@2:
bgneal@2: # draw the graph
bgneal@2: gw = GraphWorld()
bgneal@2: gw.show_graph(g, layout)
bgneal@2: gw.mainloop()
bgneal@2:
bgneal@2:
bgneal@2: if __name__ == '__main__':
bgneal@2: import sys
bgneal@2: main(*sys.argv)
bgneal@2:
bgneal@2: