|
1 /* glptsp.c */ |
|
2 |
|
3 /*********************************************************************** |
|
4 * This code is part of GLPK (GNU Linear Programming Kit). |
|
5 * |
|
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
|
7 * 2009, 2010 Andrew Makhorin, Department for Applied Informatics, |
|
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
|
9 * E-mail: <mao@gnu.org>. |
|
10 * |
|
11 * GLPK is free software: you can redistribute it and/or modify it |
|
12 * under the terms of the GNU General Public License as published by |
|
13 * the Free Software Foundation, either version 3 of the License, or |
|
14 * (at your option) any later version. |
|
15 * |
|
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT |
|
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
|
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
|
19 * License for more details. |
|
20 * |
|
21 * You should have received a copy of the GNU General Public License |
|
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>. |
|
23 ***********************************************************************/ |
|
24 |
|
25 #define _GLPSTD_ERRNO |
|
26 #define _GLPSTD_STDIO |
|
27 #include "glpenv.h" |
|
28 #include "glptsp.h" |
|
29 #define xfault xerror |
|
30 |
|
31 /*---------------------------------------------------------------------- |
|
32 -- tsp_read_data - read TSP instance data. |
|
33 -- |
|
34 -- *Synopsis* |
|
35 -- |
|
36 -- #include "glptsp.h" |
|
37 -- TSP *tsp_read_data(char *fname); |
|
38 -- |
|
39 -- *Description* |
|
40 -- |
|
41 -- The routine tsp_read_data reads a TSP (or related problem) instance |
|
42 -- data from the text file, whose name is the character string fname. |
|
43 -- |
|
44 -- For detailed description of the format recognized by the routine see |
|
45 -- the report: G.Reinelt, TSPLIB 95. |
|
46 -- |
|
47 -- *Returns* |
|
48 -- |
|
49 -- If no error occurred, the routine tsp_read_data returns a pointer to |
|
50 -- the TSP instance data block, which contains loaded data. In the case |
|
51 -- of error the routine prints an error message and returns NULL. */ |
|
52 |
|
53 struct dsa |
|
54 { /* dynamic storage area used by the routine tsp_read_data */ |
|
55 char *fname; |
|
56 /* name of the input text file */ |
|
57 FILE *fp; |
|
58 /* stream assigned to the input text file */ |
|
59 int seqn; |
|
60 /* line sequential number */ |
|
61 int c; |
|
62 /* current character */ |
|
63 char token[255+1]; |
|
64 /* current token */ |
|
65 }; |
|
66 |
|
67 static int get_char(struct dsa *dsa) |
|
68 { dsa->c = fgetc(dsa->fp); |
|
69 if (ferror(dsa->fp)) |
|
70 { xprintf("%s:%d: read error - %s\n", |
|
71 dsa->fname, dsa->seqn, strerror(errno)); |
|
72 return 1; |
|
73 } |
|
74 if (feof(dsa->fp)) |
|
75 dsa->c = EOF; |
|
76 else if (dsa->c == '\n') |
|
77 dsa->seqn++; |
|
78 else if (isspace(dsa->c)) |
|
79 dsa->c = ' '; |
|
80 else if (iscntrl(dsa->c)) |
|
81 { xprintf("%s:%d: invalid control character 0x%02X\n", |
|
82 dsa->fname, dsa->seqn, dsa->c); |
|
83 return 1; |
|
84 } |
|
85 return 0; |
|
86 } |
|
87 |
|
88 static int skip_spaces(struct dsa *dsa, int across) |
|
89 { while (dsa->c == ' ' || (across && dsa->c == '\n')) |
|
90 if (get_char(dsa)) return 1; |
|
91 return 0; |
|
92 } |
|
93 |
|
94 static int scan_keyword(struct dsa *dsa) |
|
95 { int len = 0; |
|
96 if (skip_spaces(dsa, 0)) return 1; |
|
97 dsa->token[0] = '\0'; |
|
98 while (isalnum(dsa->c) || dsa->c == '_') |
|
99 { if (len == 31) |
|
100 { xprintf("%s:%d: keyword `%s...' too long\n", dsa->fname, |
|
101 dsa->seqn, dsa->token); |
|
102 return 1; |
|
103 } |
|
104 dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0'; |
|
105 if (get_char(dsa)) return 1; |
|
106 } |
|
107 if (len == 0) |
|
108 { xprintf("%s:%d: missing keyword\n", dsa->fname, dsa->seqn); |
|
109 return 1; |
|
110 } |
|
111 return 0; |
|
112 } |
|
113 |
|
114 static int check_colon(struct dsa *dsa) |
|
115 { if (skip_spaces(dsa, 0)) return 1; |
|
116 if (dsa->c != ':') |
|
117 { xprintf("%s:%d: missing colon after `%s'\n", dsa->fname, |
|
118 dsa->seqn, dsa->token); |
|
119 return 1; |
|
120 } |
|
121 if (get_char(dsa)) return 1; |
|
122 return 0; |
|
123 } |
|
124 |
|
125 static int scan_token(struct dsa *dsa, int across) |
|
126 { int len = 0; |
|
127 if (skip_spaces(dsa, across)) return 1; |
|
128 dsa->token[0] = '\0'; |
|
129 while (!(dsa->c == EOF || dsa->c == '\n' || dsa->c == ' ')) |
|
130 { if (len == 255) |
|
131 { dsa->token[31] = '\0'; |
|
132 xprintf("%s:%d: token `%s...' too long\n", dsa->fname, |
|
133 dsa->seqn, dsa->token); |
|
134 return 1; |
|
135 } |
|
136 dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0'; |
|
137 if (get_char(dsa)) return 1; |
|
138 } |
|
139 return 0; |
|
140 } |
|
141 |
|
142 static int check_newline(struct dsa *dsa) |
|
143 { if (skip_spaces(dsa, 0)) return 1; |
|
144 if (!(dsa->c == EOF || dsa->c == '\n')) |
|
145 { xprintf("%s:%d: extra symbols detected\n", dsa->fname, |
|
146 dsa->seqn); |
|
147 return 1; |
|
148 } |
|
149 if (get_char(dsa)) return 1; |
|
150 return 0; |
|
151 } |
|
152 |
|
153 static int scan_comment(struct dsa *dsa) |
|
154 { int len = 0; |
|
155 if (skip_spaces(dsa, 0)) return 1; |
|
156 dsa->token[0] = '\0'; |
|
157 while (!(dsa->c == EOF || dsa->c == '\n')) |
|
158 { if (len == 255) |
|
159 { xprintf("%s:%d: comment too long\n", dsa->fname, dsa->seqn) |
|
160 ; |
|
161 return 1; |
|
162 } |
|
163 dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0'; |
|
164 if (get_char(dsa)) return 1; |
|
165 } |
|
166 return 0; |
|
167 } |
|
168 |
|
169 static int scan_integer(struct dsa *dsa, int across, int *val) |
|
170 { if (scan_token(dsa, across)) return 1; |
|
171 if (strlen(dsa->token) == 0) |
|
172 { xprintf("%s:%d: missing integer\n", dsa->fname, dsa->seqn); |
|
173 return 1; |
|
174 } |
|
175 if (str2int(dsa->token, val)) |
|
176 { xprintf("%s:%d: integer `%s' invalid\n", dsa->fname, dsa->seqn |
|
177 , dsa->token); |
|
178 return 1; |
|
179 } |
|
180 return 0; |
|
181 } |
|
182 |
|
183 static int scan_number(struct dsa *dsa, int across, double *val) |
|
184 { if (scan_token(dsa, across)) return 1; |
|
185 if (strlen(dsa->token) == 0) |
|
186 { xprintf("%s:%d: missing number\n", dsa->fname, dsa->seqn); |
|
187 return 1; |
|
188 } |
|
189 if (str2num(dsa->token, val)) |
|
190 { xprintf("%s:%d: number `%s' invalid\n", dsa->fname, dsa->seqn, |
|
191 dsa->token); |
|
192 return 1; |
|
193 } |
|
194 return 0; |
|
195 } |
|
196 |
|
197 TSP *tsp_read_data(char *fname) |
|
198 { struct dsa _dsa, *dsa = &_dsa; |
|
199 TSP *tsp = NULL; |
|
200 dsa->fname = fname; |
|
201 xprintf("tsp_read_data: reading TSP data from `%s'...\n", |
|
202 dsa->fname); |
|
203 dsa->fp = fopen(dsa->fname, "r"); |
|
204 if (dsa->fp == NULL) |
|
205 { xprintf("tsp_read_data: unable to open `%s' - %s\n", |
|
206 dsa->fname, strerror(errno)); |
|
207 goto fail; |
|
208 } |
|
209 tsp = xmalloc(sizeof(TSP)); |
|
210 tsp->name = NULL; |
|
211 tsp->type = TSP_UNDEF; |
|
212 tsp->comment = NULL; |
|
213 tsp->dimension = 0; |
|
214 tsp->edge_weight_type = TSP_UNDEF; |
|
215 tsp->edge_weight_format = TSP_UNDEF; |
|
216 tsp->display_data_type = TSP_UNDEF; |
|
217 tsp->node_x_coord = NULL; |
|
218 tsp->node_y_coord = NULL; |
|
219 tsp->dply_x_coord = NULL; |
|
220 tsp->dply_y_coord = NULL; |
|
221 tsp->tour = NULL; |
|
222 tsp->edge_weight = NULL; |
|
223 dsa->seqn = 1; |
|
224 if (get_char(dsa)) goto fail; |
|
225 loop: if (scan_keyword(dsa)) goto fail; |
|
226 if (strcmp(dsa->token, "NAME") == 0) |
|
227 { if (tsp->name != NULL) |
|
228 { xprintf("%s:%d: NAME entry multiply defined\n", dsa->fname, |
|
229 dsa->seqn); |
|
230 goto fail; |
|
231 } |
|
232 if (check_colon(dsa)) goto fail; |
|
233 if (scan_token(dsa, 0)) goto fail; |
|
234 if (strlen(dsa->token) == 0) |
|
235 { xprintf("%s:%d: NAME entry incomplete\n", dsa->fname, |
|
236 dsa->seqn); |
|
237 goto fail; |
|
238 } |
|
239 tsp->name = xmalloc(strlen(dsa->token) + 1); |
|
240 strcpy(tsp->name, dsa->token); |
|
241 xprintf("tsp_read_data: NAME: %s\n", tsp->name); |
|
242 if (check_newline(dsa)) goto fail; |
|
243 } |
|
244 else if (strcmp(dsa->token, "TYPE") == 0) |
|
245 { if (tsp->type != TSP_UNDEF) |
|
246 { xprintf("%s:%d: TYPE entry multiply defined\n", dsa->fname, |
|
247 dsa->seqn); |
|
248 goto fail; |
|
249 } |
|
250 if (check_colon(dsa)) goto fail; |
|
251 if (scan_keyword(dsa)) goto fail; |
|
252 if (strcmp(dsa->token, "TSP") == 0) |
|
253 tsp->type = TSP_TSP; |
|
254 else if (strcmp(dsa->token, "ATSP") == 0) |
|
255 tsp->type = TSP_ATSP; |
|
256 else if (strcmp(dsa->token, "TOUR") == 0) |
|
257 tsp->type = TSP_TOUR; |
|
258 else |
|
259 { xprintf("%s:%d: data type `%s' not recognized\n", |
|
260 dsa->fname, dsa->seqn, dsa->token); |
|
261 goto fail; |
|
262 } |
|
263 xprintf("tsp_read_data: TYPE: %s\n", dsa->token); |
|
264 if (check_newline(dsa)) goto fail; |
|
265 } |
|
266 else if (strcmp(dsa->token, "COMMENT") == 0) |
|
267 { if (tsp->comment != NULL) |
|
268 { xprintf("%s:%d: COMMENT entry multiply defined\n", |
|
269 dsa->fname, dsa->seqn); |
|
270 goto fail; |
|
271 } |
|
272 if (check_colon(dsa)) goto fail; |
|
273 if (scan_comment(dsa)) goto fail; |
|
274 tsp->comment = xmalloc(strlen(dsa->token) + 1); |
|
275 strcpy(tsp->comment, dsa->token); |
|
276 xprintf("tsp_read_data: COMMENT: %s\n", tsp->comment); |
|
277 if (check_newline(dsa)) goto fail; |
|
278 } |
|
279 else if (strcmp(dsa->token, "DIMENSION") == 0) |
|
280 { if (tsp->dimension != 0) |
|
281 { xprintf("%s:%d: DIMENSION entry multiply defined\n", |
|
282 dsa->fname, dsa->seqn); |
|
283 goto fail; |
|
284 } |
|
285 if (check_colon(dsa)) goto fail; |
|
286 if (scan_integer(dsa, 0, &tsp->dimension)) goto fail; |
|
287 if (tsp->dimension < 1) |
|
288 { xprintf("%s:%d: invalid dimension\n", dsa->fname, |
|
289 dsa->seqn); |
|
290 goto fail; |
|
291 } |
|
292 xprintf("tsp_read_data: DIMENSION: %d\n", tsp->dimension); |
|
293 if (check_newline(dsa)) goto fail; |
|
294 } |
|
295 else if (strcmp(dsa->token, "EDGE_WEIGHT_TYPE") == 0) |
|
296 { if (tsp->edge_weight_type != TSP_UNDEF) |
|
297 { xprintf("%s:%d: EDGE_WEIGHT_TYPE entry multiply defined\n", |
|
298 dsa->fname, dsa->seqn); |
|
299 goto fail; |
|
300 } |
|
301 if (check_colon(dsa)) goto fail; |
|
302 if (scan_keyword(dsa)) goto fail; |
|
303 if (strcmp(dsa->token, "GEO") == 0) |
|
304 tsp->edge_weight_type = TSP_GEO; |
|
305 else if (strcmp(dsa->token, "EUC_2D") == 0) |
|
306 tsp->edge_weight_type = TSP_EUC_2D; |
|
307 else if (strcmp(dsa->token, "ATT") == 0) |
|
308 tsp->edge_weight_type = TSP_ATT; |
|
309 else if (strcmp(dsa->token, "EXPLICIT") == 0) |
|
310 tsp->edge_weight_type = TSP_EXPLICIT; |
|
311 else if (strcmp(dsa->token, "CEIL_2D") == 0) |
|
312 tsp->edge_weight_type = TSP_CEIL_2D; |
|
313 else |
|
314 { xprintf("%s:%d: edge weight type `%s' not recognized\n", |
|
315 dsa->fname, dsa->seqn, dsa->token); |
|
316 goto fail; |
|
317 } |
|
318 xprintf("tsp_read_data: EDGE_WEIGHT_TYPE: %s\n", dsa->token); |
|
319 if (check_newline(dsa)) goto fail; |
|
320 } |
|
321 else if (strcmp(dsa->token, "EDGE_WEIGHT_FORMAT") == 0) |
|
322 { if (tsp->edge_weight_format != TSP_UNDEF) |
|
323 { xprintf( |
|
324 "%s:%d: EDGE_WEIGHT_FORMAT entry multiply defined\n", |
|
325 dsa->fname, dsa->seqn); |
|
326 goto fail; |
|
327 } |
|
328 if (check_colon(dsa)) goto fail; |
|
329 if (scan_keyword(dsa)) goto fail; |
|
330 if (strcmp(dsa->token, "UPPER_ROW") == 0) |
|
331 tsp->edge_weight_format = TSP_UPPER_ROW; |
|
332 else if (strcmp(dsa->token, "FULL_MATRIX") == 0) |
|
333 tsp->edge_weight_format = TSP_FULL_MATRIX; |
|
334 else if (strcmp(dsa->token, "FUNCTION") == 0) |
|
335 tsp->edge_weight_format = TSP_FUNCTION; |
|
336 else if (strcmp(dsa->token, "LOWER_DIAG_ROW") == 0) |
|
337 tsp->edge_weight_format = TSP_LOWER_DIAG_ROW; |
|
338 else |
|
339 { xprintf("%s:%d: edge weight format `%s' not recognized\n", |
|
340 dsa->fname, dsa->seqn, dsa->token); |
|
341 goto fail; |
|
342 } |
|
343 xprintf("tsp_read_data: EDGE_WEIGHT_FORMAT: %s\n", dsa->token); |
|
344 if (check_newline(dsa)) goto fail; |
|
345 } |
|
346 else if (strcmp(dsa->token, "DISPLAY_DATA_TYPE") == 0) |
|
347 { if (tsp->display_data_type != TSP_UNDEF) |
|
348 { xprintf("%s:%d: DISPLAY_DATA_TYPE entry multiply defined\n", |
|
349 dsa->fname, dsa->seqn); |
|
350 goto fail; |
|
351 } |
|
352 if (check_colon(dsa)) goto fail; |
|
353 if (scan_keyword(dsa)) goto fail; |
|
354 if (strcmp(dsa->token, "COORD_DISPLAY") == 0) |
|
355 tsp->display_data_type = TSP_COORD_DISPLAY; |
|
356 else if (strcmp(dsa->token, "TWOD_DISPLAY") == 0) |
|
357 tsp->display_data_type = TSP_TWOD_DISPLAY; |
|
358 else |
|
359 { xprintf("%s:%d: display data type `%s' not recognized\n", |
|
360 dsa->fname, dsa->seqn, dsa->token); |
|
361 goto fail; |
|
362 } |
|
363 xprintf("tsp_read_data: DISPLAY_DATA_TYPE: %s\n", dsa->token); |
|
364 if (check_newline(dsa)) goto fail; |
|
365 } |
|
366 else if (strcmp(dsa->token, "NODE_COORD_SECTION") == 0) |
|
367 { int n = tsp->dimension, k, node; |
|
368 if (n == 0) |
|
369 { xprintf("%s:%d: DIMENSION entry not specified\n", |
|
370 dsa->fname, dsa->seqn); |
|
371 goto fail; |
|
372 } |
|
373 if (tsp->node_x_coord != NULL) |
|
374 { xprintf("%s:%d: NODE_COORD_SECTION multiply specified\n", |
|
375 dsa->fname, dsa->seqn); |
|
376 goto fail; |
|
377 } |
|
378 if (check_newline(dsa)) goto fail; |
|
379 tsp->node_x_coord = xcalloc(1+n, sizeof(double)); |
|
380 tsp->node_y_coord = xcalloc(1+n, sizeof(double)); |
|
381 for (node = 1; node <= n; node++) |
|
382 tsp->node_x_coord[node] = tsp->node_y_coord[node] = DBL_MAX; |
|
383 for (k = 1; k <= n; k++) |
|
384 { if (scan_integer(dsa, 0, &node)) goto fail; |
|
385 if (!(1 <= node && node <= n)) |
|
386 { xprintf("%s:%d: invalid node number %d\n", dsa->fname, |
|
387 dsa->seqn, node); |
|
388 goto fail; |
|
389 } |
|
390 if (tsp->node_x_coord[node] != DBL_MAX) |
|
391 { xprintf("%s:%d: node number %d multiply specified\n", |
|
392 dsa->fname, dsa->seqn, node); |
|
393 goto fail; |
|
394 } |
|
395 if (scan_number(dsa, 0, &tsp->node_x_coord[node])) |
|
396 goto fail; |
|
397 if (scan_number(dsa, 0, &tsp->node_y_coord[node])) |
|
398 goto fail; |
|
399 if (check_newline(dsa)) goto fail; |
|
400 } |
|
401 } |
|
402 else if (strcmp(dsa->token, "DISPLAY_DATA_SECTION") == 0) |
|
403 { int n = tsp->dimension, k, node; |
|
404 if (n == 0) |
|
405 { xprintf("%s:%d: DIMENSION entry not specified\n", |
|
406 dsa->fname, dsa->seqn); |
|
407 goto fail; |
|
408 } |
|
409 if (tsp->dply_x_coord != NULL) |
|
410 { xprintf("%s:%d: DISPLAY_DATA_SECTION multiply specified\n", |
|
411 dsa->fname, dsa->seqn); |
|
412 goto fail; |
|
413 } |
|
414 if (check_newline(dsa)) goto fail; |
|
415 tsp->dply_x_coord = xcalloc(1+n, sizeof(double)); |
|
416 tsp->dply_y_coord = xcalloc(1+n, sizeof(double)); |
|
417 for (node = 1; node <= n; node++) |
|
418 tsp->dply_x_coord[node] = tsp->dply_y_coord[node] = DBL_MAX; |
|
419 for (k = 1; k <= n; k++) |
|
420 { if (scan_integer(dsa, 0, &node)) goto fail; |
|
421 if (!(1 <= node && node <= n)) |
|
422 { xprintf("%s:%d: invalid node number %d\n", dsa->fname, |
|
423 dsa->seqn, node); |
|
424 goto fail; |
|
425 } |
|
426 if (tsp->dply_x_coord[node] != DBL_MAX) |
|
427 { xprintf("%s:%d: node number %d multiply specified\n", |
|
428 dsa->fname, dsa->seqn, node); |
|
429 goto fail; |
|
430 } |
|
431 if (scan_number(dsa, 0, &tsp->dply_x_coord[node])) |
|
432 goto fail; |
|
433 if (scan_number(dsa, 0, &tsp->dply_y_coord[node])) |
|
434 goto fail; |
|
435 if (check_newline(dsa)) goto fail; |
|
436 } |
|
437 } |
|
438 else if (strcmp(dsa->token, "TOUR_SECTION") == 0) |
|
439 { int n = tsp->dimension, k, node; |
|
440 if (n == 0) |
|
441 { xprintf("%s:%d: DIMENSION entry not specified\n", |
|
442 dsa->fname, dsa->seqn); |
|
443 goto fail; |
|
444 } |
|
445 if (tsp->tour != NULL) |
|
446 { xprintf("%s:%d: TOUR_SECTION multiply specified\n", |
|
447 dsa->fname, dsa->seqn); |
|
448 goto fail; |
|
449 } |
|
450 if (check_newline(dsa)) goto fail; |
|
451 tsp->tour = xcalloc(1+n, sizeof(int)); |
|
452 for (k = 1; k <= n; k++) |
|
453 { if (scan_integer(dsa, 1, &node)) goto fail; |
|
454 if (!(1 <= node && node <= n)) |
|
455 { xprintf("%s:%d: invalid node number %d\n", dsa->fname, |
|
456 dsa->seqn, node); |
|
457 goto fail; |
|
458 } |
|
459 tsp->tour[k] = node; |
|
460 } |
|
461 if (scan_integer(dsa, 1, &node)) goto fail; |
|
462 if (node != -1) |
|
463 { xprintf("%s:%d: extra node(s) detected\n", dsa->fname, |
|
464 dsa->seqn); |
|
465 goto fail; |
|
466 } |
|
467 if (check_newline(dsa)) goto fail; |
|
468 } |
|
469 else if (strcmp(dsa->token, "EDGE_WEIGHT_SECTION") == 0) |
|
470 { int n = tsp->dimension, i, j, temp; |
|
471 if (n == 0) |
|
472 { xprintf("%s:%d: DIMENSION entry not specified\n", |
|
473 dsa->fname, dsa->seqn); |
|
474 goto fail; |
|
475 } |
|
476 if (tsp->edge_weight_format == TSP_UNDEF) |
|
477 { xprintf("%s:%d: EDGE_WEIGHT_FORMAT entry not specified\n", |
|
478 dsa->fname, dsa->seqn); |
|
479 goto fail; |
|
480 } |
|
481 if (tsp->edge_weight != NULL) |
|
482 { xprintf("%s:%d: EDGE_WEIGHT_SECTION multiply specified\n", |
|
483 dsa->fname, dsa->seqn); |
|
484 goto fail; |
|
485 } |
|
486 if (check_newline(dsa)) goto fail; |
|
487 tsp->edge_weight = xcalloc(1+n*n, sizeof(int)); |
|
488 switch (tsp->edge_weight_format) |
|
489 { case TSP_FULL_MATRIX: |
|
490 for (i = 1; i <= n; i++) |
|
491 { for (j = 1; j <= n; j++) |
|
492 { if (scan_integer(dsa, 1, &temp)) goto fail; |
|
493 tsp->edge_weight[(i - 1) * n + j] = temp; |
|
494 } |
|
495 } |
|
496 break; |
|
497 case TSP_UPPER_ROW: |
|
498 for (i = 1; i <= n; i++) |
|
499 { tsp->edge_weight[(i - 1) * n + i] = 0; |
|
500 for (j = i + 1; j <= n; j++) |
|
501 { if (scan_integer(dsa, 1, &temp)) goto fail; |
|
502 tsp->edge_weight[(i - 1) * n + j] = temp; |
|
503 tsp->edge_weight[(j - 1) * n + i] = temp; |
|
504 } |
|
505 } |
|
506 break; |
|
507 case TSP_LOWER_DIAG_ROW: |
|
508 for (i = 1; i <= n; i++) |
|
509 { for (j = 1; j <= i; j++) |
|
510 { if (scan_integer(dsa, 1, &temp)) goto fail; |
|
511 tsp->edge_weight[(i - 1) * n + j] = temp; |
|
512 tsp->edge_weight[(j - 1) * n + i] = temp; |
|
513 } |
|
514 } |
|
515 break; |
|
516 default: |
|
517 goto fail; |
|
518 } |
|
519 if (check_newline(dsa)) goto fail; |
|
520 } |
|
521 else if (strcmp(dsa->token, "EOF") == 0) |
|
522 { if (check_newline(dsa)) goto fail; |
|
523 goto done; |
|
524 } |
|
525 else |
|
526 { xprintf("%s:%d: keyword `%s' not recognized\n", dsa->fname, |
|
527 dsa->seqn, dsa->token); |
|
528 goto fail; |
|
529 } |
|
530 goto loop; |
|
531 done: xprintf("tsp_read_data: %d lines were read\n", dsa->seqn-1); |
|
532 fclose(dsa->fp); |
|
533 return tsp; |
|
534 fail: if (tsp != NULL) |
|
535 { if (tsp->name != NULL) xfree(tsp->name); |
|
536 if (tsp->comment != NULL) xfree(tsp->comment); |
|
537 if (tsp->node_x_coord != NULL) xfree(tsp->node_x_coord); |
|
538 if (tsp->node_y_coord != NULL) xfree(tsp->node_y_coord); |
|
539 if (tsp->dply_x_coord != NULL) xfree(tsp->dply_x_coord); |
|
540 if (tsp->dply_y_coord != NULL) xfree(tsp->dply_y_coord); |
|
541 if (tsp->tour != NULL) xfree(tsp->tour); |
|
542 if (tsp->edge_weight != NULL) xfree(tsp->edge_weight); |
|
543 xfree(tsp); |
|
544 } |
|
545 if (dsa->fp != NULL) fclose(dsa->fp); |
|
546 return NULL; |
|
547 } |
|
548 |
|
549 /*---------------------------------------------------------------------- |
|
550 -- tsp_free_data - free TSP instance data. |
|
551 -- |
|
552 -- *Synopsis* |
|
553 -- |
|
554 -- #include "glptsp.h" |
|
555 -- void tsp_free_data(TSP *tsp); |
|
556 -- |
|
557 -- *Description* |
|
558 -- |
|
559 -- The routine tsp_free_data frees all the memory allocated to the TSP |
|
560 -- instance data block, which the parameter tsp points to. */ |
|
561 |
|
562 void tsp_free_data(TSP *tsp) |
|
563 { if (tsp->name != NULL) xfree(tsp->name); |
|
564 if (tsp->comment != NULL) xfree(tsp->comment); |
|
565 if (tsp->node_x_coord != NULL) xfree(tsp->node_x_coord); |
|
566 if (tsp->node_y_coord != NULL) xfree(tsp->node_y_coord); |
|
567 if (tsp->dply_x_coord != NULL) xfree(tsp->dply_x_coord); |
|
568 if (tsp->dply_y_coord != NULL) xfree(tsp->dply_y_coord); |
|
569 if (tsp->tour != NULL) xfree(tsp->tour); |
|
570 if (tsp->edge_weight != NULL) xfree(tsp->edge_weight); |
|
571 xfree(tsp); |
|
572 return; |
|
573 } |
|
574 |
|
575 /*---------------------------------------------------------------------- |
|
576 -- tsp_distance - compute distance between two nodes. |
|
577 -- |
|
578 -- *Synopsis* |
|
579 -- |
|
580 -- #include "glptsp.h" |
|
581 -- int tsp_distance(TSP *tsp, int i, int j); |
|
582 -- |
|
583 -- *Description* |
|
584 -- |
|
585 -- The routine tsp_distance computes the distance between i-th and j-th |
|
586 -- nodes for the TSP instance, which tsp points to. |
|
587 -- |
|
588 -- *Returns* |
|
589 -- |
|
590 -- The routine tsp_distance returns the computed distance. */ |
|
591 |
|
592 #define nint(x) ((int)((x) + 0.5)) |
|
593 |
|
594 static double rad(double x) |
|
595 { /* convert input coordinate to longitude/latitude, in radians */ |
|
596 double pi = 3.141592, deg, min; |
|
597 deg = (int)x; |
|
598 min = x - deg; |
|
599 return pi * (deg + 5.0 * min / 3.0) / 180.0; |
|
600 } |
|
601 |
|
602 int tsp_distance(TSP *tsp, int i, int j) |
|
603 { int n = tsp->dimension, dij; |
|
604 if (!(tsp->type == TSP_TSP || tsp->type == TSP_ATSP)) |
|
605 xfault("tsp_distance: invalid TSP instance\n"); |
|
606 if (!(1 <= i && i <= n && 1 <= j && j <= n)) |
|
607 xfault("tsp_distance: node number out of range\n"); |
|
608 switch (tsp->edge_weight_type) |
|
609 { case TSP_UNDEF: |
|
610 xfault("tsp_distance: edge weight type not specified\n"); |
|
611 case TSP_EXPLICIT: |
|
612 if (tsp->edge_weight == NULL) |
|
613 xfault("tsp_distance: edge weights not specified\n"); |
|
614 dij = tsp->edge_weight[(i - 1) * n + j]; |
|
615 break; |
|
616 case TSP_EUC_2D: |
|
617 if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL) |
|
618 xfault("tsp_distance: node coordinates not specified\n"); |
|
619 { double xd, yd; |
|
620 xd = tsp->node_x_coord[i] - tsp->node_x_coord[j]; |
|
621 yd = tsp->node_y_coord[i] - tsp->node_y_coord[j]; |
|
622 dij = nint(sqrt(xd * xd + yd * yd)); |
|
623 } |
|
624 break; |
|
625 case TSP_CEIL_2D: |
|
626 if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL) |
|
627 xfault("tsp_distance: node coordinates not specified\n"); |
|
628 { double xd, yd; |
|
629 xd = tsp->node_x_coord[i] - tsp->node_x_coord[j]; |
|
630 yd = tsp->node_y_coord[i] - tsp->node_y_coord[j]; |
|
631 dij = (int)ceil(sqrt(xd * xd + yd * yd)); |
|
632 } |
|
633 break; |
|
634 case TSP_GEO: |
|
635 if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL) |
|
636 xfault("tsp_distance: node coordinates not specified\n"); |
|
637 { double rrr = 6378.388; |
|
638 double latitude_i = rad(tsp->node_x_coord[i]); |
|
639 double latitude_j = rad(tsp->node_x_coord[j]); |
|
640 double longitude_i = rad(tsp->node_y_coord[i]); |
|
641 double longitude_j = rad(tsp->node_y_coord[j]); |
|
642 double q1 = cos(longitude_i - longitude_j); |
|
643 double q2 = cos(latitude_i - latitude_j); |
|
644 double q3 = cos(latitude_i + latitude_j); |
|
645 dij = (int)(rrr * acos(0.5 * ((1.0 + q1) * q2 - |
|
646 (1.0 - q1) *q3)) + 1.0); |
|
647 } |
|
648 break; |
|
649 case TSP_ATT: |
|
650 if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL) |
|
651 xfault("tsp_distance: node coordinates not specified\n"); |
|
652 { int tij; |
|
653 double xd, yd, rij; |
|
654 xd = tsp->node_x_coord[i] - tsp->node_x_coord[j]; |
|
655 yd = tsp->node_y_coord[i] - tsp->node_y_coord[j]; |
|
656 rij = sqrt((xd * xd + yd * yd) / 10.0); |
|
657 tij = nint(rij); |
|
658 if (tij < rij) dij = tij + 1; else dij = tij; |
|
659 } |
|
660 break; |
|
661 default: |
|
662 xassert(tsp->edge_weight_type != tsp->edge_weight_type); |
|
663 } |
|
664 return dij; |
|
665 } |
|
666 |
|
667 /* eof */ |