List graphs with edge and symmetry constraints

Question

I would like to create a set of all directed graphs with n vertices, where each vertex has k direct descendants and k direct predecessors. n and k will not be so large, but about 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.

I am interested in the role of topology motives, so I don’t want to take weighting coefficients for any two graphs symmetrical to each other, where symmetry means that the permutation of the vertices does not exist on one graph, which converts it to another,

A naive solution would be to consider the adjacency matrices 2 ^ (n * (n - 1)) and eliminate all those (most of them) for which direct successors or predecessors are violated. For n = 8, this is a few more bits to represent and simply list each matrix conveniently inside uint64_t .

Tracking row counts and number of columns will be another improvement, but adding a graph to the result set will be a real bottleneck, after which we need to check the symmetry of each other that is already set in the set. For n = 8, which will already be more than 40,000 permutations per insert operation.

Can anyone refer to an algorithm that I could read could make all this smarter? 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 “compiled” all the graphs for reasonable n and k?

Answer 1

Isomorphism of graphs, in my opinion, is not what you should think about realizing yourself. I believe the current state of affairs is Brendan McKay Nauty (and related programs / libraries). This is a bit of a bear to work with, but it may be worth it to avoid your own, naive isomorphism of the graph. In addition, he is primarily focused on non-oriented graphics, but can also do digraphs. You might want to check out the geng (which generates undirected graphs) and directg (which generates digraphs based on the base graph) that come with Nauty.

Answer 2

This is more of a comment than an answer, because it seems like I missed something in your question.

First of all, is it possible for such a schedule to be acyclic?

I also wonder about your symmetry constraint. Doesn't that make all such graphs symmetrical to each other? Is it permissible to rearrange rows and columns of a join matrix?

For example, if we allow self-connections in a graph, does the following connection matrix match your conditions?

  1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 

Starting with this matrix, is it possible to rearrange rows and columns from it to obtain all such graphs, where all rows and columns have the sum of three?

One example of such a matrix can be obtained from the above matrix A as follows (using MATLAB).

 >> A(randperm(8),randperm(8)) ans = 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 1 1 0 

PS. In this case, I repeated the command several times to get a matrix with zeros in the diagonal. :)

Edit

And, I see from your comments that I'm wrong. Of course, the permutation index should be the same for rows and columns. At least I should have noticed this when I started with a schedule with self-connections and got one without them after the permutation.

A random isomorphic permutation will look like this:

 idx = randperm(8); A(idx,idx); 

which saves all self-connections.

Perhaps this may be useful in creating matrices, but it is not at all as useful as I thought it would be.