CoCalc -- stabs.c

GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
gap4r8 / pkg / carat / carat-2.1b1 / functions / Graph / stabs.c
⁵⁶³⁵⁸⁰ views
1
/* last change: 28.09.00 by Oliver Heidbuechel */
2

3

4
#include<typedef.h>
5
#include<getput.h>
6
#include<matrix.h>
7
#include<longtools.h>
8
#include<tools.h>
9
#include"zass.h"
10
#include <bravais.h>
11
#include <sort.h>
12
#include <presentation.h>
13
#include <base.h>
14
#include <graph.h>
15

16

17

18

19
/* -------------------------------------------------------------------------- */
20
/* returns 1 iff mat = Id                                                     */
21
/* -------------------------------------------------------------------------- */
22
static int is_id(matrix_TYP *mat)
23
{
24
   int i, j;
25

26
   for (i = 0; i < mat->rows; i++){
27
      for (j = 0; j < mat->cols; j++){
28
         if (i == j && mat->array.SZ[i][i] != 1)
29
            return(0);
30
         if (i != j && mat->array.SZ[i][j] != 0);
31
            return(0);
32
      }
33
   }
34
   return(1);
35
}
36

37

38

39
/* -------------------------------------------------------------------- */
40
/* Setze Matrizen (gegeben in N) in Worte ein.                          */
41
/* Streiche Identitaet und doppelte.                                    */
42
/* -------------------------------------------------------------------- */
43
/* words: Worte                                                         */
44
/* no_of_words: Anzahl der Worte                                        */
45
/* N: Matrizen, die eingesetzt werden sollen                            */
46
/*    (muss zu words "passen")                                          */
47
/* N_inv: Inversen von N (werden bei Bedarf berechnet)                  */
48
/* anz: Anzahl von N                                                    */
49
/* flag: wenn = 0, wird einfach N zurueckgegeben                        */
50
/* stab_gen_no: hier wird die Anzahl der Elemente zurueckgegeben        */
51
/* -------------------------------------------------------------------- */
52
matrix_TYP **stab_coz(int **words,
53
                      int no_of_words,
54
                      matrix_TYP **N,
55
                      matrix_TYP **N_inv,
56
                      int anz,
57
                      int flag,
58
                      int *stab_gen_no)
59
{
60
   int i, counter = 0;
61

62
   matrix_TYP **stab;
63

64

65

66
   if (flag == 0){
67
      /* the stabilizer of the cocycle is the full normalizer */
68
      stab = (matrix_TYP **)calloc(anz, sizeof(matrix_TYP *));
69
      stab_gen_no[0] = anz;
70
      for (i = 0; i < anz; i++){
71
         stab[i] = copy_mat(N[i]);
72
      }
73
   }
74
   else{
75
      stab = (matrix_TYP **)calloc(no_of_words, sizeof(matrix_TYP *));
76
      for (i = 0; i < no_of_words; i++){
77
         normalize_word(words[i]);
78
         stab[counter] = mapped_word(words[i], N, N_inv);
79

80
         if (!is_id(stab[counter])){
81
            if (mat_search(stab[counter], stab, counter, mat_comp) != -1){
82
               free_mat(stab[counter]);
83
            }
84
            else{
85
               mat_quicksort(stab, 0, counter, mat_comp);
86
               counter++;
87
            }
88
         }
89
         else{
90
            free_mat(stab[counter]);
91
         }
92
      }
93
      stab_gen_no[0] = counter;
94
   }
95

96
   return(stab);
97
}
98

99

100

101
/* -------------------------------------------------------------------------- */
102
/* Did we have this lattice bevore? If not, insert the lattice in the tree!   */
103
/* -------------------------------------------------------------------------- */
104
static int search_in_tree(struct tree *Baum,
105
                          matrix_TYP **list,
106
                          matrix_TYP *lattice,
107
                          int number)
