[Nauty-list] generating graphs, pynauty, SMILES, python
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