[Nauty] Schreir Sims Representation

[Brendan McKay]

It suffices to have a base such that the stabiliser of the whole base
is the identity.  There is no need to expand it to include every
vertex and this would only create inefficiencies.

If you want to generate the full group element by element, you can
use procedures in the nauty package.  The main file is naugroup.c.
To use it, follow the example given in the file nautyex3.c.  The cost
of making the whole group from the generators is slightly more than one
permutation multiplication per element.  Eventually there will be proper
documentation for this facility; for now the comments in nautyex3.c and
naugroup.c are the best there is.  In addition to the procedure allgroup()
used in nautyex3.c, there is allgroup2() that allows you to abort the
generation of the group at any point.

Brendan.


* Bulutoglu Dursun A Civ AFIT/ENC <Dursun.Bulutoglu at afit.edu> [040718 12:50]:
> 	Nauty gives a set of strong generators for the automorphism
> group of a graph based on a base v_0, v_2,...v_{k-1}. I was wondering if
> it is possible to get a set of strong generators for the automorphism
> group based on a base v_0,v_1, v_2, ...v_{n-1}  ie a base that uses all
> the vertices of the graph. This would give me an efficient way of
> generating the group. Since then every element of the group can be
> written uniquely as a product of strong generators. This is not the case
> when the base is a strict subset of the n vertices. If this is possible
> is the running time of the algorithm going to be effected from such a
> change. The set of strong generators based on all the vertices can be
> generated by using the strong generators based on a subset of all the
> vertices. The question is whether it would be more efficient to get the
> strong generators based on all the vertices directly from nauty. 
> 	Dursun.