[Nauty] canonical forms with nauty or traces

[Brendan McKay]

Dear Pieter,

The mailing list still runs.  I don't know why your message didn't appear.
Perhaps you sent it from a different address than what you registered under,
which causes mail to be rejected as an anti-spam feature.

At last I discovered why the archiving is not working, I think. Let's see
if it works now.

Answers to your questions:

1.  Nauty and Traces each compute specific canonical labellings which
     are defined to be fast to compute rather than easy to describe. They
     cannot compute lexicographic minimal labellings or similar.  The
     fastest method I know for that is a program you may be able to obtain
     from Ted Spence (I don't have it). It is far slower per graph than 
nauty.

2.  Probably my answer for Q1 makes this one redundant.  There is no
      built-in facility for this, but it isn't out of the question.

I'm guessing you want to generate orthogonal arrays by the orderly
method.  You might instead consider the method of canonical construction
path.  One readable introduction is in the book "Classification Algorithms
for Codes and Designs" by Kaski and Östergård, where it is called the
method of canonical augmentation.

Brendan.

On 5/11/2015 10:34 PM, Pieter Eendebak wrote:
> Dear Brendan,
>
> This week I also sent an email to the nauty mailing list, but since 
> the archives date until 2013 I am not sure whether this list is still 
> active.
>
> I am looking for an (easy) interface to extract canonical labeling for 
> graphs related to orthogonal arrays. In particular I am looking for 
> the following:
>
> - can we enfore a particular canonical labeling? In particular I would 
> like the canonical labeling of nauty to correspond to a lexicographic 
> minimal ordering for the corresponding array
> - can we perform testing whether a graph is in canonical form? In 
> particular, can we instruct nauty or traces to abort the search for a 
> canonical labeling as soon as the program has figured out that the 
> current graph is not in canonical form?
>
> With kind regards,
> Pieter Eendebak
>