think_complexity: Graph.py comparison

comparison Graph.py @ 7:69e5977417b3

Section 2.4, exercise 5, create an is_connected() method for the Graph. Also implement breadth-first search.

author	Brian Neal <bgneal@gmail.com>
date	Sun, 02 Dec 2012 21:51:51 -0600
parents	950a34c7e26b
children	1defe6fcf9d3

comparison

equal deleted inserted replaced

-:950a34c7e26b
+:69e5977417b3
 for i in range(n / 2):
 v = vs2[i]
 w = vs2[i + n / 2]
 self.add_edge(Edge(v, w))
+def bfs(self, start, visit_func=None):
+"""Perform a breadth first search starting at node start.
+The function visit_func, if supplied, is invoked on each node.
+"""
+# Mark all vertices as unvisited
+vs = self.vertices()
+for v in vs:
+v.visited = False
+# Create a work queue consisting initially of the starting node
+queue = [start]
+while queue:
+# retrieve first item from the queue
+v = queue.pop(0)
+if v.visited:
+continue            # Skip this one if we've seen it before
+# Mark it as visited and invoke user's function on it
+v.visited = True
+if visit_func:
+visit_func(v)
+# Add the adjacent neigbors to the node to the queue
+queue.extend(self.out_vertices(v))
+def is_connected(self):
+"""Returns True if the graph is connected (there is a path from every
+node to every other node) and False otherwise.
+"""
+vs = self.vertices()
+if len(vs):
+self.bfs(vs[0])
+# See if all nodes have been visited
+for v in vs:
+if not v.visited:
+return False
+return True
+return False        # Graph is empty
 def main(script, *args):
 import pprint
 x = Vertex('x')
 g.add_vertex(x)
 g.add_all_edges()
 pprint.pprint(g)
+print "g is connected?", g.is_connected()
+edges = g.out_edges(v)
+for e in edges:
+g.remove_edge(e)
+pprint.pprint(g)
+print "g is connected?", g.is_connected()
+# Isolate v and check is_connected() again
 if __name__ == '__main__':
 import sys
 main(*sys.argv)

Mercurial > public > think_complexity

comparison Graph.py @ 7:69e5977417b3