CoCalc -- polyeder

GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
gap4r8 / pkg / carat / carat-2.1b1 / functions / Polyeder / polyeder_tools.c
⁵⁶³⁶⁰⁴ views
1
#include"typedef.h"
2
#include"polyeder.h"
3
#include"matrix.h"
4
/**************************************************************************\
5
@---------------------------------------------------------------------------
6
@---------------------------------------------------------------------------
7
@ FILE: polyeder_tools.c
8
@---------------------------------------------------------------------------
9
@---------------------------------------------------------------------------
10
@
11
\**************************************************************************/
12

13

14
/**************************************************************************\
15
@---------------------------------------------------------------------------
16
@ vertex_TYP *init_vertex(dim, wall_no) 
17
@ int dim;
18
@ int wall_no;
19
@
20
@  'init_vertex' allocates a vertex_TYP *v.
21
@  For v the following is allocated:
22
@     v->dim = dim
23
@     v->wall_no = wall_no
24
@     v->v:    pointer to integer, size: dim.
25
@     v->wall_size: 0, if wall_no = 0
26
@                   (wall_no/extsize1 +1) * extsize1, else
27
@     v->wall: pointer to integer
28
@               size: 0, if wall_no = 0
29
@                        else (wall_no/extsize1 +1) * extsize1
30
@
31
@---------------------------------------------------------------------------
32
@
33
\**************************************************************************/
34
vertex_TYP *init_vertex(dim, wall_no) 
35
int dim;
36
int wall_no;
37
{
38
  int i,j;
39
  vertex_TYP *erg;
40
  erg = (vertex_TYP *)malloc(sizeof(vertex_TYP));
41
  if(dim!=0)
42
  {
43
    erg->v = (int *)malloc(dim *sizeof(int));
44
    for(i=0; i<dim; i++)
45
    erg->v[i] = 0;
46
  }
47
  erg->dim = dim;
48
  erg->wall_no = wall_no;
49
  if( wall_no > 0)
50
  {
51
    j = wall_no/extsize1 +1;
52
    erg->wall_SIZE = j * extsize1;
53
    erg->wall = (int *)malloc(erg->wall_SIZE *sizeof(int));
54
  }
55
  else
56
    erg->wall_SIZE=0;
57
    
58
  return(erg);
59
}
60

61
/* anne, 16/07/97 */
62
/**************************************************************************\
63
@---------------------------------------------------------------------------
64
@ word_TYP *init_word(dim)
65
@ int dim;
66
@ 
67
@   'init_word' allocates a word_TYP *word.
68
@   For word the following is allocated:
69
@   word->word = NULL;
70
@   matrix_TYP *trans = init_mat(dim,1,"");
71
@---------------------------------------------------------------------------
72
@
73
\**************************************************************************/
74
  word_TYP *init_word(dim)
75
  int dim;
76
  {
77
    word_TYP *erg;
78
   
79
    erg = (word_TYP*)malloc(sizeof(word_TYP));
80
    erg->dim = dim;
81
    erg->word = NULL;
82
    erg->trans = NULL; 
83
/*  erg->trans = init_mat(dim,1,""); */
84
    
85
    return(erg);
86
  }
87

