--- a/SmallWorldGraph.py	Wed Jan 02 16:50:55 2013 -0600
+++ b/SmallWorldGraph.py	Thu Jan 03 18:41:13 2013 -0600
@@ -8,6 +8,8 @@
 from RandomGraph import RandomGraph
 
 
+INFINITY = float('Inf')
+
 class SmallWorldGraph(RandomGraph):
     """A small world graph for 4.4, exercise 4 in Think Complexity."""
 
@@ -27,6 +29,11 @@
         self.add_regular_edges(k)
         self.rewire(p)
 
+        # give each edge a default length of 1; this is used by the
+        # shortest_path_tree() method
+        for e in self.edges():
+            e.length = 1
+
     def rewire(self, p):
         """Assuming the graph is initially a regular graph, rewires the graph
         using the Watts and Strogatz algorithm.
@@ -85,3 +92,54 @@
         if len(cv):
             return sum(cv.values()) / float(len(cv))
         return 0.0
+
+    def shortest_path_tree(self, source, hint=None):
+        """Finds the length of the shortest path from the source vertex to all
+        other vertices in the graph. This length is stored on the vertices as an
+        attribute named 'dist'. The algorithm used is Dijkstra's.
+
+        hint: if provided, must be a dictionary mapping tuples to already known
+        shortest path distances. This can be used to speed up the algorithm.
+
+        """
+        if not hint:
+            hint = {}
+
+        for v in self.vertices():
+            v.dist = hint.get((source, v), INFINITY)
+        source.dist = 0
+
+        queue = [v for v in self.vertices() if v.dist < INFINITY]
+        sort_flag = True
+        while len(queue):
+
+            if sort_flag:
+                queue.sort(key=lambda v: v.dist)
+                sort_flag = False
+
+            v = queue.pop(0)
+
+            # for each neighbor of v, see if we found a new shortest path
+            for w, e in self[v].iteritems():
+                d = v.dist + e.length
+                if d < w.dist:
+                    w.dist = d
+                    queue.append(w)
+                    sort_flag = True
+
+    def big_l(self):
+        """Computes the "big-L" value for the graph as per Watts & Strogatz.
+
+        big_l() is defined as the number of edges in the shortest path between
+        two vertices, averaged over all vertices.
+
+        """
+        d = {}
+        for v in self.vertices():
+            self.shortest_path_tree(v, d)
+            t = [((w, v), w.dist) for w in self.vertices() if v is not w]
+            d.update(t)
+
+        if len(d):
+            return sum(d.values()) / float(len(d))
+        return 0.0

--- a/ch4ex4.py	Wed Jan 02 16:50:55 2013 -0600
+++ b/ch4ex4.py	Thu Jan 03 18:41:13 2013 -0600
@@ -20,20 +20,23 @@
 vs = [Vertex(str(i)) for i in range(n)]
 g = SmallWorldGraph(vs, k, 0.0)
 c0 = g.clustering_coefficient()
-print 'c0 =', c0
+l0 = g.big_l()
+print 'c0 =', c0, 'l0 =', l0
 
 # compute data
-p_vals = [0,
-          0.0001, 0.0002, 0.0004, 0.0006, 0.0008,
-          0.001, 0.002, 0.004, 0.006, 0.008,
-          0.01, 0.02, 0.04, 0.06, 0.08,
-          0.1, 0.2, 0.4, 0.6, 0.8,
+p_vals = [# 0,
+          0.0001, 0.0002, 0.0004, # 0.0006, 0.0008,
+          0.001, 0.002, 0.004, # 0.006, 0.008,
+          0.01, 0.02, 0.04, # 0.06, 0.08,
+          0.1, 0.2, 0.4, # 0.6, 0.8,
           1.0]
 
 c_vals = []
+l_vals = []
 for p in p_vals:
     g = SmallWorldGraph(vs, k, p)
     c_vals.append(g.clustering_coefficient() / c0)
+    l_vals.append(g.big_l() / l0)
 
 # plot graph
 pyplot.clf()
@@ -42,6 +45,7 @@
 pyplot.title('')
 pyplot.xlabel('p')
 pyplot.ylabel('C(p)/C(0)')
-pyplot.plot(p_vals, c_vals, label=title, color='green', linewidth=3)
+pyplot.plot(p_vals, c_vals, label='C(p)/C(0)', color='green', linewidth=3)
+pyplot.plot(p_vals, l_vals, label='L(p)/L(0)', color='blue', linewidth=3)
 pyplot.legend(loc=4)
 pyplot.show()