[Nauty] help request

[Brendan McKay]

Hi Clément,

When you refer to "bicolored", do you mean that the edges are +1 or -1,
or is there an additional colouring that doesn't appear on your picture?

Can there be parallel edges (more than one edge in the same direction
between the same pair of vertices, or more than one loop on the same
vertex)?

If both answers are "no", you have "signed digraphs". I don't know of
an existing catalogue and nauty does not have a canned generator for
them.  However, if you only want order 4, it would be simplest to use
a dumb method since you only need to do it once and efficiency is
not so important.

First, make a list of the 24 permutations of {1,2,3,4}.

Next, define an ordering on 4x4 matrices. It doesn't matter what it is,
for example you can write them out as a string of {-1,0,1} and use
dictionary ordering on the strings.

Now generate one 4x4 matrix at a time. Since there are 16 positions
in the matrix and 3 values that can go there, the number of matrices
is 3^16 = 43,046,721.  Consider one matrix M.  Apply each of the
permutations to M (simultaneously to rows and columns) and reject
M if the permuted matrix is strictly less than M according to the order
you defined.  If M is never rejected, keep it.

The set of matrices you keep will be representatives of the
isomorphism classes.  Expect about 2 million.

It's possible to tune this generation method a lot to make it super-fast,
but what is the point of spending an hour to reduce the running time
from one minute to one second?  If you ever choose to go for order 5,
where there will be about 10 billion matrices, you might need more care.

Cheers, Brendan.

On 9/4/21 3:02 am, clément galan wrote:
> Hello nauty users community,
>
> I'm a bioinformatics student in my first Master's year, currently doing an
> internship in a computational biology lab. My project is about generating
> an atlas of regulatory networks (i.e. graphs) on which we define ODE
> dynamics and then study their behaviour. To this end, we want to create
> 'all' graphs of a certain size. The graphs that we are considering are all
> the non isomorphic, directed and bicolored graphs with 4 vertices,
> including loops. Here is an example of the type of graph, as an adjacency
> matrix, that we aim to have (edges can take two values, 1 and -1):
> [image: image.png]
> After reading the documentation, I assumed that to use the nauty package
> was the most efficient way to generate all the graphs. However, I
> encountered some difficulties to correctly use the nauty / gtools
> functions, since my knowledge is still limited in this field. I would
> really appreciate if someone could give me indications to tackle my
> challenge.
>
> Best regards,
>
> Clément Galan
> CRI Paris and Inria Lyon
>
>
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> https://mailman.anu.edu.au/mailman/listinfo/nauty