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: