[Nauty-list] elements of the automorphism group

[Brendan McKay]

Hi, Sorry to be out of touch.  Nauty includes an interface that
can make all the automorphisms one at a time.  See the sample
file nautyex3.c in the version 2.4 distributions.

Before calling the procedure allgroup(), you might want to check
that the group is not fantastically large.  The size is available as
   stats.grpsize1 * 10^(stats.grpsize2).

Brendan.


* Mathieu Dutour <Mathieu.Dutour at ens.fr> [071206 17:42]:
> About the generation itself, there is a theory of generation, which allow
> to iterate over the group elements. It is explained in such texts as
> "Permutation group algorithms" by Seress and implemented in such programs
> as GAP, magma.
> 
> So, depending on what you want, here are some possible solutions.
> 1> Use GAP (which has an interface to nauty) and get the automorphism
> group. Then do
>   for eElt in GRP
>   do
>     ...
>   od;
> 
> 2> do simple generation of all elements without using the tree search.
> Much slower but easily programmable in C.
> 
> 3> Implement the Schreier Sims theory in the language you need.
> It is unfortunate that the only implementation I know of permutation
> group algorithms are in GAP, magma and there is no C library available.
> 
> Anyway, here is a first sketch at how this can be done:
> --From the list of generators of G acting on [0...n], we can determine
>   easily and efficiently the orbits of elements of [0..n].
> --From the list of generators of G, we can determine a list of generators
>   of the stabilizer H=G.0 of 0 by G.
>   The problem is that the number of generators grows quadratically
> --The method is then to get a sequence of stabilizers.
>   {1}=Hm \subset Hm-1 \subset ... \subset H1 \subset H0=G.
>   and the tree search is then provided.
> 
> So, pick your poison! Personally I tend to like GAP, which is pleasant
> to use and use C only when speed I have requirements.
> 
>   Mathieu
> 
> 
> On Wed, Dec 05, 2007 at 06:20:03PM +0100, Juan Felipe Carrasquilla wrote:
> >> Dear All,
> >> 
> >> I am a newcomer in the list. I am trying to use nauty to link it to a
> >> quantum monte carlo code to generate the all the symmetries of the
> >> lattices we deal with. The lattices ( and the boundary conditions as well)
> >> can be pictured using graphs so this is why we think nauty could be very
> >> useful.
> >> 
> >> Nauty provides the information of the automorphism group of a graph in the
> >> form of a set of generators, the size of the group, and the orbits of the
> >> group. For our application, it would be desirable to have, instead of the
> >> generators and the orbit, the full group components. I have little
> >> background in group theory but as far as I understand I can generate all
> >> the components of the group by using the generating set X and a finite
> >> product of elements of it and their inverses. What I do not know is how to
> >> generate those combinations of the elements of the generating set with the
> >> information provided by nauty, namely the generating set, the orbits of
> >> the groups and the size of the group.
> >> 
> >> Is nauty able to provide the information of the automorphism group by
> >> listing all the elements?
> >> 
> >> If not, is there a systematic way to generate the elements  with the
> >> information provided by nauty? (this might not be a good question for this
> >> list but if anyone can help me I would be grateful)
> >> 
> >> Thanking you,
> >> 
> >> Juan
> >> 
> >> 
> >> ----------------------------------------------------------------
> >>   SISSA Webmail https://webmail.sissa.it/
> >>   Powered by SquirrelMail http://www.squirrelmail.org/
> >> 
> >> 
> >> _______________________________________________
> >> Nauty-list mailing list
> >> Nauty-list at cs.anu.edu.au
> >> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
> 
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list