88
/**************************************************************************\
89
@---------------------------------------------------------------------------
90
@ wall_TYP *init_wall(dim)
91
@ int dim;
92
@   'init_wall' allocates a wall_TYP *w.
93
@   For w the following is allocated:
94
@      w->dim = dim
95
@      w->gl:    pointer to integer, size: dim.
96
@      w->mat = NULL
97
@      w->product = NULL
98
@      w->nproduct = 0
99
@      w->word = NULL
100
@      w->next_no = 0
101
@      w->next = NULL
102
@      w->ext_no = 0;
103
@      w->extra= NULL;
104
@      w->neu = 0;
105
@      w->paar = 0;
106
@---------------------------------------------------------------------------
107
@
108
\**************************************************************************/
109
wall_TYP *init_wall(dim)
110
int dim;
111
{
112
  int i,j;
113
  wall_TYP *erg;
114

115
  erg = (wall_TYP *)malloc(sizeof(wall_TYP));
116
  erg->gl = (int *)calloc(dim ,sizeof(int));
117
  erg->dim = dim;
118
  erg->mat = NULL;
119
  erg->product = NULL;
120
  erg->nproduct = 0;
121
  erg->word = NULL;
122
  erg->next_no = 0;	/* next 5 lines anne 8/10/97 */
123
  erg->next = NULL;
124
  erg->ext_no = 0;
125
  erg->extra = NULL;
126
  erg->neu = 0;
127
  erg->paar = 0;
128
  return(erg);
129
}
130

131

132
/**************************************************************************\
133
@---------------------------------------------------------------------------
134
@ corner_TYP *init_corner()
135
@
136
@
137
@
138
@---------------------------------------------------------------------------
139
@
140
\**************************************************************************/
141

142

143
/**************************************************************************\
144
@---------------------------------------------------------------------------
145
@ polyeder_TYP *init_polyeder(vert_no, wall_no)
146
@ int vert_no, wall_no;
147
@ 
148
@   'init_polyeder' allocates a polyeder_TYP *P.
149
@   For P the following is allocated:
150
@     P->vert_no = vert_no;
151
@     P->wall_no = wall_no;
152
@     P->is_closed = FALSE;
153
@     P->vert_SIZE = (vert_no/extsize1 +1) * extsize1;
154
@     P->wall_SIZE = (wall_no/extsize1 +1) * extsize1;
155
@     P->corner = NULL;
156
@     P->corner_no = 0, P->corner_SIZE = 0;
157
@     P->vert = **vertex_TYP, size:  P->vert_no.
158
@     P->wall = **wall_TYP,   size:  P->wall_no.
159
@
160
@---------------------------------------------------------------------------
161
@
162
\**************************************************************************/
163
polyeder_TYP *init_polyeder(vert_no, wall_no)
164
int vert_no, wall_no;
165
{
166
  int i,j;
167
  polyeder_TYP *erg;
168

169
  erg = (polyeder_TYP *)malloc(sizeof(polyeder_TYP));
170
  erg->vert_no = vert_no;
171
  erg->wall_no = wall_no;
172
  erg->is_closed = FALSE;
173
  erg->is_degenerate = FALSE;
174
  j = vert_no/extsize1 +1;
175
  j *= extsize1;
176
  erg->vert_SIZE = j;
177
  erg->vert = (vertex_TYP **)malloc(j*sizeof(vertex_TYP *));
178
  for(i=0;i<erg->vert_SIZE;i++)
179
    erg->vert[i] = NULL;
180
  j = wall_no/extsize1 +1;
181
  j *= extsize1;
182
  erg->wall_SIZE = j;
183
  erg->wall = (wall_TYP **)malloc(j*sizeof(wall_TYP *));
184
  for(i=0;i<erg->wall_SIZE;i++)
185
    erg->wall[i] = NULL;
186
  erg->corner = NULL;			/* next 3 lines inserted by anne */
187
  erg->corner_no = 0;
188
  erg->corner_SIZE = 0;
189
  return(erg);
190
}
191

192

193

194

195

