# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1357260073 21600
# Node ID 5c2c4ce095efe259fc2c2d3694e19ed43457c48f
# Parent  74c9d126bd058f0a49d70039e322ab1975c37268
A stab at the L(p)/L(0) plot.
I still don't quite get how the graphs in the Watts and Strogatz paper were
generated. My results have basically the same shape, but don't converge to 0.
I'm not sure how this is possible if the rewire function does not remove edges.

diff -r 74c9d126bd05 -r 5c2c4ce095ef SmallWorldGraph.py
--- 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
diff -r 74c9d126bd05 -r 5c2c4ce095ef ch4ex4.py
--- 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()