--- a/SmallWorldGraph.py	Sat Jan 05 13:00:07 2013 -0600
+++ b/SmallWorldGraph.py	Sat Jan 05 13:30:58 2013 -0600
@@ -1,6 +1,7 @@
 """This module contains the SmallWorldGraph class for 4.4, exercise 4.
 
 """
+import heapq
 import itertools
 import random
 
@@ -127,6 +128,30 @@
                     queue.append(w)
                     sort_flag = True
 
+    def shortest_path_tree2(self, source):
+        """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 with a Heap
+        used to sort/store pending nodes to be examined.
+
+        """
+        for v in self.vertices():
+            v.dist = INFINITY
+        source.dist = 0
+
+        queue = []
+        heapq.heappush(queue, (0, source))
+        while len(queue):
+
+            _, v = heapq.heappop(queue)
+
+            # 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
+                    heapq.heappush(queue, (d, w))
+
     def all_pairs_floyd_warshall(self):
         """Finds the shortest paths between all pairs of vertices using the
         Floyd-Warshall algorithm.
@@ -158,7 +183,7 @@
     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
+        L is defined as the number of edges in the shortest path between
         two vertices, averaged over all vertices.
 
         Uses the shortest_path_tree() method, called once for every node.
@@ -177,7 +202,7 @@
     def big_l2(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
+        L is defined as the number of edges in the shortest path between
         two vertices, averaged over all vertices.
 
         Uses the all_pairs_floyd_warshall() method.
@@ -190,3 +215,23 @@
         if len(result):
             return sum(result) / float(len(result))
         return 0.0
+
+    def big_l3(self):
+        """Computes the "big-L" value for the graph as per Watts & Strogatz.
+
+        L is defined as the number of edges in the shortest path between
+        two vertices, averaged over all vertices.
+
+        Uses the shortest_path_tree2() method, called once for every node.
+
+        """
+        d = {}
+        for v in self.vertices():
+            self.shortest_path_tree2(v)
+            t = [((v, w), 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
+