Logo Search packages:      
Sourcecode: magnus version File versions  Download package

postproc.c

/**************************************************************************

        postproc.c
        Colin Ramsay (cram@csee.uq.edu.au)
        27 Feb 99

        ADAPTIVE COSET ENUMERATOR, Version 3.000

        Copyright 1999
        Centre for Discrete Mathematics and Computing,
        Department of Mathematics and 
        Department of Computer Science & Electrical Engineering,
        The University of Queensland, QLD 4072.
      (http://www.csee.uq.edu.au/~havas/cdmc.html)

This is the post (enumeration) processing stuff for stand-alone ACE.  Note
that many of the routines here could be considered as Level 0 or Level 1
functions, since they perform general-purpose table manipulations; however,
some of them use Level 2's error-handler, so they couldn't be moved as they
stand to a lower level.  They have been written to be as versatile and as 
`robust' as possible, although Level 2 may not take full advantage of this.

**************************************************************************/

#include "al2.h"

#include <ctype.h>

      /******************************************************************
      void al2_oo(int arg)

      Find cosets with order a multiple of |arg|, modulo the subgroup.
      If arg=0, print all orders.  Otherwise, print the first (arg>0) or
      all (arg<0) coset numbers with order a multiple of |arg|, along
      with their reps.
      ******************************************************************/

void al2_oo(int arg)
  {
  int i,j,k, aarg, ord;
  Logic found;

  if (arg < 0)
    { aarg = -arg; }
  else
    { aarg = arg; }

  found = FALSE;
  for (i = 2; i < nextdf; i++)
    {
    if (COL1(i) >= 0)
      {
      if (al1_bldrep(i))
        { 
        if ((ord = al1_ordrep()) == 0)
          { continue; }
        if ((arg == 0) || (ord%aarg == 0))
          {
          if (!found)
            {
            found = TRUE;
            fprintf(fop, "  coset |  order  rep\n");
            fprintf(fop, "--------+------------\n");
            }

          fprintf(fop, "%7d |%7d  ", i, ord);
          for (j = 0; j < repsiz; j++)
            {
            k = colgen[currrep[j]];             /* generator number */
            if (!galpha)
              { fprintf(fop, "%d ", k); }
            else
              { fprintf(fop, "%c", 
                             (k > 0) ? algen[k] : toupper(algen[-k])); }
            }
          fprintf(fop, "\n");

          if ((arg > 0) && (ord%aarg == 0))
            { break; }
          }
        }
      else
        { al2_continue("unable to build coset rep've"); }
      }
    }

  if (!found)
    { fprintf(fop, "* Nothing found\n"); }
  }

      /******************************************************************
      Logic al2_normal(int cos)

      Coset cos is normalising if for the subgroup H = <w_1,...,w_s>,
      then cos*w_j = cos (for all j=1...s).  Return T if this is the
      case, else F (incl. out-of-range/redundant).

      Warning: this routine traces thro the subgrp gens, using the
      enumerator's data structure.  Thus, it can only be used if the
      al1_start() routine has been called & nsgpg has _not_ been altered.
      Similar remarks apply to al2_normcl().
      ******************************************************************/

Logic al2_normal(int cos)
  {
  int s, *beg, *end, *pi, next;

  if (cos < 1 || cos >= nextdf || COL1(cos) < 0)
    { return(FALSE); }

  for (s = 1; s <= nsgpg; s++)
    {
    beg = &(subggen[subgindex[s]]);
    end = beg-1 + subglength[s];

    next = cos;
    for (pi = beg; pi <= end; pi++)
      {
      if ((next = CT(next,*pi)) == 0 || COL1(next) < 0)
        { return(FALSE); }
      }
    if (next != cos)
      { return(FALSE); }
    }

  return(TRUE);
  }

      /******************************************************************
      void al2_sc(int arg)

      Print the stabilising cosets of the subgrp.  arg>0 prints the first
      arg of them, arg<0 prints the first |arg| + reps, and arg=0 prints
      all of them + reps.
      ******************************************************************/

