[Nauty-list] Canonical labelling for small graphs
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