Mercurial > public > think_complexity

comparison ch4ex4.py @ 26:f6073c187926

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added a version of Dijkstra that uses a heap.
author Brian Neal <bgneal@gmail.com>
date Sat, 05 Jan 2013 13:30:58 -0600
parents a46783561538
children 15ff31ecec7a
comparison
equal deleted inserted replaced
25:a46783561538 26:f6073c187926
9 9
10 from Graph import Vertex 10 from Graph import Vertex
11 from SmallWorldGraph import SmallWorldGraph 11 from SmallWorldGraph import SmallWorldGraph
12 12
13 # Use Dijkstra or Floyd-Warshall to compute L 13 # Use Dijkstra or Floyd-Warshall to compute L
14 DIJKSTRA = False 14 DIJKSTRA = True
15 15
16 # compute C(0) 16 # compute C(0)
17 n = 1000 17 n = 1000
18 k = 10 18 k = 10
19 vs = [Vertex(str(i)) for i in range(n)] 19 vs = [Vertex(str(i)) for i in range(n)]
20 g = SmallWorldGraph(vs, k, 0.0) 20 g = SmallWorldGraph(vs, k, 0.0)
21 c0 = g.clustering_coefficient() 21 c0 = g.clustering_coefficient()
22 l0 = g.big_l() if DIJKSTRA else g.big_l2() 22 l0 = g.big_l3() if DIJKSTRA else g.big_l2()
23 print 'c0 =', c0, 'l0 =', l0 23 print 'c0 =', c0, 'l0 =', l0
24 24
25 # compute data 25 # compute data
26 p_vals = [0.0001, 0.0002, 0.0004, # 0.0006, 0.0008, 26 p_vals = [0.0001, 0.0002, 0.0004, # 0.0006, 0.0008,
27 0.001, 0.002, 0.004, # 0.006, 0.008, 27 0.001, 0.002, 0.004, # 0.006, 0.008,
32 c_vals = [] 32 c_vals = []
33 l_vals = [] 33 l_vals = []
34 for p in p_vals: 34 for p in p_vals:
35 g = SmallWorldGraph(vs, k, p) 35 g = SmallWorldGraph(vs, k, p)
36 c_vals.append(g.clustering_coefficient() / c0) 36 c_vals.append(g.clustering_coefficient() / c0)
37 l = g.big_l() if DIJKSTRA else g.big_l2() 37 l = g.big_l3() if DIJKSTRA else g.big_l2()
38 l_vals.append(l / l0) 38 l_vals.append(l / l0)
39 39
40 p_vals.insert(0, 0.0) 40 p_vals.insert(0, 0.0)
41 c_vals.insert(0, 1.0) 41 c_vals.insert(0, 1.0)
42 l_vals.insert(0, 1.0) 42 l_vals.insert(0, 1.0)