Mercurial > public > think_complexity

comparison SmallWorldGraph.py @ 24:5c2c4ce095ef

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
A stab at the L(p)/L(0) plot. I still don't quite get how the graphs in the Watts and Strogatz paper were generated. My results have basically the same shape, but don't converge to 0. I'm not sure how this is possible if the rewire function does not remove edges.
author Brian Neal <bgneal@gmail.com>
date Thu, 03 Jan 2013 18:41:13 -0600
parents 74c9d126bd05
children a46783561538
comparison
equal deleted inserted replaced
23:74c9d126bd05 24:5c2c4ce095ef
5 import random 5 import random
6 6
7 from Graph import Edge 7 from Graph import Edge
8 from RandomGraph import RandomGraph 8 from RandomGraph import RandomGraph
9 9
10
11 INFINITY = float('Inf')
10 12
11 class SmallWorldGraph(RandomGraph): 13 class SmallWorldGraph(RandomGraph):
12 """A small world graph for 4.4, exercise 4 in Think Complexity.""" 14 """A small world graph for 4.4, exercise 4 in Think Complexity."""
13 15
14 def __init__(self, vs, k, p): 16 def __init__(self, vs, k, p):
24 26
25 """ 27 """
26 super(SmallWorldGraph, self).__init__(vs=vs) 28 super(SmallWorldGraph, self).__init__(vs=vs)
27 self.add_regular_edges(k) 29 self.add_regular_edges(k)
28 self.rewire(p) 30 self.rewire(p)
31
32 # give each edge a default length of 1; this is used by the
33 # shortest_path_tree() method
34 for e in self.edges():
35 e.length = 1
29 36
30 def rewire(self, p): 37 def rewire(self, p):
31 """Assuming the graph is initially a regular graph, rewires the graph 38 """Assuming the graph is initially a regular graph, rewires the graph
32 using the Watts and Strogatz algorithm. 39 using the Watts and Strogatz algorithm.
33 40
83 90
84 # The clustering coefficient is the average of all C sub v values 91 # The clustering coefficient is the average of all C sub v values
85 if len(cv): 92 if len(cv):
86 return sum(cv.values()) / float(len(cv)) 93 return sum(cv.values()) / float(len(cv))
87 return 0.0 94 return 0.0
95
96 def shortest_path_tree(self, source, hint=None):
97 """Finds the length of the shortest path from the source vertex to all
98 other vertices in the graph. This length is stored on the vertices as an
99 attribute named 'dist'. The algorithm used is Dijkstra's.
100
101 hint: if provided, must be a dictionary mapping tuples to already known
102 shortest path distances. This can be used to speed up the algorithm.
103
104 """
105 if not hint:
106 hint = {}
107
108 for v in self.vertices():
109 v.dist = hint.get((source, v), INFINITY)
110 source.dist = 0
111
112 queue = [v for v in self.vertices() if v.dist < INFINITY]
113 sort_flag = True
114 while len(queue):
115
116 if sort_flag:
117 queue.sort(key=lambda v: v.dist)
118 sort_flag = False
119
120 v = queue.pop(0)
121
122 # for each neighbor of v, see if we found a new shortest path
123 for w, e in self[v].iteritems():
124 d = v.dist + e.length
125 if d < w.dist:
126 w.dist = d
127 queue.append(w)
128 sort_flag = True
129
130 def big_l(self):
131 """Computes the "big-L" value for the graph as per Watts & Strogatz.
132
133 big_l() is defined as the number of edges in the shortest path between
134 two vertices, averaged over all vertices.
135
136 """
137 d = {}
138 for v in self.vertices():
139 self.shortest_path_tree(v, d)
140 t = [((w, v), w.dist) for w in self.vertices() if v is not w]
141 d.update(t)
142
143 if len(d):
144 return sum(d.values()) / float(len(d))
145 return 0.0