GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

1

2
/**************************************************************************
3

4
	coinc.c
5
	Colin Ramsay ([email protected])
6
        11 Dec 00
7

8
	ADVANCED COSET ENUMERATOR, Version 3.001
9

10
	Copyright 2000 
11
	Centre for Discrete Mathematics and Computing,
12
	Department of Mathematics and 
13
	  Department of Computer Science & Electrical Engineering,
14
	The University of Queensland, QLD 4072.
15
	(http://staff.itee.uq.edu.au/havas)
16

17
This is the coincidence handling for the coset enumerator.  Conceptually,
18
this is straightforward, but in practice the details can be a trifle
19
intimidating (mood-altering chemicals help).  The current strategy is
20
simple; we process a (primary) coincidence, and any consequent (secondary)
21
coincidences, immediately & completely.  (We may, or may not, stack
22
deductions, depending on the saved flag.)  Thus, outside the coincidence 
23
handling routines, the coincidence queue is empty.  We never `defer' 
24
processing primary coincidences and we never discard them.  Processing
25
coincidences can cause a table collapse (index=1), or can result in the
26
enumeration completing (finite index).  We detect the first of these
27
(returning 1), but not the second (since it would involve `speculative'
28
computation).
29

30
It would be nice to decouple queueing a primary coincidence from processing
31
it.  However, since the queue is stored in the table, queueing a coinc
32
means altering the table & (maybe) generating more coincidences.  Further,
33
a table with queued coincidences is inconsistent, in the sense that entries
34
in the rows of non-redundant cosets can refer to redundant cosets.  It 
35
would be quite feasible to have a (small, fixed size) auxiliary queue where
36
we could store (some) primary coincs as they are discovered without 
37
processing them immediately; but this would probably not be beneficial.
38

39
Note that *during* coincidence handling, as noted above, the table is
40
inconsistent.  So we have to continue processing until there are no more 
41
coincs queued to ensure that the table will be consistent when we exit.  
42
Thus we can't bail out early, with processing outstanding, except under 
43
very special circumstances (eg, collapse to index=1).  Even if we detect a
44
big collapse, and want to bail out (abandoning any stored deductions (we
45
could also stop queueing *new* coincidences!)), we need to process all 
46
coincs before we can exit.  Similarly, if all the cosets between knr or knh
47
& nextdf become redundant, then we know (if we choose to detect this state)
48
that we *will* finish.  However, we need to continue to `fix up' the table 
49
and to determine what the final index is (it could be *less* than the value
50
of nalive when guaranteed finishing was noted).
51

52
Note that the coinc handling routines are predicated on the fact that the
53
table has at least two columns, and that the first two of these are an a &
54
A pair or an a/A & b/B pair.  This ensures that, eg, if N.a = M, then the 
55
entry for M.A = N is also within the first two columns.  Note also that the
56
arguments to the various coincidence processing routines must be valid 
57
coset numbers (ie, 1 <= x < nextdf).  If not, all bets are off!
58

59
**************************************************************************/
60

61
#include "al0.h"
62

63
	/******************************************************************
64
	During the special coincidence processing of columns 1 & 2, at most
65
	two further coincidences can be pending at any one time.  These are
66
	stored in low1s/high1s & low2s/high2s.  This macro saves a (new)
67
	coincidence in a free slot.  Note that clo & chi are >0, and that
68
	low1s/low2s =0 indicate an empty slot.
69
	******************************************************************/
70

71
#define	SAVE12(clo,chi)                     \
72
  INCR(xsave12);                            \
73
  if (clo != chi)                           \
74
    {                                       \
75
    if (clo > chi)                          \
76
      { SWAP(clo, chi); }                   \
77
    if (low1s == clo && high1s == chi)      \
78
      { INCR(s12dup); }                     \
79
    else if (low2s == clo && high2s == chi) \
80
      { INCR(s12dup); }                     \
81
    else                                    \
82
      {                                     \
83
      INCR(s12new);                         \
84
      if (low1s == 0)                       \
85
        { low1s = clo;  high1s = chi; }     \
86
      else                                  \
87
        { low2s = clo;  high2s = chi; }     \
88
      }                                     \
89
    }	
