1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glptsp.c Mon Dec 06 13:09:21 2010 +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 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 */