196
/**************************************************************************\
197
@---------------------------------------------------------------------------
198
@ polyeder_TYP *get_polyeder(file_name)
199
@ char *file_name;
200
@ 
201
@    Read a polyeder from the file 'file_name'.
202
@    If 'file_name' is NULL, get+polyeder reads from standard input.
203
@ 
204
@
205
@---------------------------------------------------------------------------
206
@
207
\**************************************************************************/
208
polyeder_TYP *get_polyeder(file_name)
209
char *file_name;
210
{  
211
int vertno, wallno;
212
int dim,wn,i,j;
213
polyeder_TYP *F;
214
FILE *infile;
215

216

217
	/*------------------------------------------------------------*\
218
	| Open input file											 |
219
	\*------------------------------------------------------------*/
220
if ( file_name == NULL )
221
	infile = stdin;
222
else
223
	if ( (infile = fopen (file_name, "r")) == NULL ) {
224
		fprintf (stderr, "Could not open input-file %s\n", file_name);
225
		exit (4);
226
		}
227
  /*--------------------------------------------------*\
228
  |  read fundamental domain                                  |
229
  \*--------------------------------------------------*/
230
fscanf (infile, "%d", &vertno);
231
fscanf (infile, "%d", &wallno);
232
F = init_polyeder(vertno, wallno);
233
for(i=0;i<vertno;i++)
234
{
235
  fscanf (infile, "%d", &dim);
236
  fscanf (infile, "%d", &wn);
237
  F->vert[i] = init_vertex(dim, wn);
238
  for(j=0;j<dim;j++)
239
    fscanf(infile, "%d", &F->vert[i]->v[j]); 
240
  for(j=0;j<wn;j++)
241
     fscanf(infile, "%d", &F->vert[i]->wall[j]);
242
}
243
for(i=0;i<wallno;i++)
244
{
245
  fscanf(infile, "%d", &dim);
246
  F->wall[i] = init_wall(dim);
247
  for(j=0;j<dim;j++)
248
    fscanf(infile, "%d", &F->wall[i]->gl[j]); 
249
}
250
  fscanf(infile, "%d", &F->is_closed);
251
  fscanf(infile, "%d", &F->is_degenerate);
252

253
   
254
	/*------------------------------------------------------------*\
255
	| close input file                                             |
256
	\*------------------------------------------------------------*/
257
if ( infile != stdin )
258
	fclose (infile);
259
return ( F );
260
}
261

262

263

264
/**************************************************************************\
265
@---------------------------------------------------------------------------
266
@ void put_polyeder(F)
267
@ polyeder_TYP *F;
268
@ 
269
@    prints a polyeder_TYP to standard output
270
@
271
@---------------------------------------------------------------------------
272
@
273
\**************************************************************************/
274
void put_polyeder(F)
275
polyeder_TYP *F;
276
{
277
  int i,j;
278
  printf("%d  %d\n", F->vert_no, F->wall_no);
279
  printf("\n");
280
  for(i=0;i<F->vert_no;i++)
281
  {
282
    printf("%d  %d\n", F->vert[i]->dim, F->vert[i]->wall_no);
283
    for(j=0;j<F->vert[i]->dim;j++)
284
      printf("%d  ", F->vert[i]->v[j]);
285
    printf("\n");
286
    for(j=0;j<F->vert[i]->wall_no;j++)
287
       printf("%d  ", F->vert[i]->wall[j]);
288
    printf("\n");
289
  }
290
  printf("\n");
291
  for(i=0;i<F->wall_no;i++)
292
  {
293
    printf("%d\n", F->wall[i]->dim);
294
    for(j=0;j<F->wall[i]->dim;j++)
295
      printf("%d  ", F->wall[i]->gl[j]);
296
    printf("\n");
297
  }
298
    
299
  printf("\n");
300
  printf("%d  %d\n", F->is_closed, F->is_degenerate);
301
  fflush(stdout);
302
}
303

304

305

306
/**************************************************************************\
307
@---------------------------------------------------------------------------
308
@ int wall_times_vertex(w, v)
309
@ wall_TYP *w;
310
@ vertex_TYP *v;
311
@ 
312
@     calculates the sum of v->v[i] * w->gl[i].
313
@
314
@---------------------------------------------------------------------------
315
@
316
\**************************************************************************/
317
int wall_times_vertex(w, v)
318
wall_TYP *w;
319
vertex_TYP *v;
320
{
321
  int i,e;
322
  e=0;
323
  for(i=0;i<v->dim;i++)
324
      e += (v->v[i] * w->gl[i]);
325
  return(e);
326
}
327

