1
#include "typedef.h"
2
#include "voronoi.h"
3
#include "symm.h"
4
#include "autgrp.h"
5
#include "bravais.h"
6
#include "base.h"
7
#include "idem.h"
8
#include "longtools.h"
9
#include "reduction.h"
10
#include "ZZ_P.h"
11
#include "ZZ_zclass_P.h"
12
#include "ZZ_cen_fun_P.h"
13
#include "graph.h"
14

15

16
int IDEM_NO;
17
extern int INFO_LEVEL;
18
ZZ_super_TYP **SUPER_info, *SUPER_INFO;
19

20

21
/* -------------------------------------------------------------------- */
22
static matrix_TYP *good_initial_basis(matrix_TYP *B,
23
                                      matrix_TYP *F)
24
{
25

26
   int i;
27

28
   matrix_TYP *NEW,
29
              *C,
30
              *D;
31

32
   NEW = scal_pr(B,F,TRUE);
33

34
   /* reduce */
35
   C = init_mat(NEW->rows,NEW->rows,"i1");
36
   D = pair_red(NEW,C);
37

38
   free_mat(D);
39
   free_mat(NEW);
40

41
   NEW = mat_mul(C,B);
42

43
   free_mat(C);
44
   free_mat(B);
45

46
   return NEW;
47
}
48

49

50
   /* free konst
51
   if (flag == 1){
52
      for (i = 0; i < super->konst->k; i++){
53
         for (j = 0; j < super->konst->s[i]; j++){
54
            for (k = 0; k < super->konst->r; k++){
55
               free_mat(super->konst->Delta[i][j][k]);
56
            }
57
            free(super->konst->Delta[i][j]);
58
         }
59
         free(super->konst->Delta[i]);
60
      }
61
      free(super->konst->Delta);
62
      free(super->konst->s);
63
      free(super->konst);
64
   }
65
*/
66

67
/* ------------------------------------------------------------------ */
68
static void free_ZZ_super(ZZ_super_TYP *super)
69
{
70
   int i, j, k;
71
	
72
   ZZ_node_t *n, *t;
73

74

75
   n = super->tree->root;
76
   do {
77
      t = n->next;		
78
      ZZ_free_node (super->data, n);
79
   } while ((n = t) != NULL);
80
   free(super->tree);
81

82
   ZZ_free_data(super->data);
83
   free(super->data);
84

85
   free(super);
86
}
87

88

89

90

91
/* ------------------------------------------------------------------ */
92
void free_QtoZ(QtoZ_TYP *inz,
93
               int flag)
94
{
95
   int i, j, k;
96

97

98
   if (inz->zoogitter != NULL){
99
      for (i = 0; i < inz->anz; i++){
100
         for (j = 0; j < inz->entry[i][0].anz; j++){
101
            if (inz->zoogitter[i][j] != NULL)
102
               free_mat(inz->zoogitter[i][j]);
103
         }
104
         if (inz->zoogitter[i] != NULL)
105
            free(inz->zoogitter[i]);
106
      }
107
      free(inz->zoogitter);
108
   }
109
   for (i = 0; i < inz->anz; i++){
110
      if (flag == 1 && inz->gitter[i] != NULL){
111
         free_mat(inz->gitter[i]);
112
         free_mat(inz->tr_gitter[i]);
113
         free_mat(inz->inv_tr_gitter[i]);
114
      }
115
      for (j = 0; j < inz->anz + flag; j++){
116
         if (inz->entry[i][j].anz != 0){
117
            free(inz->entry[i][j].I);
118
            free(inz->entry[i][j].J);
119
            free(inz->entry[i][j].flag);
120
            if (flag == 0){
121
               for (k = 0; k < inz->entry[i][j].anz; k++){
122
                  free_mat(inz->entry[i][j].lattice[k]);
123
               }
124
            }
125
            free(inz->entry[i][j].lattice);
126
            if (flag == 0){
127
               for (k = 0; k < inz->entry[i][j].anz; k++){
128
                  free_mat(inz->entry[i][j].lsf[k]);
129
               }
130
               free(inz->entry[i][j].lsf);
131
            }
132
         }
133
      }
134
      free(inz->entry[i]);
135
   }
136
   free(inz->entry);
137

138
   if (flag == 1){
139
      free(inz->gitter);
140
      free(inz->inv_tr_gitter);
141
      free(inz->tr_gitter);
142
   }
143

144
   free(inz);
145
}
146

147

148

149
/*------------------------------------------------------------------------------- */
150
static int suche_mat(matrix_TYP *mat,
151
                     matrix_TYP **liste,
152
                     int anz)
153
{
154
   int i;
155

156
   for (i = 0; i < anz; i++){
157
      if (cmp_mat(mat, liste[i]) == 0)
158
         return(i);
159
   }
160
   return(-1);
161
}
162

163

164

165
/* ------------------------------------------------------------------------------- */
166
static matrix_TYP *hom_de_super(bravais_TYP *group,
167
                                matrix_TYP *id,
168
                                matrix_TYP **idem,
169
                                int idem_no)
