--- 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