[Nauty-list] Canonical labelling for small graphs

Micha Hofri hofri at WPI.EDU
Tue Jan 4 07:48:03 EST 2011

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 

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

More information about the Nauty mailing list