1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/glptsp.c	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,667 @@
     1.4 +/* glptsp.c */
     1.5 +
     1.6 +/***********************************************************************
     1.7 +*  This code is part of GLPK (GNU Linear Programming Kit).
     1.8 +*
     1.9 +*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
    1.10 +*  2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
    1.11 +*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
    1.12 +*  E-mail: <mao@gnu.org>.
    1.13 +*
    1.14 +*  GLPK is free software: you can redistribute it and/or modify it
    1.15 +*  under the terms of the GNU General Public License as published by
    1.16 +*  the Free Software Foundation, either version 3 of the License, or
    1.17 +*  (at your option) any later version.
    1.18 +*
    1.19 +*  GLPK is distributed in the hope that it will be useful, but WITHOUT
    1.20 +*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.21 +*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
    1.22 +*  License for more details.
    1.23 +*
    1.24 +*  You should have received a copy of the GNU General Public License
    1.25 +*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
    1.26 +***********************************************************************/
    1.27 +
    1.28 +#define _GLPSTD_ERRNO
    1.29 +#define _GLPSTD_STDIO
    1.30 +#include "glpenv.h"
    1.31 +#include "glptsp.h"
    1.32 +#define xfault xerror
    1.33 +
    1.34 +/*----------------------------------------------------------------------
    1.35 +-- tsp_read_data - read TSP instance data.
    1.36 +--
    1.37 +-- *Synopsis*
    1.38 +--
    1.39 +-- #include "glptsp.h"
    1.40 +-- TSP *tsp_read_data(char *fname);
    1.41 +--
    1.42 +-- *Description*
    1.43 +--
    1.44 +-- The routine tsp_read_data reads a TSP (or related problem) instance
    1.45 +-- data from the text file, whose name is the character string fname.
    1.46 +--
    1.47 +-- For detailed description of the format recognized by the routine see
    1.48 +-- the report: G.Reinelt, TSPLIB 95.
    1.49 +--
    1.50 +-- *Returns*
    1.51 +--
    1.52 +-- If no error occurred, the routine tsp_read_data returns a pointer to
    1.53 +-- the TSP instance data block, which contains loaded data. In the case
    1.54 +-- of error the routine prints an error message and returns NULL. */
    1.55 +
    1.56 +struct dsa
    1.57 +{     /* dynamic storage area used by the routine tsp_read_data */
    1.58 +      char *fname;
    1.59 +      /* name of the input text file */
    1.60 +      FILE *fp;
    1.61 +      /* stream assigned to the input text file */
    1.62 +      int seqn;
    1.63 +      /* line sequential number */
    1.64 +      int c;
    1.65 +      /* current character */
    1.66 +      char token[255+1];
    1.67 +      /* current token */
    1.68 +};
    1.69 +
    1.70 +static int get_char(struct dsa *dsa)
    1.71 +{     dsa->c = fgetc(dsa->fp);
    1.72 +      if (ferror(dsa->fp))
    1.73 +      {  xprintf("%s:%d: read error - %s\n",
    1.74 +            dsa->fname, dsa->seqn, strerror(errno));
    1.75 +         return 1;
    1.76 +      }
    1.77 +      if (feof(dsa->fp))
    1.78 +         dsa->c = EOF;
    1.79 +      else if (dsa->c == '\n')
    1.80 +         dsa->seqn++;
    1.81 +      else if (isspace(dsa->c))
    1.82 +         dsa->c = ' ';
    1.83 +      else if (iscntrl(dsa->c))
    1.84 +      {  xprintf("%s:%d: invalid control character 0x%02X\n",
    1.85 +            dsa->fname, dsa->seqn, dsa->c);
    1.86 +         return 1;
    1.87 +      }
    1.88 +      return 0;
    1.89 +}
    1.90 +
    1.91 +static int skip_spaces(struct dsa *dsa, int across)
    1.92 +{     while (dsa->c == ' ' || (across && dsa->c == '\n'))
    1.93 +         if (get_char(dsa)) return 1;
    1.94 +      return 0;
    1.95 +}
    1.96 +
    1.97 +static int scan_keyword(struct dsa *dsa)
    1.98 +{     int len = 0;
    1.99 +      if (skip_spaces(dsa, 0)) return 1;
   1.100 +      dsa->token[0] = '\0';
   1.101 +      while (isalnum(dsa->c) || dsa->c == '_')
   1.102 +      {  if (len == 31)
   1.103 +         {  xprintf("%s:%d: keyword `%s...' too long\n", dsa->fname,
   1.104 +               dsa->seqn, dsa->token);
   1.105 +            return 1;
   1.106 +         }
   1.107 +         dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';
   1.108 +         if (get_char(dsa)) return 1;
   1.109 +      }
   1.110 +      if (len == 0)
   1.111 +      {  xprintf("%s:%d: missing keyword\n", dsa->fname, dsa->seqn);
   1.112 +         return 1;
   1.113 +      }
   1.114 +      return 0;
   1.115 +}
   1.116 +
   1.117 +static int check_colon(struct dsa *dsa)
   1.118 +{     if (skip_spaces(dsa, 0)) return 1;
   1.119 +      if (dsa->c != ':')
   1.120 +      {  xprintf("%s:%d: missing colon after `%s'\n", dsa->fname,
   1.121 +            dsa->seqn, dsa->token);
   1.122 +         return 1;
   1.123 +      }
   1.124 +      if (get_char(dsa)) return 1;
   1.125 +      return 0;
   1.126 +}
   1.127 +
   1.128 +static int scan_token(struct dsa *dsa, int across)
   1.129 +{     int len = 0;
   1.130 +      if (skip_spaces(dsa, across)) return 1;
   1.131 +      dsa->token[0] = '\0';
   1.132 +      while (!(dsa->c == EOF || dsa->c == '\n' || dsa->c == ' '))
   1.133 +      {  if (len == 255)
   1.134 +         {  dsa->token[31] = '\0';
   1.135 +            xprintf("%s:%d: token `%s...' too long\n", dsa->fname,
   1.136 +               dsa->seqn, dsa->token);
   1.137 +            return 1;
   1.138 +         }
   1.139 +         dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';
   1.140 +         if (get_char(dsa)) return 1;
   1.141 +      }
   1.142 +      return 0;
   1.143 +}
   1.144 +
   1.145 +static int check_newline(struct dsa *dsa)
   1.146 +{     if (skip_spaces(dsa, 0)) return 1;
   1.147 +      if (!(dsa->c == EOF || dsa->c == '\n'))
   1.148 +      {  xprintf("%s:%d: extra symbols detected\n", dsa->fname,
   1.149 +            dsa->seqn);
   1.150 +         return 1;
   1.151 +      }
   1.152 +      if (get_char(dsa)) return 1;
   1.153 +      return 0;
   1.154 +}
   1.155 +
   1.156 +static int scan_comment(struct dsa *dsa)
   1.157 +{     int len = 0;
   1.158 +      if (skip_spaces(dsa, 0)) return 1;
   1.159 +      dsa->token[0] = '\0';
   1.160 +      while (!(dsa->c == EOF || dsa->c == '\n'))
   1.161 +      {  if (len == 255)
   1.162 +         {  xprintf("%s:%d: comment too long\n", dsa->fname, dsa->seqn)
   1.163 +               ;
   1.164 +            return 1;
   1.165 +         }
   1.166 +         dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';
   1.167 +         if (get_char(dsa)) return 1;
   1.168 +      }
   1.169 +      return 0;
   1.170 +}
   1.171 +
   1.172 +static int scan_integer(struct dsa *dsa, int across, int *val)
   1.173 +{     if (scan_token(dsa, across)) return 1;
   1.174 +      if (strlen(dsa->token) == 0)
   1.175 +      {  xprintf("%s:%d: missing integer\n", dsa->fname, dsa->seqn);
   1.176 +         return 1;
   1.177 +      }
   1.178 +      if (str2int(dsa->token, val))
   1.179 +      {  xprintf("%s:%d: integer `%s' invalid\n", dsa->fname, dsa->seqn
   1.180 +            , dsa->token);
   1.181 +         return 1;
   1.182 +      }
   1.183 +      return 0;
   1.184 +}
   1.185 +
   1.186 +static int scan_number(struct dsa *dsa, int across, double *val)
   1.187 +{     if (scan_token(dsa, across)) return 1;
   1.188 +      if (strlen(dsa->token) == 0)
   1.189 +      {  xprintf("%s:%d: missing number\n", dsa->fname, dsa->seqn);
   1.190 +         return 1;
   1.191 +      }
   1.192 +      if (str2num(dsa->token, val))
   1.193 +      {  xprintf("%s:%d: number `%s' invalid\n", dsa->fname, dsa->seqn,
   1.194 +            dsa->token);
   1.195 +         return 1;
   1.196 +      }
   1.197 +      return 0;
   1.198 +}
   1.199 +
   1.200 +TSP *tsp_read_data(char *fname)
   1.201 +{     struct dsa _dsa, *dsa = &_dsa;
   1.202 +      TSP *tsp = NULL;
   1.203 +      dsa->fname = fname;
   1.204 +      xprintf("tsp_read_data: reading TSP data from `%s'...\n",
   1.205 +         dsa->fname);
   1.206 +      dsa->fp = fopen(dsa->fname, "r");
   1.207 +      if (dsa->fp == NULL)
   1.208 +      {  xprintf("tsp_read_data: unable to open `%s' - %s\n",
   1.209 +            dsa->fname, strerror(errno));
   1.210 +         goto fail;
   1.211 +      }
   1.212 +      tsp = xmalloc(sizeof(TSP));
   1.213 +      tsp->name = NULL;
   1.214 +      tsp->type = TSP_UNDEF;
   1.215 +      tsp->comment = NULL;
   1.216 +      tsp->dimension = 0;
   1.217 +      tsp->edge_weight_type = TSP_UNDEF;
   1.218 +      tsp->edge_weight_format = TSP_UNDEF;
   1.219 +      tsp->display_data_type = TSP_UNDEF;
   1.220 +      tsp->node_x_coord = NULL;
   1.221 +      tsp->node_y_coord = NULL;
   1.222 +      tsp->dply_x_coord = NULL;
   1.223 +      tsp->dply_y_coord = NULL;
   1.224 +      tsp->tour = NULL;
   1.225 +      tsp->edge_weight = NULL;
   1.226 +      dsa->seqn = 1;
   1.227 +      if (get_char(dsa)) goto fail;
   1.228 +loop: if (scan_keyword(dsa)) goto fail;
   1.229 +      if (strcmp(dsa->token, "NAME") == 0)
   1.230 +      {  if (tsp->name != NULL)
   1.231 +         {  xprintf("%s:%d: NAME entry multiply defined\n", dsa->fname,
   1.232 +               dsa->seqn);
   1.233 +            goto fail;
   1.234 +         }
   1.235 +         if (check_colon(dsa)) goto fail;
   1.236 +         if (scan_token(dsa, 0)) goto fail;
   1.237 +         if (strlen(dsa->token) == 0)
   1.238 +         {  xprintf("%s:%d: NAME entry incomplete\n", dsa->fname,
   1.239 +               dsa->seqn);
   1.240 +            goto fail;
   1.241 +         }
   1.242 +         tsp->name = xmalloc(strlen(dsa->token) + 1);
   1.243 +         strcpy(tsp->name, dsa->token);
   1.244 +         xprintf("tsp_read_data: NAME: %s\n", tsp->name);
   1.245 +         if (check_newline(dsa)) goto fail;
   1.246 +      }
   1.247 +      else if (strcmp(dsa->token, "TYPE") == 0)
   1.248 +      {  if (tsp->type != TSP_UNDEF)
   1.249 +         {  xprintf("%s:%d: TYPE entry multiply defined\n", dsa->fname,
   1.250 +               dsa->seqn);
   1.251 +            goto fail;
   1.252 +         }
   1.253 +         if (check_colon(dsa)) goto fail;
   1.254 +         if (scan_keyword(dsa)) goto fail;
   1.255 +         if (strcmp(dsa->token, "TSP") == 0)
   1.256 +            tsp->type = TSP_TSP;
   1.257 +         else if (strcmp(dsa->token, "ATSP") == 0)
   1.258 +            tsp->type = TSP_ATSP;
   1.259 +         else if (strcmp(dsa->token, "TOUR") == 0)
   1.260 +            tsp->type = TSP_TOUR;
   1.261 +         else
   1.262 +         {  xprintf("%s:%d: data type `%s' not recognized\n",
   1.263 +               dsa->fname, dsa->seqn, dsa->token);
   1.264 +            goto fail;
   1.265 +         }
   1.266 +         xprintf("tsp_read_data: TYPE: %s\n", dsa->token);
   1.267 +         if (check_newline(dsa)) goto fail;
   1.268 +      }
   1.269 +      else if (strcmp(dsa->token, "COMMENT") == 0)
   1.270 +      {  if (tsp->comment != NULL)
   1.271 +         {  xprintf("%s:%d: COMMENT entry multiply defined\n",
   1.272 +               dsa->fname, dsa->seqn);
   1.273 +            goto fail;
   1.274 +         }
   1.275 +         if (check_colon(dsa)) goto fail;
   1.276 +         if (scan_comment(dsa)) goto fail;
   1.277 +         tsp->comment = xmalloc(strlen(dsa->token) + 1);
   1.278 +         strcpy(tsp->comment, dsa->token);
   1.279 +         xprintf("tsp_read_data: COMMENT: %s\n", tsp->comment);
   1.280 +         if (check_newline(dsa)) goto fail;
   1.281 +      }
   1.282 +      else if (strcmp(dsa->token, "DIMENSION") == 0)
   1.283 +      {  if (tsp->dimension != 0)
   1.284 +         {  xprintf("%s:%d: DIMENSION entry multiply defined\n",
   1.285 +               dsa->fname, dsa->seqn);
   1.286 +            goto fail;
   1.287 +         }
   1.288 +         if (check_colon(dsa)) goto fail;
   1.289 +         if (scan_integer(dsa, 0, &tsp->dimension)) goto fail;
   1.290 +         if (tsp->dimension < 1)
   1.291 +         {  xprintf("%s:%d: invalid dimension\n", dsa->fname,
   1.292 +               dsa->seqn);
   1.293 +            goto fail;
   1.294 +         }
   1.295 +         xprintf("tsp_read_data: DIMENSION: %d\n", tsp->dimension);
   1.296 +         if (check_newline(dsa)) goto fail;
   1.297 +      }
   1.298 +      else if (strcmp(dsa->token, "EDGE_WEIGHT_TYPE") == 0)
   1.299 +      {  if (tsp->edge_weight_type != TSP_UNDEF)
   1.300 +         {  xprintf("%s:%d: EDGE_WEIGHT_TYPE entry multiply defined\n",
   1.301 +               dsa->fname, dsa->seqn);
   1.302 +            goto fail;
   1.303 +         }
   1.304 +         if (check_colon(dsa)) goto fail;
   1.305 +         if (scan_keyword(dsa)) goto fail;
   1.306 +         if (strcmp(dsa->token, "GEO") == 0)
   1.307 +            tsp->edge_weight_type = TSP_GEO;
   1.308 +         else if (strcmp(dsa->token, "EUC_2D") == 0)
   1.309 +            tsp->edge_weight_type = TSP_EUC_2D;
   1.310 +         else if (strcmp(dsa->token, "ATT") == 0)
   1.311 +            tsp->edge_weight_type = TSP_ATT;
   1.312 +         else if (strcmp(dsa->token, "EXPLICIT") == 0)
   1.313 +            tsp->edge_weight_type = TSP_EXPLICIT;
   1.314 +         else if (strcmp(dsa->token, "CEIL_2D") == 0)
   1.315 +            tsp->edge_weight_type = TSP_CEIL_2D;
   1.316 +         else
   1.317 +         {  xprintf("%s:%d: edge weight type `%s' not recognized\n",
   1.318 +               dsa->fname, dsa->seqn, dsa->token);
   1.319 +            goto fail;
   1.320 +         }
   1.321 +         xprintf("tsp_read_data: EDGE_WEIGHT_TYPE: %s\n", dsa->token);
   1.322 +         if (check_newline(dsa)) goto fail;
   1.323 +      }
   1.324 +      else if (strcmp(dsa->token, "EDGE_WEIGHT_FORMAT") == 0)
   1.325 +      {  if (tsp->edge_weight_format != TSP_UNDEF)
   1.326 +         {  xprintf(
   1.327 +               "%s:%d: EDGE_WEIGHT_FORMAT entry multiply defined\n",
   1.328 +               dsa->fname, dsa->seqn);
   1.329 +            goto fail;
   1.330 +         }
   1.331 +         if (check_colon(dsa)) goto fail;
   1.332 +         if (scan_keyword(dsa)) goto fail;
   1.333 +         if (strcmp(dsa->token, "UPPER_ROW") == 0)
   1.334 +            tsp->edge_weight_format = TSP_UPPER_ROW;
   1.335 +         else if (strcmp(dsa->token, "FULL_MATRIX") == 0)
   1.336 +            tsp->edge_weight_format = TSP_FULL_MATRIX;
   1.337 +         else if (strcmp(dsa->token, "FUNCTION") == 0)
   1.338 +            tsp->edge_weight_format = TSP_FUNCTION;
   1.339 +         else if (strcmp(dsa->token, "LOWER_DIAG_ROW") == 0)
   1.340 +            tsp->edge_weight_format = TSP_LOWER_DIAG_ROW;
   1.341 +         else
   1.342 +         {  xprintf("%s:%d: edge weight format `%s' not recognized\n",
   1.343 +               dsa->fname, dsa->seqn, dsa->token);
   1.344 +            goto fail;
   1.345 +         }
   1.346 +         xprintf("tsp_read_data: EDGE_WEIGHT_FORMAT: %s\n", dsa->token);
   1.347 +         if (check_newline(dsa)) goto fail;
   1.348 +      }
   1.349 +      else if (strcmp(dsa->token, "DISPLAY_DATA_TYPE") == 0)
   1.350 +      {  if (tsp->display_data_type != TSP_UNDEF)
   1.351 +         {  xprintf("%s:%d: DISPLAY_DATA_TYPE entry multiply defined\n",
   1.352 +               dsa->fname, dsa->seqn);
   1.353 +            goto fail;
   1.354 +         }
   1.355 +         if (check_colon(dsa)) goto fail;
   1.356 +         if (scan_keyword(dsa)) goto fail;
   1.357 +         if (strcmp(dsa->token, "COORD_DISPLAY") == 0)
   1.358 +            tsp->display_data_type = TSP_COORD_DISPLAY;
   1.359 +         else if (strcmp(dsa->token, "TWOD_DISPLAY") == 0)
   1.360 +            tsp->display_data_type = TSP_TWOD_DISPLAY;
   1.361 +         else
   1.362 +         {  xprintf("%s:%d: display data type `%s' not recognized\n",
   1.363 +               dsa->fname, dsa->seqn, dsa->token);
   1.364 +            goto fail;
   1.365 +         }
   1.366 +         xprintf("tsp_read_data: DISPLAY_DATA_TYPE: %s\n", dsa->token);
   1.367 +         if (check_newline(dsa)) goto fail;
   1.368 +      }
   1.369 +      else if (strcmp(dsa->token, "NODE_COORD_SECTION") == 0)
   1.370 +      {  int n = tsp->dimension, k, node;
   1.371 +         if (n == 0)
   1.372 +         {  xprintf("%s:%d: DIMENSION entry not specified\n",
   1.373 +               dsa->fname, dsa->seqn);
   1.374 +            goto fail;
   1.375 +         }
   1.376 +         if (tsp->node_x_coord != NULL)
   1.377 +         {  xprintf("%s:%d: NODE_COORD_SECTION multiply specified\n",
   1.378 +               dsa->fname, dsa->seqn);
   1.379 +            goto fail;
   1.380 +         }
   1.381 +         if (check_newline(dsa)) goto fail;
   1.382 +         tsp->node_x_coord = xcalloc(1+n, sizeof(double));
   1.383 +         tsp->node_y_coord = xcalloc(1+n, sizeof(double));
   1.384 +         for (node = 1; node <= n; node++)
   1.385 +            tsp->node_x_coord[node] = tsp->node_y_coord[node] = DBL_MAX;
   1.386 +         for (k = 1; k <= n; k++)
   1.387 +         {  if (scan_integer(dsa, 0, &node)) goto fail;
   1.388 +            if (!(1 <= node && node <= n))
   1.389 +            {  xprintf("%s:%d: invalid node number %d\n", dsa->fname,
   1.390 +                  dsa->seqn, node);
   1.391 +               goto fail;
   1.392 +            }
   1.393 +            if (tsp->node_x_coord[node] != DBL_MAX)
   1.394 +            {  xprintf("%s:%d: node number %d multiply specified\n",
   1.395 +                  dsa->fname, dsa->seqn, node);
   1.396 +               goto fail;
   1.397 +            }
   1.398 +            if (scan_number(dsa, 0, &tsp->node_x_coord[node]))
   1.399 +               goto fail;
   1.400 +            if (scan_number(dsa, 0, &tsp->node_y_coord[node]))
   1.401 +               goto fail;
   1.402 +            if (check_newline(dsa)) goto fail;
   1.403 +         }
   1.404 +      }
   1.405 +      else if (strcmp(dsa->token, "DISPLAY_DATA_SECTION") == 0)
   1.406 +      {  int n = tsp->dimension, k, node;
   1.407 +         if (n == 0)
   1.408 +         {  xprintf("%s:%d: DIMENSION entry not specified\n",
   1.409 +               dsa->fname, dsa->seqn);
   1.410 +            goto fail;
   1.411 +         }
   1.412 +         if (tsp->dply_x_coord != NULL)
   1.413 +         {  xprintf("%s:%d: DISPLAY_DATA_SECTION multiply specified\n",
   1.414 +               dsa->fname, dsa->seqn);
   1.415 +            goto fail;
   1.416 +         }
   1.417 +         if (check_newline(dsa)) goto fail;
   1.418 +         tsp->dply_x_coord = xcalloc(1+n, sizeof(double));
   1.419 +         tsp->dply_y_coord = xcalloc(1+n, sizeof(double));
   1.420 +         for (node = 1; node <= n; node++)
   1.421 +            tsp->dply_x_coord[node] = tsp->dply_y_coord[node] = DBL_MAX;
   1.422 +         for (k = 1; k <= n; k++)
   1.423 +         {  if (scan_integer(dsa, 0, &node)) goto fail;
   1.424 +            if (!(1 <= node && node <= n))
   1.425 +            {  xprintf("%s:%d: invalid node number %d\n", dsa->fname,
   1.426 +                  dsa->seqn, node);
   1.427 +               goto fail;
   1.428 +            }
   1.429 +            if (tsp->dply_x_coord[node] != DBL_MAX)
   1.430 +            {  xprintf("%s:%d: node number %d multiply specified\n",
   1.431 +                  dsa->fname, dsa->seqn, node);
   1.432 +               goto fail;
   1.433 +            }
   1.434 +            if (scan_number(dsa, 0, &tsp->dply_x_coord[node]))
   1.435 +               goto fail;
   1.436 +            if (scan_number(dsa, 0, &tsp->dply_y_coord[node]))
   1.437 +               goto fail;
   1.438 +            if (check_newline(dsa)) goto fail;
   1.439 +         }
   1.440 +      }
   1.441 +      else if (strcmp(dsa->token, "TOUR_SECTION") == 0)
   1.442 +      {  int n = tsp->dimension, k, node;
   1.443 +         if (n == 0)
   1.444 +         {  xprintf("%s:%d: DIMENSION entry not specified\n",
   1.445 +               dsa->fname, dsa->seqn);
   1.446 +            goto fail;
   1.447 +         }
   1.448 +         if (tsp->tour != NULL)
   1.449 +         {  xprintf("%s:%d: TOUR_SECTION multiply specified\n",
   1.450 +               dsa->fname, dsa->seqn);
   1.451 +            goto fail;
   1.452 +         }
   1.453 +         if (check_newline(dsa)) goto fail;
   1.454 +         tsp->tour = xcalloc(1+n, sizeof(int));
   1.455 +         for (k = 1; k <= n; k++)
   1.456 +         {  if (scan_integer(dsa, 1, &node)) goto fail;
   1.457 +            if (!(1 <= node && node <= n))
   1.458 +            {  xprintf("%s:%d: invalid node number %d\n", dsa->fname,
   1.459 +                  dsa->seqn, node);
   1.460 +               goto fail;
   1.461 +            }
   1.462 +            tsp->tour[k] = node;
   1.463 +         }
   1.464 +         if (scan_integer(dsa, 1, &node)) goto fail;
   1.465 +         if (node != -1)
   1.466 +         {  xprintf("%s:%d: extra node(s) detected\n", dsa->fname,
   1.467 +               dsa->seqn);
   1.468 +            goto fail;
   1.469 +         }
   1.470 +         if (check_newline(dsa)) goto fail;
   1.471 +      }
   1.472 +      else if (strcmp(dsa->token, "EDGE_WEIGHT_SECTION") == 0)
   1.473 +      {  int n = tsp->dimension, i, j, temp;
   1.474 +         if (n == 0)
   1.475 +         {  xprintf("%s:%d: DIMENSION entry not specified\n",
   1.476 +               dsa->fname, dsa->seqn);
   1.477 +            goto fail;
   1.478 +         }
   1.479 +         if (tsp->edge_weight_format == TSP_UNDEF)
   1.480 +         {  xprintf("%s:%d: EDGE_WEIGHT_FORMAT entry not specified\n",
   1.481 +               dsa->fname, dsa->seqn);
   1.482 +            goto fail;
   1.483 +         }
   1.484 +         if (tsp->edge_weight != NULL)
   1.485 +         {  xprintf("%s:%d: EDGE_WEIGHT_SECTION multiply specified\n",
   1.486 +               dsa->fname, dsa->seqn);
   1.487 +            goto fail;
   1.488 +         }
   1.489 +         if (check_newline(dsa)) goto fail;
   1.490 +         tsp->edge_weight = xcalloc(1+n*n, sizeof(int));
   1.491 +         switch (tsp->edge_weight_format)
   1.492 +         {  case TSP_FULL_MATRIX:
   1.493 +               for (i = 1; i <= n; i++)
   1.494 +               {  for (j = 1; j <= n; j++)
   1.495 +                  {  if (scan_integer(dsa, 1, &temp)) goto fail;
   1.496 +                     tsp->edge_weight[(i - 1) * n + j] = temp;
   1.497 +                  }
   1.498 +               }
   1.499 +               break;
   1.500 +            case TSP_UPPER_ROW:
   1.501 +               for (i = 1; i <= n; i++)
   1.502 +               {  tsp->edge_weight[(i - 1) * n + i] = 0;
   1.503 +                  for (j = i + 1; j <= n; j++)
   1.504 +                  {  if (scan_integer(dsa, 1, &temp)) goto fail;
   1.505 +                     tsp->edge_weight[(i - 1) * n + j] = temp;
   1.506 +                     tsp->edge_weight[(j - 1) * n + i] = temp;
   1.507 +                  }
   1.508 +               }
   1.509 +               break;
   1.510 +            case TSP_LOWER_DIAG_ROW:
   1.511 +               for (i = 1; i <= n; i++)
   1.512 +               {  for (j = 1; j <= i; j++)
   1.513 +                  {  if (scan_integer(dsa, 1, &temp)) goto fail;
   1.514 +                     tsp->edge_weight[(i - 1) * n + j] = temp;
   1.515 +                     tsp->edge_weight[(j - 1) * n + i] = temp;
   1.516 +                  }
   1.517 +               }
   1.518 +               break;
   1.519 +            default:
   1.520 +               goto fail;
   1.521 +         }
   1.522 +         if (check_newline(dsa)) goto fail;
   1.523 +      }
   1.524 +      else if (strcmp(dsa->token, "EOF") == 0)
   1.525 +      {  if (check_newline(dsa)) goto fail;
   1.526 +         goto done;
   1.527 +      }
   1.528 +      else
   1.529 +      {  xprintf("%s:%d: keyword `%s' not recognized\n", dsa->fname,
   1.530 +            dsa->seqn, dsa->token);
   1.531 +         goto fail;
   1.532 +      }
   1.533 +      goto loop;
   1.534 +done: xprintf("tsp_read_data: %d lines were read\n", dsa->seqn-1);
   1.535 +      fclose(dsa->fp);
   1.536 +      return tsp;
   1.537 +fail: if (tsp != NULL)
   1.538 +      {  if (tsp->name != NULL) xfree(tsp->name);
   1.539 +         if (tsp->comment != NULL) xfree(tsp->comment);
   1.540 +         if (tsp->node_x_coord != NULL) xfree(tsp->node_x_coord);
   1.541 +         if (tsp->node_y_coord != NULL) xfree(tsp->node_y_coord);
   1.542 +         if (tsp->dply_x_coord != NULL) xfree(tsp->dply_x_coord);
   1.543 +         if (tsp->dply_y_coord != NULL) xfree(tsp->dply_y_coord);
   1.544 +         if (tsp->tour != NULL) xfree(tsp->tour);
   1.545 +         if (tsp->edge_weight != NULL) xfree(tsp->edge_weight);
   1.546 +         xfree(tsp);
   1.547 +      }
   1.548 +      if (dsa->fp != NULL) fclose(dsa->fp);
   1.549 +      return NULL;
   1.550 +}
   1.551 +
   1.552 +/*----------------------------------------------------------------------
   1.553 +-- tsp_free_data - free TSP instance data.
   1.554 +--
   1.555 +-- *Synopsis*
   1.556 +--
   1.557 +-- #include "glptsp.h"
   1.558 +-- void tsp_free_data(TSP *tsp);
   1.559 +--
   1.560 +-- *Description*
   1.561 +--
   1.562 +-- The routine tsp_free_data frees all the memory allocated to the TSP
   1.563 +-- instance data block, which the parameter tsp points to. */
   1.564 +
   1.565 +void tsp_free_data(TSP *tsp)
   1.566 +{     if (tsp->name != NULL) xfree(tsp->name);
   1.567 +      if (tsp->comment != NULL) xfree(tsp->comment);
   1.568 +      if (tsp->node_x_coord != NULL) xfree(tsp->node_x_coord);
   1.569 +      if (tsp->node_y_coord != NULL) xfree(tsp->node_y_coord);
   1.570 +      if (tsp->dply_x_coord != NULL) xfree(tsp->dply_x_coord);
   1.571 +      if (tsp->dply_y_coord != NULL) xfree(tsp->dply_y_coord);
   1.572 +      if (tsp->tour != NULL) xfree(tsp->tour);
   1.573 +      if (tsp->edge_weight != NULL) xfree(tsp->edge_weight);
   1.574 +      xfree(tsp);
   1.575 +      return;
   1.576 +}
   1.577 +
   1.578 +/*----------------------------------------------------------------------
   1.579 +-- tsp_distance - compute distance between two nodes.
   1.580 +--
   1.581 +-- *Synopsis*
   1.582 +--
   1.583 +-- #include "glptsp.h"
   1.584 +-- int tsp_distance(TSP *tsp, int i, int j);
   1.585 +--
   1.586 +-- *Description*
   1.587 +--
   1.588 +-- The routine tsp_distance computes the distance between i-th and j-th
   1.589 +-- nodes for the TSP instance, which tsp points to.
   1.590 +--
   1.591 +-- *Returns*
   1.592 +--
   1.593 +-- The routine tsp_distance returns the computed distance. */
   1.594 +
   1.595 +#define nint(x) ((int)((x) + 0.5))
   1.596 +
   1.597 +static double rad(double x)
   1.598 +{     /* convert input coordinate to longitude/latitude, in radians */
   1.599 +      double pi = 3.141592, deg, min;
   1.600 +      deg = (int)x;
   1.601 +      min = x - deg;
   1.602 +      return pi * (deg + 5.0 * min / 3.0) / 180.0;
   1.603 +}
   1.604 +
   1.605 +int tsp_distance(TSP *tsp, int i, int j)
   1.606 +{     int n = tsp->dimension, dij;
   1.607 +      if (!(tsp->type == TSP_TSP || tsp->type == TSP_ATSP))
   1.608 +         xfault("tsp_distance: invalid TSP instance\n");
   1.609 +      if (!(1 <= i && i <= n && 1 <= j && j <= n))
   1.610 +         xfault("tsp_distance: node number out of range\n");
   1.611 +      switch (tsp->edge_weight_type)
   1.612 +      {  case TSP_UNDEF:
   1.613 +            xfault("tsp_distance: edge weight type not specified\n");
   1.614 +         case TSP_EXPLICIT:
   1.615 +            if (tsp->edge_weight == NULL)
   1.616 +               xfault("tsp_distance: edge weights not specified\n");
   1.617 +            dij = tsp->edge_weight[(i - 1) * n + j];
   1.618 +            break;
   1.619 +         case TSP_EUC_2D:
   1.620 +            if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)
   1.621 +               xfault("tsp_distance: node coordinates not specified\n");
   1.622 +            {  double xd, yd;
   1.623 +               xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];
   1.624 +               yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];
   1.625 +               dij = nint(sqrt(xd * xd + yd * yd));
   1.626 +            }
   1.627 +            break;
   1.628 +         case TSP_CEIL_2D:
   1.629 +            if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)
   1.630 +               xfault("tsp_distance: node coordinates not specified\n");
   1.631 +            {  double xd, yd;
   1.632 +               xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];
   1.633 +               yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];
   1.634 +               dij = (int)ceil(sqrt(xd * xd + yd * yd));
   1.635 +            }
   1.636 +            break;
   1.637 +         case TSP_GEO:
   1.638 +            if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)
   1.639 +               xfault("tsp_distance: node coordinates not specified\n");
   1.640 +            {  double rrr = 6378.388;
   1.641 +               double latitude_i = rad(tsp->node_x_coord[i]);
   1.642 +               double latitude_j = rad(tsp->node_x_coord[j]);
   1.643 +               double longitude_i = rad(tsp->node_y_coord[i]);
   1.644 +               double longitude_j = rad(tsp->node_y_coord[j]);
   1.645 +               double q1 = cos(longitude_i - longitude_j);
   1.646 +               double q2 = cos(latitude_i - latitude_j);
   1.647 +               double q3 = cos(latitude_i + latitude_j);
   1.648 +               dij = (int)(rrr * acos(0.5 * ((1.0 + q1) * q2 -
   1.649 +                  (1.0 - q1) *q3)) + 1.0);
   1.650 +            }
   1.651 +            break;
   1.652 +         case TSP_ATT:
   1.653 +            if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)
   1.654 +               xfault("tsp_distance: node coordinates not specified\n");
   1.655 +            {  int tij;
   1.656 +               double xd, yd, rij;
   1.657 +               xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];
   1.658 +               yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];
   1.659 +               rij = sqrt((xd * xd + yd * yd) / 10.0);
   1.660 +               tij = nint(rij);
   1.661 +               if (tij < rij) dij = tij + 1; else dij = tij;
   1.662 +            }
   1.663 +            break;
   1.664 +         default:
   1.665 +            xassert(tsp->edge_weight_type != tsp->edge_weight_type);
   1.666 +      }
   1.667 +      return dij;
   1.668 +}
   1.669 +
   1.670 +/* eof */