1 /****************************************************************************************/
2 /* */
3 /* vinci_file.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: May 19, 2003 */
15 /* */
16 /****************************************************************************************/
17 /* */
18 /* functions allowing to read data files in the format of Avis and Fukuda */
19 /* */
20 /****************************************************************************************/
21
22 #include "vinci.h"
23
24 /****************************************************************************************/
25
open_read(char filename[255])26 FILE * open_read (char filename [255])
27 /* opens the specified file, reads all lines up to a line 'begin' and returns a */
28 /* pointer to the file */
29
30 { FILE *fp;
31 char line [255];
32 boolean begin_found = FALSE;
33
34
35 if (! (fp = fopen (filename, "r")))
36 { fprintf (stderr, "\n***** ERROR: Could not open file '%s' in 'open_read'.\n", filename);
37 exit (0);
38 };
39 while (!feof (fp) && !begin_found)
40 { fgets (line, 255, fp);
41 if (!strncmp (line, "begin", 5)) begin_found = TRUE;
42 };
43 if (!begin_found)
44 { fprintf (stderr, "\n***** ERROR: File '%s' in 'open_read does not contain a line 'begin'.\n",
45 filename);
46 exit (0);
47 };
48 return fp;
49 }
50
51 /****************************************************************************************/
52
determine_data_type(char * data_type)53 int determine_data_type (char *data_type)
54 /* returns the integer code for the data type written in "data_type" */
55
56 {
57 if (!strcmp (data_type, "integer"))
58 return INTEGER_T;
59 else if (!strcmp (data_type, "real"))
60 return REAL_T;
61 else if (!strcmp (data_type, "rational"))
62 return RATIONAL_T;
63 else
64 { fprintf (stderr, "\n***** ERROR: '%s' is not a known data type; use integer, real or rational.",
65 data_type);
66 return NONE;
67 }
68 }
69
70 /****************************************************************************************/
71
sread_rational_value(char * s,rational * value)72 void sread_rational_value (char *s, rational *value)
73 /* reads a rational value from the specified string "s" and assigns it to "value" */
74
75 {
76 char *numerator_s, *denominator_s = NULL, *position, token;
77 int sign = 1, i;
78 rational numerator, denominator;
79
80 /* determine the sign of the number */
81 numerator_s = s;
82 if (s [0] == '-')
83 { sign = -1;
84 numerator_s++;
85 }
86 else if (s [0] == '+')
87 numerator_s++;
88
89 /* look for a sign '/' and in this case split the number in numerator and denominator */
90 position = strchr (numerator_s, '/');
91 if (position != NULL)
92 { *position = '\0'; /* terminates the numerator */
93 denominator_s = position + 1;
94 };
95
96 /* determine the floating point values of numerator and denominator */
97 numerator = 0;
98 for (i = 0; i < strlen (numerator_s); i++)
99 { token = numerator_s [i];
100 if (strchr ("0123456789", token)) /* token is a cypher */
101 numerator = 10 * numerator + (int) token - 48;
102 }
103
104 if (position != NULL)
105 { denominator = 0;
106 for (i = 0; i < strlen (denominator_s); i++)
107 { token = denominator_s [i];
108 if (strchr ("0123456789", token)) /* token is a cypher */
109 denominator = 10 * denominator + (int) token - 48;
110 }
111 }
112 else denominator = 1;
113
114 *value = sign * numerator / denominator;
115 }
116
117 /****************************************************************************************/
118
fread_rational_value(FILE * f,real * value)119 static void fread_rational_value (FILE *f, real *value)
120 /* reads a rational value from the specified file "f" and assigns it to "value" */
121
122 {
123 char number_s [255];
124 rational rational_value;
125
126 fscanf (f, "%s ", number_s);
127 sread_rational_value (number_s, &rational_value);
128 *value = rational_value;
129
130 }
131
132 /****************************************************************************************/
133
read_vertices(char filename[255])134 void read_vertices (char filename [255])
135 /* reads the vertices from the specified file to the global variable G_Vertices and */
136 /* sets G_n and G_d */
137 /* The file must contain the vertices in the following polyhedra format of Avis and */
138 /* Fukuda: */
139 /* comments */
140 /* begin */
141 /* number of vertices n dimension + 1 type of coordinates */
142 /* 1 v1 */
143 /* ... */
144 /* 1 vn */
145 /* end or any other text (is ignored) */
146
147 { FILE *f;
148 int i, j;
149 T_Vertex *v;
150 char data_type_string [255];
151 int data_type;
152
153 G_Vertices = create_empty_set ();
154 f = open_read (filename);
155 fscanf (f, "%i %i %s ", &G_n, &G_d, data_type_string);
156 G_d --;
157 data_type = determine_data_type (data_type_string);
158 if (data_type == RATIONAL_T)
159 { fprintf (stderr, "\n***** WARNING: The vertex file is of rational type; the ");
160 fprintf (stderr, "vertex coordinates\nwill be transformed to floating point ");
161 fprintf (stderr, "values.\n");
162 }
163
164 for (i = 0; i < G_n; i++)
165 { v = create_vertex ();
166 fscanf (f, "%*i "); /* skips the entry one */
167 v -> no = i; /* this assures v to be added at the end of the list */
168 if (data_type == REAL_T)
169 for (j = 0; j < G_d; j++)
170 fscanf (f, "%lg ", &(v -> coords [j]));
171 else
172 for (j = 0; j < G_d; j++)
173 fread_rational_value (f, &(v -> coords [j]));
174 add_element (&G_Vertices, v);
175 };
176 fclose (f);
177 }
178
179 /****************************************************************************************/
180
read_hyperplanes(char filename[255])181 void read_hyperplanes (char filename [255])
182 /* reads the hyperplanes from the specified file to the global variable */
183 /* G_Hyperplanes and sets G_m and G_d */
184 /* The file must contain the hyperplanes in the following polyhedra format of Avis */
185 /* and Fukuda: */
186 /* comments */
187 /* begin */
188 /* number of hyperplanes m dimension + 1 type of coordinates */
189 /* b -A */
190 /* end or any other text (is ignored) */
191
192 { FILE *f;
193 int i, j;
194 char data_type_string [255];
195 int data_type;
196
197
198 f = open_read (filename);
199 fscanf (f, "%i %i %s ", &G_m, &G_d, data_type_string);
200 G_d --;
201 data_type = determine_data_type (data_type_string);
202 if (data_type == RATIONAL_T)
203 { fprintf (stderr, "\n***** WARNING: The planes file is of rational type; all ");
204 fprintf (stderr, "coordinates will be\ntransformed to floating point values.\n");
205 }
206
207 create_hyperplanes ();
208
209 if (data_type == REAL_T)
210 for (i = 0; i < G_m; i++)
211 { fscanf (f, "%le ", &(G_Hyperplanes [i] [G_d]));
212 for (j = 0; j < G_d; j++)
213 { fscanf (f, "%le ", &(G_Hyperplanes [i] [j]));
214 G_Hyperplanes [i] [j] = - G_Hyperplanes [i] [j];
215 }
216 }
217 else
218 for (i = 0; i < G_m; i++)
219 { fread_rational_value (f, &(G_Hyperplanes [i] [G_d]));
220 for (j = 0; j < G_d; j++)
221 { fread_rational_value (f, &(G_Hyperplanes [i] [j]));
222 G_Hyperplanes [i] [j] = - G_Hyperplanes [i] [j];
223 }
224 }
225
226 fclose (f);
227 }
228
229 /****************************************************************************************/
230
compute_incidence()231 void compute_incidence ()
232 /* determines the incidence of facettes and vertices and stores the structure in the */
233 /* global variable G_Incidence */
234 /* Beware that vertices and hyperplanes have to be read before. */
235
236 { int i, j, k;
237 real diff;
238
239 create_incidence ();
240
241 for (j = 0; j < G_m; j++)
242 for (i = 0; i < G_n; i++)
243 { /* check if vertex i is incident with hyperplane j */
244 diff = G_Hyperplanes [j][G_d];
245 for (k = 0; k < G_d; k++)
246 diff -= (G_Vertices.loe [i] -> coords [k]) * G_Hyperplanes [j][k];
247 if (fabs (diff) < INCIDENCE_EPSILON)
248 G_Incidence [i][j] = TRUE;
249 else
250 G_Incidence [i][j] = FALSE;
251 }
252
253 }
254
255 /****************************************************************************************/
256 /****************************************************************************************/
257