170
{
171
   matrix_TYP *F,
172
              *tmp,
173
              *new_basis,
174
             **idem_spaces;
175

176
   int i, j, k,
177
       col, kgv,
178
       mult;
179

180

181

182
   F = rform(group->gen, group->gen_no, id, 101);
183
   idem_spaces = (matrix_TYP **)calloc(idem_no, sizeof(matrix_TYP *));
184

185
   for (i = 0; i < idem_no; i++){
186
      tmp = tr_pose(idem[i]);
187
      idem_spaces[i] = ggauss(tmp);
188
      idem_spaces[i] = good_initial_basis(idem_spaces[i], F);
189
      free_mat(tmp);
190
   }
191

192
   kgv = 1;
193
   for (i = 0; i < idem_no; i++){
194
      kgv = KGV(kgv, idem_spaces[i]->kgv);
195
   }
196

197
   for (i = 0; i < idem_no; i++){
198
      mult = kgv/idem_spaces[i]->kgv;
199
      if (mult != 1){
200
         for (j = 0; j < idem_spaces[i]->rows; j++){
201
            for (k = 0; k < idem_spaces[i]->cols; k++)
202
               idem_spaces[i]->array.SZ[j][k] *= mult;
203
         }
204
         idem_spaces[i]->kgv = kgv;
205
      }
206
   }
207

208
   new_basis = init_mat(group->dim, group->dim, "1");
209
   col = -1;
210
   for (i = 0; i < idem_no; i++){
211
      for (j = 0; j < idem_spaces[i]->rows; j++){
212
         col++;
213
         for (k = 0; k < group->dim; k++){
214
            new_basis->array.SZ[k][col] = idem_spaces[i]->array.SZ[j][k];
215
         }
216
      }
217
   }
218
   new_basis->kgv = kgv;
219
   Check_mat(new_basis);
220

221
   /* clean */
222
   for (i = 0; i < idem_no; i++){
223
      free_mat(idem_spaces[i]);
224
   }
225
   free(idem_spaces);
226
   free_mat(F);
227

228
   return(new_basis);
229
}
230

231

232

233
/* ------------------------------------------------------------------ */
234
static void get_normalizer(bravais_TYP *H)
235
{
236

237
    matrix_TYP *ID,
238
               *F,
239
               *PF,
240
              **N,
241
              **forms,
242
               *trbifo;
243

244
    bravais_TYP *Htr,
245
		  *HB;
246

247
    int i,
248
        j,
249
        vno;
250

251
    voronoi_TYP **V;
252

253
    Htr = tr_bravais(H,1,FALSE);
254
    ID = init_mat(H->dim,H->dim,"1");
255
    F = rform(H->gen,H->gen_no,ID,101);
256
    trbifo = trace_bifo(H->form,Htr->form,H->form_no);
257
    PF = first_perfect(F,H,Htr->form,trbifo,&i);
258

259
    /* calculate the normalizer of the bravais group */
260
	 HB = bravais_group(H,TRUE);
261
    V = normalizer(PF,HB,Htr,1949,&vno);
262
	 H->normal = HB->normal ; H->normal_no = HB->normal_no;
263
	 HB->normal = NULL; HB->normal_no = 0;
264
	 free_bravais(HB);
265

266
    /* calculate the bravais group itself */
267
    free_bravais(Htr);
268
    forms = (matrix_TYP **) malloc( (1+H->form_no) * sizeof(matrix_TYP *));
269
    for (i=0;i<H->form_no;i++)
270
       forms[i+1] = H->form[i];
271
    forms[0] = PF;     /* a H-perfect form is especially good */
272

273

274
    /* replaced the following two statements by a better one
275
    tilman 06.05.98:
276
    SV = short_vectors(PF,max_diagonal_entry(PF),0,0,0,&i);
277
    Htr = autgrp(forms,H->form_no+1,SV,NULL,0,NULL); */
278
    Htr = pr_aut(forms,H->form_no+1,NULL,0,NULL);
279

280
    Htr->normal = H->normal;
281
    Htr->normal_no = H->normal_no;
282
    H->normal = NULL;
283
    H->normal_no = 0;
284

285
    H->normal = normalizer_in_N(H,Htr,&H->normal_no,FALSE);
286

287
    /* clean up */
288
    free_mat(ID);
289
    free_mat(F);
290
    free_mat(PF);
291
    free_mat(trbifo);
292
    free_bravais(Htr);
293
    for (i=0;i<vno;i++){
294
       clear_voronoi(V[i]);
295
       free(V[i]);
296
    }
297
    free(V);
298
    /* free_mat(SV); */
299
    free(forms);
300

301
    return;
302
}
303

304

305

306
/* ------------------------------------------------------------------ */
307
static bravais_TYP **almost(bravais_TYP *H)
308
{
309
   int i,
310
       j,
311
       zentr_no,
312
       normal_no,
313
       cen_no;
314

315
   matrix_TYP *tmp;
316

317
   bravais_TYP **RES;
318

319
   RES = (bravais_TYP **) malloc((1+H->zentr_no) * sizeof(bravais_TYP *));
320

321
   H->gen_no -= IDEM_NO;
322
   normal_no = H->normal_no;
323
   H->normal_no = 0;
324
   cen_no = H->cen_no;
325
   H->cen_no = 0;
326
   zentr_no = H->zentr_no;
327
   H->zentr_no = 0;
328
   for (i=0;i<zentr_no;i++){
329
      if (i==0){
330
         RES[i] = copy_bravais(H);
331
      }
332
      else{
333
         tmp = mat_inv(H->zentr[i]);
334
         RES[i] = konj_bravais(H,tmp);
335
         free_mat(tmp);
336
      }
337
      for (j=0;j<H->form_no;j++){
338
         RES[i]->form[j]->kgv = 1;
339
      }
340
      long_rein_formspace(RES[i]->form,RES[i]->form_no,1);
341
      get_normalizer(RES[i]);
342
   }
343

344
   H->gen_no += IDEM_NO;
345
   H->cen_no = cen_no;
346
   H->normal_no = normal_no;
347

348
/* changed by oliver:
349
   for (i=0;i<zentr_no;i++){
350
      free_mat(H->zentr[i]);
351
   }
352
   free(H->zentr);
353
   H->zentr = NULL;
354
*/
355
   H->zentr_no = zentr_no;
356

357
   return RES;
358
}
359

