0
420
ViewsGenerate all digraphs of a given size up to isomorphism
I am trying to generate all directed graphs with a given number of nodes up to graph isomorphism so that I can feed them into another Python program. Here is a naive reference implementation using NetworkX, I would like to speed it up:
from itertools import combinations, product
import networkx as nx
def generate_digraphs(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
assert len(generate_digraphs(1)) == 1
assert len(generate_digraphs(2)) == 3
assert len(generate_digraphs(3)) == 16
The number of such graphs seems to grow pretty quickly and is given by this OEIS sequence. I am looking for a solution that is able to generate all graphs up to 7 nodes (about a billion graphs in total) in a reasonable amount of time.
Representing a graph as a NetworkX object is not very important; for example, representing a graph with an adjacency list or using a different library is good with me.
1 answers
Answer question0
Instead of using nx.is_isomorphic to compare two graphs G1 and G2, you could also generate all graphs that are isomorphic to G1 and check if the G2 is in this set.
At first, this sounds more cumbersome, but it allows you to not just check if G2 is isomorphic to G1, but also if any graph is isomorphic to G1, whereas nx.is_isomorphic always starts from scratch when comparing two graphs.
To make things easier each graph is just stored as a list of edges.
Two graphs are the same (not isomorphic) if the set of all edges is the same.
Always making sure the list of edges is a sorted tuple makes it so that == tests for exactly that equality and makes the edge lists hashable.
import itertools
def all_digraphs(n):
possible_edges = [
(i, j) for i, j in itertools.product(range(n), repeat=2) if i != j
]
for edge_mask in itertools.product([True, False], repeat=len(possible_edges)):
# The result is already sorted
yield tuple(edge for include, edge in zip(edge_mask, possible_edges) if include)
def unique_digraphs(n):
already_seen = set()
for graph in all_digraphs(n):
if graph not in already_seen:
yield graph
already_seen |= {
tuple(sorted((perm[i], perm[j]) for i, j in graph))
for perm in itertools.permutations(range(n))
}
Compared to the variants from the previous solution this gives the following timings on my machine:
This all looks quite promising, but already for 6 nodes my 16GiB of memory is not enough and the Python process is terminated by the operating system.
I'm sure you can combine this code with generating the graphs in batches for each outdegree_sequence as detailed in the previous answer.
This would allow one to empty already_seen after each batch and reduce the memory consumption drastically.