# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1357412407 21600
# Node ID a46783561538a09cf01ddea9065f331b32a18796
# Parent  5c2c4ce095efe259fc2c2d3694e19ed43457c48f
Implement Floyd-Warshall all pairs shortest path algorithm.

diff -r 5c2c4ce095ef -r a46783561538 SmallWorldGraph.py
--- a/SmallWorldGraph.py	Thu Jan 03 18:41:13 2013 -0600
+++ b/SmallWorldGraph.py	Sat Jan 05 13:00:07 2013 -0600
@@ -127,12 +127,42 @@
                     queue.append(w)
                     sort_flag = True
 
+    def all_pairs_floyd_warshall(self):
+        """Finds the shortest paths between all pairs of vertices using the
+        Floyd-Warshall algorithm.
+
+        http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm
+
+        """
+        vertices = self.vertices()
+        dist = {}
+        for i in vertices:
+            for j in vertices:
+                if i is j:
+                    dist[i, j] = 0.0
+                else:
+                    e = self.get_edge(i, j)
+                    dist[i, j] = e.length if e else INFINITY
+
+        for k in vertices:
+            for i in vertices:
+                for j in vertices:
+                    d_ik = dist[i, k]
+                    d_kj = dist[k, j]
+                    new_cost = d_ik + d_kj
+                    if new_cost < dist[i, j]:
+                        dist[i, j] = new_cost
+
+        return dist
+
     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.
 
+        Uses the shortest_path_tree() method, called once for every node.
+
         """
         d = {}
         for v in self.vertices():
@@ -143,3 +173,20 @@
         if len(d):
             return sum(d.values()) / float(len(d))
         return 0.0
+
+    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
+        two vertices, averaged over all vertices.
+
+        Uses the all_pairs_floyd_warshall() method.
+
+        """
+        dist = self.all_pairs_floyd_warshall()
+        vertices = self.vertices()
+        result = [dist[i, j] for i in vertices for j in vertices if i is not j]
+
+        if len(result):
+            return sum(result) / float(len(result))
+        return 0.0
diff -r 5c2c4ce095ef -r a46783561538 ch4ex4.py
--- a/ch4ex4.py	Thu Jan 03 18:41:13 2013 -0600
+++ b/ch4ex4.py	Sat Jan 05 13:00:07 2013 -0600
@@ -5,14 +5,13 @@
 for small values of p."
 
 """
-import random
 import matplotlib.pyplot as pyplot
 
 from Graph import Vertex
 from SmallWorldGraph import SmallWorldGraph
 
-
-title = 'C(p)/C(0)'
+# Use Dijkstra or Floyd-Warshall to compute L
+DIJKSTRA = False
 
 # compute C(0)
 n = 1000
@@ -20,12 +19,11 @@
 vs = [Vertex(str(i)) for i in range(n)]
 g = SmallWorldGraph(vs, k, 0.0)
 c0 = g.clustering_coefficient()
-l0 = g.big_l()
+l0 = g.big_l() if DIJKSTRA else g.big_l2()
 print 'c0 =', c0, 'l0 =', l0
 
 # compute data
-p_vals = [# 0,
-          0.0001, 0.0002, 0.0004, # 0.0006, 0.0008,
+p_vals = [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,
@@ -36,7 +34,12 @@
 for p in p_vals:
     g = SmallWorldGraph(vs, k, p)
     c_vals.append(g.clustering_coefficient() / c0)
-    l_vals.append(g.big_l() / l0)
+    l = g.big_l() if DIJKSTRA else g.big_l2()
+    l_vals.append(l / l0)
+
+p_vals.insert(0, 0.0)
+c_vals.insert(0, 1.0)
+l_vals.insert(0, 1.0)
 
 # plot graph
 pyplot.clf()