360

361

362
/* ------------------------------------------------------------------ */
363
/* this function was for test purposes only
364
static matrix_TYP *better_base2(matrix_TYP *B,
365
                                int number,
366
                                matrix_TYP **SP)
367
{
368

369
   int i,
370
       j,
371
       k,
372
       offset = 0;
373

374
   matrix_TYP *NEW,
375
              *C;
376

377
   put_mat(B,NULL,"B",0);
378
   NEW = init_mat(B->rows,B->cols,"i");
379

380
   for (i=0;i<number;i++){
381
      C = init_mat(SP[i]->rows,B->rows,"i");
382
      for (j=0;j<SP[i]->rows;j++){
383
         for (k=0;k<B->rows;k++){
384
            C->array.SZ[j][k] = B->array.SZ[k][j+offset];
385
         }
386
      }
387

388
      long_row_basis(C,TRUE);
389

390
      for (j=0;j<SP[i]->rows;j++){
391
         for (k=0;k<B->rows;k++){
392
            NEW->array.SZ[k][j+offset] = C->array.SZ[j][k];
393
         }
394
      }
395
      free_mat(C);
396

397
      offset += SP[i]->rows;
398
   }
399

400
   free_mat(B);
401

402
   return NEW;
403
}  */
404

405

406

407
/* ------------------------------------------------------------------ */
408
static matrix_TYP *better_base(matrix_TYP *B,
409
                               matrix_TYP *F,
410
                               int number,
411
                               matrix_TYP **SP)
412
{
413

414
   int i,
415
       j,
416
       k,
417
       offset = 0;
418

419

420
   matrix_TYP *NEW,
421
              *TR,
422
              *C,
423
              *D;
424

425
   /* put_mat(B,NULL,"B",0); */
426

427
   TR = init_mat(B->cols,B->cols,"i");
428
   for (i=0;i<number;i++){
429
      C = init_mat(SP[i]->rows,B->rows,"i");
430
      for (j=0;j<B->rows;j++){
431
         for (k=0;k<SP[i]->rows;k++){
432
            C->array.SZ[k][j] = B->array.SZ[j][k+offset];
433
         }
434
      }
435

436
      /* calculate the form on this subspace */
437
      NEW = scal_pr(C,F,TRUE);
438
      free_mat(C);
439

440
      /* reduce the form */
441
      C = init_mat(NEW->rows,NEW->rows,"i1");
442
      D = pair_red(NEW,C);
443
      free_mat(D);
444

445
      /* store the transformation */
446
      for (j=0;j<C->rows;j++){
447
         for (k=0;k<C->cols;k++){
448
            TR->array.SZ[offset+k][offset+j] = C->array.SZ[j][k];
449
         }
450
      }
451

452
      free_mat(C);
453
      free_mat(NEW);
454
      offset += SP[i]->rows;
455
   }
456

457
   /* put_mat(TR,0,"TR",0); */
458
   mat_muleq(B, TR);
459

460
   return(TR);
461
}
462

463

464
static matrix_TYP **get_better_base(bravais_TYP *H,
465
                                    matrix_TYP *F,
466
                                    int number,
467
                                    matrix_TYP **SPACES)
468
{
469

470
   int i;
471

472
   matrix_TYP *id = NULL,
473
              **better,
474
               *tmp;
475

476

477
   if (F == NULL){
478
      id = init_mat(H->dim,H->dim,"i1");
479
      F = rform(H->gen,H->gen_no,id,101);
480
   }
481
   better = (matrix_TYP **)calloc(H->zentr_no, sizeof(matrix_TYP *));
482

483
   for (i = 1; i < H->zentr_no; i++){
484
      better[i] = better_base(H->zentr[i],F,number,SPACES);
485
   }
486

487
   if (id){
488
      free_mat(F);
489
      free_mat(id);
490
   }
491

492
   return(better);
493

494
}
495

496

497

498

