Mercurial > public > think_complexity
annotate ch5ex6-2.py @ 48:98eb01502cf5 tip
Follow up to last commit. Re-orient the r-pentomino. Added progress display.
| author | Brian Neal <bgneal@gmail.com> |
|---|---|
| date | Wed, 31 Jul 2013 20:37:12 -0500 |
| 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) |