328

329

330
/**************************************************************************\
331
@---------------------------------------------------------------------------
332
@ void free_vertex(v)
333
@ vertex_TYP **v;
334
@
335
@    frees, what was allocated in *v and sets (*v) = NULL 
336
@---------------------------------------------------------------------------
337
@
338
\**************************************************************************/
339
void free_vertex(v)
340
vertex_TYP **v;
341
{
342
 int i;
343
 if((*v)!= NULL)
344
 {
345
   free((*v)->v);
346
   if((*v)->wall_SIZE != 0)
347
     free((*v)->wall);
348
   free((*v));
349
   (*v)=NULL;
350
 }
351
}
352

353

354
/**************************************************************************\
355
@---------------------------------------------------------------------------
356
@ void free_wall(v)
357
@ wall_TYP **v;
358
@ 
359
@    frees, what was allocated in *v and sets (*v) = NULL 
360
@
361
@---------------------------------------------------------------------------
362
@
363
\**************************************************************************/
364
void free_wall(v)
365
wall_TYP **v;
366
{
367
 int i;
368

369
 if((*v)!= NULL)
370
 {
371
   free((*v)->gl);
372
   if((*v)->mat != 0)
373
     free_mat((*v)->mat);
374
   if((*v)->next != NULL){		/* next 7 lines anne, 8/10/97 */
375
     for(i=0; i<(*v)->next_no; i++)
376
         free((*v)->next[i]);
377
     free((*v)->next);
378
   }
379
   if((*v)->extra != NULL){
380
     for(i=0; i<(*v)->ext_no; i++)
381
         free((*v)->extra[i]);
382
     free((*v)->extra);
383
   } 
384
   if((*v)->word != NULL){		/* next 7 lines anne, 1.4. 98 */
385
     if((*v)->word->trans != NULL){
386
        free_mat((*v)->word->trans); (*v)->word->trans = NULL; } 
387
     if((*v)->word->word != NULL)
388
        free((*v)->word->word);
389
   free((*v)->word);
390
   }
391
   free((*v));
392
   if((*v)->product != NULL)
393
     free((*v)->product);
394

395
   (*v)=NULL;
396
 }
397
}
398

399
/* anne, 16/07/97  */
400
/**************************************************************************\
401
@---------------------------------------------------------------------------
402
@ void free_word(word)
403
@ word_TYP *word; 
404
@
405
@    frees, what was allocated in word and sets word = NULL 
406
@
407
@---------------------------------------------------------------------------
408
@
409
\**************************************************************************/
410
void free_word(word)
411
word_TYP *word;
412
{
413
   if (word != NULL){
414
      if (word->trans != NULL)
415
         free_mat(word->trans);
416
      if (word->word[0] > 0 &&
417
          word->word != NULL)
418
         free(word->word);
419
      free(word);
420
      word = NULL;
421
   }
422
}
423

424
/**************************************************************************\
425
@---------------------------------------------------------------------------
426
@ wall_TYP *mat_to_wall(M)
427
@ matrix_TYP *M;
428
@ 
429
@     creates a wall_TYP *w with w->dim = M->cols
430
@     and the entries of w->gl equal to the entries of the first row of M.
431
@
432
@---------------------------------------------------------------------------
433
@
434
\**************************************************************************/
435
wall_TYP *mat_to_wall(M)
436
matrix_TYP *M;
437
{
438
  int i;
439
  wall_TYP *erg;
440
  erg = init_wall(M->cols);
441
  for(i=0;i<erg->dim;i++)
442
    erg->gl[i] = M->array.SZ[0][i];
443
  return(erg);
444
}
445

446