499
static matrix_TYP **GL_n_Z(int dim,int *no)
500
{
501

502
   int i;
503

504
   matrix_TYP **RES;
505

506
   if (dim == 1){
507
      *no = 1;
508
      RES = (matrix_TYP **) malloc(1*sizeof(matrix_TYP *));
509
      RES[0] = init_mat(1,1,"i0");
510
      RES[0]->array.SZ[0][0] = -1;
511
   }
512
   else{
513
      *no = 4;
514
      RES = (matrix_TYP **) malloc(4*sizeof(matrix_TYP *));
515
      RES[0] = init_mat(dim,dim,"i1");
516
      RES[0]->array.SZ[0][0] = -1;
517
      RES[1] = init_mat(dim,dim,"i1");
518
      RES[1]->array.SZ[0][1] = 1;
519
      RES[2] = init_mat(dim,dim,"i1");
520
      RES[2]->array.SZ[0][1] = 1;
521
      RES[2]->array.SZ[1][0] = 1;
522
      RES[2]->array.SZ[0][0] = 0;
523
      RES[2]->array.SZ[1][1] = 0;
524
      RES[3] = init_mat(dim,dim,"i0");
525
      for (i=0;i<dim;i++)
526
         RES[3]->array.SZ[i][(i+1)%dim] = 1;
527
      for (i=0;i<4;i++)
528
         Check_mat(RES[i]);
529
   }
530

531
   return RES;
532

533
}
534

535
/* -------------------------------------------------------------------- */
536
/* -------------------------------------------------------------------- */
537
/* -------------------------------------------------------------------- */
538
bravais_TYP **q2z(bravais_TYP *G,
539
                  int *number,
540
                  int ADFLAG,
541
                  QtoZ_TYP *INZ,
542
                  int quiet)