void al2_sc(int arg)
  {
  int i,j,k, aarg;
  Logic found;

  if (arg < 0)
    { aarg = -arg; }
  else
    { aarg = arg; }

  found = FALSE;
  for (i = 2; i < nextdf; i++)
    {
    if (COL1(i) >= 0)
      {
      if (al2_normal(i))
        {
        if (!found)
          {
          found = TRUE;
          if (arg <= 0)
            { fprintf(fop, "Stabilising cosets (+ reps):\n"); }
          else
            { fprintf(fop, "Stabilising cosets:\n"); }
          }

        fprintf(fop, "%7d", i);
        if (arg <= 0)
          {
          if (!al1_bldrep(i))
            { al2_continue("unable to build coset rep've"); }
          fprintf(fop, "  ");
          for (j = 0; j < repsiz; j++)
            {
            k = colgen[currrep[j]];
            if (!galpha)
              { fprintf(fop, "%d ", k); }
            else
              { fprintf(fop, "%c", 
                             (k > 0) ? algen[k] : toupper(algen[-k])); }
            }
          }
        fprintf(fop, "\n");

        if ((aarg != 0) && (--aarg == 0))
          { break; }
        }
      }
    }

  if (!found)
    { fprintf(fop, "* Nothing found\n"); }
  }

      /******************************************************************
      void al2_cycles(void)

      Print out the coset table in cycles (permutation representation).
      This _must_ only be called when a completed _and_ compacted coset 
      table is present; ie, when a finite index has been computed & a
      (final) CO phase has been run.  The dispatcher code in parser.c 
      enforces this.  Note the use of the sign bit to track processed 
      cosets for each generator.

      ToDo: what about faithfulness?!
      ******************************************************************/

void al2_cycles(void)
  {
  int i, j, k, kn, t, length;
  Logic id;

  for (j = 1; j <= ndgen; j++) 
    {
    k = gencol[ndgen+j];      /* find the column k for generator j */
    id = TRUE;                /* assume action is the identity */

    if (!galpha)        /* print lhs & record its length */
      { 
      fprintf(fop, "%d = ", j);
      length = al2_outlen(j) + 3;
      } 
    else 
      { 
      fprintf(fop, "%c = ", algen[j]);
      length = 4;
      }

    for (i = 1; i <= nalive; i++) 
      {
      if (CT(i, k) == i)      /* skip if i is a one-cycle */
        { 
        CT(i, k) = -i; 
        continue; 
        }

      /* have we used coset i in previous cycle?  */

      if (CT((kn = i), k) < 0) 
        { continue; } 

      id = FALSE;             /* action of generator not identity */

      /* no, trace out this cycle  */

      length += al2_outlen(kn) + 1;
      if (length < LLL) 
        { fprintf(fop, "(%d", kn); }
      else
        {
        fprintf(fop, "\n  (%d", kn); 
        length = al2_outlen(kn) + 3;
        }

      t = CT(kn, k);
      CT(kn, k) = -t;         /* mark this coset as used */
      kn = t;

      while (CT(kn,k) > 0) 
        {
        length += al2_outlen(kn) + 1;
        if (length < LLL) 
          { fprintf(fop, ",%d", kn); }
        else 
          { 
          fprintf(fop, ",\n  %d", kn); 
          length = al2_outlen(kn) + 2;
          } 

        t = CT(kn, k);
        CT(kn, k) = -t;
        kn = t;
        }

      /* we have reached the end of the cycle */

      fprintf(fop, ")"); 
      length++;
      }

    if (id) 
      { fprintf(fop, "identity\n"); } 
    else 
      { fprintf(fop, "\n"); }

    /* change all the (negative) values in this column back to positive */

    for (i = 1; i <= nalive; i++) 
      { CT(i, k) = -CT(i, k); }
    }
  }

      /******************************************************************
      void al2_normcl(Logic build)

      Check normal closure.  Trace g^-1 * w * g and g * w * g^-1 for all 
      group generators g and all subgroup generator words w, noting 
      whether we get back to coset 1 or not.  Note that 1.w^g = 1 iff
        1.Gwg = 1 iff 1.Gw = 1.G (hence the apparent switch in the sense of
        first when we set it).  If build is T, then the non-normalising
      conjugates are added to the list of subgroup generators; the _user_
      has rerun the enumeration.  Note that coset #1 is never redundant;
      however, others may be, and the table may be incomplete.

        Note: if g has a finite order, say n, then G=g^{n-1}.  So either 
        both or neither of g/G normalise w (ie, we need check only one).
      However, g may have infinite/unknown order so, in general, we have
      to check both.

      Remark: we choose to ignore those g/w pairs where the trace does
      not complete.  It could be argued that we should include them in 
      the list of non-normalising conjugates (as ACE2 did).  If we did, 
      this would require definitions to be made during the rerun of the 
      SG phase.  By including only those pairs which do trace, but not 
      to 1, we effectively introduce coincidences.
      ******************************************************************/