447
/**************************************************************************\
448
@---------------------------------------------------------------------------
449
@ void normal_wall(v)
450
@ wall_TYP *v;
451
@ 
452
@     Divides the entries of v->gl by their greatest common divisor.
453
@
454
@---------------------------------------------------------------------------
455
@
456
\**************************************************************************/
457
void normal_wall(v)
458
wall_TYP *v;
459
{
460
  int i,j;
461
  int w1,w2;
462
 
463
  if(v->dim>0)
464
  {
465
    i=0;
466
    while(i<v->dim && v->gl[i] == 0)
467
       i++;
468
    if(i<v->dim)
469
      w1 = v->gl[i];
470
    for(j=i+1;j<v->dim && w1 != 1 && w1 != -1;j++)
471
    {
472
     if(v->gl[j] != 0)
473
     {
474
       w2 = GGT(w1, v->gl[j]);
475
       w1 = w2;
476
     }
477
    }
478
    if(w1 < 0)
479
      w1 = -w1;
480
    if(w1 != 0)
481
    {
482
       for(j=0;j<v->dim;j++)
483
         v->gl[j] /= w1;
484
    }
485
  }
486
}
487

488

489

490

491
/**************************************************************************\
492
@---------------------------------------------------------------------------
493
@ void normal_vertex(v)
494
@ vertex_TYP *v;
495
@ 
496
@     Divides the entries of v->v by their greatest common divisor.
497
@
498
@---------------------------------------------------------------------------
499
@
500
\**************************************************************************/
501
void normal_vertex(v)
502
vertex_TYP *v;
503
{
504
  int i,j;
505
  int w1,w2;
506
 
507
  if(v->dim>0)
508
  {
509
    i=0;
510
    while(i<v->dim && v->v[i] == 0)
511
       i++;
512
    if(i<v->dim)
513
      w1 = v->v[i];
514
    for(j=i+1;j<v->dim && w1 != 1 && w1 != -1;j++)
515
    {
516
     if(v->v[j] != 0)
517
     {
518
       w2 = GGT(w1, v->v[j]);
519
       w1 = w2;
520
     }
521
    }
522
    if(w1 < 0)
523
      w1 = -w1;
524
    if(w1 != 0)
525
    {
526
       for(j=0;j<v->dim;j++)
527
         v->v[j] /= w1;
528
    }
529
  }
530
}
531

532

533

534

535

536
/**************************************************************************\
537
@---------------------------------------------------------------------------
538
@ int is_vertex_of_wallno(v, w)
539
@ vertex_TYP *v;
540
@ int w;
541
@ 
542
@     Checks if the inter w is an entry of v->wall.
543
@     If w is an entry of w->wall, the result is 1, otherwise 0.
544
@     CAUTION: the entries of v->wall have to be ordered, t.m. 
545
@              v->wall[i] < v->wall[i+1].
546
@
547
@---------------------------------------------------------------------------
548
@
549
\**************************************************************************/
550
int is_vertex_of_wallno(v, w)
551
vertex_TYP *v;
552
int w;
553
{
554
  int o,u,t;
555
  o=w;
556
  u=0;
557
  if(o>= v->wall_no)
558
    o=v->wall_no-1;
559
  while(o>u)
560
  {
561
    t=(o+u)/2;
562
    if(v->wall[t] < w)
563
      u=t+1;
564
    else
565
      o=t;
566
  } 
567
  if(w == v->wall[u])
568
    return(TRUE);
569
  return(FALSE);
570
}
571

572
/**************************************************************************\
573
@---------------------------------------------------------------------------
574
@ word_TYP *copy_word(w)
575
@ word_TYP *w;
576
@  make returns a copy of w.
577
@ in w->word[0] the length of w->word is encoded.
578
@---------------------------------------------------------------------------
579
\**************************************************************************/
580
word_TYP *copy_word(w)
581
word_TYP *w;
582
{
583
  word_TYP *erg;
584
  int	   i;
585

586
  erg = init_word(w->dim);
587
  erg->word = (int*)malloc((w->word[0]+1)* sizeof(int));
588
  for(i=0; i<= w->word[0]; i++)
589
     erg->word[i] = w->word[i];
590
  if(w->trans != NULL)
591
     erg->trans = copy_mat(w->trans);
592

593
  return(erg);
594
}
595

