Mercurial > public > think_complexity

comparison ch5ex6.py @ 35:10db8c3a6b83

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Chapter 5.5, exercise 6, #2: plot P(k) vs. k for a WS graph.
author Brian Neal <bgneal@gmail.com>
date Wed, 09 Jan 2013 20:51:16 -0600
parents 66a5e7f7c10f
children
comparison
equal deleted inserted replaced
34:66a5e7f7c10f 35:10db8c3a6b83
4 1. Read Barabási and Albert’s paper and implement their algorithm for generating 4 1. Read Barabási and Albert’s paper and implement their algorithm for generating
5 graphs. See if you can replicate their Figure 2(A), which shows P(k) versus 5 graphs. See if you can replicate their Figure 2(A), which shows P(k) versus
6 k for a graph with 150 000 vertices. 6 k for a graph with 150 000 vertices.
7 7
8 """ 8 """
9 import collections
10 import random 9 import random
11 import sys 10 import sys
12 11
13 from matplotlib import pyplot 12 from matplotlib import pyplot
14 13
84 v = Vertex() 83 v = Vertex()
85 self.add_vertex(v) 84 self.add_vertex(v)
86 for w in vs: 85 for w in vs:
87 self.add_edge(Edge(v, w)) 86 self.add_edge(Edge(v, w))
88 87
89 def get_p(self):
90 """This method returns a dictionary of probabilities where each key is
91 the connectivity k and the value is the probability [0-1] for this
92 graph.
93
94 """
95 # First, for each vertex, count up how many neighbors it has
96 vs = self.vertices()
97
98 c = collections.Counter()
99 for v in vs:
100 n = len(self.out_vertices(v))
101 c[n] += 1
102
103 n = len(vs)
104 if n > 0:
105 for k in c:
106 c[k] = float(c[k]) / n
107
108 return c
109
110 88
111 def main(script, m0, m, n): 89 def main(script, m0, m, n):
112 90
113 # create a BAGraph with parameters m0 & m: 91 # create a BAGraph with parameters m0 & m:
114 m0, m, n = int(m0), int(m), int(n) 92 m0, m, n = int(m0), int(m), int(n)