Mercurial > public > think_complexity

annotate ch5ex6-2.py @ 45:1804f09a7adb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Chapter 6, exercise 4, part 4. A Turing Machine drawer.
author Brian Neal <bgneal@gmail.com>
date Sat, 19 Jan 2013 14:17:12 -0600
parents 10db8c3a6b83
children
rev   line source
bgneal@35 1 """Chapter 5.5, exercise 6 in Allen Downey's Think Complexity book.
bgneal@35 2
bgneal@35 3 2. Use the WS model to generate the largest graph you can in a reasonable amount
bgneal@35 4 of time. Plot P(k) versus k and see if you can characterize the tail
bgneal@35 5 behavior.
bgneal@35 6
bgneal@35 7 """
bgneal@35 8 import sys
bgneal@35 9
bgneal@35 10 from matplotlib import pyplot
bgneal@35 11
bgneal@35 12 from Graph import Vertex
bgneal@35 13 from SmallWorldGraph import SmallWorldGraph
bgneal@35 14
bgneal@35 15
bgneal@35 16
bgneal@35 17 def main(script, n, k, p):
bgneal@35 18
bgneal@35 19 # create a SmallWorldGraph with n vertices, k regular edges between
bgneal@35 20 # vertices, and rewiring probability p.
bgneal@35 21
bgneal@35 22 n, k, p = int(n), int(k), float(p)
bgneal@35 23 vs = [Vertex() for i in xrange(n)]
bgneal@35 24
bgneal@35 25 g = SmallWorldGraph(vs, k, p)
bgneal@35 26
bgneal@35 27 # retrieve probabilities
bgneal@35 28 p = g.get_p()
bgneal@35 29
bgneal@35 30 # plot P(k) versus k on a log-log scale
bgneal@35 31
bgneal@35 32 vals = p.items()
bgneal@35 33 vals.sort(key=lambda t: t[0])
bgneal@35 34 x, y = zip(*vals)
bgneal@35 35
bgneal@35 36 assert abs(sum(y) - 1.0) < 1e-6
bgneal@35 37
bgneal@35 38 pyplot.clf()
bgneal@35 39 pyplot.xscale('log')
bgneal@35 40 pyplot.yscale('log')
bgneal@35 41 pyplot.title('P(k) versus k')
bgneal@35 42 pyplot.xlabel('k')
bgneal@35 43 pyplot.ylabel('P(k)')
bgneal@35 44 pyplot.plot(x, y, label='P(k) vs. k', color='green', linewidth=3)
bgneal@35 45 pyplot.legend(loc='upper right')
bgneal@35 46 pyplot.show()
bgneal@35 47
bgneal@35 48
bgneal@35 49 if __name__ == '__main__':
bgneal@35 50 main(*sys.argv)