596

597
/**************************************************************************\
598
@---------------------------------------------------------------------------
599
@ wall_TYP *copy_wall(w)
600
@ wall_TYP *w;
601
@  make returns a copy of w.
602
@---------------------------------------------------------------------------
603
@
604
\**************************************************************************/
605
wall_TYP *copy_wall(w)
606
wall_TYP *w;
607
{
608
  wall_TYP *erg;
609
  int i;
610
  int j;
611

612
  erg = init_wall(w->dim);
613
  for(i=0;i<w->dim;i++)
614
   erg->gl[i] = w->gl[i];
615
  if(w->mat != NULL)
616
   erg->mat = copy_mat(w->mat);
617
  else
618
   erg->mat = NULL;
619
  if(w->word != NULL)                    /*anne, 16/07/97 */
620
   erg->word = copy_word(w->word);
621
  else
622
   erg->word = NULL;
623
  if(w->next != NULL){			/* 3 lines anne 8/10/97 */
624
   erg->next_no = w->next_no;
625
   erg->next = (int **)malloc(w->next_no *sizeof(int*));
626
   for(j=0; j<w->next_no; j++){
627
      erg->next[j] = (int*)malloc(w->dim * sizeof(int));
628
      for(i=0;i<w->dim;i++)
629
         erg->next[j][i] = w->next[j][i]; 
630
   }
631
  }
632
  else{
633
   erg->next = NULL;
634
   erg->next_no = 0;
635
  }
636
  if(w->extra != NULL){		/* 12 lines, anne 14/10/97 */
637
   erg->ext_no = w->ext_no;
638
   erg->extra = (int **)malloc(w->ext_no *sizeof(int*));
639
   for(j=0; j<w->ext_no; j++){
640
      erg->extra[j] = (int*)malloc(w->dim * sizeof(int));
641
      for(i=0;i<w->dim;i++)
642
         erg->extra[j][i] = w->extra[j][i]; 
643
   }
644
  }
645
  else{
646
   erg->extra = NULL;
647
   erg->ext_no = 0;
648
  }
649
  erg->neu = w->neu;
650
  erg->nproduct = w->nproduct;
651
  if(w->nproduct != 0)
652
  {
653
     if( (erg->product = (int *)malloc(w->nproduct *sizeof(int))) == 0)
654
     {
655
        printf("malloc failed in copy_wall\n");
656
        exit(2);
657
     }
658
  }
659
  for(i=0;i<w->nproduct;i++)
660
    erg->product[i] = w->product[i];
661
  return(erg);
662
}
663

664

665
/**************************************************************************\
666
@---------------------------------------------------------------------------
667
@ void free_polyeder(P)
668
@ polyeder_TYP *P;
669
@
670
@  frees all the pointers allocated in P, and P itself
671
@---------------------------------------------------------------------------
672
@
673
\**************************************************************************/
674
void free_polyeder(P)
675
polyeder_TYP *P;
676
{
677
  int i;
678
  for(i=0;i<P->vert_no;i++)
679
  {
680
    if(P->vert[i] != NULL)
681
      free_vertex(&P->vert[i]);
682
  }
683
  free(P->vert);
684
  for(i=0;i<P->wall_no; i++)
685
  {
686
   if(P->wall[i] != 0)
687
        free_wall(&P->wall[i]);
688
  }
689
  if(P->corner != NULL) 
690
    free(P->corner);
691
  if(P->wall != NULL)
692
    free(P->wall);
693
  free(P);
694
}
695

696
Product

Resources

Company
