Enumerate graphs under edge and symmetry constraints

Question

I would like to create the set of all directed graphs with n vertices where each vertex has k direct successors and k direct predecessors. n and k won't be that large, rather around n = 8 and k = 3. The set includes cyclic and acyclic graphs. Each graph in turn will serve as a template for sampling a large number of weighted graphs.

My interest is in the role of topology motifs so I don't want to sample weights for any two graphs that are symmetric to each other, where symmetry means that no permutation of vertices exists in one graph that transforms it into the other.

A naive solution would be to consider the 2 ^ (n * (n - 1)) adjacency matrices and eliminate all those (most of them) for which direct successor or predecessor constraints are violated. For n = 8, that's still few enough bits to represent and simply enumerate each matrix comfortably inside a uint64_t.

Keeping track of row counts and column counts would be another improvement, but the real bottleneck will be adding the graph to the result set, at which point we need to test for symmetry against each other graph that's already in the set. For n = 8 that would be already more than 40,000 permutations per insert operation.

Could anyone refer me to an algorithm that I could read up on that can do all this in a smarter way? Is there a graph library for C, C++, Java, or Python that already implements such a comprehensive graph generator? Is there a repository where someone has already "tabulated" all graphs for reasonable n and k?

Answer 1

Graph isomorphism is, in my opinion, not something you should be thinking about implementing yourself. I believe the current state-of-the-art is Brendan McKay's Nauty (and associated programs/libraries). It's a bit of a bear to work with, but it may be worth it to avoid doing your own, naive graph isomorphism. Also, it's primarily geared towards undirected graphs, but it can do digraphs as well. You may want to check out the geng (which generates undirected graphs) and directg (which generates digraphs given an underlying graph) utilities that come with Nauty.