void al2_normcl(Logic build)
  {
  int col, first, next, s, *beg, *end, *pi, j,k,l;
  Logic found;
  Wlist *list;
  Wlelt *lelt;

  found = FALSE;
  list  = NULL;

  for (col = 1; col <= ncol; col++) /* all `significant' gen'rs */
    {
    if ((first = CT(1,invcol[col])) == 0 || COL1(first) < 0)
      { continue; }                 /* trace incomplete, next col */

    for (s = 1; s <= nsgpg; s++)    /* all (original) subgrp gens */
      {
      beg = &subggen[subgindex[s]];
      end = beg-1 + subglength[s];

      next = first;
      for (pi = beg; pi <= end; pi++)
        {
        if ((next = CT(next,*pi)) == 0 || COL1(next) < 0)
          { goto next_s; }          /* trace incomplete, next gen */
        }
      if (next == first)
        { continue; }               /* closes, next gen */

      /* At this point, we know that the trace of s^col completes but does
      not get back to 1.  So we have a non-normalising combo. */

      found = TRUE;                 /* at least one non-normalised */

      k = colgen[col];              /* (signed) generator number */
      if (!galpha) 
        { 
        fprintf(fop, "Grp gen'r \"%d\" does not normalise", k); 
        fprintf(fop, " subgrp gen'r \"");
        for (pi = beg; pi <= end; pi++)
          { fprintf(fop, " %d", colgen[*pi]); }
        }
      else 
        { 
        fprintf(fop, "Grp gen'r \"%c\" does not normalise",
                     (k > 0) ? algen[k] : toupper(algen[-k]));
        fprintf(fop, " subgrp gen'r \"");
        for (pi = beg; pi <= end; pi++)
          {
          if ((l = colgen[*pi]) > 0)
            { fprintf(fop, "%c", algen[l]); }
          else
            { fprintf(fop, "%c", toupper(algen[-l])); }
          }
        }
      fprintf(fop, "\"\n");

      if (build)
        {
        if (list == NULL)
          {
          if ((list = al1_newwl()) == NULL)
            { al2_continue("unable to create new subgrp gen'r list"); }
          }

        if ((lelt = al1_newelt()) == NULL)
          {
          al1_emptywl(list);
          free(list);
          al2_continue("unable to create subgrp gen'r list elt"); 
          }

        lelt->len = subglength[s] + 2;          /* gen'r + col/col^-1 */
        if ((lelt->word = (int*)malloc((lelt->len+1)*sizeof(int))) == NULL)
          {
          al1_emptywl(list);
          free(list);
          free(lelt);
          al2_continue("unable to create subgrp gen'r list elt word"); 
          }
        lelt->exp = 1;

        lelt->word[1] = -k;
        for (pi = beg, j = 2; pi <= end; pi++, j++)
          { lelt->word[j] = colgen[*pi]; }
        lelt->word[lelt->len] = k;

        al1_addwl(list,lelt);
        }

      next_s:
        ;
      }
    }

  if (!found)
    { fprintf(fop, "* All (traceable) conjugates in subgroup\n"); }

  /* If list != NULL then we must have created a list with at least one new
  subgrp gen'r; so found is T & genlst is non-NULL/non-empty!  Append the
  list of new gen'rs & update the enumeration status. */

  if (list != NULL)
    {
    al1_concatwl(genlst,list);

    nsgpg = genlst->len;

    okcont  = FALSE;
    tabinfo = tabindex = FALSE;

    fprintf(fop, "* Subgroup generators have been augmented\n");
    }
  }

      /******************************************************************
      void al2_cc(int cos)

      cos is guaranteed (by the caller) to be a non-redundant coset in 
      the range 2..nextdf-1.  Get its rep & add it to the subgroup gens.
      ******************************************************************/

