think_complexity: Graph.py comparison

Chapter 5.5, exercise 6, #2: plot P(k) vs. k for a WS graph.

comparison

equal deleted inserted replaced

-:66a5e7f7c10f
+:10db8c3a6b83
 Copyright 2011 Allen B. Downey.
 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):
 """Exception for Graph errors"""
 pass
 visited = self.bfs(vs[0])
 # See if all nodes have been visited
 return len(vs) == len(visited)
 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

Mercurial > public > think_complexity