[Nauty-list] Canonical labelling for small graphs

Micha Hofri hofri at WPI.EDU
Tue Jan 4 12:42:33 EST 2011


Dear Brendan,

Thank you for your response, which helped me learn more about your tool, 
but is not yet that which I need.  The generation part needs to be done 
by my program, since each digraph carries a history (specifically, the 
probability it is the one that gets generated), and for each I would need
to compute a canonical label which I use to make sure it is the only
isomorph of its cohort; cohorts are determined by the number of edges.

So it is the labeling, not the generation I need, and reading my earlier
post I could see where I was not sufficiently clear.

With many thanks,                       --Micha


At 10:58 on 01/04/11 Brendan McKay sent:

: 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
: 
: _______________________________________________
: 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