Package networkx :: Package tests :: Module benchmark
[hide private]
[frames] | no frames]

Source Code for Module networkx.tests.benchmark

  1  from timeit import Timer 
  2   
  3  # This is gratefully modeled after the benchmarks found in  
  4  # the numpy svn repository.  http://svn.scipy.org/svn/numpy/trunk 
  5   
6 -class Benchmark(object):
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 # set up the test string if it is the same for all classes. 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
47 - def run(self):
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 # print "%s: %s" % (name, timer.repeat(self.runs,self.reps)) 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 # set up for all routines: 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 # Choose which tests to run 81 tests=all_tests 82 #tests=all_tests[-1:] 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