alpar@1: /* glptsp.c */
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@1: *
alpar@1: *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@1: *  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@1: *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@1: *  E-mail: <mao@gnu.org>.
alpar@1: *
alpar@1: *  GLPK is free software: you can redistribute it and/or modify it
alpar@1: *  under the terms of the GNU General Public License as published by
alpar@1: *  the Free Software Foundation, either version 3 of the License, or
alpar@1: *  (at your option) any later version.
alpar@1: *
alpar@1: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@1: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@1: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@1: *  License for more details.
alpar@1: *
alpar@1: *  You should have received a copy of the GNU General Public License
alpar@1: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: #define _GLPSTD_ERRNO
alpar@1: #define _GLPSTD_STDIO
alpar@1: #include "glpenv.h"
alpar@1: #include "glptsp.h"
alpar@1: #define xfault xerror
alpar@1: 
alpar@1: /*----------------------------------------------------------------------
alpar@1: -- tsp_read_data - read TSP instance data.
alpar@1: --
alpar@1: -- *Synopsis*
alpar@1: --
alpar@1: -- #include "glptsp.h"
alpar@1: -- TSP *tsp_read_data(char *fname);
alpar@1: --
alpar@1: -- *Description*
alpar@1: --
alpar@1: -- The routine tsp_read_data reads a TSP (or related problem) instance
alpar@1: -- data from the text file, whose name is the character string fname.
alpar@1: --
alpar@1: -- For detailed description of the format recognized by the routine see
alpar@1: -- the report: G.Reinelt, TSPLIB 95.
alpar@1: --
alpar@1: -- *Returns*
alpar@1: --
alpar@1: -- If no error occurred, the routine tsp_read_data returns a pointer to
alpar@1: -- the TSP instance data block, which contains loaded data. In the case
alpar@1: -- of error the routine prints an error message and returns NULL. */
alpar@1: 
alpar@1: struct dsa
alpar@1: {     /* dynamic storage area used by the routine tsp_read_data */
alpar@1:       char *fname;
alpar@1:       /* name of the input text file */
alpar@1:       FILE *fp;
alpar@1:       /* stream assigned to the input text file */
alpar@1:       int seqn;
alpar@1:       /* line sequential number */
alpar@1:       int c;
alpar@1:       /* current character */
alpar@1:       char token[255+1];
alpar@1:       /* current token */
alpar@1: };
alpar@1: 
alpar@1: static int get_char(struct dsa *dsa)
alpar@1: {     dsa->c = fgetc(dsa->fp);
alpar@1:       if (ferror(dsa->fp))
alpar@1:       {  xprintf("%s:%d: read error - %s\n",
alpar@1:             dsa->fname, dsa->seqn, strerror(errno));
alpar@1:          return 1;
alpar@1:       }
alpar@1:       if (feof(dsa->fp))
alpar@1:          dsa->c = EOF;
alpar@1:       else if (dsa->c == '\n')
alpar@1:          dsa->seqn++;
alpar@1:       else if (isspace(dsa->c))
alpar@1:          dsa->c = ' ';
alpar@1:       else if (iscntrl(dsa->c))
alpar@1:       {  xprintf("%s:%d: invalid control character 0x%02X\n",
alpar@1:             dsa->fname, dsa->seqn, dsa->c);
alpar@1:          return 1;
alpar@1:       }
alpar@1:       return 0;
alpar@1: }
alpar@1: 
alpar@1: static int skip_spaces(struct dsa *dsa, int across)
alpar@1: {     while (dsa->c == ' ' || (across && dsa->c == '\n'))
alpar@1:          if (get_char(dsa)) return 1;
alpar@1:       return 0;
alpar@1: }
alpar@1: 
alpar@1: static int scan_keyword(struct dsa *dsa)
alpar@1: {     int len = 0;
alpar@1:       if (skip_spaces(dsa, 0)) return 1;
alpar@1:       dsa->token[0] = '\0';
alpar@1:       while (isalnum(dsa->c) || dsa->c == '_')
alpar@1:       {  if (len == 31)
alpar@1:          {  xprintf("%s:%d: keyword `%s...' too long\n", dsa->fname,
alpar@1:                dsa->seqn, dsa->token);
alpar@1:             return 1;
alpar@1:          }
alpar@1:          dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';
alpar@1:          if (get_char(dsa)) return 1;
alpar@1:       }
alpar@1:       if (len == 0)
alpar@1:       {  xprintf("%s:%d: missing keyword\n", dsa->fname, dsa->seqn);
alpar@1:          return 1;
alpar@1:       }
alpar@1:       return 0;
alpar@1: }
alpar@1: 
alpar@1: static int check_colon(struct dsa *dsa)
alpar@1: {     if (skip_spaces(dsa, 0)) return 1;
alpar@1:       if (dsa->c != ':')
alpar@1:       {  xprintf("%s:%d: missing colon after `%s'\n", dsa->fname,
alpar@1:             dsa->seqn, dsa->token);
alpar@1:          return 1;
alpar@1:       }
alpar@1:       if (get_char(dsa)) return 1;
alpar@1:       return 0;
alpar@1: }
alpar@1: 
alpar@1: static int scan_token(struct dsa *dsa, int across)
alpar@1: {     int len = 0;
alpar@1:       if (skip_spaces(dsa, across)) return 1;
alpar@1:       dsa->token[0] = '\0';
alpar@1:       while (!(dsa->c == EOF || dsa->c == '\n' || dsa->c == ' '))
alpar@1:       {  if (len == 255)
alpar@1:          {  dsa->token[31] = '\0';
alpar@1:             xprintf("%s:%d: token `%s...' too long\n", dsa->fname,
alpar@1:                dsa->seqn, dsa->token);
alpar@1:             return 1;
alpar@1:          }
alpar@1:          dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';
alpar@1:          if (get_char(dsa)) return 1;
alpar@1:       }
alpar@1:       return 0;
alpar@1: }
alpar@1: 
alpar@1: static int check_newline(struct dsa *dsa)
alpar@1: {     if (skip_spaces(dsa, 0)) return 1;
alpar@1:       if (!(dsa->c == EOF || dsa->c == '\n'))
alpar@1:       {  xprintf("%s:%d: extra symbols detected\n", dsa->fname,
alpar@1:             dsa->seqn);
alpar@1:          return 1;
alpar@1:       }
alpar@1:       if (get_char(dsa)) return 1;
alpar@1:       return 0;
alpar@1: }
alpar@1: 
alpar@1: static int scan_comment(struct dsa *dsa)
alpar@1: {     int len = 0;
alpar@1:       if (skip_spaces(dsa, 0)) return 1;
alpar@1:       dsa->token[0] = '\0';
alpar@1:       while (!(dsa->c == EOF || dsa->c == '\n'))
alpar@1:       {  if (len == 255)
alpar@1:          {  xprintf("%s:%d: comment too long\n", dsa->fname, dsa->seqn)
alpar@1:                ;
alpar@1:             return 1;
alpar@1:          }
alpar@1:          dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';
alpar@1:          if (get_char(dsa)) return 1;
alpar@1:       }
alpar@1:       return 0;
alpar@1: }
alpar@1: 
alpar@1: static int scan_integer(struct dsa *dsa, int across, int *val)
alpar@1: {     if (scan_token(dsa, across)) return 1;
alpar@1:       if (strlen(dsa->token) == 0)
alpar@1:       {  xprintf("%s:%d: missing integer\n", dsa->fname, dsa->seqn);
alpar@1:          return 1;
alpar@1:       }
alpar@1:       if (str2int(dsa->token, val))
alpar@1:       {  xprintf("%s:%d: integer `%s' invalid\n", dsa->fname, dsa->seqn
alpar@1:             , dsa->token);
alpar@1:          return 1;
alpar@1:       }
alpar@1:       return 0;
alpar@1: }
alpar@1: 
alpar@1: static int scan_number(struct dsa *dsa, int across, double *val)
alpar@1: {     if (scan_token(dsa, across)) return 1;
alpar@1:       if (strlen(dsa->token) == 0)
alpar@1:       {  xprintf("%s:%d: missing number\n", dsa->fname, dsa->seqn);
alpar@1:          return 1;
alpar@1:       }
alpar@1:       if (str2num(dsa->token, val))
alpar@1:       {  xprintf("%s:%d: number `%s' invalid\n", dsa->fname, dsa->seqn,
alpar@1:             dsa->token);
alpar@1:          return 1;
alpar@1:       }
alpar@1:       return 0;
alpar@1: }
alpar@1: 
alpar@1: TSP *tsp_read_data(char *fname)
alpar@1: {     struct dsa _dsa, *dsa = &_dsa;
alpar@1:       TSP *tsp = NULL;
alpar@1:       dsa->fname = fname;
alpar@1:       xprintf("tsp_read_data: reading TSP data from `%s'...\n",
alpar@1:          dsa->fname);
alpar@1:       dsa->fp = fopen(dsa->fname, "r");
alpar@1:       if (dsa->fp == NULL)
alpar@1:       {  xprintf("tsp_read_data: unable to open `%s' - %s\n",
alpar@1:             dsa->fname, strerror(errno));
alpar@1:          goto fail;
alpar@1:       }
alpar@1:       tsp = xmalloc(sizeof(TSP));
alpar@1:       tsp->name = NULL;
alpar@1:       tsp->type = TSP_UNDEF;
alpar@1:       tsp->comment = NULL;
alpar@1:       tsp->dimension = 0;
alpar@1:       tsp->edge_weight_type = TSP_UNDEF;
alpar@1:       tsp->edge_weight_format = TSP_UNDEF;
alpar@1:       tsp->display_data_type = TSP_UNDEF;
alpar@1:       tsp->node_x_coord = NULL;
alpar@1:       tsp->node_y_coord = NULL;
alpar@1:       tsp->dply_x_coord = NULL;
alpar@1:       tsp->dply_y_coord = NULL;
alpar@1:       tsp->tour = NULL;
alpar@1:       tsp->edge_weight = NULL;
alpar@1:       dsa->seqn = 1;
alpar@1:       if (get_char(dsa)) goto fail;
alpar@1: loop: if (scan_keyword(dsa)) goto fail;
alpar@1:       if (strcmp(dsa->token, "NAME") == 0)
alpar@1:       {  if (tsp->name != NULL)
alpar@1:          {  xprintf("%s:%d: NAME entry multiply defined\n", dsa->fname,
alpar@1:                dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_colon(dsa)) goto fail;
alpar@1:          if (scan_token(dsa, 0)) goto fail;
alpar@1:          if (strlen(dsa->token) == 0)
alpar@1:          {  xprintf("%s:%d: NAME entry incomplete\n", dsa->fname,
alpar@1:                dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          tsp->name = xmalloc(strlen(dsa->token) + 1);
alpar@1:          strcpy(tsp->name, dsa->token);
alpar@1:          xprintf("tsp_read_data: NAME: %s\n", tsp->name);
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "TYPE") == 0)
alpar@1:       {  if (tsp->type != TSP_UNDEF)
alpar@1:          {  xprintf("%s:%d: TYPE entry multiply defined\n", dsa->fname,
alpar@1:                dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_colon(dsa)) goto fail;
alpar@1:          if (scan_keyword(dsa)) goto fail;
alpar@1:          if (strcmp(dsa->token, "TSP") == 0)
alpar@1:             tsp->type = TSP_TSP;
alpar@1:          else if (strcmp(dsa->token, "ATSP") == 0)
alpar@1:             tsp->type = TSP_ATSP;
alpar@1:          else if (strcmp(dsa->token, "TOUR") == 0)
alpar@1:             tsp->type = TSP_TOUR;
alpar@1:          else
alpar@1:          {  xprintf("%s:%d: data type `%s' not recognized\n",
alpar@1:                dsa->fname, dsa->seqn, dsa->token);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          xprintf("tsp_read_data: TYPE: %s\n", dsa->token);
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "COMMENT") == 0)
alpar@1:       {  if (tsp->comment != NULL)
alpar@1:          {  xprintf("%s:%d: COMMENT entry multiply defined\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_colon(dsa)) goto fail;
alpar@1:          if (scan_comment(dsa)) goto fail;
alpar@1:          tsp->comment = xmalloc(strlen(dsa->token) + 1);
alpar@1:          strcpy(tsp->comment, dsa->token);
alpar@1:          xprintf("tsp_read_data: COMMENT: %s\n", tsp->comment);
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "DIMENSION") == 0)
alpar@1:       {  if (tsp->dimension != 0)
alpar@1:          {  xprintf("%s:%d: DIMENSION entry multiply defined\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_colon(dsa)) goto fail;
alpar@1:          if (scan_integer(dsa, 0, &tsp->dimension)) goto fail;
alpar@1:          if (tsp->dimension < 1)
alpar@1:          {  xprintf("%s:%d: invalid dimension\n", dsa->fname,
alpar@1:                dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          xprintf("tsp_read_data: DIMENSION: %d\n", tsp->dimension);
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "EDGE_WEIGHT_TYPE") == 0)
alpar@1:       {  if (tsp->edge_weight_type != TSP_UNDEF)
alpar@1:          {  xprintf("%s:%d: EDGE_WEIGHT_TYPE entry multiply defined\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_colon(dsa)) goto fail;
alpar@1:          if (scan_keyword(dsa)) goto fail;
alpar@1:          if (strcmp(dsa->token, "GEO") == 0)
alpar@1:             tsp->edge_weight_type = TSP_GEO;
alpar@1:          else if (strcmp(dsa->token, "EUC_2D") == 0)
alpar@1:             tsp->edge_weight_type = TSP_EUC_2D;
alpar@1:          else if (strcmp(dsa->token, "ATT") == 0)
alpar@1:             tsp->edge_weight_type = TSP_ATT;
alpar@1:          else if (strcmp(dsa->token, "EXPLICIT") == 0)
alpar@1:             tsp->edge_weight_type = TSP_EXPLICIT;
alpar@1:          else if (strcmp(dsa->token, "CEIL_2D") == 0)
alpar@1:             tsp->edge_weight_type = TSP_CEIL_2D;
alpar@1:          else
alpar@1:          {  xprintf("%s:%d: edge weight type `%s' not recognized\n",
alpar@1:                dsa->fname, dsa->seqn, dsa->token);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          xprintf("tsp_read_data: EDGE_WEIGHT_TYPE: %s\n", dsa->token);
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "EDGE_WEIGHT_FORMAT") == 0)
alpar@1:       {  if (tsp->edge_weight_format != TSP_UNDEF)
alpar@1:          {  xprintf(
alpar@1:                "%s:%d: EDGE_WEIGHT_FORMAT entry multiply defined\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_colon(dsa)) goto fail;
alpar@1:          if (scan_keyword(dsa)) goto fail;
alpar@1:          if (strcmp(dsa->token, "UPPER_ROW") == 0)
alpar@1:             tsp->edge_weight_format = TSP_UPPER_ROW;
alpar@1:          else if (strcmp(dsa->token, "FULL_MATRIX") == 0)
alpar@1:             tsp->edge_weight_format = TSP_FULL_MATRIX;
alpar@1:          else if (strcmp(dsa->token, "FUNCTION") == 0)
alpar@1:             tsp->edge_weight_format = TSP_FUNCTION;
alpar@1:          else if (strcmp(dsa->token, "LOWER_DIAG_ROW") == 0)
alpar@1:             tsp->edge_weight_format = TSP_LOWER_DIAG_ROW;
alpar@1:          else
alpar@1:          {  xprintf("%s:%d: edge weight format `%s' not recognized\n",
alpar@1:                dsa->fname, dsa->seqn, dsa->token);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          xprintf("tsp_read_data: EDGE_WEIGHT_FORMAT: %s\n", dsa->token);
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "DISPLAY_DATA_TYPE") == 0)
alpar@1:       {  if (tsp->display_data_type != TSP_UNDEF)
alpar@1:          {  xprintf("%s:%d: DISPLAY_DATA_TYPE entry multiply defined\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_colon(dsa)) goto fail;
alpar@1:          if (scan_keyword(dsa)) goto fail;
alpar@1:          if (strcmp(dsa->token, "COORD_DISPLAY") == 0)
alpar@1:             tsp->display_data_type = TSP_COORD_DISPLAY;
alpar@1:          else if (strcmp(dsa->token, "TWOD_DISPLAY") == 0)
alpar@1:             tsp->display_data_type = TSP_TWOD_DISPLAY;
alpar@1:          else
alpar@1:          {  xprintf("%s:%d: display data type `%s' not recognized\n",
alpar@1:                dsa->fname, dsa->seqn, dsa->token);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          xprintf("tsp_read_data: DISPLAY_DATA_TYPE: %s\n", dsa->token);
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "NODE_COORD_SECTION") == 0)
alpar@1:       {  int n = tsp->dimension, k, node;
alpar@1:          if (n == 0)
alpar@1:          {  xprintf("%s:%d: DIMENSION entry not specified\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (tsp->node_x_coord != NULL)
alpar@1:          {  xprintf("%s:%d: NODE_COORD_SECTION multiply specified\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:          tsp->node_x_coord = xcalloc(1+n, sizeof(double));
alpar@1:          tsp->node_y_coord = xcalloc(1+n, sizeof(double));
alpar@1:          for (node = 1; node <= n; node++)
alpar@1:             tsp->node_x_coord[node] = tsp->node_y_coord[node] = DBL_MAX;
alpar@1:          for (k = 1; k <= n; k++)
alpar@1:          {  if (scan_integer(dsa, 0, &node)) goto fail;
alpar@1:             if (!(1 <= node && node <= n))
alpar@1:             {  xprintf("%s:%d: invalid node number %d\n", dsa->fname,
alpar@1:                   dsa->seqn, node);
alpar@1:                goto fail;
alpar@1:             }
alpar@1:             if (tsp->node_x_coord[node] != DBL_MAX)
alpar@1:             {  xprintf("%s:%d: node number %d multiply specified\n",
alpar@1:                   dsa->fname, dsa->seqn, node);
alpar@1:                goto fail;
alpar@1:             }
alpar@1:             if (scan_number(dsa, 0, &tsp->node_x_coord[node]))
alpar@1:                goto fail;
alpar@1:             if (scan_number(dsa, 0, &tsp->node_y_coord[node]))
alpar@1:                goto fail;
alpar@1:             if (check_newline(dsa)) goto fail;
alpar@1:          }
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "DISPLAY_DATA_SECTION") == 0)
alpar@1:       {  int n = tsp->dimension, k, node;
alpar@1:          if (n == 0)
alpar@1:          {  xprintf("%s:%d: DIMENSION entry not specified\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (tsp->dply_x_coord != NULL)
alpar@1:          {  xprintf("%s:%d: DISPLAY_DATA_SECTION multiply specified\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:          tsp->dply_x_coord = xcalloc(1+n, sizeof(double));
alpar@1:          tsp->dply_y_coord = xcalloc(1+n, sizeof(double));
alpar@1:          for (node = 1; node <= n; node++)
alpar@1:             tsp->dply_x_coord[node] = tsp->dply_y_coord[node] = DBL_MAX;
alpar@1:          for (k = 1; k <= n; k++)
alpar@1:          {  if (scan_integer(dsa, 0, &node)) goto fail;
alpar@1:             if (!(1 <= node && node <= n))
alpar@1:             {  xprintf("%s:%d: invalid node number %d\n", dsa->fname,
alpar@1:                   dsa->seqn, node);
alpar@1:                goto fail;
alpar@1:             }
alpar@1:             if (tsp->dply_x_coord[node] != DBL_MAX)
alpar@1:             {  xprintf("%s:%d: node number %d multiply specified\n",
alpar@1:                   dsa->fname, dsa->seqn, node);
alpar@1:                goto fail;
alpar@1:             }
alpar@1:             if (scan_number(dsa, 0, &tsp->dply_x_coord[node]))
alpar@1:                goto fail;
alpar@1:             if (scan_number(dsa, 0, &tsp->dply_y_coord[node]))
alpar@1:                goto fail;
alpar@1:             if (check_newline(dsa)) goto fail;
alpar@1:          }
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "TOUR_SECTION") == 0)
alpar@1:       {  int n = tsp->dimension, k, node;
alpar@1:          if (n == 0)
alpar@1:          {  xprintf("%s:%d: DIMENSION entry not specified\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (tsp->tour != NULL)
alpar@1:          {  xprintf("%s:%d: TOUR_SECTION multiply specified\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:          tsp->tour = xcalloc(1+n, sizeof(int));
alpar@1:          for (k = 1; k <= n; k++)
alpar@1:          {  if (scan_integer(dsa, 1, &node)) goto fail;
alpar@1:             if (!(1 <= node && node <= n))
alpar@1:             {  xprintf("%s:%d: invalid node number %d\n", dsa->fname,
alpar@1:                   dsa->seqn, node);
alpar@1:                goto fail;
alpar@1:             }
alpar@1:             tsp->tour[k] = node;
alpar@1:          }
alpar@1:          if (scan_integer(dsa, 1, &node)) goto fail;
alpar@1:          if (node != -1)
alpar@1:          {  xprintf("%s:%d: extra node(s) detected\n", dsa->fname,
alpar@1:                dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "EDGE_WEIGHT_SECTION") == 0)
alpar@1:       {  int n = tsp->dimension, i, j, temp;
alpar@1:          if (n == 0)
alpar@1:          {  xprintf("%s:%d: DIMENSION entry not specified\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (tsp->edge_weight_format == TSP_UNDEF)
alpar@1:          {  xprintf("%s:%d: EDGE_WEIGHT_FORMAT entry not specified\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (tsp->edge_weight != NULL)
alpar@1:          {  xprintf("%s:%d: EDGE_WEIGHT_SECTION multiply specified\n",
alpar@1:                dsa->fname, dsa->seqn);
alpar@1:             goto fail;
alpar@1:          }
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:          tsp->edge_weight = xcalloc(1+n*n, sizeof(int));
alpar@1:          switch (tsp->edge_weight_format)
alpar@1:          {  case TSP_FULL_MATRIX:
alpar@1:                for (i = 1; i <= n; i++)
alpar@1:                {  for (j = 1; j <= n; j++)
alpar@1:                   {  if (scan_integer(dsa, 1, &temp)) goto fail;
alpar@1:                      tsp->edge_weight[(i - 1) * n + j] = temp;
alpar@1:                   }
alpar@1:                }
alpar@1:                break;
alpar@1:             case TSP_UPPER_ROW:
alpar@1:                for (i = 1; i <= n; i++)
alpar@1:                {  tsp->edge_weight[(i - 1) * n + i] = 0;
alpar@1:                   for (j = i + 1; j <= n; j++)
alpar@1:                   {  if (scan_integer(dsa, 1, &temp)) goto fail;
alpar@1:                      tsp->edge_weight[(i - 1) * n + j] = temp;
alpar@1:                      tsp->edge_weight[(j - 1) * n + i] = temp;
alpar@1:                   }
alpar@1:                }
alpar@1:                break;
alpar@1:             case TSP_LOWER_DIAG_ROW:
alpar@1:                for (i = 1; i <= n; i++)
alpar@1:                {  for (j = 1; j <= i; j++)
alpar@1:                   {  if (scan_integer(dsa, 1, &temp)) goto fail;
alpar@1:                      tsp->edge_weight[(i - 1) * n + j] = temp;
alpar@1:                      tsp->edge_weight[(j - 1) * n + i] = temp;
alpar@1:                   }
alpar@1:                }
alpar@1:                break;
alpar@1:             default:
alpar@1:                goto fail;
alpar@1:          }
alpar@1:          if (check_newline(dsa)) goto fail;
alpar@1:       }
alpar@1:       else if (strcmp(dsa->token, "EOF") == 0)
alpar@1:       {  if (check_newline(dsa)) goto fail;
alpar@1:          goto done;
alpar@1:       }
alpar@1:       else
alpar@1:       {  xprintf("%s:%d: keyword `%s' not recognized\n", dsa->fname,
alpar@1:             dsa->seqn, dsa->token);
alpar@1:          goto fail;
alpar@1:       }
alpar@1:       goto loop;
alpar@1: done: xprintf("tsp_read_data: %d lines were read\n", dsa->seqn-1);
alpar@1:       fclose(dsa->fp);
alpar@1:       return tsp;
alpar@1: fail: if (tsp != NULL)
alpar@1:       {  if (tsp->name != NULL) xfree(tsp->name);
alpar@1:          if (tsp->comment != NULL) xfree(tsp->comment);
alpar@1:          if (tsp->node_x_coord != NULL) xfree(tsp->node_x_coord);
alpar@1:          if (tsp->node_y_coord != NULL) xfree(tsp->node_y_coord);
alpar@1:          if (tsp->dply_x_coord != NULL) xfree(tsp->dply_x_coord);
alpar@1:          if (tsp->dply_y_coord != NULL) xfree(tsp->dply_y_coord);
alpar@1:          if (tsp->tour != NULL) xfree(tsp->tour);
alpar@1:          if (tsp->edge_weight != NULL) xfree(tsp->edge_weight);
alpar@1:          xfree(tsp);
alpar@1:       }
alpar@1:       if (dsa->fp != NULL) fclose(dsa->fp);
alpar@1:       return NULL;
alpar@1: }
alpar@1: 
alpar@1: /*----------------------------------------------------------------------
alpar@1: -- tsp_free_data - free TSP instance data.
alpar@1: --
alpar@1: -- *Synopsis*
alpar@1: --
alpar@1: -- #include "glptsp.h"
alpar@1: -- void tsp_free_data(TSP *tsp);
alpar@1: --
alpar@1: -- *Description*
alpar@1: --
alpar@1: -- The routine tsp_free_data frees all the memory allocated to the TSP
alpar@1: -- instance data block, which the parameter tsp points to. */
alpar@1: 
alpar@1: void tsp_free_data(TSP *tsp)
alpar@1: {     if (tsp->name != NULL) xfree(tsp->name);
alpar@1:       if (tsp->comment != NULL) xfree(tsp->comment);
alpar@1:       if (tsp->node_x_coord != NULL) xfree(tsp->node_x_coord);
alpar@1:       if (tsp->node_y_coord != NULL) xfree(tsp->node_y_coord);
alpar@1:       if (tsp->dply_x_coord != NULL) xfree(tsp->dply_x_coord);
alpar@1:       if (tsp->dply_y_coord != NULL) xfree(tsp->dply_y_coord);
alpar@1:       if (tsp->tour != NULL) xfree(tsp->tour);
alpar@1:       if (tsp->edge_weight != NULL) xfree(tsp->edge_weight);
alpar@1:       xfree(tsp);
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: /*----------------------------------------------------------------------
alpar@1: -- tsp_distance - compute distance between two nodes.
alpar@1: --
alpar@1: -- *Synopsis*
alpar@1: --
alpar@1: -- #include "glptsp.h"
alpar@1: -- int tsp_distance(TSP *tsp, int i, int j);
alpar@1: --
alpar@1: -- *Description*
alpar@1: --
alpar@1: -- The routine tsp_distance computes the distance between i-th and j-th
alpar@1: -- nodes for the TSP instance, which tsp points to.
alpar@1: --
alpar@1: -- *Returns*
alpar@1: --
alpar@1: -- The routine tsp_distance returns the computed distance. */
alpar@1: 
alpar@1: #define nint(x) ((int)((x) + 0.5))
alpar@1: 
alpar@1: static double rad(double x)
alpar@1: {     /* convert input coordinate to longitude/latitude, in radians */
alpar@1:       double pi = 3.141592, deg, min;
alpar@1:       deg = (int)x;
alpar@1:       min = x - deg;
alpar@1:       return pi * (deg + 5.0 * min / 3.0) / 180.0;
alpar@1: }
alpar@1: 
alpar@1: int tsp_distance(TSP *tsp, int i, int j)
alpar@1: {     int n = tsp->dimension, dij;
alpar@1:       if (!(tsp->type == TSP_TSP || tsp->type == TSP_ATSP))
alpar@1:          xfault("tsp_distance: invalid TSP instance\n");
alpar@1:       if (!(1 <= i && i <= n && 1 <= j && j <= n))
alpar@1:          xfault("tsp_distance: node number out of range\n");
alpar@1:       switch (tsp->edge_weight_type)
alpar@1:       {  case TSP_UNDEF:
alpar@1:             xfault("tsp_distance: edge weight type not specified\n");
alpar@1:          case TSP_EXPLICIT:
alpar@1:             if (tsp->edge_weight == NULL)
alpar@1:                xfault("tsp_distance: edge weights not specified\n");
alpar@1:             dij = tsp->edge_weight[(i - 1) * n + j];
alpar@1:             break;
alpar@1:          case TSP_EUC_2D:
alpar@1:             if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)
alpar@1:                xfault("tsp_distance: node coordinates not specified\n");
alpar@1:             {  double xd, yd;
alpar@1:                xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];
alpar@1:                yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];
alpar@1:                dij = nint(sqrt(xd * xd + yd * yd));
alpar@1:             }
alpar@1:             break;
alpar@1:          case TSP_CEIL_2D:
alpar@1:             if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)
alpar@1:                xfault("tsp_distance: node coordinates not specified\n");
alpar@1:             {  double xd, yd;
alpar@1:                xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];
alpar@1:                yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];
alpar@1:                dij = (int)ceil(sqrt(xd * xd + yd * yd));
alpar@1:             }
alpar@1:             break;
alpar@1:          case TSP_GEO:
alpar@1:             if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)
alpar@1:                xfault("tsp_distance: node coordinates not specified\n");
alpar@1:             {  double rrr = 6378.388;
alpar@1:                double latitude_i = rad(tsp->node_x_coord[i]);
alpar@1:                double latitude_j = rad(tsp->node_x_coord[j]);
alpar@1:                double longitude_i = rad(tsp->node_y_coord[i]);
alpar@1:                double longitude_j = rad(tsp->node_y_coord[j]);
alpar@1:                double q1 = cos(longitude_i - longitude_j);
alpar@1:                double q2 = cos(latitude_i - latitude_j);
alpar@1:                double q3 = cos(latitude_i + latitude_j);
alpar@1:                dij = (int)(rrr * acos(0.5 * ((1.0 + q1) * q2 -
alpar@1:                   (1.0 - q1) *q3)) + 1.0);
alpar@1:             }
alpar@1:             break;
alpar@1:          case TSP_ATT:
alpar@1:             if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)
alpar@1:                xfault("tsp_distance: node coordinates not specified\n");
alpar@1:             {  int tij;
alpar@1:                double xd, yd, rij;
alpar@1:                xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];
alpar@1:                yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];
alpar@1:                rij = sqrt((xd * xd + yd * yd) / 10.0);
alpar@1:                tij = nint(rij);
alpar@1:                if (tij < rij) dij = tij + 1; else dij = tij;
alpar@1:             }
alpar@1:             break;
alpar@1:          default:
alpar@1:             xassert(tsp->edge_weight_type != tsp->edge_weight_type);
alpar@1:       }
alpar@1:       return dij;
alpar@1: }
alpar@1: 
alpar@1: /* eof */