Mercurial > public > think_complexity
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()