Quelle  schreier.txt   Sprache: Text

Instructions for using schreier.c - May 12, 2010.
-------------------------------------------------

Declarations:
    #include "schreier.h"

    schreier  *gp;    /* This will point to the Schreier structure */
    permnode  *gens;  /* This will point to the stored generators */

Initialising group:

    newgroup(&gp, &gens, n);
       - This creates the two structures needed for a trivial group
         of degree n.  In the case that &gens == NULL, it creates the
         scheier structure only.  This enables a previous set of 
         generators to be used to initialise a new group;

Adding a generator p[0..n-1] :

  There are three options:

    addpermutation(&gens, p, n);
       - This just adds p to the stored generators without updating
         the Schreier structure.

    addgenerator(&gp, &gens, p, n);
       - This filters p through the Schreier structure once, adding 
         either p or an equivalent generator if it is not found to
         be in the group already. It is possible that the generator
         can be added even though it is not needed, even if it is
         identical to a previous generator. It returns a boolean
         value which is FALSE if p was found to be in the group and
         useless, otherwise it returns TRUE.

    condaddgenerator(&gp, &gens, p, n);
       - This is the same as addgenerator() except that it guarantees
         to never add a generator which is identical to a previous
         generator.  However, it still might not notice if it is in
         the group generated by the previous generators.

Updating the Schreier structure:

  At any moment, a partial base is known (initially empty) and some
  partial Schreier vectors and orbits relative to that partial base.  
  To make the Schreier vectors and orbits more likely to be complete,
  you can filter random group elements through it:

    expandschreier(gp, &gens, n);
        - Filter random elements until schreierfails consecutive
          failures occur.  Uses the existing partial base and does
          not attempt to extend it.

    schreier_fails(fails);
        - Change the value of schreierfails (default 10).  The previous
          is returned as the function value.

Orbits of stabiliser of partial base fix[0..nfix-1]:

    getorbits(fix, nfix, gp, &gens, n);
        - If fix[0..nfix-1] is a prefix of the partial base held
          internally, the existing orbits are returned immediately
          without changing the Schreier structure.  (Call
          expandschreier() first if this is not good enough.)
        - Otherwise, the Schreier structure is modified to use the
          partial base fix[0..nfix-1], keeping as much information
          as possible. Then expandschreier() is called and the
          orbits are returned.
  The function value points to an int array containing the orbits.
  The orbits are in nauty format (orbits[i] is the least vertex in
  the same orbit as vertex i). Since a randomised algorithm is used,
  correctness is not guaranteed. However, the partition returned is
  guaranteed to be finer than the true orbits partition.

    getorbitsmin(fix, nfix, gp, &gens, &orbits, cell, ncell, n);
        - If the basis elements fix[0..nfix-1] are minimal in their
          orbits, as far as we know, return value nfix and set *orbits
          to point to orbits fixing fix[0..nfix-1].  If fix[i] is seen
          to be not minimal for some i <= nfix-1, return i and set
          *orbits to point to orbits fixing fix[0..i-1]. If the partial
          base is already known, or fix[0..nfix-1] can already be seen
          to be non-minimal, do this work without more filtering.
        - Otherwise, filter until schreierfails failures, or until
          cell[0..ncell-1] is a subset of an orbit.  This last test
          is omitted if cell=NULL. 
          The pointer &orbits remains valid until getorbits() or
          getorbitsmin() is called with an incompatible base (neither
          a prefix nor an extension).

  For both getorbits() and getorbitsmin(), the orbits vector whose
  address is returned MUST NOT BE MODIFIED by the calling program.
  The pointer will remain valid until getorbits(), getorbitsmin(),
  pruneset() or grouporder() is called for a base that is neither a
  prefix nor an extension of this base.  During that time it will
  contain the orbits of some group (not necessarily the full group)
  fixing this base.

Finishing:

   deleteunmarked(&gens);
 - Delete some redundant generators.  Those left are guaranteed
          to generate the group. This invalidates the Schreier
          structure, so call freeschreier(&gp, NULL) afterwards.

   freeschreier(&gp, &gens);
        - Free these two structures.  Do this before using (gp,gens)
          for another group.

   schreier_freedyn();
        - Frees all the dynamic memory allocated by the Schreier code.
          This is optional since the same dynamic memory will be reused
          if you have a new group. 

Getting information:

    schreier_gens(gens)
        - Return the number of stored generators.

    grouporder(fix, nfix, gp, &gens, &grpsize1, &grpsize2, n);
 - Make an estimate of the group size using the base or
          base-less-one fix[0..nfix-1].  grpsize1 is double and
          grpsize2 is int, as in nauty.h.  The value returned is
          the product of the orbit sizes at each level times the
          largest orbit size at the end.  Correct with some
          probability.

    dumpschreier(FILE* f, gp, gens, n);
        - Write to file f a complete description of the structures.

    permnode *findpermutation(permnode *gens, int *p, int n)
        - return a pointer to the permnode in the circular list which
          is identical to p, if it exists.  Otherwise return NULL.