lemon-project-template-glpk

annotate deps/glpk/src/glptsp.c @ 11:4fc6ad2fb8a6

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