1 /****************************************************************************************/
2 /* */
3 /* vinci_set.c */
4 /* */
5 /****************************************************************************************/
6 /* */
7 /* Authors: Benno Bueeler (bueeler@ifor.math.ethz.ch) */
8 /* and */
9 /* Andreas Enge (enge@ifor.math.ethz.ch) */
10 /* Institute for Operations Research */
11 /* Swiss Federal Institute of Technology Zurich */
12 /* Switzerland */
13 /* */
14 /* Last Changes: February 4, 2001 */
15 /* */
16 /****************************************************************************************/
17 /* */
18 /* functions on the data structures "set of pointers to vertices" and sets of them */
19 /* */
20 /****************************************************************************************/
21
22 #include "vinci.h"
23
24 /****************************************************************************************/
25 /* functions on sets of vertices */
26 /****************************************************************************************/
27
redimloe(T_VertexSet * s)28 static void redimloe (T_VertexSet *s)
29 /* adds some space to loe */
30
31 {
32 s -> maxel += ARRAYSIZESTEP;
33
34 s -> loe = (T_Vertex **)
35 my_realloc (s -> loe, (s -> maxel + 1) * sizeof (T_Vertex *),
36 ARRAYSIZESTEP * sizeof (T_Vertex *));
37 }
38
39 /****************************************************************************************/
40
position_of_element(T_Vertex * e,T_VertexSet s)41 static int position_of_element (T_Vertex *e, T_VertexSet s)
42 /* If e is in s, the function returns the index i with s.loe [i] = e. Otherwise, -1 */
43 /* is returned. The function uses a binary search algorithm. */
44
45 { int first = 0, last = s.lastel; /* e is searched between loe [first] and loe [last]. */
46 int middle, e_no = e -> no, middle_no;
47
48 if (s.lastel == -1) return -1;
49 while (last - first > 1)
50 { middle = (first + last) / 2;
51 middle_no = s.loe [middle] -> no;
52 if (middle_no == e_no)
53 return middle;
54 else if (middle_no > e_no)
55 last = middle;
56 else
57 first = middle;
58 }
59 if (s.loe [first] -> no == e_no)
60 return first;
61 else if (s.loe [last] -> no == e_no)
62 return last;
63 else
64 return -1;
65 }
66
67 /****************************************************************************************/
68 /****************************************************************************************/
69
create_empty_set()70 T_VertexSet create_empty_set ()
71 /* returns an empty set */
72
73 { T_VertexSet s;
74
75 s.maxel = G_d + ARRAYSIZESTEP;
76 s.loe = NULL;
77 s.lastel = -1;
78 s.loe = (T_Vertex **) my_malloc ((s.maxel + 1) * sizeof (T_Vertex *));
79 return s;
80 }
81
82 /****************************************************************************************/
83
free_set(T_VertexSet s)84 void free_set (T_VertexSet s)
85 /* frees the memory space used by s. Attention: You will not be able to use s after! */
86
87 {
88 my_free (s.loe, (s.maxel + 1) * sizeof (T_Vertex *));
89 }
90
91 /****************************************************************************************/
92
free_set_and_vertices(T_VertexSet s)93 void free_set_and_vertices (T_VertexSet s)
94 /* frees the memory space used by s and all its elements. Attention: You will nei- */
95 /* ther be able to use s nor any of its elements after! */
96
97 { int i;
98
99 for (i = 0; i <= s.lastel; i++) free_vertex (s.loe [i]);
100 free_set (s);
101 }
102
103 /****************************************************************************************/
104
clear_set(T_VertexSet * s)105 void clear_set (T_VertexSet *s)
106 /* empty the set s */
107
108 { (*s).lastel = -1;
109 }
110
111 /****************************************************************************************/
112
duplicate_set(T_VertexSet s)113 T_VertexSet duplicate_set (T_VertexSet s)
114 /* creates a new set with the same elements as s */
115
116 { T_VertexSet newset;
117
118 newset.maxel = s.lastel;
119 newset.lastel = s.lastel;
120 newset.loe = (T_Vertex **) my_malloc ((s.lastel + 1) * sizeof (T_Vertex *));
121 memcpy (newset.loe, s.loe, (s.lastel + 1) * sizeof (T_Vertex *));
122 return newset;
123 }
124
125 /****************************************************************************************/
126
copy_set(T_VertexSet s1,T_VertexSet * s2)127 void copy_set (T_VertexSet s1, T_VertexSet *s2)
128 /* copies the set s1 elementwise to s2 */
129
130 { int i;
131
132 clear_set (s2);
133 for (i = 0; i <= s1.lastel; i++) add_element (s2, s1.loe [i]);
134 }
135
136 /****************************************************************************************/
137
renumber_vertices()138 void renumber_vertices ()
139 /* The vertices in the global variable G_Vertices are renumbered in the following */
140 /* way: If the i-th vertex is contained in k hyperplanes, it gets the number - k so */
141 /* that highly degenerate vertices get lower numbers. Then the set is reordered and */
142 /* numbered from 0 on. If it is not void, the global variable G_Incidence is */
143 /* changed accordingly. */
144
145
146 {
147 int i, j, k;
148 T_Vertex *tmp_vertex;
149 boolean *tmp_incidence;
150
151 for (i = 0; i < G_n; i++)
152 G_Vertices.loe [i] -> no = 0;
153
154 for (i = 0; i < G_n; i++)
155 for (j = 0; j < G_m; j++)
156 if (G_Incidence [i][j])
157 G_Vertices.loe [i] -> no --;
158
159 /* sort the set of vertices */
160 for (i = 0; i < G_n - 1; i++)
161 {
162 /* look for the smallest vertex with index j >= i and swap with i */
163 j = i;
164 for (k = i + 1; k < G_n; k++)
165 if (G_Vertices.loe [k] -> no < G_Vertices.loe [j] -> no)
166 j = k;
167 if (i != j)
168 {
169 tmp_vertex = G_Vertices.loe [i];
170 G_Vertices.loe [i] = G_Vertices.loe [j];
171 G_Vertices.loe [j] = tmp_vertex;
172 if (G_Incidence != NULL)
173 {
174 tmp_incidence = G_Incidence [i];
175 G_Incidence [i] = G_Incidence [j];
176 G_Incidence [j] = tmp_incidence;
177 }
178 }
179 }
180
181 for (i = 0; i < G_n; i++)
182 G_Vertices.loe [i] -> no = i;
183
184 printf ("Vertices reordered.\n");
185 }
186
187 /****************************************************************************************/
188
normalise_vertices()189 rational normalise_vertices ()
190 /* The vertices are expected in the global variable G_Vertices. In each dimension */
191 /* they are multiplied by a factor so that the entries are between -1 and 1. The */
192 /* return value is the product over the scaling factors in all dimensions; it is the */
193 /* scaling factor for the volume. G_d must be known! */
194
195 {
196 rational *scaling = create_vector ();
197 rational scaling_volume = 1;
198 rational absolute;
199 int i, j;
200
201 for (j = 0; j < G_d; j ++)
202 scaling [j] = -1;
203
204 for (j = 0; j < G_d; j++)
205 for (i = 0; i <= G_Vertices.lastel; i++)
206 { absolute = fabs (G_Vertices.loe [i] -> coords [j]);
207 if (absolute > scaling [j])
208 scaling [j] = absolute;
209 }
210
211 for (j = 0; j < G_d; j++)
212 { scaling_volume *= scaling [j];
213 for (i = 0; i <= G_Vertices.lastel; i++)
214 G_Vertices.loe [i] -> coords [j] /= scaling [j];
215 }
216
217 return scaling_volume;
218 }
219
220 /****************************************************************************************/
221
print_set(FILE * f,T_VertexSet s)222 void print_set (FILE *f, T_VertexSet s)
223 /* prints the numbers of the elements of s to the (already opened) file f */
224
225 { int i;
226
227 if (empty (s)) fprintf (f, "\nThe set is empty.");
228 else
229 for (i=0; i <= (s.lastel); i++)
230 fprintf (f, "%i\t", s.loe [i] -> no);
231 }
232
233 /****************************************************************************************/
234
empty(T_VertexSet s)235 boolean empty (T_VertexSet s)
236
237 {
238 return (s.lastel == -1);
239 }
240
241 /****************************************************************************************/
242
is_in_hyperplane(T_Vertex * e,int j)243 boolean is_in_hyperplane (T_Vertex *e, int j)
244
245 {
246 return G_Incidence [e -> no][j];
247 }
248
249 /****************************************************************************************/
250
are_equal_sets(T_VertexSet s1,T_VertexSet s2)251 boolean are_equal_sets (T_VertexSet s1, T_VertexSet s2)
252
253 {
254 if (s1.lastel != s2.lastel) return FALSE;
255 else if (empty (s1)) return TRUE;
256 else
257 return (!(memcmp (s1.loe, s2.loe, (s1.lastel + 1) * sizeof (T_Vertex *))));
258
259 }
260
261 /****************************************************************************************/
262
add_element(T_VertexSet * s,T_Vertex * e)263 void add_element (T_VertexSet *s, T_Vertex *e)
264 /* adds the element e to the set s. */
265
266 { int i, pos, first = 0, last = s -> lastel, e_no = e -> no;
267 int middle, middle_no;
268
269 if (last == s -> maxel) redimloe (s);
270 if (empty (*s))
271 { s -> lastel = 0;
272 s -> loe [0] = e;
273 }
274 else if (e_no > s -> loe [last] -> no)
275 /* insert element at the end of the list */
276 s -> loe [++ s -> lastel] = e;
277 else if (e_no < s -> loe [0] -> no)
278 { /* insert element at the beginning of the list */
279 for (i = last; i >= 0; i--) s -> loe [i+1] = s -> loe [i];
280 s -> loe [0] = e;
281 s -> lastel++;
282 }
283 else
284 { /* The element will be inserted after position pos. */
285 /* look for pos between first and last */
286 while (last - first > 1)
287 { middle = (first + last) / 2;
288 middle_no = (*s).loe [middle] -> no;
289 if (middle_no >= e_no)
290 last = middle;
291 else
292 first = middle;
293 }
294 pos = first;
295 for (i = s -> lastel; i > pos; i--) s -> loe [i+1] = s -> loe [i];
296 s -> loe [pos + 1] = e;
297 s -> lastel++;
298 }
299 }
300
301 /****************************************************************************************/
302
delete_element(T_VertexSet * s,T_Vertex * e)303 boolean delete_element (T_VertexSet *s, T_Vertex *e)
304 /* removes the element e from the set s. Return value is TRUE if the element actual- */
305 /* ly was in the set, FALSE otherwise. */
306
307 { int j, position;
308
309 /* look for element in the list */
310 position = position_of_element (e, *s);
311 if (position == -1) return FALSE;
312 else
313 { for (j = position; j < s -> lastel; j++)
314 s -> loe [j] = s -> loe [j+1];
315 s -> lastel --;
316 return TRUE;
317 }
318 }
319
320 /****************************************************************************************/
321
intersect_with_hyperplane(T_VertexSet s,int j,T_VertexSet * inter)322 void intersect_with_hyperplane (T_VertexSet s, int j, T_VertexSet *inter)
323 /* stores the intersection of s with hyperplane j in inter */
324
325 {
326 int i;
327
328 inter -> lastel = -1;
329 if (!(empty (s)))
330 for (i = 0; i <= s.lastel; i++)
331 if (is_in_hyperplane (s.loe [i], j))
332 { /* add_element (inter, s.loe [i]); */
333 if (inter -> lastel == inter -> maxel) redimloe (inter);
334 inter -> loe [++ inter -> lastel] = s.loe [i];
335 }
336 }
337
338 /****************************************************************************************/
339 /* functions on sets of sets, called 'supersets' */
340 /****************************************************************************************/
341
create_empty_superset()342 T_VertexSuperset *create_empty_superset ()
343 /* returns an empty set of sets */
344
345 { return NULL;
346 }
347
348 /****************************************************************************************/
349
free_superset(T_VertexSuperset ** S)350 void free_superset (T_VertexSuperset **S)
351 /* frees the memory space used by S. */
352 {
353 T_VertexSuperset *L;
354
355 while (*S != NULL)
356 {
357 L = *S;
358 (*S) = (*S) -> next;
359 free_set (L -> content);
360 my_free (L, sizeof (T_VertexSuperset));
361 }
362 }
363
364 /****************************************************************************************/
365
print_superset(FILE * f,T_VertexSuperset * S)366 void print_superset (FILE *f, T_VertexSuperset *S)
367 /* prints the elements of S to the (already opened) file f */
368
369 {
370 if (S == NULL) printf ("The set of sets is empty.\n");
371 else
372 { printf ("The set of sets contains the following sets:\n");
373 while (S != NULL)
374 { print_set (f, S -> content);
375 S = S -> next;}
376 }
377 }
378
379 /****************************************************************************************/
380
is_in_superset(T_VertexSet s,T_VertexSuperset * S)381 boolean is_in_superset (T_VertexSet s, T_VertexSuperset *S)
382 /* tests whether s is contained in S */
383
384 { while (S != NULL && !are_equal_sets (S -> content, s)) S = S -> next;
385 if (S == NULL) return FALSE;
386 else return TRUE;
387 }
388
389 /****************************************************************************************/
390
add_superelement(T_VertexSuperset ** S,T_VertexSet s)391 void add_superelement (T_VertexSuperset **S, T_VertexSet s)
392 /* adds the element s at the beginning to the set S. */
393
394 { T_VertexSuperset *L;
395
396 L = (T_VertexSuperset *) my_malloc (sizeof (T_VertexSuperset));
397 L -> content = s;
398 L -> next = *S;
399 *S = L;
400 }
401
402 /****************************************************************************************/
403 /****************************************************************************************/
404