void al2_cc(int cos)
  {
  int i,j;
  Wlelt *lelt;

  /* Build & printout the representative */

  if (!al1_bldrep(cos))
    { al2_continue("unable to build rep've"); }

  fprintf(fop, "Coset #%d: ", cos);
  for (i = 0; i < repsiz; i++)
    {
    j = colgen[currrep[i]];
    if (!galpha)
      { fprintf(fop, "%d ", j); }
    else
      { fprintf(fop, "%c", (j > 0) ? algen[j] : toupper(algen[-j])); }
    }
  fprintf(fop, "\n");

  /* Add the rep to the subgroup generators */

  if ((lelt = al1_newelt()) == NULL)
    { al2_continue("unable to create new subgrp gen'r"); }

  lelt->len = repsiz;
  if ((lelt->word = (int*)malloc((lelt->len+1)*sizeof(int))) == NULL)
    {
    free(lelt);
    al2_continue("unable to create subgrp gen'r word"); 
    }
  lelt->exp = 1;

  for (i = 0; i < repsiz; i++)
    { lelt->word[i+1] = colgen[currrep[i]]; }

  /* Add the new element to the (possibly non-existent) gen list */

  if (genlst == NULL)
    {
    if ((genlst = al1_newwl()) == NULL)
      {
      free(lelt->word);
      free(lelt);
      al2_continue("unable to create subgrp gen'r list"); 
      }
    }
  al1_addwl(genlst,lelt);
  nsgpg++;

  /* Reset enumeration status & `remind' the user */

  okcont  = FALSE;
  tabinfo = tabindex = FALSE;

  fprintf(fop, "* Subgroup generators have been augmented\n");
  }

      /******************************************************************
      void al2_rc(int desire, int count)

      Try to find a nontrival subgroup with index a multiple of a desired
        index `desire' by repeatedly putting randomly chosen cosets 
      coincident with coset 1 and seeing what happens.  We use the (not 
      very good, but ok for our purposes) random number generator rand(),
      which returns numbers in the range 0..32767 (ie, lower 15 bits).  
      We take care to ensure that we generate a `valid' coset to set
      coincident with #1.  If an attempt fails, we restore the original 
      subgrp gens, rerun the original enumeration, and try again (making 
      up to count attempts in all).  We use the asis flag to prevent 
      subgroup generator reordering, so that we can easily blow away the
      added generators.

      Notes:
      (i) This routine presupposes that an enumeration has already been
      performed (this may or may not have yielded a finite index).  The
      presentation and all the control parameters (apart from asis) are 
      frozen at their current values during this call; only the subgroup
      generator list is altered.  Any redo (or start) calls to the
      enumerator use the current settings, including any messaging.
      (ii) This routine can take a _long_ time.
      (iii) On success, the presentation/table reflects the discovered
      subgroup.  On failure, it reflects the original status.
      (iv) We try hard to ensure that the system is always left in a
      consistent state, and that all errors are picked up.  However, it
      is _strongly_ recommended that a positive result is checked (by 
      doing a complete enumeration), and that nothing is assumed about 
      the presentation/table on a negative result or on an error (note
      that the call to al2_cc() could cause an error return).
      (v) Note that the value of cos, before it is reduced modulo nextdf,
      is limited to 30 bits (ie, 0..1073741823).
      ******************************************************************/

