Mercurial > public > think_complexity

comparison ch4ex4.py @ 25:a46783561538

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
24:5c2c4ce095ef 25:a46783561538
3 "Make a graph that replicates the line marked C(p)/C(0) in Figure 2 of the 3 "Make a graph that replicates the line marked C(p)/C(0) in Figure 2 of the
4 paper. In other words, confirm that the clustering coefficient drops off slowly 4 paper. In other words, confirm that the clustering coefficient drops off slowly
5 for small values of p." 5 for small values of p."
6 6
7 """ 7 """
8 import random
9 import matplotlib.pyplot as pyplot 8 import matplotlib.pyplot as pyplot
10 9
11 from Graph import Vertex 10 from Graph import Vertex
12 from SmallWorldGraph import SmallWorldGraph 11 from SmallWorldGraph import SmallWorldGraph
13 12
14 13 # Use Dijkstra or Floyd-Warshall to compute L
15 title = 'C(p)/C(0)' 14 DIJKSTRA = False
16 15
17 # compute C(0) 16 # compute C(0)
18 n = 1000 17 n = 1000
19 k = 10 18 k = 10
20 vs = [Vertex(str(i)) for i in range(n)] 19 vs = [Vertex(str(i)) for i in range(n)]
21 g = SmallWorldGraph(vs, k, 0.0) 20 g = SmallWorldGraph(vs, k, 0.0)
22 c0 = g.clustering_coefficient() 21 c0 = g.clustering_coefficient()
23 l0 = g.big_l() 22 l0 = g.big_l() if DIJKSTRA else g.big_l2()
24 print 'c0 =', c0, 'l0 =', l0 23 print 'c0 =', c0, 'l0 =', l0
25 24
26 # compute data 25 # compute data
27 p_vals = [# 0, 26 p_vals = [0.0001, 0.0002, 0.0004, # 0.0006, 0.0008,
28 0.0001, 0.0002, 0.0004, # 0.0006, 0.0008,
29 0.001, 0.002, 0.004, # 0.006, 0.008, 27 0.001, 0.002, 0.004, # 0.006, 0.008,
30 0.01, 0.02, 0.04, # 0.06, 0.08, 28 0.01, 0.02, 0.04, # 0.06, 0.08,
31 0.1, 0.2, 0.4, # 0.6, 0.8, 29 0.1, 0.2, 0.4, # 0.6, 0.8,
32 1.0] 30 1.0]
33 31
34 c_vals = [] 32 c_vals = []
35 l_vals = [] 33 l_vals = []
36 for p in p_vals: 34 for p in p_vals:
37 g = SmallWorldGraph(vs, k, p) 35 g = SmallWorldGraph(vs, k, p)
38 c_vals.append(g.clustering_coefficient() / c0) 36 c_vals.append(g.clustering_coefficient() / c0)
39 l_vals.append(g.big_l() / l0) 37 l = g.big_l() if DIJKSTRA else g.big_l2()
38 l_vals.append(l / l0)
39
40 p_vals.insert(0, 0.0)
41 c_vals.insert(0, 1.0)
42 l_vals.insert(0, 1.0)
40 43
41 # plot graph 44 # plot graph
42 pyplot.clf() 45 pyplot.clf()
43 pyplot.xscale('log') 46 pyplot.xscale('log')
44 pyplot.yscale('log') 47 pyplot.yscale('log')