The 
#!/usr/bin/env python
"""
Efficient motif generation.
"""
from timeit import timeit
from itertools import combinations, product
import matplotlib.pyplot as plt
import networkx as nx
# for profiling with kernprof/line_profiler
try:
profile
except NameError:
profile = lambda x: x
@profile
def version_1(n):
graphs_so_far = list()
nodes = list(range(n))
possible_edges = [(i, j) for i, j in product(nodes, nodes) if i != j]
for edge_mask in product([True, False], repeat=len(possible_edges)):
edges = [edge for include, edge in zip(edge_mask, possible_edges) if include]
g = nx.DiGraph()
g.add_nodes_from(nodes)
g.add_edges_from(edges)
if not any(nx.is_isomorphic(g_before, g) for g_before in graphs_so_far):
graphs_so_far.append(g)
return graphs_so_far
@profile
def version_2(n):
graphs_so_far = list()
nodes = list(range(n))
possible_edges = [(i, j) for i, j in product(nodes, nodes) if i != j]
for ii in range(len(possible_edges) 1):
tmp = []
for edges in combinations(possible_edges, ii):
g = nx.from_edgelist(edges, create_using=nx.DiGraph)
if not any(nx.is_isomorphic(g_before, g) for g_before in tmp):
tmp.append(g)
graphs_so_far.extend(tmp)
return graphs_so_far
if __name__ == '__main__':
order = range(1, 5)
t1 = [timeit(lambda : version_1(n), number=3) for n in order]
t2 = [timeit(lambda : version_2(n), number=3) for n in order]
fig, ax = plt.subplots()
ax.plot(np.array(t1) / np.array(t2))
ax.set_ylabel('Execution time v1/v2')
ax.set_xlabel('Graph order')
plt.show()