543
{
544
   bravais_TYP **GROUPS,
545
               **ADGROUPS,
546
                *H,
547
                *group,
548
                *ggg;
549

550
   matrix_TYP **IDEM,
551
              **IDEM_SPACES,
552
              **idem_spaces,
553
               *F,
554
               *tmp,
555
               *new_base,
556
               *id,
557
               *X,
558
/*               *test, */
559
              **conj_idem,
560
              **real_idem,
561
               *zoo_kon,
562
               *lattice,
563
               *zoolattice,
564
               *zoolattice_hnf,
565
               *zoolattice_inv,
566
               *zoo_inv,
567
               *elementar,
568
              **better,
569
              **trash,
570
               *zwischen,
571
               *ttt,
572
              **zentr_inv;
573

574
   char zzoptions[128],
575
        string[128];
576

577
   int i,
578
       j,
579
       k,
580
       l,
581
       m,
582
       f,
583
       kgv, mult,
584
       aa, bb,
585
       counter,
586
       ganzzahlig,
587
       help,
588
       idem_no,
589
       ad_no,
590
       col,
591
       dimc,
592
       dimcc,
593
       zen_nr, cen_nr, normal_nr,
594
       zoo, bahnnummer,
595
       samezoo, yeah,
596
      *liste;
597

598
   QtoZ_TYP **inzidenz;
599

600
   ZZ_node_t *node, *Knoten;
601

602
   ZZ_couple_t *laeufer;
603

604

605
   /* handle the case of the groups G=<I> and G=<-I> differently,
606
      because the first one couldn't be handled by this anyway,
607
      and the second one trivial is but computationaly hard in dim 5 & 6 */
608
   k = TRUE; l = TRUE;
609
   for (i=0;i<G->gen_no && k;i++){
610
      Check_mat(G->gen[i]);
611
      k = k && G->gen[i]->flags.Scalar;
612
      l = l && G->gen[i]->array.SZ[1][1] == 1;
613
   }
614
   if (l && k && G->order == 1)
615
      for (i = 0;i<100 ; l = l && G->divisors[i] == 0, i++);
616
   if ((k && G->dim > 4) ||
617
      (k && l )){
618
      GROUPS = (bravais_TYP **) malloc(1 * sizeof(bravais_TYP *));
619
      GROUPS[0] = copy_bravais(G);
620
      if (GROUPS[0]->normal && GROUPS[0]->normal_no > 0){
621
         for (k=0;k<GROUPS[0]->normal_no;k++) free_mat(GROUPS[0]->normal[i]);
622
         free(GROUPS[0]->normal);
623
      }
624
      GROUPS[0]->normal = GL_n_Z(G->dim,&GROUPS[0]->normal_no);
625
      *number = 1;
626
      if (ADFLAG){
627
          GROUPS[0]->zentr = (matrix_TYP **) malloc(1 * sizeof(matrix_TYP));
628
          GROUPS[0]->zentr[0] = init_mat(G->dim,G->dim,"1");
629
          GROUPS[0]->zentr_no = 1;
630
      }
631
      return GROUPS;
632
   }
633

634
   /* avoid silly mistakes */
635
   if (G->form == NULL ||
636
      G->form_no == 0 ||
637
      G->order == 0 ){
638
      fprintf(stderr,"You didn't specify G in an accurate way\n");
639
      exit(3);
640
   }
641

642
   id = init_mat(G->dim,G->dim,"1");
643

644
   /* we need a G-invariant, positive definite form for various reasons */
645
   F = rform(G->gen,G->gen_no,id,101);
646

647
   /* get the idempotents of the group */
648
   IDEM = idempotente(G->gen,G->gen_no,F,&IDEM_NO,&dimc,&dimcc,NULL);
649
   G->gen = (matrix_TYP **) realloc(G->gen,(G->gen_no+IDEM_NO)
650
                                    * sizeof(matrix_TYP*));
651
   IDEM_SPACES = (matrix_TYP **) malloc(IDEM_NO * sizeof(matrix_TYP *));
652
   for (i=0;i<IDEM_NO;i++){
653
      G->gen[i+G->gen_no] = IDEM[i];
654
      tmp = tr_pose(IDEM[i]);
655
      IDEM_SPACES[i] = long_rein_mat(tmp);
656
      IDEM_SPACES[i] = good_initial_basis(IDEM_SPACES[i],F);
657
      free_mat(tmp);
658
   }
659
   G->gen_no += IDEM_NO;
660
   kgv = 1;
661
   for (i = 0; i < IDEM_NO; i++){
662
      kgv = KGV(kgv, IDEM_SPACES[i]->kgv);
663
   }
664

665
   for (i = 0; i < IDEM_NO; i++){
666
      mult = kgv/IDEM_SPACES[i]->kgv;
667
      if (mult != 1){
668
         for (j = 0; j < IDEM_SPACES[i]->rows; j++){
669
            for (k = 0; k < IDEM_SPACES[i]->cols; k++)
670
               IDEM_SPACES[i]->array.SZ[j][k] *= mult;
671
         }
672
         IDEM_SPACES[i]->kgv = kgv;
673
      }
674
   }
675

676
   /* transform G to H which is an almost decomposable group */
677
   new_base = init_mat(G->dim,G->dim,"1");
678
   col = -1;
679
   for (i=0;i<IDEM_NO;i++){
680
      for (j=0;j<IDEM_SPACES[i]->rows;j++){
681
         col++;
682
         for (k=0;k<G->dim;k++){
683
            new_base->array.SZ[k][col] = IDEM_SPACES[i]->array.SZ[j][k];
684
         }
685
      }
686
   }
687

688
   new_base->kgv = kgv;
689
   Check_mat(new_base);
690
   tmp = mat_inv(new_base);
691
   i = G->zentr_no;
692
   G->zentr_no = 0;
693
   H = konj_bravais(G,tmp);
694
   for (m = 0; m < H->form_no; m++){
695
      H->form[m]->kgv = 1;
696
   }
697
   long_rein_formspace(H->form, H->form_no, 0);
698
   real_idem = &H->gen[H->gen_no - IDEM_NO];
699
   G->zentr_no = i;
700
   free_mat(tmp);
701

702
   /* make the ZZ options for the first call of ZZ */
703
   if (quiet)
704
      sprintf(zzoptions,"qtugZ");
705
   else
706
      sprintf(zzoptions,"tugZ");
707

708
   if (INFO_LEVEL & 4){
709
      put_mat(new_base,NULL,"new_base",2);
710
      put_bravais(H,NULL,"H");
711
      printf("zzoptions:  %s\n",zzoptions);
712
   }
713

714
   /* call the ZZ to get all almost decomposable groups in this Q-class */
715
   free_mat(F);
716
   F = rform(H->gen,H->gen_no- IDEM_NO,id,101);
717
   ZZ(H,F,NULL,NULL,zzoptions,NULL,0,-1);
718

719
   if (INFO_LEVEL & 4){
720
      put_bravais(H,NULL,"H");
721
   }
722

723
   /* apply a base reduction algorithm to the found new basises
724
      BASISES ARE CHANGED !!!!!!!!!!!!!!!!!!!!!!!!!!! */
725
   if (GRAPH){
726
      better = get_better_base(H,F,IDEM_NO,IDEM_SPACES);
727
      better[0] = init_mat(G->dim,G->dim,"1");
728
   }
729
   else{
730
      trash = get_better_base(H,F,IDEM_NO,IDEM_SPACES);
731
      for (j = 1; j < H->zentr_no; j++){
732
         free_mat(trash[j]);
733
      }
734
      free(trash);
735
   }
736

737
   /* get all almost decomposable groups */
738
   ad_no = H->zentr_no;
739
   ADGROUPS = almost(H);
740

741
   if (INFO_LEVEL & 4){
742
      fprintf(stderr,"=== Number of almost decomposable groups %d\n",ad_no);
743
   }
744

745
   /* make the ZZ options for the second call of ZZ */
746
   if (quiet)
747
      sprintf(zzoptions,"tuqzgp%d",IDEM_NO);
748
   else
749
      sprintf(zzoptions,"tuzgp%d",IDEM_NO);
750

751
   for (i = 0; i < IDEM_NO; i++){
752
      sprintf(string,"%s/%d",zzoptions,IDEM_SPACES[i]->rows);
753
      sprintf(zzoptions,"%s",string);
754
   }
755

756
   /* call the ZZ again to get all sublattices which fullfill the projection
757
      property (for each group in  ADGROUPS) */
758
   idem_no = IDEM_NO;
759
   IDEM_NO = 0;
760

761
   if (GRAPH){
762
      inzidenz = (QtoZ_TYP **)calloc(ad_no, sizeof(QtoZ_TYP *));
763
      SUPER_info = (ZZ_super_TYP **)calloc(ad_no, sizeof(ZZ_super_TYP *));
764
      for (i = 0; i < ad_no; i++){
765
         inzidenz[i] = (QtoZ_TYP *)calloc(1, sizeof(QtoZ_TYP));
766
         inzidenz[i]->gitter = (matrix_TYP **)calloc(1024, sizeof(matrix_TYP *));
767
         inzidenz[i]->inv_tr_gitter = (matrix_TYP **)calloc(1024, sizeof(matrix_TYP *));
768
         inzidenz[i]->tr_gitter = (matrix_TYP **)calloc(1024, sizeof(matrix_TYP *));
769
         inzidenz[i]->zoogitter = (matrix_TYP ***)calloc(1024, sizeof(matrix_TYP **));
770
         inzidenz[i]->entry = (QtoZ_entry_TYP **)calloc(1024, sizeof(QtoZ_entry_TYP *));
771
         ZZ(ADGROUPS[i],F,NULL,inzidenz[i],zzoptions,NULL,i,(i == 0));
772
      }
773
   }
774
   else{
775
      for (i = 0; i < ad_no; i++){
776
         ZZ(ADGROUPS[i],F,NULL,NULL,zzoptions,NULL,i,0);
777

778
	 /* apply a base reduction algorithm to the found new basises */
779
         trash = get_better_base(ADGROUPS[i],NULL,1,ADGROUPS[i]->gen);
780
         for (j = 1; j < ADGROUPS[i]->zentr_no; j++){
781
            free_mat(trash[j]);
782
         }
783
         free(trash);
784
      }
785
   }
786

787
   /* apply a base reduction algorithm to the found new basises */
788
/*
789
   for (i = 0; i < ad_no; i++){
790
      trash = get_better_base(ADGROUPS[i],NULL,1,ADGROUPS[i]->gen);
791
      for (j = 1; j < inzidenz[i]->anz; j++){
792
         free_mat(trash[j]);
793
      }
794
      free(trash);
795
   }
796
*/
797

798
   if (GRAPH){
799
      zentr_inv = (matrix_TYP **)calloc(ad_no, sizeof(matrix_TYP *));
800
      for (i = 0; i < ad_no; i++){
801
         zentr_inv[i] = mat_inv(H->zentr[i]);
802
         INZ->anz += inzidenz[i]->anz;
803
      }
804
      INZ->entry = (QtoZ_entry_TYP **)calloc(INZ->anz, sizeof(QtoZ_entry_TYP *));
805
      for (i = 0; i < INZ->anz; i++){
806
         INZ->entry[i] = (QtoZ_entry_TYP *)calloc(INZ->anz, sizeof(QtoZ_entry_TYP));
807
      }
808
      liste = (int *)calloc(ad_no + 1, sizeof(int));
809
      liste[0] = counter = 0;
810
      for (i = 0; i < ad_no; i++){
811
         for (j = 0; j < inzidenz[i]->anz; j++){
812
            for (l = 0 ; l < inzidenz[i]->anz; l++){
813
               help = INZ->entry[j + counter][l + counter].anz = inzidenz[i]->entry[j][l + 1].anz;
814
               if (help != 0){
815
                  INZ->entry[j + counter][l + counter].I = (int *)calloc(1024, sizeof(int));
816
                  INZ->entry[j + counter][l + counter].J = (int *)calloc(1024, sizeof(int));
817
                  INZ->entry[j + counter][l + counter].flag = (int *)calloc(1024, sizeof(int));
818
                  INZ->entry[j + counter][l + counter].lattice =
819
                                         (matrix_TYP **)calloc(1024, sizeof(matrix_TYP *));
820
                  for (m = 0; m < help; m++){
821
                     INZ->entry[j + counter][l + counter].I[m] = inzidenz[i]->entry[j][l + 1].I[m];
822
                     INZ->entry[j + counter][l + counter].J[m] = inzidenz[i]->entry[j][l + 1].J[m];
823
                     INZ->entry[j + counter][l + counter].flag[m] =
824
                                              inzidenz[i]->entry[j][l + 1].flag[m];
825
                     INZ->entry[j + counter][l + counter].lattice[m] =
826
                                                           inzidenz[i]->entry[j][l + 1].lattice[m];
827
                     Check_mat(INZ->entry[j + counter][l + counter].lattice[m]);
828
                  }
829
               }
830
            }
831
         }
832
         counter += inzidenz[i]->anz;
833
         liste[i+1] = counter;
834
      }
835

836
      /* handle the lattices, which might be in another zoo */
837
      for (i = 0; i < ad_no; i++){
838
         zen_nr = ADGROUPS[i]->zentr_no;
839
         normal_nr = ADGROUPS[i]->normal_no;
840
         cen_nr = ADGROUPS[i]->cen_no;
841
         ADGROUPS[i]->zentr_no = 0;
842
         ADGROUPS[i]->normal_no = 0;
843
         ADGROUPS[i]->cen_no = 0;
844
         for (j = 0; j < inzidenz[i]->anz; j++){
845
            for (l = 0; l < inzidenz[i]->entry[j][0].anz; l++){
846
               samezoo = 0;
847

848
               /* calculate group */
849
               zoo_inv = mat_inv(inzidenz[i]->zoogitter[j][l]);
850
               ggg = konj_bravais(ADGROUPS[i], zoo_inv);
851
               for (m = 0; m < ggg->form_no; m++){
852
                  ggg->form[m]->kgv = 1;
853
               }
854
               long_rein_formspace(ggg->form, ggg->form_no, 0);
855

856
               /* conjugate idempotents (the idempotents are equal for all
857
                  homogeneously decomposable lattices) */
858
               conj_idem = (matrix_TYP **)calloc(idem_no, sizeof(matrix_TYP *));
859
               ganzzahlig = 1;
860
               for (m = 0; m < idem_no; m++){
861
                  conj_idem[m] = mat_kon(zoo_inv ,real_idem[m], inzidenz[i]->zoogitter[j][l]);
862
                  Check_mat(conj_idem[m]);
863
                  if (conj_idem[m]->kgv != 1){
864
                     ganzzahlig = 0;
865
                  }
866
               }
867

868
               if (ganzzahlig == 1){
869
                  /* it's an homogeneously decomposable lattice */
870
                  group = ggg;
871
               }
872
               else{
873
                  /* calculate the minimal homogeneously decomposable superlattice */
874
                  lattice = hom_de_super(ggg, id, conj_idem, idem_no);
875
                  tmp = mat_inv(lattice);
876
                  group = konj_bravais(ggg, tmp);
877
	          for (f = 0; f < group->form_no; f++)
878
		     group->form[f]->kgv = 1;
879
	          long_rein_formspace(group->form, group->form_no, 1);
880
               }
881

882
               /* which one of the old homogeneously decomposable lattices is it */
883
               zoo_kon = special_deal_with_zclass(SUPER_INFO->tree, group, &zoo);
884

885
               if (ganzzahlig != 1){
886
                  if (zoo != i){
887
                     /* another zoo */
888
                     samezoo = 0;
889
                  }
890
                  else{
891
                     /* same zoo */
892
                     samezoo = 1;
893
                  }
894
                  Knoten = SUPER_INFO->tree->root;
895
                  for (f = 0; f < zoo; f++){
896
                     Knoten = Knoten->next;
897
                  }
898
                  zwischen = mat_kon(zoo_kon, Knoten->Q, better[zoo]);
899
                  ttt = mat_inv(zwischen);
900
                  zoolattice = mat_mul(ttt, tmp);
901
                  free_mat(ttt);
902
                  Knoten = NULL;
903
               }
904

905
               /* free */
906
               if (ganzzahlig == 1){
907
                  group = NULL;
908
               }
909
               else{
910
                  free_bravais(group);
911
               }
912
               for (m = 0; m < idem_no; m++){
913
                  free_mat(conj_idem[m]);
914
               }
915
               free(conj_idem);
916
               free_bravais(ggg);
917

918
               /* which lattice in the zoo? */
919
               aa = liste[i] + j;
920

921
               if (ganzzahlig == 1){
922
                  /* it is the homogeneously decomposable lattice */
923
                  bb = liste[zoo];
924
                  bahnnummer = 0;
925
               }
926
               else{
927
                  /* search in the tree */
928
                  zoolattice_hnf = copy_mat(zoolattice);
929
                  long_col_hnf(zoolattice_hnf);
930
                  node = SUPER_info[zoo]->tree->root;
931
                  yeah = 0;
932
                  while (node != NULL){
933
                     /* could be made better: compare el_div first */
934
                     if (in_bahn(zoolattice_hnf, node, &bahnnummer) == 1){
935
                        yeah = 1;
936
                        break;
937
                     }
938
                     node = node->next;
939
                  }
940
                  if (yeah == 0){
941
                     fprintf(stderr,"ERROR 1 in q2z!\n");
942
                     exit(3);
943
                  }
944
  	          laeufer = node->child;
945
      	          for (m = 0; m < node->N_no_orbits - bahnnummer; m++){
946
	             laeufer = laeufer->elder;
947
  	             if (laeufer == NULL){
948
   	                fprintf(stderr,"ERROR 2 in q2z!\n");
949
 	                exit(2);
950
 	             }
951
	          }
952
  	          bahnnummer = suche_mat(laeufer->he->U, inzidenz[zoo]->gitter, inzidenz[zoo]->anz);
953
                  if (bahnnummer == -1){
954
	             fprintf(stderr,"ERROR 3 in q2z!\n");
955
 	             exit(3);
956
	          }
957
	          bb = liste[zoo] + bahnnummer;
958
	          node = NULL;
959

960
                  free_mat(zoolattice_hnf);
961
               }
962

963
               /* write information in INZ */
964
               help = INZ->entry[aa][bb].anz;
965
               if (help == 0){
966
                  INZ->entry[aa][bb].I = (int *)calloc(1024, sizeof(int));
967
                  INZ->entry[aa][bb].J = (int *)calloc(1024, sizeof(int));
968
                  INZ->entry[aa][bb].flag = (int *)calloc(1024, sizeof(int));
969
                  INZ->entry[aa][bb].lattice = (matrix_TYP **)calloc(1024, sizeof(matrix_TYP *));
970
               }
971
               INZ->entry[aa][bb].I[help] = inzidenz[i]->entry[j][0].I[l];
972
               INZ->entry[aa][bb].J[help] = inzidenz[i]->entry[j][0].J[l];
973
               INZ->entry[aa][bb].flag[help] = inzidenz[i]->entry[j][0].flag[l];
974

975
               if (ganzzahlig == 1){
976
                  Knoten = SUPER_INFO->tree->root;
977
                  for (f = 0; f < zoo; f++){
978
                     Knoten = Knoten->next;
979
                  }
980
                  mat_muleq(inzidenz[i]->entry[j][0].lattice[l], inzidenz[i]->zoogitter[j][l]);
981
                  mat_muleq(inzidenz[i]->entry[j][0].lattice[l], zoo_kon);
982
                  mat_muleq(inzidenz[i]->entry[j][0].lattice[l], Knoten->Q);
983
                  mat_muleq(inzidenz[i]->entry[j][0].lattice[l], better[zoo]);
984
               }
985
               else{
986
                  zoolattice_inv = mat_inv(zoolattice);
987
                  X = konjugierende(zoolattice_inv, SUPER_info[zoo]->tree->root->col_group,
988
                                    laeufer->he);
989
                  free_mat(zoolattice_inv);
990
                  if (X == NULL){
991
                     fprintf(stderr, "ERROR 4 in q2z!\n");
992
                     exit(9);
993
                  }
994

995
                  /*
996
                  if (samezoo != 1){
997
                     mat_muleq(inzidenz[i]->entry[j][0].lattice[l], zentr_inv[j]);
998
                     mat_muleq(inzidenz[i]->entry[j][0].lattice[l], H->zentr[zoo]);
999
                  }
1000
                  */
1001
                  mat_muleq(inzidenz[i]->entry[j][0].lattice[l], inzidenz[i]->zoogitter[j][l]);
1002
                  /*
1003
                  mat_muleq(inzidenz[i]->entry[j][0].lattice[l], lattice);
1004
                  mat_muleq(inzidenz[i]->entry[j][0].lattice[l], zwischen);
1005
                  mat_muleq(inzidenz[i]->entry[j][0].lattice[l], zoolattice);
1006
                  */
1007
                  mat_muleq(inzidenz[i]->entry[j][0].lattice[l], X);
1008
                  free_mat(X);
1009
                  free_mat(zoolattice);
1010
                  free_mat(lattice);
1011
                  free_mat(tmp);
1012
                  free_mat(zwischen);
1013
               }
1014
               INZ->entry[aa][bb].lattice[help] = inzidenz[i]->entry[j][0].lattice[l];
1015
               Check_mat(INZ->entry[aa][bb].lattice[help]);
1016
               INZ->entry[aa][bb].anz++;
1017
               if (zoo_inv != NULL)
1018
                  free_mat(zoo_inv);
1019
               free_mat(zoo_kon);
1020
            }
1021
         }
1022
         ADGROUPS[i]->zentr_no = zen_nr;
1023
         ADGROUPS[i]->normal_no = normal_nr;
1024
         ADGROUPS[i]->cen_no = cen_nr;
1025
      }
1026

1027
      /* print the matrix of incidences for the Z-classes */
1028
      /*
1029
      test = init_mat(INZ->anz, INZ->anz, "");
1030
      for (i = 0; i < INZ->anz; i++){
1031
         for (j = 0; j < INZ->anz; j++){
1032
            test->array.SZ[i][j] = INZ->entry[i][j].anz;
1033
         }
1034
      }
1035
      put_mat(test,0,"graph for the arithmetic classes",0);
1036
      free_mat(test);
1037
      */
1038

1039
      /* calculate standard form for the lattices */
1040
      for (i = 0; i < INZ->anz; i++){
1041
         for (j = 0; j < INZ->anz; j++){
1042
            if (INZ->entry[i][j].anz != 0){
1043
               INZ->entry[i][j].lsf = (matrix_TYP **)calloc(INZ->entry[i][j].anz,
1044
                                                            sizeof(matrix_TYP *));
1045
               for (k = 0; k < INZ->entry[i][j].anz; k++){
1046
                  INZ->entry[i][j].lsf[k] = copy_mat(INZ->entry[i][j].lattice[k]);
1047
                  long_col_hnf(INZ->entry[i][j].lsf[k]);
1048
               }
1049
            }
1050
         }
1051
      }
1052
   }
1053

1054
   if (!ADFLAG){
1055
      GROUPS = get_groups(ADGROUPS,ad_no,number);
1056
   }
1057

1058
   /* clean up */
1059
   if (!ADFLAG){
1060
      for (i=0;i<ad_no;i++){
1061
         free_bravais(ADGROUPS[i]);
1062
      }
1063
      free(ADGROUPS);
1064
   }
1065

1066
   if (GRAPH){
1067
      /* free better, inzidenz, SUPER_info and SUPER_INFO (oliver: 9.8.00) */
1068
      free_ZZ_super(SUPER_INFO);
1069
      for (i = 0; i < ad_no; i++){
1070
         free_mat(zentr_inv[i]);
1071
         free_ZZ_super(SUPER_info[i]);
1072
         free_QtoZ(inzidenz[i], 1);
1073
         free_mat(better[i]);
1074
      }
1075
      free(zentr_inv);
1076
      free(liste);
1077
      free(SUPER_info);
1078
      free(inzidenz);
1079
      free(better);
1080
      ZZ_get_data (NULL, NULL, NULL, NULL, NULL, NULL, -3);
1081
   }
1082

1083
   free_bravais(H);
1084
   free_mat(id);
1085
   free_mat(new_base);
1086
   free_mat(F);
1087
   for (i=0;i<idem_no+dimc+dimcc;i++){
1088
      free_mat(IDEM[i]);
1089
   }
1090
   free(IDEM);
1091
   for (i=0;i<idem_no;i++){
1092
      free_mat(IDEM_SPACES[i]);
1093
   }
1094
   free(IDEM_SPACES);
1095
   G->gen_no -= idem_no;
1096

1097
   if (ADFLAG){
1098
      number[0] = ad_no;
1099
      return ADGROUPS;
1100
   }
1101
   else{
1102
      return GROUPS;
1103
   }
1104
}
1105

1106