[Nauty-list] Canonical labelling for small graphs

[Brendan McKay]

Dear Micha,

You can call the nauty procedure for single graphs from your program.
The data structures and calling sequence are described in the manual.
In the case of digraphs, in addition to the compulsory
    options.digraph = TRUE;
I recommend
    options.invarproc = adjacencies;  (or adjacencies_sg if you use the
                                         sparse data structures)
    options.mininvarlevel = 0;
    options.maxinvarlevel = 99;

Perhaps there is an easier way for you.  The program directg takes
undirected graphs and changes undirected edges into directed edges
in all possible ways.  For example, to make all the directed graphs
with 10 vertices and 10 edges:

% geng 10 5-10 | directg -e10 -u
>A geng -d0D9 n=10 e=5-10
>A directg -ue10:10
>Z 4557 graphs generated in 0.01 sec
>Z 4557 graphs read from stdin; 2645480 digraphs generated; 2.29 sec

(Change -u to -T to actually see the digraphs.) If you only want
weakly connected digraphs with no 2-cycles:

% geng -c 10 10 | directg -e10 -o -u
>A geng -cd1D9 n=10 e=10
>A directg -oue10:10
>Z 657 graphs generated in 0.00 sec
>Z 657 graphs read from stdin; 352286 digraphs generated; 0.31 sec

Here are all the digraphs without 2-cycles whose underlying undirected
graphs have 13 vertices, 16 edges, have no 3-cycles, and are 2-connected:

geng -tC 13 16 | directg -o -u
>A geng -Ctd2D12 n=13 e=16
>A directg -ou
>Z 4624 graphs generated in 0.21 sec
>Z 4624 graphs read from stdin; 233387624 digraphs generated; 27.41 sec

Depending on how far you want to go, you might be able to get by just
by filtering the outputs from these programs.  It is also possible to
interfere with the running of directg to enforce degree sequence
constraints during the construction: see the description of DEGPRUNE
in the source code directg.c.

Gunnar Brinkmann has a program that can probably outperform the above
examples.  However, I suspect you are generating a very restricted 
class of digraph.  The best approach depends on the nature of your
restrictions.  Perhaps if you tell me more details about that I can
give more precise advice.

Cheers, Brendan.


* Micha Hofri <hofri at WPI.EDU> [110104 07:48]:
>
> Dear list members:
>
> I am a nauty newbie, but have now scanned the manual and mailing lists,  
> and while my needs are very likely to be covered, I did not find it.  
> Most likely --- a matter of terminology.
> How to do the following?
>
> I look at simple digraphs with a fixed number of vertices (n=9 is  
> typical), and add edges, keeping nonisomorphic entries only.  Up to m  
> edges m=9 this is pretty fast, but then my hand-cobbled isomorphism test  
> is too slow, even for the couple of millions with 10 edges (at this  
> stage many are dropped for satisfying other conditions, which depend on  
> the exact purpose of the calculation, and there can be several different  
> ones).
>
> The only gtool I saw, labelg, is not suitable, because of the iterative  
> way needed to generate the graphs, and if I read the description right it 
> is a batch tool -- gets a file of graphs and generate their labels; I  
> need to call (from my C program) a function, for a graph at a time.
>
> The program would use the labels as keys in a binary search tree to  
> eliminate canonical duplicates.
>
> Can I use nauty for the purpose?  Thanks for any clues,
>
> Sincerely,                      --Micha Hofri
>
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list