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)