[Nauty-list] Nauty with Latin Squares

[damian]

Hello, thanks a lot for a quick answer, these are the information i've been
looking for, however, I'm still a bit confused about a couple of things.
Allow me to explain what I am doing now. Assuming  we have already chosen
k-1 blocks in U, we apply sigma-autotipism to blocks which legally extend U
to k blocks. After that, we use nauty to tell, if new rectangle with k
blocks fullfills "the second rule" - check if it is in the first orbit in
canong (with sufficient rows) if yes, store the rectangle with auomorphisms
(which we acquired from nauty too)

Now for the questions, the thing I am mainly confused about are the (sigma)
invariants, could you please give a very simple example (just hint) to get
me started? I have read the discussion, and I see, that avoiding nauty is
probably key to fast generation, however I can't grasp the ivariants - how
to construct them, how to use them, or how to create a suitable one. Even
if I have one, from the discussion in section 3 I understand, that a
suitable invariant can be used to compute f(L(k)) - the second rule. Can I
avoid nauty when determining orbits of sigma autotopisms on blocks (which
are to be used to extend U)?

I'm sorry to ask about stuff that may seem very basic, but I couldn't find
relevant answers anywhere else.
Damian


2013/4/26 Brendan McKay <bdm at cs.anu.edu.au>

> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20130426/0bd3b083/attachment.html