[Nauty-list] Canonical labelling for small graphs
hofri at WPI.EDU
Tue Jan 4 12:42:33 EST 2011
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
More information about the Nauty