98-99% of computation time is used for the isomorphism tests, so the name of the game is to reduce the number of necessary tests.
Here, I create the graphs in batches such that graphs have to be tested for isomorphisms only within a batch.
In the first variant (version 2 below), all graphs within a batch have the same number of edges. This leads to appreaciable but moderate improvements in running time (2.5 times faster for graphs of size 4, with larger gains in speed for larger graphs).
In the second variant (version 3 below), all graphs within a batch have the same out-degree sequence. This leads to substantial improvements in running time (35 times faster for graphs of size 4, with larger gains in speed for larger graphs).
In the third variant (version 4 below), all graphs within a batch have the same out-degree sequence. Additionally, within a batch all graphs are sorted by in-degree sequence. This leads to modest improvements in speed compared to version 3 (1.3 times faster for graphs of size 4; 2.1 times faster for graphs of size 5).
#!/usr/bin/env python
"""
Efficient motif generation.
"""
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
from timeit import timeit
from itertools import combinations, product, chain, combinations_with_replacement
# for profiling with kernprof/line_profiler
try:
profile
except NameError:
profile = lambda x: x
@profile
def version_1(n):
"""Original implementation by @hilberts_drinking_problem"""
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):
"""Creates graphs in batches, where each batch contains graphs with
the same number of edges. Only graphs within a batch have to be tested
for isomorphisms."""
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
@profile
def version_3(n):
"""Creates graphs in batches, where each batch contains graphs with
the same out-degree sequence. Only graphs within a batch have to be tested
for isomorphisms."""
graphs_so_far = list()
outdegree_sequences_so_far = list()
for outdegree_sequence in product(*[range(n) for _ in range(n)]):
# skip degree sequences which we have already seen as the resulting graphs will be isomorphic
if sorted(outdegree_sequence) not in outdegree_sequences_so_far:
tmp = []
for edges in generate_graphs(outdegree_sequence):
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)
outdegree_sequences_so_far.append(sorted(outdegree_sequence))
return graphs_so_far
def generate_graphs(outdegree_sequence):
"""Generates all directed graphs with a given out-degree sequence."""
for edges in product(*[generate_edges(node, degree, len(outdegree_sequence)) \
for node, degree in enumerate(outdegree_sequence)]):
yield(list(chain(*edges)))
def generate_edges(node, outdegree, total_nodes):
"""Generates all edges for a given node with a given out-degree and a given graph size."""
for targets in combinations(set(range(total_nodes)) - {node}, outdegree):
yield([(node, target) for target in targets])
@profile
def version_4(n):
"""Creates graphs in batches, where each batch contains graphs with
the same out-degree sequence. Within a batch, graphs are sorted
by in-degree sequence, such that only graphs with the same
in-degree sequence have to be tested for isomorphism.
"""
graphs_so_far = list()
for outdegree_sequence in combinations_with_replacement(range(n), n):
tmp = dict()
for edges in generate_graphs(outdegree_sequence):
g = nx.from_edgelist(edges, create_using=nx.DiGraph)
indegree_sequence = tuple(sorted(degree for _, degree in g.in_degree()))
if indegree_sequence in tmp:
if not any(nx.is_isomorphic(g_before, g) for g_before in tmp[indegree_sequence]):
tmp[indegree_sequence].append(g)
else:
tmp[indegree_sequence] = [g]
for graphs in tmp.values():
graphs_so_far.extend(graphs)
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]
t3 = [timeit(lambda : version_3(n), number=3) for n in order]
t4 = [timeit(lambda : version_4(n), number=3) for n in order]
fig, ax = plt.subplots()
for ii, t in enumerate([t1, t2, t3, t4]):
ax.plot(t, label=f"Version no. {ii+1}")
ax.set_yscale('log')
ax.set_ylabel('Execution time [s]')
ax.set_xlabel('Graph order')
ax.legend()
plt.show()
