Last active
July 8, 2022 18:37
-
-
Save dschult/baa5fd69d81304d4959cee9d3a1443de to your computer and use it in GitHub Desktop.
A script to time simple operations with various graph classes. The output is just text tables of the timing results. The code itself is pretty ugly, but it gets the job done.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from timeit import Timer | |
# This is gratefully modeled after the benchmarks found in | |
# the numpy svn repository. http://svn.scipy.org/svn/numpy/trunk | |
import networkx as nx | |
class Benchmark(object): | |
""" | |
Benchmark a method or simple bit of code using different Graph classes. | |
If the test code is the same for each graph class, then you can set it | |
during instantiation through the argument test_string. | |
The argument test_string can also be a tuple of test code and setup code. | |
The code is entered as a string valid for use with the timeit module. | |
Example: | |
>>> b=Benchmark(['Graph','XGraph']) | |
>>> b['Graph']=('G.add_nodes_from(nlist)','nlist=range(100)') | |
>>> b.run() | |
""" | |
def __init__(self,graph_classes,title='',test_string=None,runs=7,reps=1000): | |
self.runs = runs | |
self.reps = reps | |
self.title = title | |
self.class_tests = dict((gc,'') for gc in graph_classes) | |
# set up the test string if it is the same for all classes. | |
if test_string is not None: | |
if isinstance(test_string,tuple): | |
self['all']=test_string | |
else: | |
self['all']=(test_string,'') | |
def __setitem__(self, graph_class, inputs): | |
""" | |
Set a simple bit of code and setup string for the test. | |
Use this for cases where the code differs from one class to another. | |
""" | |
test_str, setup_str = inputs | |
self.setup_str = setup_str | |
self.test_str = test_str | |
if graph_class == 'all': | |
graph_class = self.class_tests.keys() | |
elif not isinstance(graph_class,list): | |
graph_class = [graph_class] | |
for GC in graph_class: | |
if "CachedGraph" in GC: | |
GCmodule = "graph" | |
else: | |
GCmodule = GC | |
setup_string='import networkx as NX\nG=NX.%s.%s()\n'%\ | |
(GCmodule.lower(),GC) + setup_str | |
self.class_tests[GC] = Timer(test_str, setup_string) | |
def run(self): | |
"""Run the benchmark for each class and print results.""" | |
column_len = max(len(G) for G in self.class_tests) | |
print('='*72) | |
if self.title: | |
#print("%s: %s runs, %s reps"% (self.title,self.runs,self.reps)) | |
print(f"{self.title}: {self.reps} reps, min of {self.runs} runs") | |
print(f"setup:--------------------\n{self.setup_str}") | |
print(f"test :--------------------\n{self.test_str}") | |
print( '='*72) | |
times=[] | |
for GC,timer in self.class_tests.items(): | |
name = GC.ljust(column_len) | |
try: | |
#t=sum(timer.repeat(self.runs,self.reps))/self.runs | |
t=min(timer.repeat(self.runs,self.reps)) | |
# print( "%s: %s" % (name, timer.repeat(self.runs,self.reps)) | |
times.append((t,name)) | |
except Exception as e: | |
raise | |
print( "%s: Failed to benchmark (%s)." % (name,e)) | |
#times.sort() | |
tmin=times[0][0] | |
for t,name in times: | |
print( "%s: %5.1f%% %12.3e" % (name, t/tmin*100.,t)) | |
print('-'*72) | |
print() | |
if __name__ == "__main__": | |
# set up for all routines: | |
classes=['Graph','MultiGraph','DiGraph','MultiDiGraph'] | |
classes=["CachedGraphProperties", | |
"CachedGraphDataDescriptor", | |
"CachedGraphSetattr", | |
"CachedGraphSetOnlyDataDescriptor", | |
"CachedGraphSetOnlyDataDescriptorTextName", | |
] | |
classes=['CachedGraphProperties','CachedGraphDataDescriptor','CachedGraphSetattr','CachedGraphSetOnlyDataDescriptor','CachedGraphSetOnlyDataDescriptorTextName'] | |
all_tests=['add_nodes','add_edges','remove_nodes','remove_edges',\ | |
'neighbors','copy','edges','edges_incident','degree','dijkstra','shortest path',\ | |
'subgraph','laplacian'] | |
# Choose which tests to run | |
tests=all_tests | |
# tests=['degree'] | |
tests=['add_nodes','add_edges','remove_nodes','remove_edges',\ | |
'copy', 'neighbors','edges','set_foo'] | |
# tests=['add_nodes','add_edges', 'copy', 'neighbors','edges'] | |
# tests=['add_edges', 'copy', 'neighbors','create'] | |
tests=['create', 'set_adj', 'get_adj', 'neighbors', 'add_edges', 'set_foo', 'copy'] | |
# tests=['edges'] | |
#tests=all_tests[-1:] | |
N=100 | |
R=7 # runs | |
REPS=100000 | |
if 'add_nodes' in tests: | |
title='Benchmark: Adding nodes' | |
test_string=('G.add_nodes_from(nlist)','nlist=range(%i)'%N) | |
b=Benchmark(classes,title,test_string,runs=R,reps=REPS) | |
b.run() | |
if 'add_edges' in tests: | |
title='Benchmark: Adding edges' | |
setup='elist=[(i,i+3) for i in range(%s-3)]\nG.add_nodes_from(range(%i))'%(N,N) | |
test_string=('G.add_edges_from(elist)',setup) | |
b=Benchmark(classes,title,test_string,runs=R,reps=REPS) | |
b.run() | |
if 'remove_nodes' in tests: | |
title='Benchmark: Adding and Deleting nodes' | |
setup='nlist=range(%i)'%N | |
test_string=('G.add_nodes_from(nlist)\nG.remove_nodes_from(nlist)',setup) | |
b=Benchmark(classes,title,test_string,runs=R,reps=REPS) | |
b.run() | |
if 'remove_edges' in tests: | |
title='Benchmark: Adding and Deleting edges' | |
setup='elist=[(i,i+3) for i in range(%s-3)]'%N | |
test_string=('G.add_edges_from(elist)\nG.remove_edges_from(elist)',setup) | |
b=Benchmark(classes,title,test_string,runs=R,reps=REPS) | |
b.run() | |
if 'getadj' in tests: | |
title='Benchmark: Graph.adj' | |
setup='NX.add_path(G, range(%s))\nG.adj'%N | |
test_string=('G.adj',setup) | |
b=Benchmark(classes,title,test_string,runs=30,reps=REPS) | |
b.run() | |
if 'get_adj' in tests: | |
title='Benchmark: Graph._adj' | |
setup='NX.add_path(G, range(%s))'%N | |
test_string=('G._adj',setup) | |
b=Benchmark(classes,title,test_string,runs=30,reps=REPS) | |
b.run() | |
if 'set_adj' in tests: | |
title='Benchmark: reset Graph._adj' | |
setup='NX.add_path(G, range(%s))\nG.adj'%N | |
test_string='G._adj={}' | |
test_pair=(test_string, setup) | |
b=Benchmark(classes,title,test_pair,runs=30,reps=REPS) | |
if "Graph" in classes: | |
this_test = test_string+'\nif "adj" in G.__dict__:\n del G.__dict__["adj"]' | |
b["Graph"]=(this_test, setup) | |
b.run() | |
if 'set_foo' in tests: | |
title='Benchmark: Graph.foo=4' | |
setup='NX.add_path(G, range(%s))'%N | |
test_string=('G.foo=4',setup) | |
b=Benchmark(classes,title,test_string,runs=30,reps=REPS) | |
b.run() | |
if 'create' in tests: | |
title='Benchmark: create Graph' | |
setup='MyGraph=G.__class__' | |
test_string=('MyGraph()',setup) | |
b=Benchmark(classes,title,test_string,runs=30,reps=REPS) | |
b.run() | |
if 'copy' in tests: | |
title='Benchmark: Copy Graph' | |
setup='elist=[(i,i+3) for i in range(%s-3)]'%N | |
test_string=('G.copy()',setup) | |
b=Benchmark(classes,title,test_string,runs=30,reps=REPS) | |
b.run() | |
if 'neighbors' in tests: | |
N=500 | |
p=0.3 | |
title='Benchmark: reporting neighbors' | |
all_setup='H=NX.binomial_graph(%s,%s,seed=42)\nfor (u,v) in H.edges():\n '%(N,p) | |
setup=all_setup+'G.add_edge(u,v)\n' | |
test_string='for n in G:\n for nbr in G.neighbors(n):\n pass' | |
test_pair=(test_string, setup) | |
b=Benchmark(classes,title,test_pair,runs=R,reps=1000) | |
if 'DiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v),(v,u)])' | |
b['DiGraph']=(test_string,setup) | |
if 'MultiGraph' in classes: | |
setup=all_setup+'G.add_edge(u,v,1)' | |
b['MultiGraph']=(test_string,setup) | |
if 'MultiDiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])' | |
b['MultiDiGraph']=(test_string,setup) | |
b.run() | |
if 'edges_incident' in tests: | |
N=500 | |
p=0.3 | |
title='Benchmark: reporting edges incident to each node' | |
test_string='for n in G:\n for e in G.edges(n):\n pass' | |
all_setup='H=NX.binomial_graph(%s,%s,seed=42)\nfor (u,v) in H.edges():\n '%(N,p) | |
setup=all_setup+'G.add_edge(u,v)\n' | |
b=Benchmark(classes,title,(test_string,setup),runs=R,reps=1000) | |
if 'DiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v),(v,u)])' | |
b['DiGraph']=(test_string,setup) | |
if 'MultiGraph' in classes: | |
setup=all_setup+'G.add_edge(u,v,1)' | |
b['MultiGraph']=(test_string,setup) | |
if 'MultiDiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])' | |
b['MultiDiGraph']=(test_string,setup) | |
b.run() | |
if 'edges' in tests: | |
N=500 | |
p=0.3 | |
title='Benchmark: reporting edges of whole graph' | |
test_string='G.edges()' | |
all_setup='H=NX.binomial_graph(%s,%s,seed=42)\nfor (u,v) in H.edges():\n '%(N,p) | |
setup=all_setup+'G.add_edge(u,v)\n' | |
b=Benchmark(classes,title,(test_string,setup),runs=R,reps=1000) | |
if 'DiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v),(v,u)])' | |
b['DiGraph']=(test_string,setup) | |
if 'MultiGraph' in classes: | |
setup=all_setup+'G.add_edge(u,v,1)' | |
b['MultiGraph']=(test_string,setup) | |
if 'MultiDiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])' | |
b['MultiDiGraph']=(test_string,setup) | |
b.run() | |
if 'degree' in tests: | |
N=500 | |
p=0.3 | |
title='Benchmark: reporting degree' | |
test_string='for d in G.degree():\n pass' | |
all_setup='H=NX.binomial_graph(%s,%s,seed=42)\nfor (u,v) in H.edges():\n '%(N,p) | |
setup=all_setup+'G.add_edge(u,v)\n' | |
b=Benchmark(classes,title,(test_string,setup),runs=R,reps=1000) | |
if 'DiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v),(v,u)])' | |
b['DiGraph']=(test_string,setup) | |
if 'MultiGraph' in classes: | |
setup=all_setup+'G.add_edge(u,v,1)' | |
b['MultiGraph']=(test_string,setup) | |
if 'MultiDiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])' | |
b['MultiDiGraph']=(test_string,setup) | |
b.run() | |
if 'dijkstra' in tests: | |
N=500 | |
p=0.3 | |
title='dijkstra single source shortest path' | |
test_string='p=NX.single_source_dijkstra(G,i)' | |
all_setup='i=6\nH=NX.binomial_graph(%s,%s,seed=42)\nfor (u,v) in H.edges():\n '%(N,p) | |
setup=all_setup+'G.add_edge(u,v)' | |
b=Benchmark(classes,title,(test_string,setup),runs=R,reps=10) | |
if 'DiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v),(v,u)])' | |
b['DiGraph']=(test_string,setup) | |
if 'MultiGraph' in classes: | |
setup=all_setup+'G.add_edge(u,v,1)' | |
b['MultiGraph']=(test_string,setup) | |
if 'MultiDiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])' | |
b['MultiDiGraph']=(test_string,setup) | |
b.run() | |
if 'shortest path' in tests: | |
N=500 | |
p=0.3 | |
title='single source shortest path' | |
test_string='p=NX.single_source_shortest_path(G,i)' | |
all_setup='i=6\nH=NX.binomial_graph(%s,%s,seed=42)\nfor (u,v) in H.edges():\n '%(N,p) | |
setup=all_setup+'G.add_edge(u,v)' | |
b=Benchmark(classes,title,(test_string,setup),runs=R,reps=10) | |
if 'DiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v),(v,u)])' | |
b['DiGraph']=(test_string,setup) | |
if 'MultiGraph' in classes: | |
setup=all_setup+'G.add_edge(u,v,1)' | |
b['MultiGraph']=(test_string,setup) | |
if 'MultiDiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])' | |
b['MultiDiGraph']=(test_string,setup) | |
b.run() | |
if 'subgraph' in tests: | |
N=500 | |
p=0.3 | |
title='subgraph method' | |
test_string='G.subgraph(nlist)' | |
all_setup='nlist=range(100,150)\nH=NX.binomial_graph(%s,%s,seed=42)\nfor (u,v) in H.edges():\n '%(N,p) | |
setup=all_setup+'G.add_edge(u,v)' | |
b=Benchmark(classes,title,(test_string,setup),runs=R,reps=10) | |
if 'DiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v),(v,u)])' | |
b['DiGraph']=(test_string,setup) | |
if 'MultiGraph' in classes: | |
setup=all_setup+'G.add_edge(u,v,1)' | |
b['MultiGraph']=(test_string,setup) | |
if 'MultiDiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])' | |
b['MultiDiGraph']=(test_string,setup) | |
b.run() | |
if 'laplacian' in tests: | |
N=500 | |
p=0.3 | |
title='creation of laplacian matrix' | |
test_string='NX.directed_laplacian_matrix if G.is_directed() else NX.laplacian_matrix(G)' | |
all_setup='H=NX.binomial_graph(%s,%s,seed=42)\nfor (u,v) in H.edges():\n '%(N,p) | |
setup=all_setup+'G.add_edge(u,v)' | |
b=Benchmark(classes,title,(test_string,setup),runs=R,reps=10) | |
if 'DiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v),(v,u)])' | |
b['DiGraph']=(test_string,setup) | |
if 'MultiGraph' in classes: | |
setup=all_setup+'G.add_edge(u,v,1)' | |
b['MultiGraph']=(test_string,setup) | |
if 'MultiDiGraph' in classes: | |
setup=all_setup+'G.add_edges_from([(u,v,1),(v,u,1)])' | |
b['MultiDiGraph']=(test_string,setup) | |
b.run() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
======================================================================== | |
Benchmark: Adding edges: 100000 reps, min of 7 runs | |
setup:-------------------- | |
elist=[(i,i+3) for i in range(100-3)] | |
G.add_nodes_from(range(100)) | |
test :-------------------- | |
G.add_edges_from(elist) | |
======================================================================== | |
CachedGraphProperties : 100.0% 8.332e+00 | |
CachedGraphDataDescriptor : 105.2% 8.764e+00 | |
CachedGraphSetattr : 64.9% 5.403e+00 | |
CachedGraphSetOnlyDataDescriptor : 67.9% 5.657e+00 | |
CachedGraphSetOnlyDataDescriptorTextName: 67.7% 5.641e+00 | |
------------------------------------------------------------------------ | |
======================================================================== | |
Benchmark: Graph._adj: 100000 reps, min of 30 runs | |
setup:-------------------- | |
NX.add_path(G, range(100)) | |
test :-------------------- | |
G._adj | |
======================================================================== | |
CachedGraphProperties : 100.0% 1.089e-02 | |
CachedGraphDataDescriptor : 113.0% 1.230e-02 | |
CachedGraphSetattr : 29.3% 3.194e-03 | |
CachedGraphSetOnlyDataDescriptor : 31.0% 3.371e-03 | |
CachedGraphSetOnlyDataDescriptorTextName: 29.9% 3.253e-03 | |
------------------------------------------------------------------------ | |
======================================================================== | |
Benchmark: reset Graph._adj: 100000 reps, min of 30 runs | |
setup:-------------------- | |
NX.add_path(G, range(100)) | |
G.adj | |
test :-------------------- | |
G._adj={} | |
======================================================================== | |
CachedGraphProperties : 100.0% 1.829e-02 | |
CachedGraphDataDescriptor : 93.6% 1.712e-02 | |
CachedGraphSetattr : 121.2% 2.218e-02 | |
CachedGraphSetOnlyDataDescriptor : 147.3% 2.694e-02 | |
CachedGraphSetOnlyDataDescriptorTextName: 94.7% 1.732e-02 | |
------------------------------------------------------------------------ | |
======================================================================== | |
Benchmark: Graph.foo=4: 100000 reps, min of 30 runs | |
setup:-------------------- | |
NX.add_path(G, range(100)) | |
test :-------------------- | |
G.foo=4 | |
======================================================================== | |
CachedGraphProperties : 100.0% 4.317e-03 | |
CachedGraphDataDescriptor : 97.7% 4.219e-03 | |
CachedGraphSetattr : 425.7% 1.838e-02 | |
CachedGraphSetOnlyDataDescriptor : 103.0% 4.445e-03 | |
CachedGraphSetOnlyDataDescriptorTextName: 99.3% 4.287e-03 | |
------------------------------------------------------------------------ | |
======================================================================== | |
Benchmark: create Graph: 100000 reps, min of 30 runs | |
setup:-------------------- | |
MyGraph=G.__class__ | |
test :-------------------- | |
MyGraph() | |
======================================================================== | |
CachedGraphProperties : 100.0% 1.022e-01 | |
CachedGraphDataDescriptor : 98.5% 1.006e-01 | |
CachedGraphSetattr : 237.5% 2.427e-01 | |
CachedGraphSetOnlyDataDescriptor : 115.6% 1.181e-01 | |
CachedGraphSetOnlyDataDescriptorTextName: 105.5% 1.078e-01 | |
------------------------------------------------------------------------ | |
======================================================================== | |
Benchmark: Copy Graph: 100000 reps, min of 30 runs | |
setup:-------------------- | |
elist=[(i,i+3) for i in range(100-3)] | |
test :-------------------- | |
G.copy() | |
======================================================================== | |
CachedGraphProperties : 100.0% 2.430e-01 | |
CachedGraphDataDescriptor : 91.8% 2.232e-01 | |
CachedGraphSetattr : 143.5% 3.487e-01 | |
CachedGraphSetOnlyDataDescriptor : 94.9% 2.307e-01 | |
CachedGraphSetOnlyDataDescriptorTextName: 87.6% 2.130e-01 | |
------------------------------------------------------------------------ | |
======================================================================== | |
Benchmark: reporting neighbors: 1000 reps, min of 7 runs | |
setup:-------------------- | |
H=NX.binomial_graph(500,0.3,seed=42) | |
for (u,v) in H.edges(): | |
G.add_edge(u,v) | |
test :-------------------- | |
for n in G: | |
for nbr in G.neighbors(n): | |
pass | |
======================================================================== | |
CachedGraphProperties : 100.0% 9.660e-01 | |
CachedGraphDataDescriptor : 102.6% 9.914e-01 | |
CachedGraphSetattr : 85.5% 8.258e-01 | |
CachedGraphSetOnlyDataDescriptor : 86.5% 8.360e-01 | |
CachedGraphSetOnlyDataDescriptorTextName: 89.0% 8.601e-01 | |
------------------------------------------------------------------------ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment