--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/SmallWorldGraph.py	Wed Jan 02 16:50:55 2013 -0600
@@ -0,0 +1,87 @@
+"""This module contains the SmallWorldGraph class for 4.4, exercise 4.
+
+"""
+import itertools
+import random
+
+from Graph import Edge
+from RandomGraph import RandomGraph
+
+
+class SmallWorldGraph(RandomGraph):
+    """A small world graph for 4.4, exercise 4 in Think Complexity."""
+
+    def __init__(self, vs, k, p):
+        """Create a small world graph. Parameters:
+            vs - a list of vertices
+            k - regular graph parameter k: the number of edges between vertices
+            p - probability for rewiring.
+
+        First a regular graph is created from the list of vertices and parameter
+        k, which specifies how many edges each vertex should have. Then the
+        rewire() method is called with parameter p to rewire the graph according
+        to the algorithm by Watts and Strogatz.
+
+        """
+        super(SmallWorldGraph, self).__init__(vs=vs)
+        self.add_regular_edges(k)
+        self.rewire(p)
+
+    def rewire(self, p):
+        """Assuming the graph is initially a regular graph, rewires the graph
+        using the Watts and Strogatz algorithm.
+
+        """
+        # We iterate over the edges in a random order:
+        edges = self.edges()
+        random.shuffle(edges)
+        vertices = self.vertices()
+
+        for e in edges:
+            if random.random() < p:
+                v, w = e    # remember the 2 vertices this edge connected
+                self.remove_edge(e)     # remove from graph
+
+                # pick another vertex to connect to v; duplicate edges are
+                # forbidden
+                while True:
+                    x = random.choice(vertices)
+                    if v is not x and not self.get_edge(v, x):
+                        self.add_edge(Edge(v, x))
+                        break
+
+    def clustering_coefficient(self):
+        """Compute the clustering coefficient for this graph as defined by Watts
+        and Strogatz.
+
+        """
+        cv = {}
+        for v in self:
+            # consider a node and its neighbors
+            nodes = self.out_vertices(v)
+            nodes.append(v)
+
+            # compute the maximum number of possible edges between these nodes
+            # if they were all connected to each other:
+            n = len(nodes)
+            if n == 1:
+                # edge case of only 1 node; handle this case to avoid division
+                # by zero in the general case
+                cv[v] = 1.0
+                continue
+
+            possible = n * (n - 1) / 2.0
+
+            # now compute how many edges actually exist between the nodes
+            actual = 0
+            for x, y in itertools.combinations(nodes, 2):
+                if self.get_edge(x, y):
+                    actual += 1
+
+            # the fraction of actual / possible is this nodes C sub v value
+            cv[v] = actual / possible
+
+        # The clustering coefficient is the average of all C sub v values
+        if len(cv):
+            return sum(cv.values()) / float(len(cv))
+        return 0.0