1 /****************************************************************************
2 **
3 *A interactive_pq.c ANUPQ source Eamonn O'Brien
4 **
5 *Y Copyright 1995-2001, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
6 *Y Copyright 1995-2001, School of Mathematical Sciences, ANU, Australia
7 **
8 */
9
10 #include "pq_defs.h"
11 #include "pcp_vars.h"
12 #include "pga_vars.h"
13 #include "exp_vars.h"
14 #include "constants.h"
15 #include "menus.h"
16 #include "pq_functions.h"
17 #include "pretty_filterfns.h"
18 #include "word_types.h"
19 #include "global.h"
20
21 #define MAXOPTION 31 /* maximum number of menu options */
22 #define GAP_PRES_FORMAT 2
23
24 #define BOTH_TAILS 0
25 #define NEW_TAILS 1
26 #define COMPUTE_TAILS 2
27
28 #if defined(GROUP)
29
30 /* interactive menu for p-quotient calculation */
31
interactive_pq(Logical group_present,int format,int output_level,int ** head,int ** list,struct pcp_vars * pcp)32 void interactive_pq(Logical group_present,
33 int format,
34 int output_level,
35 int **head,
36 int **list,
37 struct pcp_vars *pcp)
38 {
39 register int *y = y_address;
40
41 int option, t, class;
42 register int cp;
43 Logical print_flag;
44 int type;
45 int i;
46 int factor, limit;
47 int ***auts;
48 char *s;
49 char *name;
50 FILE *FileName;
51
52 int *queue, *long_queue;
53 int start_length = 0;
54 int prev_qlength = 0, current_qlength;
55 int long_queue_length = 0, queue_length = 0;
56 int consistency_type;
57 int nmr_of_auts;
58 int nmr_of_exponents;
59 int tail_type;
60 int start_gen, final_gen;
61
62 Logical queue_setup = FALSE; /* redundancy queue set up? */
63 Logical echelon_ready = FALSE; /* ready to echelonise? */
64
65 Logical output; /* temporarily store value of pcp->fullop */
66 struct exp_vars exp_flag;
67
68 Logical symbols_setup = FALSE;
69
70 int file_format;
71
72 if (isatty(0))
73 list_interactive_pq_menu();
74
75 if (format != BASIC && group_present == TRUE) {
76 setup_symbols(pcp);
77 symbols_setup = TRUE;
78 }
79
80 do {
81 option = read_option(MAXOPTION);
82 switch (option) {
83
84 case -1:
85 list_interactive_pq_menu();
86 break;
87
88 case COLLECT:
89 t = runTime();
90 if (format != BASIC && symbols_setup == FALSE) {
91 setup_symbols(pcp);
92 symbols_setup = TRUE;
93 }
94 type = WORD;
95 if (!is_space_exhausted(3 * pcp->lastg + 2, pcp)) {
96 cp = pcp->lused;
97 setup_word_to_collect(stdin, format, type, cp, pcp);
98 t = runTime() - t;
99 printf("Collection took %.2f seconds\n", t * CLK_SCALE);
100 echelon_ready = TRUE;
101 }
102 break;
103
104 case SOLVE:
105 t = runTime();
106 if (format != BASIC && symbols_setup == FALSE) {
107 setup_symbols(pcp);
108 symbols_setup = TRUE;
109 }
110 setup_to_solve_equation(format, pcp);
111 t = runTime() - t;
112 printf("Solving the equation took %.2f seconds\n", t * CLK_SCALE);
113 break;
114
115 case COMMUTATOR:
116 t = runTime();
117 if (format != BASIC && symbols_setup == FALSE) {
118 setup_symbols(pcp);
119 symbols_setup = TRUE;
120 }
121 calculate_commutator(format, pcp);
122 cp = pcp->lused;
123 echelon_ready = TRUE;
124 t = runTime() - t;
125 printf("Commutator calculation took %.2f seconds\n", t * CLK_SCALE);
126 break;
127
128 case DISPLAY_PRESENTATION:
129 print_flag = (output_level >= MAX_PRINT - 1) ? TRUE : FALSE;
130 print_presentation(print_flag, pcp);
131 break;
132
133 case PRINT_LEVEL:
134 print_level(&output_level, pcp);
135 break;
136
137 case SETUP:
138 if (pcp->complete) {
139 printf("Group is complete\n");
140 break;
141 }
142 setup(pcp);
143 pcp->update = FALSE;
144 pcp->middle_of_tails = FALSE;
145 printf("Setup performed for class %d\n", pcp->cc);
146 break;
147
148 case TAILS:
149 t = runTime();
150 if (pcp->complete) {
151 printf("Group is complete\n");
152 break;
153 }
154 pcp->middle_of_tails = FALSE;
155 read_value(TRUE,
156 "Input class for tails computation (0 for all): ",
157 &class,
158 -9999);
159 /* by negative class we mean that we want to extend the lower central
160 series up to -class, by adding p-powers. Variable i is hijacked. */
161 if (class < 0) { i = class; class = 0; } else { i = 1; }
162
163 tail_info(&tail_type);
164 if (class == 0 || (class > 1 && class <= pcp->cc)) {
165 if (class > 0) {
166 tails(tail_type, class, pcp->cc, i, pcp);
167 if (class != 2)
168 pcp->middle_of_tails = TRUE;
169 } else {
170 /* variable end_weight is never used. We hijack it to pass the
171 l.c.s. desired depth. */
172 for (class = pcp->cc; class > 1; --class)
173 tails(tail_type, class, pcp->cc, i, pcp);
174 }
175 if (pcp->overflow && !isatty(0))
176 exit(FAILURE);
177 t = runTime() - t;
178 printf("Tails computation took %.2f seconds \n", t * CLK_SCALE);
179 } else
180 printf("Class %d is invalid for tails calculations\n", class);
181 break;
182
183 case CONSISTENCY:
184 t = runTime();
185 if (pcp->complete) {
186 printf("Group is complete\n");
187 break;
188 }
189 read_value(TRUE,
190 "Input class for consistency check (0 for all): ",
191 &class,
192 0);
193 consistency_info(&consistency_type);
194 if (class == 0 || (class > 2 && class <= pcp->cc)) {
195 if (pcp->m != 0) {
196 queue_setup = TRUE;
197 start_length = queue_length;
198 queue_space(
199 &queue, &long_queue, ¤t_qlength, &prev_qlength, pcp);
200 }
201
202 if (class > 0)
203 consistency(consistency_type, queue, &queue_length, class, pcp);
204 else
205 for (class = pcp->cc; class > 2; --class)
206 consistency(
207 consistency_type, queue, &queue_length, class, pcp);
208 if (pcp->overflow && !isatty(0))
209 exit(FAILURE);
210
211 if (pcp->m != 0) {
212 s = (queue_length - start_length == 1) ? "y" : "ies";
213 printf("Consistency checks gave %d redundanc%s\n",
214 queue_length - start_length,
215 s);
216 }
217 if (pcp->complete && output_level <= 1)
218 text(5, pcp->cc, pcp->p, pcp->lastg, 0);
219 t = runTime() - t;
220 printf("Consistency checks took %.2f seconds\n", t * CLK_SCALE);
221 } else
222 printf("Class %d is invalid for consistency checks\n", class);
223 break;
224
225 case RELATIONS:
226 t = runTime();
227 if (pcp->complete) {
228 printf("Group is complete\n");
229 break;
230 }
231
232 /* if no tails have been added, do not perform update */
233 if (y[pcp->clend + pcp->cc - 1] < pcp->lastg) {
234 if (!pcp->complete && pcp->cc > 1 && !pcp->middle_of_tails &&
235 !pcp->update) {
236 update_generators(pcp);
237 pcp->update = TRUE;
238 }
239 if (!pcp->complete)
240 collect_relations(pcp);
241 }
242
243 if (pcp->complete && output_level <= 1)
244 text(5, pcp->cc, pcp->p, pcp->lastg, 0);
245
246 t = runTime() - t;
247 printf("Collection of relations took %.2f seconds\n", t * CLK_SCALE);
248 break;
249
250 case EXTRA_RELATIONS:
251 t = runTime();
252 if (pcp->complete) {
253 printf("Group is complete\n");
254 break;
255 }
256 if (pcp->extra_relations == 0) {
257 read_value(TRUE,
258 "Input exponent law (0 if none): ",
259 &pcp->extra_relations,
260 0);
261 }
262 read_value(TRUE,
263 "Input start weight for exponent checking: ",
264 &pcp->start_wt,
265 1);
266 read_value(TRUE,
267 "Input end weight for exponent checking: ",
268 &pcp->end_wt,
269 pcp->start_wt);
270 exponent_info(&exp_flag, pcp);
271 if (pcp->m != 0) {
272 queue_setup = TRUE;
273 start_length = queue_length;
274 queue_space(
275 &queue, &long_queue, ¤t_qlength, &prev_qlength, pcp);
276 exp_flag.queue = queue;
277 exp_flag.queue_length = queue_length;
278 }
279
280 extra_relations(&exp_flag, pcp);
281
282 if (pcp->m != 0) {
283 queue = exp_flag.queue;
284 queue_length = exp_flag.queue_length;
285 s = (queue_length - start_length == 1) ? "y" : "ies";
286 printf("Exponent checks gave %d redundanc%s\n",
287 queue_length - start_length,
288 s);
289 }
290
291 if (pcp->complete && output_level <= 1)
292 text(5, pcp->cc, pcp->p, pcp->lastg, 0);
293
294 t = runTime() - t;
295 printf("Time to check exponents is %.2f seconds\n", t * CLK_SCALE);
296 break;
297
298 case ELIMINATE:
299 t = runTime();
300 symbols_setup = FALSE;
301 if (pcp->cc == 1)
302 class1_eliminate(pcp);
303 else {
304 /* if no tails have been added, do not perform update */
305 if (y[pcp->clend + pcp->cc - 1] < pcp->lastg) {
306 if (pcp->cc > 1 && !pcp->middle_of_tails && !pcp->update) {
307 update_generators(pcp);
308 pcp->update = TRUE;
309 }
310 eliminate(pcp->middle_of_tails, pcp);
311 queue_length = 0;
312 long_queue_length = 0;
313 }
314 }
315
316 t = runTime() - t;
317 printf("Elimination took %.2f seconds\n", t * CLK_SCALE);
318 break;
319
320 case LAST_CLASS:
321 last_class(pcp);
322 break;
323
324 case MAXOCCUR:
325 set_maxoccur(pcp);
326 break;
327
328 case METABELIAN:
329 pcp->metabelian = TRUE;
330 break;
331
332 case JACOBI:
333 calculate_jacobi(pcp);
334 if (pcp->redgen != 0 && pcp->m != 0) {
335 queue_setup = TRUE;
336 if (prev_qlength == 0)
337 queue_space(
338 &queue, &long_queue, ¤t_qlength, &prev_qlength, pcp);
339 queue[++queue_length] = pcp->redgen;
340 }
341 break;
342
343 case ECHELON:
344 if (echelon_ready) {
345 for (i = 1; i <= pcp->lastg; ++i)
346 y[cp + pcp->lastg + i] = 0;
347 output = pcp->fullop;
348 pcp->fullop = TRUE;
349 echelon(pcp);
350 pcp->fullop = output;
351 if (pcp->redgen != 0 && pcp->m != 0) {
352 queue_setup = TRUE;
353 if (prev_qlength == 0)
354 queue_space(&queue,
355 &long_queue,
356 ¤t_qlength,
357 &prev_qlength,
358 pcp);
359 queue[++queue_length] = pcp->redgen;
360 }
361 echelon_ready = FALSE;
362 } else
363 printf("No relation to echelonise; first collect or commute\n");
364 break;
365
366 case AUTS:
367 t = runTime();
368 if (pcp->m == 0) {
369 auts = read_auts(PQ, &pcp->m, &nmr_of_exponents, pcp);
370 Setup_Action(head, list, auts, nmr_of_exponents, pcp);
371 }
372 Extend_Auts(head, list, y[pcp->clend + 1] + 1, pcp);
373
374 #ifdef DEBUG
375 read_value(TRUE, "Input start generator: ", &start_gen, 1);
376 read_value(TRUE, "Input final generator: ", &final_gen, start_gen);
377 List_Auts(*head, *list, start_gen, final_gen, pcp);
378 /* print_array (*head, 0, (*head)[0] + 2); */
379 #endif
380 queue_setup = TRUE;
381 queue_space(&queue, &long_queue, ¤t_qlength, &prev_qlength, pcp);
382
383 t = runTime() - t;
384 printf("Extension of automorphisms took %.2f seconds\n",
385 t * CLK_SCALE);
386 break;
387
388 case CLOSE_RELATIONS:
389 t = runTime();
390 s = (queue_length == 1) ? "y" : "ies";
391 printf("The queue currently contains %d entr%s\n", queue_length, s);
392 /*
393 print_array (queue, 1, queue_length + 1);
394 */
395 read_value(TRUE, "Input queue factor: ", &factor, 0);
396 limit = factor * (pcp->lastg - pcp->ccbeg + 1) / 100;
397 if (!pcp->complete) {
398 close_relations(TRUE,
399 limit,
400 1,
401 *head,
402 *list,
403 queue,
404 queue_length,
405 long_queue,
406 &long_queue_length,
407 pcp);
408 }
409
410 if (!pcp->complete && !pcp->overflow) {
411 if (pcp->fullop || pcp->diagn)
412 printf("Length of long queue after short queue closed is %d\n",
413 long_queue_length);
414 close_relations(TRUE,
415 limit,
416 2,
417 *head,
418 *list,
419 long_queue,
420 long_queue_length,
421 long_queue,
422 &long_queue_length,
423 pcp);
424 if (pcp->fullop || pcp->diagn) {
425 printf("Final long queue length was %d\n", long_queue_length);
426 }
427 }
428
429 if (pcp->complete && output_level <= 1)
430 text(5, pcp->cc, pcp->p, pcp->lastg, 0);
431
432 queue_length = long_queue_length = 0;
433 t = runTime() - t;
434 printf("Closing relations took %.2f seconds\n", t * CLK_SCALE);
435 break;
436
437 case STRUCTURE:
438 read_value(
439 TRUE, "Input initial pcp generator number: ", &start_gen, 1);
440 if (start_gen <= pcp->lastg) {
441 read_value(TRUE,
442 "Input final pcp generator number: ",
443 &final_gen,
444 start_gen);
445 print_structure(start_gen, MIN(final_gen, pcp->lastg), pcp);
446 } else
447 printf("Invalid range supplied for pcp generator numbers\n");
448 break;
449
450 case ENGEL:
451 t = runTime();
452 queue_setup = TRUE;
453 queue_space(&queue, &long_queue, ¤t_qlength, &prev_qlength, pcp);
454 list_commutators(queue, &queue_length, pcp);
455
456 /*
457 List_Commutators (queue, &queue_length, pcp);
458 */
459 t = runTime() - t;
460 printf(
461 "Evaluation of Engel [y, (p - 1)x] identity took %.2f seconds\n",
462 t * CLK_SCALE);
463 break;
464
465 case LIST_AUTOMORPHISMS:
466 read_value(TRUE, "Input start generator: ", &start_gen, 1);
467 read_value(TRUE, "Input final generator: ", &final_gen, start_gen);
468 List_Auts(*head, *list, start_gen, final_gen, pcp);
469 break;
470
471 break;
472
473 case RELATIONS_FILE:
474 t = runTime();
475 if (pcp->m != 0) {
476 queue_setup = TRUE;
477 start_length = queue_length;
478 queue_space(
479 &queue, &long_queue, ¤t_qlength, &prev_qlength, pcp);
480 }
481
482 read_relator_file(queue, &queue_length, pcp);
483
484 if (pcp->m != 0) {
485 s = (queue_length - start_length == 1) ? "y" : "ies";
486 printf("Relation file gave %d redundanc%s\n",
487 queue_length - start_length,
488 s);
489 if (queue_length != 0)
490 print_array(queue, 1, queue_length + 1);
491 }
492 t = runTime() - t;
493 printf("Processing relations file took %.2f seconds\n", t * CLK_SCALE);
494 break;
495
496 case DGEN_WORD:
497 if (format != BASIC && symbols_setup == FALSE) {
498 setup_symbols(pcp);
499 symbols_setup = TRUE;
500 }
501 type = WORD;
502 if (!is_space_exhausted(3 * pcp->lastg + 2, pcp)) {
503 cp = pcp->lused;
504 setup_defgen_word_to_collect(stdin, format, type, pcp->lused, pcp);
505 echelon_ready = TRUE;
506 }
507 break;
508
509 case DGEN_COMM:
510 if (format != BASIC && symbols_setup == FALSE) {
511 setup_symbols(pcp);
512 symbols_setup = TRUE;
513 }
514 commute_defining_generators(format, pcp);
515 echelon_ready = TRUE;
516 break;
517
518 case DGEN_AUT:
519 if (format != BASIC && symbols_setup == FALSE) {
520 setup_symbols(pcp);
521 symbols_setup = TRUE;
522 }
523 auts = determine_action(format, &nmr_of_auts, pcp);
524 break;
525
526 case COMPACT:
527 compact(pcp);
528 break;
529
530 case FORMULA:
531 t = runTime();
532 if (pcp->m != 0) {
533 queue_setup = TRUE;
534 start_length = queue_length;
535 queue_space(
536 &queue, &long_queue, ¤t_qlength, &prev_qlength, pcp);
537 }
538
539 evaluate_formula(queue, &queue_length, pcp);
540
541 if (pcp->m != 0) {
542 s = (queue_length - start_length == 1) ? "y" : "ies";
543 printf("Formula checks gave %d redundanc%s\n",
544 queue_length - start_length,
545 s);
546 if (queue_length != 0)
547 print_array(queue, 1, queue_length + 1);
548 }
549
550 t = runTime() - t;
551 printf("Formula evaluation took %.2f seconds\n", t * CLK_SCALE);
552 break;
553
554 case OUTPUT_PRESENTATION:
555 /* TODO: We used to support more output formats, but now only
556 GAP output is supported. As such, the following query is no redundant.
557 We keep it for backward compatibility only. */
558 name = GetString("Enter output file name: ");
559 read_value(TRUE,
560 "Output file in GAP (2) format? ",
561 &file_format,
562 GAP_PRES_FORMAT);
563 FileName = OpenFile(name, "a+");
564 if (FileName != NULL) {
565 if (file_format == GAP_PRES_FORMAT) {
566 GAP_presentation(FileName, pcp, 1);
567 printf("Group presentation written in GAP format to file\n");
568 } else
569 printf("Format must be %d\n", GAP_PRES_FORMAT);
570 }
571 CloseFile(FileName);
572 break;
573
574 case COMPACT_PRESENTATION:
575 compact_description(TRUE, pcp);
576 printf("Group description written to gps%d^%d\n", pcp->p, pcp->lastg);
577 break;
578
579 case EXIT:
580 case MAXOPTION:
581 printf("Exiting from interactive p-Quotient menu\n");
582 break;
583
584 } /* switch */
585 } while (option != 0 && option != MAXOPTION);
586
587 if (queue_setup) {
588 free_vector(queue, 1);
589 free_vector(long_queue, 1);
590 }
591 }
592
593 /* interactive p-quotient menu */
594
list_interactive_pq_menu(void)595 void list_interactive_pq_menu(void)
596 {
597 printf("\nAdvanced p-Quotient Menu\n");
598 printf("-------------------------\n");
599 printf("%d. Do individual collection\n", COLLECT);
600 printf("%d. Solve the equation ax = b for x\n", SOLVE);
601 printf("%d. Calculate commutator\n", COMMUTATOR);
602 printf("%d. Display group presentation\n", DISPLAY_PRESENTATION);
603 printf("%d. Set print level\n", PRINT_LEVEL);
604 printf("%d. Set up tables for next class\n", SETUP);
605 printf("%d. Insert tails for some or all classes\n", TAILS);
606 printf("%d. Check consistency for some or all classes\n", CONSISTENCY);
607 printf("%d. Collect defining relations\n", RELATIONS);
608 printf("%d. Carry out exponent checks\n", EXTRA_RELATIONS);
609 printf("%d. Eliminate redundant generators\n", ELIMINATE);
610 printf("%d. Revert to presentation for previous class\n", LAST_CLASS);
611 printf("%d. Set maximal occurrences for pcp generators\n", MAXOCCUR);
612 printf("%d. Set metabelian flag\n", METABELIAN);
613 printf("%d. Carry out an individual consistency calculation\n", JACOBI);
614 printf("%d. Carry out compaction\n", COMPACT);
615 printf("%d. Carry out echelonisation\n", ECHELON);
616 printf("%d. Supply and/or extend automorphisms\n", AUTS);
617 printf("%d. Close relations under automorphism actions\n", CLOSE_RELATIONS);
618 printf("%d. Print structure of a range of pcp generators\n", STRUCTURE);
619 printf("%d. Display automorphism actions on generators\n",
620 LIST_AUTOMORPHISMS);
621 printf("%d. Collect word in defining generators\n", DGEN_WORD);
622 printf("%d. Compute commutator of defining generators\n", DGEN_COMM);
623 printf("%d. Write presentation to file in GAP format\n",
624 OUTPUT_PRESENTATION);
625 printf("%d. Write compact description of group to file\n",
626 COMPACT_PRESENTATION);
627 printf("%d. Evaluate certain formulae\n", FORMULA);
628 printf("%d. Evaluate action specified on defining generators\n", DGEN_AUT);
629 printf("%d. Evaluate Engel (p - 1)-identity\n", ENGEL);
630 printf("%d. Process contents of relation file\n", RELATIONS_FILE);
631 printf("%d. Exit to basic menu\n", MAXOPTION);
632 }
633
634 #endif
635
636 /* set up space for the queues used in exponent checking */
637
queue_space(int ** queue,int ** long_queue,int * current_qlength,int * prev_qlength,struct pcp_vars * pcp)638 int queue_space(int **queue,
639 int **long_queue,
640 int *current_qlength,
641 int *prev_qlength,
642 struct pcp_vars *pcp)
643 {
644 *current_qlength = pcp->lastg - pcp->ccbeg + 1;
645 if (*prev_qlength == 0) {
646 *queue = allocate_vector(*current_qlength, 1, FALSE);
647 *long_queue = allocate_vector(*current_qlength, 1, FALSE);
648 } else if (*current_qlength != *prev_qlength) {
649 *queue =
650 reallocate_vector(*queue, *prev_qlength, *current_qlength, 1, FALSE);
651 *long_queue = reallocate_vector(
652 *long_queue, *prev_qlength, *current_qlength, 1, FALSE);
653 }
654 *prev_qlength = *current_qlength;
655
656 return 0;
657 }
658