90

91
	/******************************************************************
92
	CREP(path,rep) traces back through coincidence queue, starting at
93
	path, to find which coset path is ultimately equal to; rep is set 
94
	to this value (we can have rep=path).  COMPRESS(path,rep) resets 
95
	all cosets along path's path to point to rep, to speed up future 
96
	processing (we hope; cf. Union Find problem).  We always have to
97
	find reps during coincidence processing (so that we put information
98
	in the correct place & move it as infrequently as possible), but
99
	whether or not compressing the paths as stored in the coinc list is
100
	beneficial is a moot point.  Continually trying to compress paths
101
	which are already `essentially' compressed may waste more time than
102
	it saves!  The pcomp flag allows compression to be turned off.  At 
103
	a guess, if the enumeration is `large' and the number of secondary
104
	coincs per primary coinc is `large', then compression is 
105
	beneficial; otherwise, it wastes more time than it saves.
106

107
	Note that these do *not* trace through, or disturb in any way, the 
108
	coincidence queue (which is stored in column 2), but merely 
109
	trace/reset the coset pointed to (in column 1) by those members of
110
	the queue with which path is coincident.
111

112
	Note that, if we want to find path's current rep *and* compress its
113
	path down to this, then it is more efficient to combine the 
114
	routines into one, as was done in ACE2.  However, in _cols12() we 
115
	have to find both reps first, and then compress (if compression on)
116
	both of them down to the smaller, so we couldn't use the combined 
117
	routine there.
118
	******************************************************************/
119

120
#define CREP(path,rep)         \
121
  INCR(xcrep);                 \
122
  if ((i = COL1(path)) < 0)    \
123
    {                          \
124
    INCR(crepred);             \
125
    while ((j = COL1(-i)) < 0) \
126
      {                        \
127
      INCR(crepwrk);           \
128
      i = j;                   \
129
      }                        \
130
    rep = -i;                  \
131
    }                          \
132
  else                         \
133
    { rep = path; }
134

135
#define COMPRESS(path,rep)  \
136
  INCR(xcomp);              \
137
  l = path;                 \
138
  while ((j = COL1(l)) < 0) \
139
    {                       \
140
    INCR(compwrk);          \
141
    COL1(l) = -rep;         \
142
    l = -j;                 \
143
    }
144

145
	/******************************************************************
146
	static Logic al0_chk1(void)
147

148
	This routine is called only by al0_cols12, and only when nalive=1
149
	and CT(1,1) & CT(1,2) are defined.  al0_coinc() has already
150
	collapsed all information in positions 1/2 (destroying the entries 
151
	there in the process); thus, if all other entries in coset 1's row 
152
	are defined (or are coincident with defined entries), then the 
153
	index must be 1; i.e., *all* the cosets are coincident and *all*
154
	entries in row 1 are defined (as 1, or synonyms thereof).
155

156
	Note that this routine does not (and, indeed, cannot (simply,
157
	anyway)) distinguish between coincidences consequent on the current
158
	primary coincidence and those from a previous primary coincidence.
159
	However, *provided* that all previous coincidences (that were
160
	processed) were fully processed then any data (in any col>2) in any
161
	row of the table is either valid or has been copied to a valid row.
162
	So, any non-zero entry means that the corresponding col in row 1
163
	*will* be non-zero.
164
	******************************************************************/
165