void al2_rc(int desire, int count)
  {
  int r1, r2, cos, old, i;
  Logic tmp;
  Wlelt *p, *q;

  /* Record current status; asis flag & subgrp gen list */

  tmp  = asis;
  asis = TRUE;
  old  = nsgpg;

  while (count-- > 0)               /* Try up to count times */
    {
    while (TRUE)              /* Try until success / too small */
      {
      do
        {
        r1 = rand();
        r2 = rand();
        cos = ((r1 << 15) + r2)%nextdf;
        }
      while (cos < 2 || COL1(cos) < 0);

      al2_cc(cos);

      /* This chunk of code, for redo, is pinched from the parser */

      al1_rslt(lresult = al1_start(2));

      if (lresult > 0 && sgdone)
        {
        okcont  = TRUE;
        tabinfo = tabindex = TRUE;
        }
      else if (lresult >= -259 && sgdone)
        { 
        okcont   = TRUE;
        tabinfo  = TRUE;
        tabindex = FALSE;
        }
      else
        { 
        okcont  = FALSE;
        tabinfo = tabindex = FALSE;
        }
      if (lresult < -260)
        { okredo = FALSE; }

      /* Try and sort out what happened! */

      if (!(okcont && okredo && tabinfo))
        {
        asis = tmp;
        al2_restart("* An unknown problem has occurred");
        }

      if (tabindex && lresult%desire == 0)
        {
        fprintf(fop, "* An appropriate subgroup has been found\n");
        asis = tmp;
        return;
        }
      if (tabindex && lresult < desire)
        { goto restore; }
      };

    /* Setup for another attempt */

    restore:

    fprintf(fop, "* Recalculating original table\n");

    /* Remove added subgroup generators (of which there is at least 1) */

    if (old == 0)
      {
      al1_emptywl(genlst);
      nsgpg = 0;
      }
    else
      {
      for (i = 1, p = genlst->first; i <= old; i++, p = p->next)
        { ; }

      q = p->next;            /* Points to first added generator */

      genlst->last        = p;
      genlst->last->next  = NULL;
      genlst->len = nsgpg = old;

      for (p = q; p != NULL; )
        {
        q = p->next;

        if (p->word != NULL)
          { free(p->word); }
        free(p);
    
        p = q;
        }
      }

    /* Rerun the (original) enumeration (using code pinched from the
    parser), and then try to sort out what happened. */

    al1_rslt(lresult = al1_start(0));

    if (lresult > 0 && sgdone)
      {
      okcont  = okredo   = TRUE;
      tabinfo = tabindex = TRUE;
      }
    else if (lresult >= -259 && sgdone)
      { 
      okcont   = okredo = TRUE;
      tabinfo  = TRUE;
      tabindex = FALSE;
      }
    else
      {
      okcont  = okredo   = FALSE;
      tabinfo = tabindex = FALSE;
      }

    if (!(okcont && okredo && tabinfo))
      {
      asis = tmp;
      al2_restart("* An unknown problem has occurred");
      }
    if (tabindex && lresult%desire == 0)
      {
      fprintf(fop, "* An appropriate subgroup has been found\n");
      asis = tmp;
      return;
      }
    if (desire >= nalive)
      {
      asis = tmp;
      al2_restart("* Unable to restore original status");
      }
    };

  /* Our efforts failed.  The last time through the outer loop restored the
  original subgrp gens & table, so just restore asis & print a message. */

  fprintf(fop, "* No success; original status restored\n");
  asis = tmp;
  }

      /******************************************************************
      void al2_dw(Wlist *p)

      Delete the list of words given by intarr[] from the word list p.
      Both intarr[] & *p are guaranteed to be non-empty.
      ******************************************************************/

void al2_dw(Wlist *p)
  {
  int i,j;
  Wlelt *old, *tmp; 

  /* Check the 1st value, and then ensure that (any) others are strictly 
  increasing and don't exceed the list length. */

  if (intarr[0] < 1 || intarr[0] > p->len)
    { al2_continue("first argument out of range"); }
  for (i = 1; i < intcnt; i++)
    {
    if (intarr[i] <= intarr[i-1] || intarr[i] > p->len)
      { al2_continue("bad argument list"); }
    }

  /* Trace through the list, `moving' the required words & dropping those
  not required (freeing their space). */

  old = p->first;       /* Start at front of old list ... */
  i   = 0;

  j = 0;                /* First deletion is position intarr[0] */

  p->first = p->last = NULL;  /* Clear `new' list ... */
  p->len   = 0;

  while (old != NULL)
    {
    tmp = old;                /* `Chop' head of old list off */
    old = old->next;
    i++;                /* Current position */

    if (i == intarr[j])       /* Delete this one */
      {
      if (tmp->word != NULL)
        { free(tmp->word); }
      free(tmp);

      j++;
      }
    else                /* Keep this one */
      {
      if (p->first == NULL)
        { p->first = tmp; }
      else
        { p->last->next = tmp; }
      tmp->next = NULL;
      p->last   = tmp;
      p->len++;
      }
    }
  }

