# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1354506711 21600
# Node ID 69e5977417b35a577199a1310ce2f6ef82798539
# Parent  950a34c7e26bdd4f546baffc329087f433291365
Section 2.4, exercise 5, create an is_connected() method for the Graph.
Also implement breadth-first search.

diff -r 950a34c7e26b -r 69e5977417b3 Graph.py
--- a/Graph.py	Sat Dec 01 18:17:58 2012 -0600
+++ b/Graph.py	Sun Dec 02 21:51:51 2012 -0600
@@ -192,6 +192,51 @@
             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
@@ -235,6 +280,15 @@
     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