# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1357786276 21600
# Node ID 10db8c3a6b830cace1369f901b9ded90f75aefa4
# Parent  66a5e7f7c10f039f671387098245a965d6332c83
Chapter 5.5, exercise 6, #2: plot P(k) vs. k for a WS graph.

diff -r 66a5e7f7c10f -r 10db8c3a6b83 Graph.py
--- a/Graph.py	Wed Jan 09 20:19:49 2013 -0600
+++ b/Graph.py	Wed Jan 09 20:51:16 2013 -0600
@@ -7,7 +7,7 @@
 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
 """
 import itertools
-from collections import deque
+from collections import deque, Counter
 
 
 class GraphError(Exception):
@@ -236,6 +236,27 @@
 
         return False        # Graph is empty
 
+    def get_p(self):
+        """This method returns a dictionary of probabilities where each key is
+        the connectivity k and the value is the probability [0-1] for this
+        graph.
+
+        """
+        # First, for each vertex, count up how many neighbors it has
+        vs = self.vertices()
+
+        c = Counter()
+        for v in vs:
+            n = len(self.out_vertices(v))
+            c[n] += 1
+
+        n = len(vs)
+        if n > 0:
+            for k in c:
+                c[k] = float(c[k]) / n
+
+        return c
+
 
 def main(script, *args):
     import pprint
diff -r 66a5e7f7c10f -r 10db8c3a6b83 ch5ex6-2.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ch5ex6-2.py	Wed Jan 09 20:51:16 2013 -0600
@@ -0,0 +1,50 @@
+"""Chapter 5.5, exercise 6 in Allen Downey's Think Complexity book.
+
+2. Use the WS model to generate the largest graph you can in a reasonable amount
+   of time. Plot P(k) versus k and see if you can characterize the tail
+   behavior.
+
+"""
+import sys
+
+from matplotlib import pyplot
+
+from Graph import Vertex
+from SmallWorldGraph import SmallWorldGraph
+
+
+
+def main(script, n, k, p):
+
+    # create a SmallWorldGraph with n vertices, k regular edges between
+    # vertices, and rewiring probability p.
+
+    n, k, p = int(n), int(k), float(p)
+    vs = [Vertex() for i in xrange(n)]
+
+    g = SmallWorldGraph(vs, k, p)
+
+    # retrieve probabilities
+    p = g.get_p()
+
+    # plot P(k) versus k on a log-log scale
+
+    vals = p.items()
+    vals.sort(key=lambda t: t[0])
+    x, y = zip(*vals)
+
+    assert abs(sum(y) - 1.0) < 1e-6
+
+    pyplot.clf()
+    pyplot.xscale('log')
+    pyplot.yscale('log')
+    pyplot.title('P(k) versus k')
+    pyplot.xlabel('k')
+    pyplot.ylabel('P(k)')
+    pyplot.plot(x, y, label='P(k) vs. k', color='green', linewidth=3)
+    pyplot.legend(loc='upper right')
+    pyplot.show()
+
+
+if __name__ == '__main__':
+    main(*sys.argv)
diff -r 66a5e7f7c10f -r 10db8c3a6b83 ch5ex6.py
--- a/ch5ex6.py	Wed Jan 09 20:19:49 2013 -0600
+++ b/ch5ex6.py	Wed Jan 09 20:51:16 2013 -0600
@@ -6,7 +6,6 @@
    k for a graph with 150 000 vertices.
 
 """
-import collections
 import random
 import sys
 
@@ -86,27 +85,6 @@
         for w in vs:
             self.add_edge(Edge(v, w))
 
-    def get_p(self):
-        """This method returns a dictionary of probabilities where each key is
-        the connectivity k and the value is the probability [0-1] for this
-        graph.
-
-        """
-        # First, for each vertex, count up how many neighbors it has
-        vs = self.vertices()
-
-        c = collections.Counter()
-        for v in vs:
-            n = len(self.out_vertices(v))
-            c[n] += 1
-
-        n = len(vs)
-        if n > 0:
-            for k in c:
-                c[k] = float(c[k]) / n
-
-        return c
-
 
 def main(script, m0, m, n):