/**************************************************************************
The stuff under here is all concerned with testing various equivalent
presentations; either doing a random selection thereof, or all of them.  It
is guaranteed that the (top-level) routines are only called if the relator
list is non-empty.  The code here is all very naive, but there is little
point in trying to be clever/efficient.  Note that, no matter how we
cycle/invert/permute the relators, the data attached to each word (ie, its
length & exponent, and how it was entered) remains valid.
**************************************************************************/

      /******************************************************************
      void al2_inv_rel(Wlelt *p)

      Formally invert the word pointed to by p.
      ******************************************************************/

void al2_inv_rel(Wlelt *p)
  {
  int j,k, len;

  len = p->len;

  for (j = 1; j <= len/2; j++)
    {
    k                =  p->word[j];
    p->word[j]       = -p->word[len+1-j];
    p->word[len+1-j] = -k;
    }
  if (len%2 == 1)
    { p->word[1 + len/2] = -p->word[1 + len/2]; }
  }

      /******************************************************************
      void al2_cyc_rel(Wlelt *p)

      Cycle the word pointed to by p by 1 position.
      ******************************************************************/

void al2_cyc_rel(Wlelt *p)
  {
  int j,k;

  k = p->word[1];
  for (j = 1; j <= p->len-1; j++)
    { p->word[j] = p->word[j+1]; }
  p->word[p->len] = k;
  }

      /******************************************************************
      void al2_per_rel(void)

      Randomly pick a position in the relator list, and move it to the
      front of the list.  The list is guaranteed to contain at least 2 
      elements.
      ******************************************************************/

void al2_per_rel(void)
  {
  Wlelt *p, *pp;
  int c,i;

  c = 1 + rand()%rellst->len;       /* 1 <= c <= rellst->len */
  if (c == 1)
    { return; }                     /* do nothing */

  pp = rellst->first;
  p  = pp->next;
  i  = 2;
  for ( ; i < c; i++)
    { pp = p;  p = p->next; }

  if (rellst->last == p)
    {
    pp->next     = NULL;
    rellst->last = pp;
    }
  else
    { pp->next = p->next; }

  p->next       = rellst->first;
  rellst->first = p;
  }

      /******************************************************************
      void al2_munge_cyc(void)
      void al2_munge_inv(void)
      void al2_munge_pre(void)

      These 3 routines implement random cyclings, inversions & 
      permutations of the relators respectively.  Note that we have to 
      take a `guess' as to how many relator list element moves are needed
      to `randomly' reorder the relators.  The permutation becomes 
      progressivly `better' the more runs we do.
      ******************************************************************/

void al2_munge_cyc(void)
  {
  Wlelt *p;
  int c;

  for (p = rellst->first; p != NULL; p = p->next)
    {
    if ((c = rand()%p->len) > 0)
      { 
      while (c-- > 0)
        { al2_cyc_rel(p); }
      }
    }
  }

void al2_munge_inv(void)
  {
  Wlelt *p;

  for (p = rellst->first; p != NULL; p = p->next)
    {
    if (rand()%2 == 1)
      { al2_inv_rel(p); }
    }
  }

void al2_munge_per(void)
  {
  int len = rellst->len;

  while ((len /= 2) >= 1)
    { al2_per_rel(); }
  }

      /******************************************************************
      void al2_rep(int cntrl, int cnt)

      Do cnt enumerations using random equivalent presentations.  The 3
      lsbs of cntrl control cycling, inverting & permuting respectively.
      We turn messaging off, dump the relators _after_ each run (ie, 
      after al1_start() processes them, so that we see what they actually
      were for the run), and use asis to prevent al1_start() from 
      messing up the relator ordering.
      ******************************************************************/

