--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ch4ex2.py	Mon Dec 31 18:58:21 2012 -0600
@@ -0,0 +1,174 @@
+"""Section 4.2, exercise 2.
+
+"The following implementation of a BFS contains two performance errors. What are
+they? What is the actual order of growth for this algorithm?
+
+def bfs(top_node, visit):
+    'Breadth-first search on a graph, starting at top_node.'
+    visited = set()
+    queue = [top_node]
+    while len(queue):
+        curr_node = queue.pop(0)    # Dequeue
+        visit(curr_node)            # Visit the node
+        visited.add(curr_node)
+
+        # Enqueue non-visited and non-enqueued children
+        queue.extend(c for c in curr_node.children
+                     if c not in visited and c not in queue)
+
+Test this code with a range of graph sizes and check your analysis. Then use
+a FIFO implementation to fix the errors and confirm that your algorithm is
+linear."
+
+----
+
+I think the 2 performance errors are:
+    1) Using a list as the queue, and popping element 0.
+    2) Doing a linear search to see if the child node is already in the queue.
+
+To characterize this bfs, I'll inherit from my Graph class and add
+a flawed_bfs() method which implements the above. I'll then plot both the
+flawed_bfs and the bfs method I wrote earlier.
+
+This program tests complete graphs. The flawed_bfs is plotted along with a curve
+of slope 3, which fits well, and shows that this search is O(|V|^3). Next, the bfs
+method is plotted with a curve of slope 2, which fits well. This shows that bfs
+is quadratic, or O(|V|^2), on a complete graph, which is what we expect.
+
+"""
+import timeit
+import matplotlib.pyplot as pyplot
+
+from Graph import Graph, Vertex
+
+
+class FlawedGraph(Graph):
+
+    def flawed_bfs(self, start, visit=None):
+        """A breadth-first search with performance problems."""
+        visited = set()
+        queue = [start]
+        while len(queue):
+            curr_node = queue.pop(0)
+            if visit:
+                visit(curr_node)
+            visited.add(curr_node)
+
+            queue.extend(c for c in self.out_vertices(curr_node)
+                            if c not in visited and c not in queue)
+
+GRAPH = None
+METHOD = None
+V = None
+
+
+def test_graph_search():
+
+    if METHOD == 'flawed_bfs':
+        GRAPH.flawed_bfs(V)
+    else:
+        GRAPH.bfs(V)
+
+
+def test_func():
+
+    elapsed = timeit.timeit('test_graph_search()',
+        setup='from __main__ import test_graph_search', number=1)
+    return elapsed
+
+
+def test(method):
+    """Tests the given function with a range of values for n.
+
+    Returns a list of ns and a list of run times.
+    """
+    global GRAPH, METHOD, V
+
+    METHOD = method
+    factor = 10
+
+    # test (f) over a range of values for (n)
+    ns = []
+    ts = []
+    for i in range(10, 50):
+        n = factor * i
+
+        GRAPH = FlawedGraph()
+        V = None
+        # Add n vertices and connect them
+        for i in range(n):
+            v = Vertex()
+            if not V:
+                V = v
+            GRAPH.add_vertex(v)
+
+        GRAPH.add_all_edges()   # make g a complete graph
+
+        t = test_func()
+
+        print n, t
+        ns.append(n)
+        ts.append(t)
+
+    return ns, ts
+
+
+def plot(ns, ts, label, color='blue', exp=1.0):
+    """Plots data and a fitted curve.
+
+    ns: sequence of n (problem size)
+    ts: sequence of t (run time)
+    label: string label for the data curve
+    color: string color for the data curve
+    exp: exponent (slope) for the fitted curve
+    """
+    tfit = fit(ns, ts, exp)
+    pyplot.plot(ns, tfit, color='0.7', linewidth=2, linestyle='dashed')
+    pyplot.plot(ns, ts, label=label, color=color, linewidth=3)
+
+
+def fit(ns, ts, exp=1.0, index=-1):
+    """Fits a curve with the given exponent.
+
+    Use the given index as a reference point, and scale all other
+    points accordingly.
+    """
+    nref = ns[index]
+    tref = ts[index]
+
+    tfit = []
+    for n in ns:
+        ratio = float(n) / nref
+        t = ratio**exp * tref
+        tfit.append(t)
+
+    return tfit
+
+
+def make_fig(funcs):
+    pyplot.clf()
+    pyplot.xscale('log')
+    pyplot.yscale('log')
+    pyplot.title('')
+    pyplot.xlabel('n')
+    pyplot.ylabel('run time (s)')
+
+    colors = ['red', 'green']
+
+    for func, color in zip(funcs, colors):
+        data = test(func)
+        exp = 3.0 if func == 'flawed_bfs' else 2.0
+        plot(*data, label=func, color=color, exp=exp)
+
+    pyplot.legend(loc=4)
+
+    pyplot.show()
+
+
+def main(script):
+    make_fig(['flawed_bfs', 'bfs'])
+
+
+if __name__ == '__main__':
+    import sys
+    main(*sys.argv)