166
static Logic al0_chk1(void)
167
  {
168
  int i, j;
169

170
  for (j = 3; j <= ncol; j++) 
171
    { 
172
    if (CT(1,j) != 0) 
173
      { continue; }
174

175
    /* If CT(1,j)==0, look down column j for *any* non-zero entry. */
176

177
    for (i = 2; i < nextdf; i++) 
178
      { 
179
      if (CT(i,j) != 0) 
180
        { goto conti; }
181
      }
182
    return(FALSE); 		/* column j has no defined entry */
183

184
    conti:			/* continue, to next column */
185
      ;				/* prevent non-ANSI warning ! */
186
    }
187

188
  /* Index *is* 1: set all entries in first row to 1 and bump knr/knh up to
189
  nextdf (& nextdf down to 2). */
190

191
  for (i = 1; i <= ncol; i++) 
192
    { CT(1,i) = 1; }
193
  knr = knh = nextdf = 2;
194

195
  /* Wipe out the coincidence list and any outstanding pd's.  Empty the 
196
  dedn stack & say there were no discards.  The SG phase is unnecessary. */
197

198
  chead  = ctail  = 0;
199
  toppd  = botpd  = 0;
200
  topded = -1;
201
  disded = FALSE;
202
  sgdone = TRUE;
203

204
  return(TRUE);
205
  }
206

207
	/******************************************************************
208
	static Logic al0_cols12(int low, int high, Logic saved)
209

210
	Process cols 1 and 2 of cosets low = high and their consequences.
211
	While handling the coincidences coming from the processing of the 
212
	first 2 columns and the possible coincidences arising from them, we
213
	have at most 2 more unprocessed coincidences which we need to save
214
	somewhere to have their columns 1 and 2 processed later.  Thus we 
215
	set aside 4 locations (low1s, high1s; low2s, high2s) to store such 
216
	coincident cosets as may arise.  Note that a total collapse (ie, 
217
	index=1) may occur, in which case we return TRUE (if not, FALSE).
218
	This routine is only called from al0_coinc, as part of our strategy
219
	of fully processing all coincidences immediately. 
220

221
	Note that on the first pass thro the loop, low & high are the input
222
	arguments.  On subsequent passes (if any) they are consequences of
223
	the data in cols 1/2 of an earlier pass.  When we queue & process
224
	coincidences, we always copy data from high nos to low nos and mark
225
	the high nos as redundant & pointing to the low on the queue.
226

227
	In general, we enter our main loop with only one save slot (the one
228
	we've just removed to process) empty.  It may appear that 
229
	processing this can generate *two* more coincidences to be saved.
230
	However, this is only true on the *first* pass through the loop, 
231
	when both slots are empty.  On subsequent passes, the coincidence 
232
	being processed was generated by an earlier coincidence, and 
233
	processing this has removed an entry from it (via processing an 
234
	inverse entry).  So at most *one* new coincidence can be generated.
235
	******************************************************************/
236

