diff ch4ex4.py @ 25:a46783561538

Implement Floyd-Warshall all pairs shortest path algorithm.
author Brian Neal <bgneal@gmail.com>
date Sat, 05 Jan 2013 13:00:07 -0600
parents 5c2c4ce095ef
children f6073c187926
line wrap: on
line diff
--- 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()