COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: glpk-cmake/src/glptsp.c @ 2:4c8956a7bdf4

Last change on this file since 2:4c8956a7bdf4 was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 14 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 23.6 KB
RevLine 
[1]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
53struct 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
67static 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
88static 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
94static 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
114static 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
125static 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
142static 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
153static 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
169static 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
183static 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
197TSP *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;
225loop: 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;
531done: xprintf("tsp_read_data: %d lines were read\n", dsa->seqn-1);
532      fclose(dsa->fp);
533      return tsp;
534fail: 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
562void 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
594static 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
602int 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 */
Note: See TracBrowser for help on using the repository browser.