Mercurial > public > think_complexity

comparison ch5ex7.py @ 37:931f60dee99e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Chapter 5.6, exercise 7. Exploring the Texas road network.
author Brian Neal <bgneal@gmail.com>
date Thu, 10 Jan 2013 20:23:52 -0600
parents
children d876711b88b5
comparison
equal deleted inserted replaced
36:305cc03c2750 37:931f60dee99e
1 """Chapter 5.6, exercise 7 in Allen Downey's Think Complexity book.
2
3 "The Stanford Large Network Dataset Collection is a repository of datasets from
4 a variety of networks, including social networks, communication and
5 collaboration, Internet and road networks. See
6 http://snap.stanford.edu/data/index.html. Download one of these datasets and
7 explore. Is there evidence of small-world behavior? Is the network scale-free?
8 What else can you discover?"
9
10 Here we will analyze the Texas road network:
11 http://snap.stanford.edu/data/roadNet-TX.html
12
13 """
14 import sys
15 from collections import defaultdict
16
17 from matplotlib import pyplot
18
19 from Graph import Edge, Vertex, Graph
20
21
22 def main(script, datafile):
23
24 node_map = defaultdict(Vertex)
25 g = Graph()
26 print 'Reading road network data...'
27 with open(datafile, 'r') as fp:
28 for line in fp:
29 if line.startswith('#'):
30 continue
31 vn, wn = line.split()
32
33 v = node_map[vn]
34 w = node_map[wn]
35
36 if v not in g:
37 g.add_vertex(v)
38 if w not in g:
39 g.add_vertex(w)
40
41 g.add_edge(Edge(v, w))
42
43 print 'Calculating P(k)...'
44 # retrieve probabilities
45 p = g.get_p()
46
47 # plot P(k) versus k on a log-log scale
48
49 vals = p.items()
50 print 'Sorting data...'
51 vals.sort(key=lambda t: t[0])
52 x, y = zip(*vals)
53
54 assert abs(sum(y) - 1.0) < 1e-6
55
56 print 'Calculating clustering coefficient...'
57 c = g.clustering_coefficient()
58 print 'c =', c
59 print 'Setting edge lengths...'
60 g.set_edge_length(1)
61 print 'Calculating characteristic length L...'
62 l3 = g.big_l3()
63 print 'L =', l3
64
65 print 'Plotting data...'
66 pyplot.clf()
67 pyplot.xscale('log')
68 pyplot.yscale('log')
69 pyplot.title('P(k) versus k')
70 pyplot.xlabel('k')
71 pyplot.ylabel('P(k)')
72 pyplot.plot(x, y, label='P(k) vs. k', color='green', linewidth=3)
73 pyplot.legend(loc='upper right')
74 pyplot.show()
75
76
77 if __name__ == '__main__':
78 main(*sys.argv)