[Nauty-list] Nauty with Latin Squares

[Brendan McKay]

Hi, one thing is that you shouldn't use directed edges unless it
is necessary. In your case, that means use directed edges for the
cycles of the autotopism but undirected edges for everything else.
All the edges in the definition of G2 should go in both directions,
otherwise you are asking for trouble.

Secondly, these graphs are intrinsically difficult. To make the
generation fly you need to partition the vertices of the graph
according to invariants. See the discussion in the final pages
of Section 3. I'm not sure exactly what you are doing, but you
can probably use sigma in computing invariants. Another source
is the cycle structure of the permutations mapping the rows onto
each other. The real secret behind fast generation is to invent
invariants that are strong enough to usually avoid calling nauty at
all (see the discussion in the same place).

Brendan.

* damian <damian.vizar at gmail.com> [130426 08:47]:
> Hello,
> 
> I am trying to recreate the cannonical construction method described in
> article "Small Latin Square, Quasigroups and Loops" (as a Master Thesis -
> we need the square with non trivial auto-isotopy group to prove a
> hypothesis).
> 
> I experience some trouble when calling nauty to graph derived from
> incomplete latin square with respect to a certain isotopism (in article
> graph G2(L), where L may be unfinished square, consisting of k blocks+
> extra edges are added to represent the sigma autotopism). Problem is, that
> the call to nauty is too slow (0.1s to few seconds). I think I might be
> doing some sort of fundamental mistake.
> 
> My program is in C++, but I have compiled nauty to a .a static library as C
> program. I use sparse graph representation, where the graph is a digraph
> (to correctly represent the cycles in autotopism sigma).
> 
> Thanks in advance for any advice or hint.
> Damian Vizar

> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list