[Nauty-list] (run-time) Canonical labeling and matching of DAGs

[Yogesh Varma]

I am a new user and trying to learn by reading the user guide, papers and
archive. My goal is to make a program to:

   1. Construct graphs during execution of my program (which gives only
   adjacency and vertex types) (shall I call nauty - how to format the input
   graphs?)
   2. Canonically label each such graph (can I use labelg for this step)
   3. Compare each new graphs with current canonicalized graphs to form a
   histogram (how to compare/match)

I am working with DAGs (with no cycles or triangles). These DAGs are formed
by instruction chains captured during a benchmark program simulation, which
is slow as it is. The number of vertices per chain vary from 4 to 12 (but
also above 20 at times) and the degree of each vertex is 3 to 4 (or more at
times). So I am also wondering about efficiency of the prunning method and
resultant large search tree.

>From what I read in archives:

>* nauty already computes canonical labellings for directed graphs.... *
> >* there is no need to modify the algorithm.*
> >* *
> >* However the default settings for the "options" structure is to have *
> >* options.digraph set to FALSE - presumably because some speed can be *
> >* gained if the algorithm can rely on the input being undirected *
> >* without actually confirming that edge j-i is present when it notices *
> >* edge i-j.*
> >* *
> >* So, just set options.digraph = TRUE before your call to nauty, and it *
> >* will treat it as a directed graph*
>
> If you are calling nauty from your own problem, I also recommend
> options.mininvarlevel = 1;
> options.maxinvarlevel = 99; /* or something */
> options.invarproc = adjacencies;
> For long jobs you might want to test whether this helps or hurts.
> The values of these parameters can change the canonical labelling
> so be consistent.
>

and

> >* Under what conditions will the canonical graph of a directed graph be
> *>* lower triangular?
> *
> There aren't any guarantees of this at all.  If you need a
> canonical form for an acyclic directed graph you will need
> to add an extra relabelling stage after applying nauty.
>
> Incidentally, acyclic directed graphs don't much like the
> default parameters of nauty.  For better average efficiency,
> use the invariant "adjacencies".
>
>
It would be great to get some pointers/ideas about which nauty functions to
use in my program and which parameter to use for effective implementation.

Thanks a lot!

Yogesh Varma
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20090222/c3801e5c/attachment.html