[Nauty-list] generating graphs, pynauty, SMILES, python

butch konneker bootch at nc.rr.com
Wed Feb 21 02:34:52 EST 2007

Here I describe my application of nauty and pose a few questions.  I 
would appreciate insights and referrals to related work.

I am generating graphs from a BNF grammar.  A grammar lets you easily 
change what class of graphs you are generating.  The generator 
exhaustively generates SMILES strings, a linear, readable representation 
of graphs.  Its not a straight generation from a pure BNF grammar, you 
could say the grammar is augmented with code that generates permutations 
of what are called closures in SMILES: numbered links out of the linear 
string.  The generator proceeds BFT, breadth first traversal.  The 
generator generates many duplicates.  I use nauty to find duplicates.   
I find duplicates not only in the terminal sentences, but in the 
partially generated graphs (when DFT stacks a traversal to be continued 
later.)  I am writing in Python, using Pynauty, an interface from Python 
to nauty,  which I have modified to generate a canonical labeled graph 
in SMILES (the current version of pynauty only gives a signature.)  I am 
also using frowns, a chemistry tool in Python for representing molecules 
(which are graphs.)

I skimmed with interest your paper on exhaustive generation.  I must say 
it was heavy going for me, and I don't understand how it applies to the 
way I am generating graphs, yet.

I know there are other graph grammars, but I can't say how they differ 
from what I am doing.

One question I have concerns nauty and trees.  The partially generated 
graphs comprise a terminal (in the grammatical  sense that it is 
complete) graph attached to a tree (by its root) of the syntax of the 
grammar to be continued.  To nauty, its all just a graph.  Would it be 
more efficient to apply a different algorithm for tree isomorphism to 
the syntax tree portion, and nauty to the terminal graph, then lookup 
the pair of canonical ID's in a dictionary?  Instead of applying nauty 
to the entire graph, and looking up the canonical ID of the entire graph.

More information about the Nauty mailing list