1 from timeit import Timer
2
3
4
5
7 """
8 Benchmark a method or simple bit of code using different Graph classes.
9 If the test code is the same for each graph class, then you can set it
10 during instantiation through the argument test_string.
11 The argument test_string can also be a tuple of test code and setup code.
12 The code is entered as a string valid for use with the timeit module.
13
14 Example:
15 >>> b=Benchmark(['Graph','XGraph'])
16 >>> b['Graph']=('G.add_nodes_from(nlist)','nlist=range(100)')
17 >>> b.run()
18 """
19 - def __init__(self,graph_classes,title='',test_string=None,runs=3,reps=1000):
20 self.runs = runs
21 self.reps = reps
22 self.title = title
23 self.class_tests = dict((gc,'') for gc in graph_classes)
24
25 if test_string is not None:
26 if isinstance(test_string,tuple):
27 self['all']=test_string
28 else:
29 self['all']=(test_string,'')
30
31 - def __setitem__(self,graph_class,(test_str,setup_str)):
32 """
33 Set a simple bit of code and setup string for the test.
34 Use this for cases where the code differs from one class to another.
35 """
36 if graph_class == 'all':
37 graph_class = self.class_tests.keys()
38 elif not isinstance(graph_class,list):
39 graph_class = [graph_class]
40
41 for GC in graph_class:
42 setup_string='import networkx as NX\nG=NX.%s.%s()\n'%\
43 (GC.lower(),GC) + setup_str
44 self.class_tests[GC] = Timer(test_str, setup_string)
45
46
48 """Run the benchmark for each class and print results."""
49 column_len = max(len(G) for G in self.class_tests)
50
51 print '='*72
52 if self.title:
53 print "%s: %s runs, %s reps"% (self.title,self.runs,self.reps)
54 print '='*72
55
56 times=[]
57 for GC,timer in self.class_tests.items():
58 name = GC.ljust(column_len)
59 try:
60 t=sum(timer.repeat(self.runs,self.reps))/self.runs
61
62 times.append((t,name))
63 except Exception, e:
64 print "%s: Failed to benchmark (%s)." % (name,e)
65
66
67 times.sort()
68 tmin=times[0][0]
69 for t,name in times:
70 print "%s: %5.2f %s" % (name, t/tmin*100.,t)
71 print '-'*72
72 print
73
74 if __name__ == "__main__":
75
76 classes=['Graph','XGraph','DiGraph','XDiGraph']
77 all_tests=['add_nodes','add_edges','delete_nodes','delete_edges',\
78 'neighbors','edges','degree','dijkstra','shortest path',\
79 'subgraph','laplacian']
80
81 tests=all_tests
82
83 N=100
84
85 if 'add_nodes' in tests:
86 title='Benchmark: Adding nodes'
87 test_string=('G.add_nodes_from(nlist)','nlist=range(%i)'%N)
88 b=Benchmark(classes,title,test_string,runs=3,reps=1000)
89 b.run()
90
91 if 'add_edges' in tests:
92 title='Benchmark: Adding edges'
93 setup='elist=[(i,i+3) for i in range(%s-3)]\nG.add_nodes_from(range(%i))'%(N,N)
94 test_string=('G.add_edges_from(elist)',setup)
95 b=Benchmark(classes,title,test_string,runs=3,reps=1000)
96 b.run()
97
98 if 'delete_nodes' in tests:
99 title='Benchmark: Adding and Deleting nodes'
100 setup='nlist=range(%i)'%N
101 test_string=('G.add_nodes_from(nlist)\nG.delete_nodes_from(nlist)',setup)
102 b=Benchmark(classes,title,test_string,runs=3,reps=1000)
103 b.run()
104
105 if 'delete_edges' in tests:
106 title='Benchmark: Adding and Deleting edges'
107 setup='elist=[(i,i+3) for i in range(%s-3)]'%N
108 test_string=('G.add_edges_from(elist)\nG.delete_edges_from(elist)',setup)
109 b=Benchmark(classes,title,test_string,runs=3,reps=1000)
110 b.run()
111
112 if 'neighbors' in tests:
113 N=500
114 p=0.3
115 title='Benchmark: reporting neighbors'
116 b=Benchmark(classes,title,runs=3,reps=1)
117 test_string='for n in G:\n for nbr in G.neighbors(n):\n pass'
118 all_setup='H=NX.binomial_graph(%s,%s)\nfor (u,v) in H.edges_iter():\n '%(N,p)
119 setup=all_setup+'G.add_edge(u,v)\n'
120 b['Graph']=(test_string,setup)
121 setup=all_setup+'G.add_edges_from([(u,v),(v,u)])'
122 b['DiGraph']=(test_string,setup)
123 setup=all_setup+'G.add_edge(u,v,1)'
124 b['XGraph']=(test_string,setup)
125 setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])'
126 b['XDiGraph']=(test_string,setup)
127 b.run()
128
129 if 'edges' in tests:
130 N=500
131 p=0.3
132 title='Benchmark: reporting edges'
133 b=Benchmark(classes,title,runs=3,reps=1)
134 test_string='for n in G:\n for e in G.edges(n):\n pass'
135 all_setup='H=NX.binomial_graph(%s,%s)\nfor (u,v) in H.edges_iter():\n '%(N,p)
136 setup=all_setup+'G.add_edge(u,v)\n'
137 b['Graph']=(test_string,setup)
138 setup=all_setup+'G.add_edges_from([(u,v),(v,u)])'
139 b['DiGraph']=(test_string,setup)
140 setup=all_setup+'G.add_edge(u,v,1)'
141 b['XGraph']=(test_string,setup)
142 setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])'
143 b['XDiGraph']=(test_string,setup)
144 b.run()
145
146 if 'degree' in tests:
147 N=500
148 p=0.3
149 title='Benchmark: reporting degree'
150 b=Benchmark(classes,title,runs=3,reps=1)
151 test_string='for d in G.degree():\n pass'
152 all_setup='H=NX.binomial_graph(%s,%s)\nfor (u,v) in H.edges_iter():\n '%(N,p)
153 setup=all_setup+'G.add_edge(u,v)\n'
154 b['Graph']=(test_string,setup)
155 setup=all_setup+'G.add_edges_from([(u,v),(v,u)])'
156 b['DiGraph']=(test_string,setup)
157 setup=all_setup+'G.add_edge(u,v,1)'
158 b['XGraph']=(test_string,setup)
159 setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])'
160 b['XDiGraph']=(test_string,setup)
161 b.run()
162
163 if 'dijkstra' in tests:
164 N=500
165 p=0.3
166 title='dijkstra single source shortest path'
167 b=Benchmark(classes,title,runs=3,reps=1)
168 test_string='p=NX.single_source_dijkstra(G,i)'
169 all_setup='i=6\nH=NX.binomial_graph(%s,%s)\nfor (u,v) in H.edges_iter():\n '%(N,p)
170 setup=all_setup+'G.add_edge(u,v)'
171 b['Graph']=(test_string,setup)
172 setup=all_setup+'G.add_edges_from([(u,v),(v,u)])'
173 b['DiGraph']=(test_string,setup)
174 setup=all_setup+'G.add_edge(u,v,1)'
175 b['XGraph']=(test_string,setup)
176 setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])'
177 b['XDiGraph']=(test_string,setup)
178 b.run()
179
180 if 'shortest path' in tests:
181 N=500
182 p=0.3
183 title='single source shortest path'
184 b=Benchmark(classes,title,runs=3,reps=1)
185 test_string='p=NX.single_source_shortest_path(G,i)'
186 all_setup='i=6\nH=NX.binomial_graph(%s,%s)\nfor (u,v) in H.edges_iter():\n '%(N,p)
187 setup=all_setup+'G.add_edge(u,v)'
188 b['Graph']=(test_string,setup)
189 setup=all_setup+'G.add_edges_from([(u,v),(v,u)])'
190 b['DiGraph']=(test_string,setup)
191 setup=all_setup+'G.add_edge(u,v,1)'
192 b['XGraph']=(test_string,setup)
193 setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])'
194 b['XDiGraph']=(test_string,setup)
195 b.run()
196
197 if 'subgraph' in tests:
198 N=500
199 p=0.3
200 title='subgraph method'
201 b=Benchmark(classes,title,runs=3,reps=1)
202 test_string='G.subgraph(nlist)'
203 all_setup='nlist=range(100,150)\nH=NX.binomial_graph(%s,%s)\nfor (u,v) in H.edges_iter():\n '%(N,p)
204 setup=all_setup+'G.add_edge(u,v)'
205 b['Graph']=(test_string,setup)
206 setup=all_setup+'G.add_edges_from([(u,v),(v,u)])'
207 b['DiGraph']=(test_string,setup)
208 setup=all_setup+'G.add_edge(u,v,1)'
209 b['XGraph']=(test_string,setup)
210 setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])'
211 b['XDiGraph']=(test_string,setup)
212 b.run()
213
214 if 'laplacian' in tests:
215 N=500
216 p=0.3
217 title='creation of laplacian matrix'
218 b=Benchmark(classes,title,runs=3,reps=1)
219 test_string='NX.laplacian(G)'
220 all_setup='H=NX.binomial_graph(%s,%s)\nfor (u,v) in H.edges_iter():\n '%(N,p)
221 setup=all_setup+'G.add_edge(u,v)'
222 b['Graph']=(test_string,setup)
223 setup=all_setup+'G.add_edges_from([(u,v),(v,u)])'
224 b['DiGraph']=(test_string,setup)
225 setup=all_setup+'G.add_edge(u,v,1)'
226 b['XGraph']=(test_string,setup)
227 setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])'
228 b['XDiGraph']=(test_string,setup)
229 b.run()
230