comparison ch4ex2.py @ 22:84e183b40c63

Added exercises 1 and 2 from chapter 4.
author Brian Neal <bgneal@gmail.com>
date Mon, 31 Dec 2012 18:58:21 -0600
parents
children
comparison
equal deleted inserted replaced
21:55880b29b4d4 22:84e183b40c63
1 """Section 4.2, exercise 2.
2
3 "The following implementation of a BFS contains two performance errors. What are
4 they? What is the actual order of growth for this algorithm?
5
6 def bfs(top_node, visit):
7 'Breadth-first search on a graph, starting at top_node.'
8 visited = set()
9 queue = [top_node]
10 while len(queue):
11 curr_node = queue.pop(0) # Dequeue
12 visit(curr_node) # Visit the node
13 visited.add(curr_node)
14
15 # Enqueue non-visited and non-enqueued children
16 queue.extend(c for c in curr_node.children
17 if c not in visited and c not in queue)
18
19 Test this code with a range of graph sizes and check your analysis. Then use
20 a FIFO implementation to fix the errors and confirm that your algorithm is
21 linear."
22
23 ----
24
25 I think the 2 performance errors are:
26 1) Using a list as the queue, and popping element 0.
27 2) Doing a linear search to see if the child node is already in the queue.
28
29 To characterize this bfs, I'll inherit from my Graph class and add
30 a flawed_bfs() method which implements the above. I'll then plot both the
31 flawed_bfs and the bfs method I wrote earlier.
32
33 This program tests complete graphs. The flawed_bfs is plotted along with a curve
34 of slope 3, which fits well, and shows that this search is O(|V|^3). Next, the bfs
35 method is plotted with a curve of slope 2, which fits well. This shows that bfs
36 is quadratic, or O(|V|^2), on a complete graph, which is what we expect.
37
38 """
39 import timeit
40 import matplotlib.pyplot as pyplot
41
42 from Graph import Graph, Vertex
43
44
45 class FlawedGraph(Graph):
46
47 def flawed_bfs(self, start, visit=None):
48 """A breadth-first search with performance problems."""
49 visited = set()
50 queue = [start]
51 while len(queue):
52 curr_node = queue.pop(0)
53 if visit:
54 visit(curr_node)
55 visited.add(curr_node)
56
57 queue.extend(c for c in self.out_vertices(curr_node)
58 if c not in visited and c not in queue)
59
60 GRAPH = None
61 METHOD = None
62 V = None
63
64
65 def test_graph_search():
66
67 if METHOD == 'flawed_bfs':
68 GRAPH.flawed_bfs(V)
69 else:
70 GRAPH.bfs(V)
71
72
73 def test_func():
74
75 elapsed = timeit.timeit('test_graph_search()',
76 setup='from __main__ import test_graph_search', number=1)
77 return elapsed
78
79
80 def test(method):
81 """Tests the given function with a range of values for n.
82
83 Returns a list of ns and a list of run times.
84 """
85 global GRAPH, METHOD, V
86
87 METHOD = method
88 factor = 10
89
90 # test (f) over a range of values for (n)
91 ns = []
92 ts = []
93 for i in range(10, 50):
94 n = factor * i
95
96 GRAPH = FlawedGraph()
97 V = None
98 # Add n vertices and connect them
99 for i in range(n):
100 v = Vertex()
101 if not V:
102 V = v
103 GRAPH.add_vertex(v)
104
105 GRAPH.add_all_edges() # make g a complete graph
106
107 t = test_func()
108
109 print n, t
110 ns.append(n)
111 ts.append(t)
112
113 return ns, ts
114
115
116 def plot(ns, ts, label, color='blue', exp=1.0):
117 """Plots data and a fitted curve.
118
119 ns: sequence of n (problem size)
120 ts: sequence of t (run time)
121 label: string label for the data curve
122 color: string color for the data curve
123 exp: exponent (slope) for the fitted curve
124 """
125 tfit = fit(ns, ts, exp)
126 pyplot.plot(ns, tfit, color='0.7', linewidth=2, linestyle='dashed')
127 pyplot.plot(ns, ts, label=label, color=color, linewidth=3)
128
129
130 def fit(ns, ts, exp=1.0, index=-1):
131 """Fits a curve with the given exponent.
132
133 Use the given index as a reference point, and scale all other
134 points accordingly.
135 """
136 nref = ns[index]
137 tref = ts[index]
138
139 tfit = []
140 for n in ns:
141 ratio = float(n) / nref
142 t = ratio**exp * tref
143 tfit.append(t)
144
145 return tfit
146
147
148 def make_fig(funcs):
149 pyplot.clf()
150 pyplot.xscale('log')
151 pyplot.yscale('log')
152 pyplot.title('')
153 pyplot.xlabel('n')
154 pyplot.ylabel('run time (s)')
155
156 colors = ['red', 'green']
157
158 for func, color in zip(funcs, colors):
159 data = test(func)
160 exp = 3.0 if func == 'flawed_bfs' else 2.0
161 plot(*data, label=func, color=color, exp=exp)
162
163 pyplot.legend(loc=4)
164
165 pyplot.show()
166
167
168 def main(script):
169 make_fig(['flawed_bfs', 'bfs'])
170
171
172 if __name__ == '__main__':
173 import sys
174 main(*sys.argv)