Mercurial > public > think_complexity

annotate SmallWorldGraph.py @ 45:1804f09a7adb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Chapter 6, exercise 4, part 4. A Turing Machine drawer.
author Brian Neal <bgneal@gmail.com>
date Sat, 19 Jan 2013 14:17:12 -0600
parents 305cc03c2750
children
rev   line source
bgneal@23 1 """This module contains the SmallWorldGraph class for 4.4, exercise 4.
bgneal@23 2
bgneal@23 3 """
bgneal@23 4 import random
bgneal@23 5
bgneal@23 6 from Graph import Edge
bgneal@23 7 from RandomGraph import RandomGraph
bgneal@23 8
bgneal@23 9
bgneal@23 10 class SmallWorldGraph(RandomGraph):
bgneal@23 11 """A small world graph for 4.4, exercise 4 in Think Complexity."""
bgneal@23 12
bgneal@23 13 def __init__(self, vs, k, p):
bgneal@23 14 """Create a small world graph. Parameters:
bgneal@23 15 vs - a list of vertices
bgneal@23 16 k - regular graph parameter k: the number of edges between vertices
bgneal@23 17 p - probability for rewiring.
bgneal@23 18
bgneal@23 19 First a regular graph is created from the list of vertices and parameter
bgneal@23 20 k, which specifies how many edges each vertex should have. Then the
bgneal@23 21 rewire() method is called with parameter p to rewire the graph according
bgneal@23 22 to the algorithm by Watts and Strogatz.
bgneal@23 23
bgneal@23 24 """
bgneal@23 25 super(SmallWorldGraph, self).__init__(vs=vs)
bgneal@23 26 self.add_regular_edges(k)
bgneal@23 27 self.rewire(p)
bgneal@36 28 self.set_edge_length(1)
bgneal@24 29
bgneal@23 30 def rewire(self, p):
bgneal@23 31 """Assuming the graph is initially a regular graph, rewires the graph
bgneal@23 32 using the Watts and Strogatz algorithm.
bgneal@23 33
bgneal@23 34 """
bgneal@23 35 # We iterate over the edges in a random order:
bgneal@23 36 edges = self.edges()
bgneal@23 37 random.shuffle(edges)
bgneal@23 38 vertices = self.vertices()
bgneal@23 39
bgneal@23 40 for e in edges:
bgneal@23 41 if random.random() < p:
bgneal@23 42 v, w = e # remember the 2 vertices this edge connected
bgneal@23 43 self.remove_edge(e) # remove from graph
bgneal@23 44
bgneal@23 45 # pick another vertex to connect to v; duplicate edges are
bgneal@23 46 # forbidden
bgneal@23 47 while True:
bgneal@23 48 x = random.choice(vertices)
bgneal@23 49 if v is not x and not self.get_edge(v, x):
bgneal@23 50 self.add_edge(Edge(v, x))
bgneal@23 51 break
bgneal@23 52