108
{
109
   int flag, no;
110

111
   no = Baum->no;
112
   flag = cmp_mat(list[no], lattice);
113

114
   if (flag == 0)
115
      return(no);
116
   if (flag < 0){
117
      if (Baum->left == NULL){
118
         Baum->left = (struct tree *)calloc(1, sizeof(struct tree));
119
         Baum->left->no = number;
120
         return(-1);
121
      }
122
      else{
123
         return(search_in_tree(Baum->left, list, lattice, number));
124
      }
125
   }
126
   else{
127
      if (Baum->right == NULL){
128
         Baum->right = (struct tree *)calloc(1, sizeof(struct tree));
129
         Baum->right->no = number;
130
         return(-1);
131
      }
132
      else{
133
         return(search_in_tree(Baum->right, list, lattice, number));
134
      }
135

136
   }
137
}
138

139

140

141
/* -------------------------------------------------------------------------- */
142
/* mark the lattices in the orbit under the stablizer of a cocycle            */
143
/* -------------------------------------------------------------------------- */
144
static void mark_lattice(boolean *lattice_orbit,
145
                         matrix_TYP **LIST,
146
                         int anz,
147
                         matrix_TYP *mat)
148
{
149
   int i;
150

151
   for (i = 0; i < anz; i++){
152
      if (cmp_mat(mat, LIST[i]) == 0){
153
         lattice_orbit[i] = TRUE;
154
         return;
155
      }
156
   }
157
   fprintf(stderr, "ERROR in mark_lattice!\n");
158
   exit(7);
159
}
160

161

162

163
/* -------------------------------------------------------------------------- */
164
/* Calculate the stabilizer of a lattice and return the words;                */
165
/* save the number of words in no                                             */
166
/* -------------------------------------------------------------------------- */
167
int **stab_lattice(matrix_TYP *lattice,
168
                   matrix_TYP **N,
169
                   int N_gen_no,
170
                   int *no,
171
                   matrix_TYP **LIST,
172
                   int anz,
173
                   boolean *lattice_orbit)
174
{
175
   int i, j, k, flag,
176
       counter = 1, number,
177
       **words, **WORDS;
178

179
   matrix_TYP **list;
180

181
   struct tree *Baum;
182

183

184
   list = (matrix_TYP **)calloc(MIN_SPEICHER, sizeof(matrix_TYP *));
185
   words = (int **)calloc(MIN_SPEICHER, sizeof(int *));
186
   WORDS = (int **)calloc(MIN_SPEICHER, sizeof(int *));
187
   list[0] = lattice;
188
   Baum = (struct tree *)calloc(1, sizeof(struct tree));
189
   Baum->no = i = no[0] = 0;
190

191
   while (i < counter){
192
      for (j = 0; j < N_gen_no; j++){
193
         list[counter] = mat_mul(N[j], list[i]);
194
         long_col_hnf(list[counter]);
195
         flag = search_in_tree(Baum, list, list[counter], counter);
196
         if (flag == -1){
197
            /* new lattice */
198
            words[counter] = (int *)calloc(MIN_SPEICHER, sizeof(int));
199
            if (i != 0){
200
               memcpy(words[counter], words[i], (words[i][0] + 1) * sizeof(int));
201
               words[counter][words[i][0] + 1] = -(j+1);
202
               words[counter][0]++;
203
            }
204
            else{
205
               words[counter][0] = 1;
206
               words[counter][1] = -(j+1);
207
            }
208
            if (lattice_orbit != NULL && LIST != NULL && anz != 0)
209
               mark_lattice(lattice_orbit, LIST, anz, list[counter]);
210
            counter++;
211
         }
212
         else{
213
            /* we got this lattice already */
214
            free_mat(list[counter]);
215
            WORDS[no[0]] = (int *)calloc(MIN_SPEICHER, sizeof(int));
216
            if (i != 0){
217
               memcpy(WORDS[no[0]], words[i], (words[i][0] + 1) * sizeof(int));
218
               WORDS[no[0]][words[i][0] + 1] = -(j+1);
219
               WORDS[no[0]][0]++;
220
            }
221
            else{
222
               WORDS[no[0]][0] = 1;
223
               WORDS[no[0]][1] = -(j+1);
224
            }
225
            if (flag != 0){
226
               number = WORDS[no[0]][0] + words[flag][0];
227
               for (k = 0; k < words[flag][0]; k++){
228
                  WORDS[no[0]][number - k] = -words[flag][k + 1];
229
               }
230
               WORDS[no[0]][0] = number;
231
            }
232
            no[0]++;
233
         }
234
      }
235
      i++;
236
   }
237

238
   /* clean */
239
   for (i = 1; i < counter; i++){
240
      free(words[i]);
241
      free_mat(list[i]);
242
   }
243
   free(words);
244
   free(list);
245
   free_tree(Baum);
246

247
   return(WORDS);
248
}
249