void al2_rep(int cntrl, int cnt)
  {
  Logic tmpa, tmpm;

  tmpa    = asis;
  asis    = TRUE;
  tmpm    = msgctrl;
  msgctrl = FALSE;

  while (cnt-- > 0)
    {
    if ((cntrl & 0x1) != 0)
      { al2_munge_cyc(); }
    if ((cntrl & 0x2) != 0)
      { al2_munge_inv(); }
    if ((cntrl & 0x4) != 0)
      { al2_munge_per(); }

    /* (Re)run the enumeration, and then try to sort out what happened. */

    lresult = al1_start(0);
    fprintf(fop, "Group Relators: ");
    al1_prtwl(rellst, 16);
    fprintf(fop, ";\n");
    al1_rslt(lresult);

    if (lresult > 0 && sgdone)
      {
      okcont  = okredo   = TRUE;
      tabinfo = tabindex = TRUE;
      }
    else if (lresult >= -259 && sgdone)
      { 
      okcont   = okredo = TRUE;
      tabinfo  = TRUE;
      tabindex = FALSE;
      }
    else
      {
      okcont  = okredo   = FALSE;
      tabinfo = tabindex = FALSE;
      }

    if (!(okcont && okredo && tabinfo))
      {
      asis    = tmpa;
      msgctrl = tmpm;
      al2_restart("* An unknown problem has occurred");
      }
    }

  asis    = tmpa;
  msgctrl = tmpm;
  }

      /******************************************************************
      void al2_aep2(Wlelt *p, int *d)

      For this permutation, recursively do all cycles/inversions.
      ******************************************************************/

void al2_aep2(Wlelt *p, int *d)
  {
  Logic flg;
  int i,blen;

  if (p == NULL)              /* End of list, run enumerator */
    {
    /* Run the enumeration, and then try to sort out what happened. */

    d[2]++;
    lresult = al1_start(0);

    if (lresult > 0 && sgdone)
      {
      okcont  = okredo   = TRUE;
      tabinfo = tabindex = TRUE;
      }
    else if (lresult >= -259 && sgdone)
      { 
      okcont   = okredo = TRUE;
      tabinfo  = TRUE;
      tabindex = FALSE;
      }
    else
      {
      okcont  = okredo   = FALSE;
      tabinfo = tabindex = FALSE;
      }

    if (!(okcont && okredo && tabinfo))
      {
      asis    = (Logic)d[0];
      msgctrl = (Logic)d[1];
      al2_restart("* An unknown problem has occurred");
      }

    /* Did we get an index?  Any new best/worst values? */

    if (tabindex)
      {
      d[8]++;

      flg = FALSE;
      if (maxcos < d[3])
        {
        d[3] = maxcos;
        flg = TRUE;
        }
      if (maxcos > d[4])
        { 
        d[4] = maxcos;
        flg = TRUE;
        }
      if (totcos < d[5])
        {
        d[5] = totcos; 
        flg = TRUE;
        }
      if (totcos > d[6])
        { 
        d[6] = totcos;
        flg = TRUE;
        }
      if (flg)
        {
        fprintf(fop, "Group Relators: ");
        al1_prtwl(rellst, 16);
        fprintf(fop, ";\n");
        al1_rslt(lresult);
        }
      }
    }

  /* Cycle and/or invert this word, and then recurse.  Note the care to 
  ensure that we always do just what is required; in particular, we must 
  ensure we restore a word to its original form.  Note that we correctly
  cope with cycling in the presence of non-1 exponents.  We _cannot_ 
  suppress inverting (x)^n, if x is an involution, since the geninv[]
  array is recalculated by al1_start() & may change since we're
  manipulating asis.  To implement this, we'd need to duplicate the code in
  the al1_chkinvol() function.  In fact, there's no end to this, since
  inverting (ab)^n, if a & b are involutions, is equivalent to cycling it, 
  and doing _both_ is wasteful! */

  else
    {
    blen = p->len/p->exp;           /* Baselength of word */

    if ((d[7] & 0x3) == 0)          /* Do nothing */
      { al2_aep2(p->next, d); }
    else if ((d[7] & 0x3) == 1)           /* Cycle only */
      {
      for (i = 0; i < blen; i++)
        {
        al2_cyc_rel(p);
        al2_aep2(p->next, d);
        }
      }
    else if ((d[7] & 0x3) == 2)           /* Invert only */
      {
      al2_aep2(p->next, d);
      al2_inv_rel(p);
      al2_aep2(p->next, d);
      al2_inv_rel(p);
      }
    else                      /* Cycle & invert */
      {
      for (i = 0; i < blen; i++)
        {
        al2_cyc_rel(p);
        al2_aep2(p->next, d);
        }
      al2_inv_rel(p);
      for (i = 0; i < blen; i++)
        {
        al2_cyc_rel(p);
        al2_aep2(p->next, d);
        }
      al2_inv_rel(p);
      }
    }
  }

      /******************************************************************
      void al2_aep1(int *d, Wlelt *p)

      Recursively generate the permutations, calling al2_aep2() for each
      one.  p is a pointer to parent node of the unprocessed `tail' of 
      rellst.  rellst contains >1 elts & p is (initially) the 1st elt.
      ******************************************************************/

