Mercurial > public > think_complexity

annotate ch4ex4.py @ 42:039249efe42f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Chapter 6, exercise 2, #4. Wrote a program to output the center column of a rule 30 CA as a stream of bytes. It is very slow though. It has to run a very long time to produce enough data for dieharder. Committing it now but will have to let it run overnight or something to generate a large file.
author Brian Neal <bgneal@gmail.com>
date Sun, 13 Jan 2013 16:24:00 -0600
parents 15ff31ecec7a
children
rev   line source
bgneal@23 1 """This program performs item 4 in 4.4 exercise 4.
bgneal@23 2
bgneal@23 3 "Make a graph that replicates the line marked C(p)/C(0) in Figure 2 of the
bgneal@23 4 paper. In other words, confirm that the clustering coefficient drops off slowly
bgneal@23 5 for small values of p."
bgneal@23 6
bgneal@23 7 """
bgneal@23 8 import matplotlib.pyplot as pyplot
bgneal@23 9
bgneal@23 10 from Graph import Vertex
bgneal@23 11 from SmallWorldGraph import SmallWorldGraph
bgneal@23 12
bgneal@25 13 # Use Dijkstra or Floyd-Warshall to compute L
bgneal@26 14 DIJKSTRA = True
bgneal@23 15
bgneal@23 16 # compute C(0)
bgneal@23 17 n = 1000
bgneal@23 18 k = 10
bgneal@23 19 vs = [Vertex(str(i)) for i in range(n)]
bgneal@23 20 g = SmallWorldGraph(vs, k, 0.0)
bgneal@23 21 c0 = g.clustering_coefficient()
bgneal@26 22 l0 = g.big_l3() if DIJKSTRA else g.big_l2()
bgneal@24 23 print 'c0 =', c0, 'l0 =', l0
bgneal@23 24
bgneal@23 25 # compute data
bgneal@25 26 p_vals = [0.0001, 0.0002, 0.0004, # 0.0006, 0.0008,
bgneal@24 27 0.001, 0.002, 0.004, # 0.006, 0.008,
bgneal@24 28 0.01, 0.02, 0.04, # 0.06, 0.08,
bgneal@24 29 0.1, 0.2, 0.4, # 0.6, 0.8,
bgneal@23 30 1.0]
bgneal@23 31
bgneal@23 32 c_vals = []
bgneal@24 33 l_vals = []
bgneal@23 34 for p in p_vals:
bgneal@23 35 g = SmallWorldGraph(vs, k, p)
bgneal@23 36 c_vals.append(g.clustering_coefficient() / c0)
bgneal@26 37 l = g.big_l3() if DIJKSTRA else g.big_l2()
bgneal@25 38 l_vals.append(l / l0)
bgneal@25 39
bgneal@25 40 p_vals.insert(0, 0.0)
bgneal@25 41 c_vals.insert(0, 1.0)
bgneal@25 42 l_vals.insert(0, 1.0)
bgneal@23 43
bgneal@23 44 # plot graph
bgneal@23 45 pyplot.clf()
bgneal@23 46 pyplot.xscale('log')
bgneal@28 47 pyplot.yscale('linear')
bgneal@23 48 pyplot.title('')
bgneal@23 49 pyplot.xlabel('p')
bgneal@23 50 pyplot.ylabel('C(p)/C(0)')
bgneal@24 51 pyplot.plot(p_vals, c_vals, label='C(p)/C(0)', color='green', linewidth=3)
bgneal@24 52 pyplot.plot(p_vals, l_vals, label='L(p)/L(0)', color='blue', linewidth=3)
bgneal@28 53 pyplot.legend(loc='lower left')
bgneal@23 54 pyplot.show()