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