void al2_aep1(int *d, Wlelt *p)
  {
  Wlelt *t0, *t1;

  if (p->next == NULL)
    { al2_aep2(rellst->first, d); }
  else
    {
    /* Move the head of the unprocessed tail to all possible positions. */

    t0 = p->next;             /* Node being moved */
    p->next = t0->next;             /* Slice it out ... */
    if (rellst->last == t0)
      { rellst->last = p; }
    
    /* The head ... */

    t0->next = rellst->first;
    rellst->first = t0;

    al2_aep1(d, p);

    rellst->first = t0->next;

    /* The middle ... */

    for (t1 = rellst->first; t1 != p; t1 = t1->next)
      {
      t0->next = t1->next;
      t1->next = t0;

      al2_aep1(d, p);

      t1->next = t0->next;
      }

    /* The tail (where it started) ... */

    t0->next = p->next;
    p->next = t0;
    if (rellst->last == p)
      { rellst->last = t0; }

    al2_aep1(d, p->next);
    }
  }

      /******************************************************************
      void al2_aep(int cntrl)

      Do all enumerations using equivalent presentations; see comments
      for al2_rep().  To prevent having lots of global data floating
      around, we pass a pointer to the datum array, which contains:
            [0]   original asis
            [1]   original msgctrl
            [2]   number of runs
            [3]   min maxcos
            [4]   max maxcos
            [5]   min totcos
            [6]   max totcos
            [7]   cntrl
            [8]   number of successes
      ******************************************************************/

void al2_aep(int cntrl)
  {
  int datum[9];

  /* Temporary code, until we split al1_start() and do the presentation
  altering in the middle.  We need to ensure that the current presentation
  has been processed so that the word exponents are correctly set.  We do
  this run using whatever the current setup is, _before_ we set asis &
  turn messaging off.  After this run, the exponents will be fixed.
  However, setting asis may screw up involutions (ie, whether or not we'd
  need to invert some relators, if requested).  Note that this also sets
  maxrow to a valid U.B. for maxcos/totcos. */

  fprintf(fop, "* Priming run ...\n");
  al1_rslt(lresult = al1_start(0));

  if (lresult > 0 && sgdone)
    {
    okcont  = okredo   = TRUE;
    tabinfo = tabindex = TRUE;
    }
  else if (lresult >= -259 && sgdone)
    { 
    okcont   = okredo = TRUE;
    tabinfo  = TRUE;
    tabindex = FALSE;
    }
  else
    {
    okcont  = okredo   = FALSE;
    tabinfo = tabindex = FALSE;
    }

  if (!(okcont && okredo && tabinfo))
    { al2_restart("* An unknown problem has occurred"); }

  /* Start of the `proper' code. */

  datum[0] = (int)asis;
  asis     = TRUE;
  datum[1] = (int)msgctrl;
  msgctrl  = FALSE;
  datum[2] = 0;
  datum[3] = maxrow+1;
  datum[4] = 0;
  datum[5] = maxrow+1;
  datum[6] = 0;
  datum[7] = cntrl;
  datum[8] = 0;

  fprintf(fop, "* Equivalent runs ...\n");
  if ((cntrl & 0x4) == 0 || rellst->len < 2)    /* No permutations */
    { al2_aep2(rellst->first, datum); }
  else
    { al2_aep1(datum, rellst->first); }

  if (datum[8] == 0)
    { fprintf(fop, "* There were no successes in %d runs\n", datum[2]); }
  else
    {
    fprintf(fop, "* There were %d successes in %d runs:\n", 
                 datum[8], datum[2]);
    fprintf(fop, "*   maxcos=%d..%d, totcos=%d..%d\n", 
                 datum[3], datum[4], datum[5], datum[6]); 
    }

  asis    = (Logic)datum[0];
  msgctrl = (Logic)datum[1];
  }


Generated by  Doxygen 1.6.0   Back to index