Mercurial > public > think_complexity

comparison SmallWorldGraph.py @ 25:a46783561538

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Implement Floyd-Warshall all pairs shortest path algorithm.
author Brian Neal <bgneal@gmail.com>
date Sat, 05 Jan 2013 13:00:07 -0600
parents 5c2c4ce095ef
children f6073c187926
comparison
equal deleted inserted replaced
24:5c2c4ce095ef 25:a46783561538
125 if d < w.dist: 125 if d < w.dist:
126 w.dist = d 126 w.dist = d
127 queue.append(w) 127 queue.append(w)
128 sort_flag = True 128 sort_flag = True
129 129
130 def all_pairs_floyd_warshall(self):
131 """Finds the shortest paths between all pairs of vertices using the
132 Floyd-Warshall algorithm.
133
134 http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm
135
136 """
137 vertices = self.vertices()
138 dist = {}
139 for i in vertices:
140 for j in vertices:
141 if i is j:
142 dist[i, j] = 0.0
143 else:
144 e = self.get_edge(i, j)
145 dist[i, j] = e.length if e else INFINITY
146
147 for k in vertices:
148 for i in vertices:
149 for j in vertices:
150 d_ik = dist[i, k]
151 d_kj = dist[k, j]
152 new_cost = d_ik + d_kj
153 if new_cost < dist[i, j]:
154 dist[i, j] = new_cost
155
156 return dist
157
130 def big_l(self): 158 def big_l(self):
131 """Computes the "big-L" value for the graph as per Watts & Strogatz. 159 """Computes the "big-L" value for the graph as per Watts & Strogatz.
132 160
133 big_l() is defined as the number of edges in the shortest path between 161 big_l() is defined as the number of edges in the shortest path between
134 two vertices, averaged over all vertices. 162 two vertices, averaged over all vertices.
163
164 Uses the shortest_path_tree() method, called once for every node.
135 165
136 """ 166 """
137 d = {} 167 d = {}
138 for v in self.vertices(): 168 for v in self.vertices():
139 self.shortest_path_tree(v, d) 169 self.shortest_path_tree(v, d)
141 d.update(t) 171 d.update(t)
142 172
143 if len(d): 173 if len(d):
144 return sum(d.values()) / float(len(d)) 174 return sum(d.values()) / float(len(d))
145 return 0.0 175 return 0.0
176
177 def big_l2(self):
178 """Computes the "big-L" value for the graph as per Watts & Strogatz.
179
180 big_l() is defined as the number of edges in the shortest path between
181 two vertices, averaged over all vertices.
182
183 Uses the all_pairs_floyd_warshall() method.
184
185 """
186 dist = self.all_pairs_floyd_warshall()
187 vertices = self.vertices()
188 result = [dist[i, j] for i in vertices for j in vertices if i is not j]
189
190 if len(result):
191 return sum(result) / float(len(result))
192 return 0.0