Mercurial > public > think_complexity

comparison SmallWorldGraph.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 305cc03c2750
comparison
equal deleted inserted replaced
25:a46783561538 26:f6073c187926
1 """This module contains the SmallWorldGraph class for 4.4, exercise 4. 1 """This module contains the SmallWorldGraph class for 4.4, exercise 4.
2 2
3 """ 3 """
4 import heapq
4 import itertools 5 import itertools
5 import random 6 import random
6 7
7 from Graph import Edge 8 from Graph import Edge
8 from RandomGraph import RandomGraph 9 from RandomGraph import RandomGraph
124 d = v.dist + e.length 125 d = v.dist + e.length
125 if d < w.dist: 126 if d < w.dist:
126 w.dist = d 127 w.dist = d
127 queue.append(w) 128 queue.append(w)
128 sort_flag = True 129 sort_flag = True
130
131 def shortest_path_tree2(self, source):
132 """Finds the length of the shortest path from the source vertex to all
133 other vertices in the graph. This length is stored on the vertices as an
134 attribute named 'dist'. The algorithm used is Dijkstra's with a Heap
135 used to sort/store pending nodes to be examined.
136
137 """
138 for v in self.vertices():
139 v.dist = INFINITY
140 source.dist = 0
141
142 queue = []
143 heapq.heappush(queue, (0, source))
144 while len(queue):
145
146 _, v = heapq.heappop(queue)
147
148 # for each neighbor of v, see if we found a new shortest path
149 for w, e in self[v].iteritems():
150 d = v.dist + e.length
151 if d < w.dist:
152 w.dist = d
153 heapq.heappush(queue, (d, w))
129 154
130 def all_pairs_floyd_warshall(self): 155 def all_pairs_floyd_warshall(self):
131 """Finds the shortest paths between all pairs of vertices using the 156 """Finds the shortest paths between all pairs of vertices using the
132 Floyd-Warshall algorithm. 157 Floyd-Warshall algorithm.
133 158
156 return dist 181 return dist
157 182
158 def big_l(self): 183 def big_l(self):
159 """Computes the "big-L" value for the graph as per Watts & Strogatz. 184 """Computes the "big-L" value for the graph as per Watts & Strogatz.
160 185
161 big_l() is defined as the number of edges in the shortest path between 186 L is defined as the number of edges in the shortest path between
162 two vertices, averaged over all vertices. 187 two vertices, averaged over all vertices.
163 188
164 Uses the shortest_path_tree() method, called once for every node. 189 Uses the shortest_path_tree() method, called once for every node.
165 190
166 """ 191 """
175 return 0.0 200 return 0.0
176 201
177 def big_l2(self): 202 def big_l2(self):
178 """Computes the "big-L" value for the graph as per Watts & Strogatz. 203 """Computes the "big-L" value for the graph as per Watts & Strogatz.
179 204
180 big_l() is defined as the number of edges in the shortest path between 205 L is defined as the number of edges in the shortest path between
181 two vertices, averaged over all vertices. 206 two vertices, averaged over all vertices.
182 207
183 Uses the all_pairs_floyd_warshall() method. 208 Uses the all_pairs_floyd_warshall() method.
184 209
185 """ 210 """
188 result = [dist[i, j] for i in vertices for j in vertices if i is not j] 213 result = [dist[i, j] for i in vertices for j in vertices if i is not j]
189 214
190 if len(result): 215 if len(result):
191 return sum(result) / float(len(result)) 216 return sum(result) / float(len(result))
192 return 0.0 217 return 0.0
218
219 def big_l3(self):
220 """Computes the "big-L" value for the graph as per Watts & Strogatz.
221
222 L is defined as the number of edges in the shortest path between
223 two vertices, averaged over all vertices.
224
225 Uses the shortest_path_tree2() method, called once for every node.
226
227 """
228 d = {}
229 for v in self.vertices():
230 self.shortest_path_tree2(v)
231 t = [((v, w), w.dist) for w in self.vertices() if v is not w]
232 d.update(t)
233
234 if len(d):
235 return sum(d.values()) / float(len(d))
236 return 0.0
237