237
static Logic al0_cols12(int low, int high, Logic saved)
238
  {
239
  int i, j, l;				/* for CREP()/COMPRESS() macros */
240
  int low1s, low2s, high1s, high2s;	/* consequent coincidences */
241
  int inv1, inv2;			/* column inverses */
242
  int rlow, rhigh;			/* reps of low/high */
243
  int src, dst;				/* source & dest'n for info move */
244
  int low1, low2, high1, high2;		/* original data from cols 1/2 */
245
  int lowi;				/* temp */
246

247
  INCR(xcols12);
248

249
  if (low == high)			/* Paranoia prevents problems */
250
    { return(FALSE); }
251

252
  low1s = low2s = 0;
253

254
  inv1 = invcol[1];			/* Make these globals ? */
255
  inv2 = invcol[2];
256

257
  while (TRUE) 
258
    {
259
    CREP(low,rlow); 
260
    CREP(high,rhigh);
261
    if (rlow <= rhigh)
262
      { src = rhigh;  dst = rlow; }
263
    else
264
      { src = rlow;  dst = rhigh; }
265

266
    /* If the two reps are equal there's nothing to do (ie, no info to
267
    move) & we jump over this if().  If not, we're in one of four states,
268
    depending as low (high) is (is not) redundant.  In any event, both src
269
    & dst are *not* redundant, and data from cols 1/2 has to be moved from
270
    src to dst (since queueing src as coincident overwrites this data).  
271
    Since a coset is queued (made redundant) as its data is processed, all
272
    relevant data is processed once only & is moved to the smallest coset
273
    currently known to be equivalent.  If dst later becomes redundant this
274
    is ok, since it will be queued, and later dequeued, *after* src. */
275

276
    if (src != dst)
277
      {
278
      /* Mark src coincident with dst and queue the coincidence, recording
279
      the values of CT(src,1) & CT(src,2) before we destroy them! */
280

281
      high1 = COL1(src);
282
      high2 = COL2(src);
283

284
      COL1(src) = -dst; 
285
      if (chead == 0) 
286
        { chead = src; }
287
      else 
288
        { COL2(ctail) = src; }
289
      ctail = src; 
290
      COL2(src) = 0;
291

292
      INCR(qcoinc);
293

294
      /* To check that the following is correct, you have to check the
295
      cases where cols 1 & 2 are a/A & b/B or a & A separately.  For each
296
      of these, you have to consider all possible patterns of entries in 
297
      rows scr & dst (0, src, dst, X, Y), and check that the right thing is
298
      always done.  Note that we are guaranteed that at least one, but not
299
      necessarily both, of low1s/high1s & low2s/high2s are free at this 
300
      point.  This code could be rewritten to be *much* clearer; it would
301
      be a lot longer, but whether or not it would be faster is moot.
302

303
      Note that at this point, CT(src,1) & CT(src,2) contain coinc queue
304
      info and must *not* be altered; so we have to take care in the
305
      handling of inverse entries and/or if any of low1s/high1s or
306
      low2s/high2s equal src. */
307

308
      /* Look at the consequences of column 1 of rows src & dst. */
309

310
      if (high1 != 0) 
311
        { 
312
        /* Delete ct(high1, inv1) at this stage rather than replace by dst
313
        to avoid having two occurrences of dst in the one column. */
314

315
        if (high1 != src) 
316
          { CT(high1,inv1) = 0; }
317
        else 
318
          { high1 = dst; }
319

320
        if ((low1 = COL1(dst)) != 0)	/* note the coincidence */ 
321
          { SAVE12(low1, high1); } 
322
        else 				/* note the deduction */
323
          { 
324
          COL1(dst) = high1;
325
          if (saved)
326
            { SAVED(dst,1); }
327
          }
328
 
329
        if ((lowi = COL1(dst)) != 0 && CT(lowi,inv1) == 0 && lowi != src) 
330
          { CT(lowi,inv1) = dst; }
331
        }
332

333
      /* Look at the consequences of column 2 of rows src & dst. */
334

335
      if (high2 != 0) 
336
        { 
337
        /* Delete ct(high2, inv2) at this stage rather than replace by dst
338
        to avoid having two occurrences of dst in the one column. */
339

340
        if (high2 != src) 
341
          { CT(high2,inv2) = 0; }
342
        else 
343
          { high2 = dst; }
344
 
345
        if ((low2 = COL2(dst)) != 0)	/* note the coincidence */ 
346
          { SAVE12(low2,high2); } 
347
        else 				/* note the deduction */
348
          { 
349
          COL2(dst) = high2;
350
          if (saved)
351
            { SAVED(dst,2); }
352
          }
353
 
354
        if ((lowi = COL2(dst)) != 0 && CT(lowi,inv2) == 0 && lowi != src) 
355
          { CT(lowi,inv2) = dst; }
356
        }
357

358
      /* Adjust nalive & check to see if we've hit the jackpot.  Also see
359
      if we have to fire up a message. */
360

361
      if (--nalive == 1 && COL1(1) != 0 && COL2(1) != 0) 
362
        { 
363
        if (al0_chk1())   
364
          { return(TRUE); }
365
        }
366

367
#ifdef AL0_CC
368
      if (msgctrl && --msgnext == 0)
369
        {
370
        msgnext = msgincr;
371
        ETINT;
372
        fprintf(fop, "CC: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
373
        MSGMID;
374
        fprintf(fop, " d=%d\n", topded+1);
375
        BTINT;
376
        }
377
#endif
378
      }
379

380
    /* Now compress both paths down to dst, if required.  This *may*
381
    speed up future calls to CREP (on ave).  Also, if CREP is *not* used 
382
    in al0_coinc, it can dramatically decrease the amount of information 
383
    moved & deductions stacked when processing cols >=3 (ie, cded's).  Of
384
    course, lots of these stacked ded'ns will be redundant, but still. */
385

386
    if (pcomp)
387
      {
388
      COMPRESS(high,dst);
389
      COMPRESS(low,dst);
390
      }
391

392
    /* After processing high (=rhigh) = low (=rlow) ==> dst, we can remove
393
   this, and any coincidences rendered redundant, from the stored pair.
394
   Note that we must preserve the pair's order here, so that SAVE12 works 
395
   ok.  Is it necessary to check *all* these cases? */
396

397
    if (low1s != 0)
398
      {
399
      if (low1s == high || low1s == low || low1s == src)
400
        { low1s = dst; }
401
      if (high1s == high || high1s == low || high1s == src)
402
        { high1s  = dst; }
403

404
      if (low1s == high1s)
405
        { low1s = 0; }
406
      else if (low1s > high1s)
407
        { SWAP(low1s, high1s); }
408
      }
409

410
    if (low2s != 0)
411
      {
412
      if (low2s == high || low2s == low || low2s == src)
413
        { low2s = dst; }
414
      if (high2s == high || high2s == low || high2s == src)
415
        { high2s = dst; }
416

417
      if (low2s == high2s)
418
        { low2s = 0; }
419
      else if (low2s > high2s)
420
        { SWAP(low2s, high2s); }
421
      }
422

423
    /* Find the next coincident pair to process. */
424

425
    if (low1s != 0)
426
      {
427
      low = low1s;
428
      low1s = 0;
429
      high = high1s;
430
      }
431
    else if (low2s != 0)
432
      {
433
      low = low2s;
434
      low2s = 0;
435
      high = high2s;
436
      }
437
    else			/* nothing left to do */
438
      { return(FALSE); }
439
    }
440
  }
441

442
	/******************************************************************
443
	int al0_coinc(int low, int high, Logic saved)
444

445
	Process the primary coincidence low = high and its consequences.
446
	This routine (well, al0_cols12 actually) uses the idea described by
447
	Beetham ("Space saving in coset enumeration", Durham Proceedings 
448
	(Academic Press, 1984)) but not the data structure.  It uses the 
449
	data structure used in CDHW ("Implementation and analysis of the 
450
	Todd-Coxeter algorithm", Mathematics of Computation, 1973), with 
451
	some modifications.
452

453
	If saved is TRUE, we save any deductions on the stack.  (In the old
454
	adaptive stategy we were free not to do this, or to detect a `big'
455
	collapse `early' and stop recording deductions (& new coincs?) & 
456
	throw away any existing ones.)  If we have a collapse to 1 in 
457
	al0_cols12, we return 1, having adjusted knr/knh/nextdf.  We choose
458
	*not* to do any speculative checking as to whether or not knr/knh 
459
	bumps into nextdf, which would imply a finite index (although not
460
	necessarily =nalive), since this would not give an early result
461
	frequently enough to justify its cost.  So, apart from the collapse
462
	to 1 case, we return -1 and do not change knr/knh/nextdf.  However,
463
	the cosets pointed to by knr/knh *can* become redundant, and it is 
464
	the caller's responsibility to check for this and take apporpriate
465
	action.
466

467
	Since we fully process all primary coincidences as they occur, the
468
	coincidence queue is guaranteed empty at entry and when we return.
469
	We throw away any outstanding p.d.'s, since they're (probably)
470
	invalid & it's too much trouble to sort it all out.  We may exit
471
	this routine with a large deduction stack, so we try to cull 
472
	redundant entries from this (if permitted by dedmode).  However, we
473
	can do little regarding duplicate entries, or entries of a 
474
	deduction & it's inverse.
475
	******************************************************************/
476

477
int al0_coinc(int low, int high, Logic saved)
478
  { 
479
  int i, j;				/* Temps / for macros */
480
  int lowi, highi;
481
  int chigh, clow, crep;		/* current high, low & rep */
482

483
  /* The xcoinc statistic counts the number of calls to this function.  We
484
  drop out immediately if we're called `needlessly'. */
485

486
  INCR(xcoinc);
487

488
  if (low == high) 
489
    { return(-1); }
490

491
  /* Process columns 1 and 2 of the primary coincidence. */
492

493
  if (al0_cols12(low,high,saved))  
494
    { return(1); }
495

496
  /* While there are coincidences on the queue, process columns 3 to ncol 
497
  of the coincidence chigh=clow.  Note that crep <= clow < chigh is 
498
  guaranteed.  When chigh = clow was queued, clow was non-redundant and
499
  the rep of chigh.  This may no longer be true, so we could pick up the
500
  current rep of clow (chigh *must* be left alone).  Formally, there is no
501
  problem if we do not do this, since if clow is now redundant it was
502
  queued *after* chigh.  So all we'd do is move info to clow, and then move
503
  it again when clow is processed.
504

505
  The (optional) path compression code in 3.000 has been removed. */
506

507
  while (chead != 0) 
508
    { 
509
    chigh = chead;
510
    crep  = clow = -COL1(chigh);
511
    chead = COL2(chead);		/* dequeue coinc being processed */
512

513
    for (i = 3; i <= ncol; i++) 
514
      {	
515
      /* highi - column i entry of coset chigh */
516
      if ((highi = CT(chigh, i)) == 0) 
517
        { continue; }
518
      j = invcol[i];
519

520
      /* Delete CT(highi,j) at this stage rather than replace by crep to
521
      avoid having two occurrences of crep in the one column. */
522

523
      if (highi != chigh) 
524
        { CT(highi,j) = 0; }
525
      else 
526
        { highi = crep; }
527

528
      /* lowi - column i entry for coset crep */
529
      if ((lowi = CT(crep,i)) != 0) 
530
        {
531
        if (lowi == chigh) 
532
          { lowi = crep; }
533

534
        /* We have found a (possibly new) coincidence highi=lowi. */
535

536
        if (al0_cols12(lowi,highi,saved)) 
537
          { return(1); }
538
        } 
539
      else 
540
        {			/* Mark new ded'n for later processing? */
541
        CT(crep,i) = highi;
542
        if (saved)
543
          { SAVED(crep,i); }
544
        }
545

546
      if ((lowi = CT(crep, i)) != 0 && CT(lowi, j) == 0)  
547
        { CT(lowi, j) = crep; }
548
      }
549
    }
550

551
  chead = ctail = 0; 		/* guaranteed empty coincidence list */
552
  toppd = botpd = 0;		/* pd's no longer valid */
553

554
  /* At this stage we may or may not have a `large' stack, and it may or
555
  may not contain redundancies/duplicates/inverses.  We have a choice of 
556
  many things to do with it ...  At some point we might want to add some
557
  special tracing code to find out just what's in the stack! */
558

559
  switch(dedmode)
560
    {
561
    case 1:
562
    while(topded >= 0 && COL1(dedrow[topded]) < 0)
563
      { topded--; }
564
    break;
565

566
    case 2:
567
    /* Delete all entries referencing dead cosets from the list of
568
    deductions, by `compacting' the stack.  We make no attempt to cull
569
    duplicate or `inverse' entries. */
570

571
    j = -1;
572
    i = 0;
573
    while (i <= topded && COL1(dedrow[i]) >= 0)
574
      { j++;  i++; }
575
    for ( ; i <= topded; i++)
576
      {
577
      if (COL1(dedrow[i]) >= 0)
578
        {
579
        dedrow[++j] = dedrow[i];
580
        dedcol[j]   = dedcol[i];
581
        }
582
      }
583
    topded = j;
584
    break;
585
    }
586

587
  return(-1);
588
  }
589

590

591