lemon-project-template-glpk

comparison deps/glpk/src/glptsp.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:194aaa14a0d1
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, 2011 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 */