[Nauty-list] Functional digraphs

Brendan McKay Brendan.McKay at anu.edu.au
Sun Oct 20 00:41:29 EST 2013


There isn't anything matching this exactly, but you can manage.

You can get the digraphs of all functions like this (for n=12):
   geng 12 0:12 | watercluster2 T o1
It writes 57903 digraphs like this:
   
12 5 0 10 1 11 2 11 10 11 11 0
12 6 0 11 2 11 3 11 4 11 10 0 11 1
12 7 0 11 1 11 2 11 3 11 4 11 10 0 11 1
12 6 1 11 2 11 3 11 4 11 10 0 11 0
12 6 0 11 1 11 2 11 3 11 4 11 10 0


The number of vertices, the number of edges, then a list of edges.

Now, if you don't want to include the functions that have fixed
points, filter out those with any vertices of out-degree 0, which
are also those which have less than 12 edges (pipe through
egrep "^12 12"), leaving 18264 digraphs.

If you do want functions with fixed points, keep them all but add
a loop on every vertex of out-degree 0.

The relevant counts are at
  http://oeis.org/A001373
  http://oeis.org/A001372

It makes about 25,000 digraphs per second so you can get up over
n=20 without much trouble.

Brendan.


On 19/10/13 11:59 PM, "James Mitchell" <jdm3 at st-and.ac.uk> wrote:
>Dear Nauty-List,
>
>I'm a novice user of Nauty, and I wondered: is there any way to
>generate the functional digraphs (digraphs with out-degree 1 for every
>vertex) up to isomorphism using the programs in gtools, or otherwise?
>I'd like to be able to do this for some small values, say n<=12.
>
>Thanks in advance for any information you might be able to provide.
>
>Regards,
>
>
>James
>
>
>
>-- 
>James Mitchell
>tinyurl.com/jdmitchell
>
>The University of St Andrews is a charity registered in Scotland : No
>SC013532
>
>_______________________________________________
>Nauty-list mailing list
>Nauty-list at cs.anu.edu.au
>http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
>






More information about the Nauty mailing list