Mercurial > public > think_complexity

comparison Graph.py @ 8:1defe6fcf9d3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Improvements to Graph's bfs.
author Brian Neal <bgneal@gmail.com>
date Mon, 03 Dec 2012 19:11:17 -0600
parents 69e5977417b3
children 84e183b40c63
comparison
equal deleted inserted replaced
7:69e5977417b3 8:1defe6fcf9d3
5 5
6 Copyright 2011 Allen B. Downey. 6 Copyright 2011 Allen B. Downey.
7 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html. 7 Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
8 """ 8 """
9 import itertools 9 import itertools
10 from collections import deque
10 11
11 12
12 class GraphError(Exception): 13 class GraphError(Exception):
13 """Exception for Graph errors""" 14 """Exception for Graph errors"""
14 pass 15 pass
195 def bfs(self, start, visit_func=None): 196 def bfs(self, start, visit_func=None):
196 """Perform a breadth first search starting at node start. 197 """Perform a breadth first search starting at node start.
197 198
198 The function visit_func, if supplied, is invoked on each node. 199 The function visit_func, if supplied, is invoked on each node.
199 200
200 """ 201 The set of visited nodes is returned.
201 # Mark all vertices as unvisited 202
202 vs = self.vertices() 203 """
203 for v in vs: 204 visited = set()
204 v.visited = False
205 205
206 # Create a work queue consisting initially of the starting node 206 # Create a work queue consisting initially of the starting node
207 queue = [start] 207 queue = deque([start])
208 208
209 while queue: 209 while queue:
210 # retrieve first item from the queue 210 # retrieve first item from the queue
211 v = queue.pop(0) 211 v = queue.popleft()
212 212
213 if v.visited: 213 if v in visited:
214 continue # Skip this one if we've seen it before 214 continue # Skip this one if we've seen it before
215 215
216 # Mark it as visited and invoke user's function on it 216 # Mark it as visited and invoke user's function on it
217 v.visited = True 217 visited.add(v)
218 if visit_func: 218 if visit_func:
219 visit_func(v) 219 visit_func(v)
220 220
221 # Add the adjacent neigbors to the node to the queue 221 # Add the adjacent neigbors to the node to the queue
222 queue.extend(self.out_vertices(v)) 222 queue.extend(self.out_vertices(v))
223
224 return visited
223 225
224 def is_connected(self): 226 def is_connected(self):
225 """Returns True if the graph is connected (there is a path from every 227 """Returns True if the graph is connected (there is a path from every
226 node to every other node) and False otherwise. 228 node to every other node) and False otherwise.
227 229
228 """ 230 """
229 vs = self.vertices() 231 vs = self.vertices()
230 if len(vs): 232 if len(vs):
231 self.bfs(vs[0]) 233 visited = self.bfs(vs[0])
232 # See if all nodes have been visited 234 # See if all nodes have been visited
233 for v in vs: 235 return len(vs) == len(visited)
234 if not v.visited:
235 return False
236 return True
237 236
238 return False # Graph is empty 237 return False # Graph is empty
239 238
240 239
241 def main(script, *args): 240 def main(script, *args):