250

251

252
/* -------------------------------------------------------------------------- */
253
/* returns 1 if  word[n] == word[i] for a 0 <= i < n                          */
254
/* returns 0 otherwise                                                        */
255
/* -------------------------------------------------------------------------- */
256
int word_already_there(int **WORDS,
257
                       int n)
258
{
259
   int i, j, flagge = 0;
260

261
   for (i = 0; i < n && flagge == 0; i++){
262
      flagge = 1;
263
      for (j = 0; j <= WORDS[i][0]; j++){
264
         if (WORDS[i][j] != WORDS[n][j]){
265
            flagge = 0;
266
            break;
267
         }
268
      }
269
   }
270
   return(flagge);
271
}
272

273

274

275
/* -------------------------------------------------------------------------- */
276
/* Calculate the stabilizer of lattice under N and return the words;          */
277
/* save the number of words in no                                             */
278
/* -------------------------------------------------------------------------- */
279
matrix_TYP **calculate_S1(matrix_TYP *lattice,
280
                          matrix_TYP **N,
281
                          int anz,
282
                          int *no,
283
                          matrix_TYP **dataN,
284
                          matrix_TYP **dataNinv,
285
                          matrix_TYP *dataX)
286
{
287
   int i, j, k, flag, i__, addmem,
288
       counter = 1, number,
289
       **words, **WORDS;
290

291
   matrix_TYP **list, **S1,
292
              **Ninv, *tmp;
293

294
   struct tree *Baum;
295

296
   if (GRAPH_DEBUG){
297
      Ninv = (matrix_TYP **)calloc(anz, sizeof(matrix_TYP *));
298
   }
299

300
   list = (matrix_TYP **)calloc(1024, sizeof(matrix_TYP *));
301
   words = (int **)calloc(1024, sizeof(int *));
302
   WORDS = (int **)calloc(1024, sizeof(int *));
303
   list[0] = lattice;
304
   Baum = (struct tree *)calloc(1, sizeof(struct tree));
305
   Baum->no = i = no[0] = 0;
306

307
   while (i < counter){
308
      for (j = 0; j < anz; j++){
309
         if (counter % 1024 == 0){
310
	    list = (matrix_TYP **)realloc(list, (counter + 1024) * sizeof(int *));
311
	 }
312
         list[counter] = mat_mul(N[j], list[i]);
313
         long_col_hnf(list[counter]);
314
         flag = search_in_tree(Baum, list, list[counter], counter);
315
         if (flag == -1){
316
            /* new lattice */
317
	    if (counter % 1024 == 0){
318
	       words = (int **)realloc(words, (counter + 1024) * sizeof(int *));
319
	    }
320
            /* words[counter] = (int *)calloc(1024, sizeof(int)); */
321
            if (i != 0){
322
	       words[counter] = (int *)calloc(words[i][0] + 2, sizeof(int));
323
               /*memcpy(words[counter], words[i], (words[i][0] + 1) * sizeof(int));*/
324
	       for (i__ = 0; i__ < words[i][0] + 1; i__++){
325
	          words[counter][i__] = words[i][i__];
326
	       }
327
               words[counter][words[i][0] + 1] = -(j+1);
328
               words[counter][0]++;
329
            }
330
            else{
331
	       words[counter] = (int *)calloc(2, sizeof(int));
332
               words[counter][0] = 1;
333
               words[counter][1] = -(j+1);
334
            }
335
            counter++;
336
         }
337
         else{
338
            /* we got this lattice already */
339
            free_mat(list[counter]);
340
	    if (no[0] % 1024){
341
	       WORDS = (int **)realloc(WORDS, (no[0] + 1024) * sizeof(int *));
342
	    }
343
            /*WORDS[no[0]] = (int *)calloc(1024, sizeof(int));*/
344
	    if (flag != 0){
345
	       addmem = words[flag][0];
346
	    }
347
	    else{
348
	       addmem = 0;
349
	    }
350
            if (i != 0){
351
               WORDS[no[0]] = (int *)calloc(words[i][0] + 2 + addmem, sizeof(int));
352
               /*memcpy(WORDS[no[0]], words[i], (words[i][0] + 1) * sizeof(int));*/
353
	       for (i__ = 0; i__ < words[i][0] + 1; i__++){
354
	          WORDS[no[0]][i__] = words[i][i__];
355
	       }
356
               WORDS[no[0]][words[i][0] + 1] = -(j+1);
357
               WORDS[no[0]][0]++;
358
            }
359
            else{
360
	       WORDS[no[0]] = (int *)calloc(2 + addmem, sizeof(int));
361
               WORDS[no[0]][0] = 1;
362
               WORDS[no[0]][1] = -(j+1);
363
            }
364
            if (flag != 0){
365
               number = WORDS[no[0]][0] + words[flag][0];
366
               for (k = 0; k < words[flag][0]; k++){
367
                  WORDS[no[0]][number - k] = -words[flag][k + 1];
368
               }
369
               WORDS[no[0]][0] = number;
370
            }
371
            no[0]++;
372
         }
373
      }
374
      i++;
375
   }
376

377
   if (GRAPH_DEBUG){
378
      /* is this really an element of the stabilizer? */
379
      for (i = 0; i < no[0]; i++){
380
         tmp = mapped_word(WORDS[i], N, Ninv);
381
         tmp = mat_muleq(tmp, lattice);
382
         long_col_hnf(tmp);
383
         if (cmp_mat(tmp, lattice) != 0){
384
            fprintf(stderr, "MIST!\n");
385
            exit(9);
386
         }
387
         free_mat(tmp);
388
      }
389
      for (i = 0; i < anz; i++){
390
         if (Ninv[i] != NULL) free_mat(Ninv[i]);
391
      }
392
      free(Ninv);
393
   }
394

395
   /* clean */
396
   for (i = 1; i < counter; i++){
397
      free(words[i]);
398
      free_mat(list[i]);
399
   }
400
   free(words);
401
   free(list);
402
   free_tree(Baum);
403

404
   /* now calculate the matrices */
405
   counter = 0;
406
   S1 = (matrix_TYP **)calloc(no[0], sizeof(matrix_TYP *));
407
   for (i = 0; i < no[0]; i++){
408
      /* simplify the words */
409
      normalize_word(WORDS[i]);
410
      if (WORDS[i][0] == 1 && WORDS[i][1] < 0)
411
         WORDS[i][1] *= (-1);
412
      if (word_already_there(WORDS, i) == 0){
413
         S1[counter] = graph_mapped_word(WORDS[i], dataN, dataNinv, dataX);
414
         if (mat_search(S1[counter], S1, counter, mat_comp) != -1){
415
            free_mat(S1[counter]);
416
         }
417
         else{
418
            mat_quicksort(S1, 0, counter, mat_comp);
419
            counter++;
420
         }
421
      }
422
   }
423
   for (i = 0; i < no[0]; i++)
424
      free(WORDS[i]);
425
   free(WORDS);
426

427
   no[0] = counter;
428
   return(S1);
429
}
430

431

432

433

434

435

436
Product

Resources

Company
