glpk-cmake: src/glptsp.c@c445c931472f

     1 /* glptsp.c */

     3 /***********************************************************************

     4 *  This code is part of GLPK (GNU Linear Programming Kit).

5 *

     6 *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,

     7 *  2009, 2010 Andrew Makhorin, Department for Applied Informatics,

     8 *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.

     9 *  E-mail: <mao@gnu.org>.

    10 *

    11 *  GLPK is free software: you can redistribute it and/or modify it

    12 *  under the terms of the GNU General Public License as published by

    13 *  the Free Software Foundation, either version 3 of the License, or

    14 *  (at your option) any later version.

    15 *

    16 *  GLPK is distributed in the hope that it will be useful, but WITHOUT

    17 *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY

    18 *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public

    19 *  License for more details.

    20 *

    21 *  You should have received a copy of the GNU General Public License

    22 *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.

    23 ***********************************************************************/

    25 #define _GLPSTD_ERRNO

    26 #define _GLPSTD_STDIO

    27 #include "glpenv.h"

    28 #include "glptsp.h"

    29 #define xfault xerror

    31 /*----------------------------------------------------------------------

    32 -- tsp_read_data - read TSP instance data.

    33 --

    34 -- *Synopsis*

    35 --

    36 -- #include "glptsp.h"

    37 -- TSP *tsp_read_data(char *fname);

    38 --

    39 -- *Description*

    40 --

    41 -- The routine tsp_read_data reads a TSP (or related problem) instance

    42 -- data from the text file, whose name is the character string fname.

    43 --

    44 -- For detailed description of the format recognized by the routine see

    45 -- the report: G.Reinelt, TSPLIB 95.

    46 --

    47 -- *Returns*

    48 --

    49 -- If no error occurred, the routine tsp_read_data returns a pointer to

    50 -- the TSP instance data block, which contains loaded data. In the case

    51 -- of error the routine prints an error message and returns NULL. */

    53 struct dsa

    54 {     /* dynamic storage area used by the routine tsp_read_data */

    55       char *fname;

    56       /* name of the input text file */

    57       FILE *fp;

    58       /* stream assigned to the input text file */

    59       int seqn;

    60       /* line sequential number */

    61       int c;

    62       /* current character */

    63       char token[255+1];

    64       /* current token */

    65 };

    67 static int get_char(struct dsa *dsa)

    68 {     dsa->c = fgetc(dsa->fp);

    69       if (ferror(dsa->fp))

    70       {  xprintf("%s:%d: read error - %s\n",

    71             dsa->fname, dsa->seqn, strerror(errno));

    72          return 1;

    73       }

    74       if (feof(dsa->fp))

    75          dsa->c = EOF;

    76       else if (dsa->c == '\n')

    77          dsa->seqn++;

    78       else if (isspace(dsa->c))

    79          dsa->c = ' ';

    80       else if (iscntrl(dsa->c))

    81       {  xprintf("%s:%d: invalid control character 0x%02X\n",

    82             dsa->fname, dsa->seqn, dsa->c);

    83          return 1;

    84       }

    85       return 0;

    86 }

    88 static int skip_spaces(struct dsa *dsa, int across)

    89 {     while (dsa->c == ' ' || (across && dsa->c == '\n'))

    90          if (get_char(dsa)) return 1;

    91       return 0;

    92 }

    94 static int scan_keyword(struct dsa *dsa)

    95 {     int len = 0;

    96       if (skip_spaces(dsa, 0)) return 1;

    97       dsa->token[0] = '\0';

    98       while (isalnum(dsa->c) || dsa->c == '_')

    99       {  if (len == 31)

   100          {  xprintf("%s:%d: keyword `%s...' too long\n", dsa->fname,

   101                dsa->seqn, dsa->token);

   102             return 1;

   103          }

   104          dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';

   105          if (get_char(dsa)) return 1;

   106       }

   107       if (len == 0)

   108       {  xprintf("%s:%d: missing keyword\n", dsa->fname, dsa->seqn);

   109          return 1;

   110       }

   111       return 0;

   112 }

   114 static int check_colon(struct dsa *dsa)

   115 {     if (skip_spaces(dsa, 0)) return 1;

   116       if (dsa->c != ':')

   117       {  xprintf("%s:%d: missing colon after `%s'\n", dsa->fname,

   118             dsa->seqn, dsa->token);

   119          return 1;

   120       }

   121       if (get_char(dsa)) return 1;

   122       return 0;

   123 }

   125 static int scan_token(struct dsa *dsa, int across)

   126 {     int len = 0;

   127       if (skip_spaces(dsa, across)) return 1;

   128       dsa->token[0] = '\0';

   129       while (!(dsa->c == EOF || dsa->c == '\n' || dsa->c == ' '))

   130       {  if (len == 255)

   131          {  dsa->token[31] = '\0';

   132             xprintf("%s:%d: token `%s...' too long\n", dsa->fname,

   133                dsa->seqn, dsa->token);

   134             return 1;

   135          }

   136          dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';

   137          if (get_char(dsa)) return 1;

   138       }

   139       return 0;

   140 }

   142 static int check_newline(struct dsa *dsa)

   143 {     if (skip_spaces(dsa, 0)) return 1;

   144       if (!(dsa->c == EOF || dsa->c == '\n'))

   145       {  xprintf("%s:%d: extra symbols detected\n", dsa->fname,

   146             dsa->seqn);

   147          return 1;

   148       }

   149       if (get_char(dsa)) return 1;

   150       return 0;

   151 }

   153 static int scan_comment(struct dsa *dsa)

   154 {     int len = 0;

   155       if (skip_spaces(dsa, 0)) return 1;

   156       dsa->token[0] = '\0';

   157       while (!(dsa->c == EOF || dsa->c == '\n'))

   158       {  if (len == 255)

   159          {  xprintf("%s:%d: comment too long\n", dsa->fname, dsa->seqn)

   160                ;

   161             return 1;

   162          }

   163          dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';

   164          if (get_char(dsa)) return 1;

   165       }

   166       return 0;

   167 }

   169 static int scan_integer(struct dsa *dsa, int across, int *val)

   170 {     if (scan_token(dsa, across)) return 1;

   171       if (strlen(dsa->token) == 0)

   172       {  xprintf("%s:%d: missing integer\n", dsa->fname, dsa->seqn);

   173          return 1;

   174       }

   175       if (str2int(dsa->token, val))

   176       {  xprintf("%s:%d: integer `%s' invalid\n", dsa->fname, dsa->seqn

   177             , dsa->token);

   178          return 1;

   179       }

   180       return 0;

   181 }

   183 static int scan_number(struct dsa *dsa, int across, double *val)

   184 {     if (scan_token(dsa, across)) return 1;

   185       if (strlen(dsa->token) == 0)

   186       {  xprintf("%s:%d: missing number\n", dsa->fname, dsa->seqn);

   187          return 1;

   188       }

   189       if (str2num(dsa->token, val))

   190       {  xprintf("%s:%d: number `%s' invalid\n", dsa->fname, dsa->seqn,

   191             dsa->token);

   192          return 1;

   193       }

   194       return 0;

   195 }

   197 TSP *tsp_read_data(char *fname)

   198 {     struct dsa _dsa, *dsa = &_dsa;

   199       TSP *tsp = NULL;

   200       dsa->fname = fname;

   201       xprintf("tsp_read_data: reading TSP data from `%s'...\n",

   202          dsa->fname);

   203       dsa->fp = fopen(dsa->fname, "r");

   204       if (dsa->fp == NULL)

   205       {  xprintf("tsp_read_data: unable to open `%s' - %s\n",

   206             dsa->fname, strerror(errno));

   207          goto fail;

   208       }

   209       tsp = xmalloc(sizeof(TSP));

   210       tsp->name = NULL;

   211       tsp->type = TSP_UNDEF;

   212       tsp->comment = NULL;

   213       tsp->dimension = 0;

   214       tsp->edge_weight_type = TSP_UNDEF;

   215       tsp->edge_weight_format = TSP_UNDEF;

   216       tsp->display_data_type = TSP_UNDEF;

   217       tsp->node_x_coord = NULL;

   218       tsp->node_y_coord = NULL;

   219       tsp->dply_x_coord = NULL;

   220       tsp->dply_y_coord = NULL;

   221       tsp->tour = NULL;

   222       tsp->edge_weight = NULL;

   223       dsa->seqn = 1;

   224       if (get_char(dsa)) goto fail;

   225 loop: if (scan_keyword(dsa)) goto fail;

   226       if (strcmp(dsa->token, "NAME") == 0)

   227       {  if (tsp->name != NULL)

   228          {  xprintf("%s:%d: NAME entry multiply defined\n", dsa->fname,

   229                dsa->seqn);

   230             goto fail;

   231          }

   232          if (check_colon(dsa)) goto fail;

   233          if (scan_token(dsa, 0)) goto fail;

   234          if (strlen(dsa->token) == 0)

   235          {  xprintf("%s:%d: NAME entry incomplete\n", dsa->fname,

   236                dsa->seqn);

   237             goto fail;

   238          }

   239          tsp->name = xmalloc(strlen(dsa->token) + 1);

   240          strcpy(tsp->name, dsa->token);

   241          xprintf("tsp_read_data: NAME: %s\n", tsp->name);

   242          if (check_newline(dsa)) goto fail;

   243       }

   244       else if (strcmp(dsa->token, "TYPE") == 0)

   245       {  if (tsp->type != TSP_UNDEF)

   246          {  xprintf("%s:%d: TYPE entry multiply defined\n", dsa->fname,

   247                dsa->seqn);

   248             goto fail;

   249          }

   250          if (check_colon(dsa)) goto fail;

   251          if (scan_keyword(dsa)) goto fail;

   252          if (strcmp(dsa->token, "TSP") == 0)

   253             tsp->type = TSP_TSP;

   254          else if (strcmp(dsa->token, "ATSP") == 0)

   255             tsp->type = TSP_ATSP;

   256          else if (strcmp(dsa->token, "TOUR") == 0)

   257             tsp->type = TSP_TOUR;

   258          else

   259          {  xprintf("%s:%d: data type `%s' not recognized\n",

   260                dsa->fname, dsa->seqn, dsa->token);

   261             goto fail;

   262          }

   263          xprintf("tsp_read_data: TYPE: %s\n", dsa->token);

   264          if (check_newline(dsa)) goto fail;

   265       }

   266       else if (strcmp(dsa->token, "COMMENT") == 0)

   267       {  if (tsp->comment != NULL)

   268          {  xprintf("%s:%d: COMMENT entry multiply defined\n",

   269                dsa->fname, dsa->seqn);

   270             goto fail;

   271          }

   272          if (check_colon(dsa)) goto fail;

   273          if (scan_comment(dsa)) goto fail;

   274          tsp->comment = xmalloc(strlen(dsa->token) + 1);

   275          strcpy(tsp->comment, dsa->token);

   276          xprintf("tsp_read_data: COMMENT: %s\n", tsp->comment);

   277          if (check_newline(dsa)) goto fail;

   278       }

   279       else if (strcmp(dsa->token, "DIMENSION") == 0)

   280       {  if (tsp->dimension != 0)

   281          {  xprintf("%s:%d: DIMENSION entry multiply defined\n",

   282                dsa->fname, dsa->seqn);

   283             goto fail;

   284          }

   285          if (check_colon(dsa)) goto fail;

   286          if (scan_integer(dsa, 0, &tsp->dimension)) goto fail;

   287          if (tsp->dimension < 1)

   288          {  xprintf("%s:%d: invalid dimension\n", dsa->fname,

   289                dsa->seqn);

   290             goto fail;

   291          }

   292          xprintf("tsp_read_data: DIMENSION: %d\n", tsp->dimension);

   293          if (check_newline(dsa)) goto fail;

   294       }

   295       else if (strcmp(dsa->token, "EDGE_WEIGHT_TYPE") == 0)

   296       {  if (tsp->edge_weight_type != TSP_UNDEF)

   297          {  xprintf("%s:%d: EDGE_WEIGHT_TYPE entry multiply defined\n",

   298                dsa->fname, dsa->seqn);

   299             goto fail;

   300          }

   301          if (check_colon(dsa)) goto fail;

   302          if (scan_keyword(dsa)) goto fail;

   303          if (strcmp(dsa->token, "GEO") == 0)

   304             tsp->edge_weight_type = TSP_GEO;

   305          else if (strcmp(dsa->token, "EUC_2D") == 0)

   306             tsp->edge_weight_type = TSP_EUC_2D;

   307          else if (strcmp(dsa->token, "ATT") == 0)

   308             tsp->edge_weight_type = TSP_ATT;

   309          else if (strcmp(dsa->token, "EXPLICIT") == 0)

   310             tsp->edge_weight_type = TSP_EXPLICIT;

   311          else if (strcmp(dsa->token, "CEIL_2D") == 0)

   312             tsp->edge_weight_type = TSP_CEIL_2D;

   313          else

   314          {  xprintf("%s:%d: edge weight type `%s' not recognized\n",

   315                dsa->fname, dsa->seqn, dsa->token);

   316             goto fail;

   317          }

   318          xprintf("tsp_read_data: EDGE_WEIGHT_TYPE: %s\n", dsa->token);

   319          if (check_newline(dsa)) goto fail;

   320       }

   321       else if (strcmp(dsa->token, "EDGE_WEIGHT_FORMAT") == 0)

   322       {  if (tsp->edge_weight_format != TSP_UNDEF)

   323          {  xprintf(

   324                "%s:%d: EDGE_WEIGHT_FORMAT entry multiply defined\n",

   325                dsa->fname, dsa->seqn);

   326             goto fail;

   327          }

   328          if (check_colon(dsa)) goto fail;

   329          if (scan_keyword(dsa)) goto fail;

   330          if (strcmp(dsa->token, "UPPER_ROW") == 0)

   331             tsp->edge_weight_format = TSP_UPPER_ROW;

   332          else if (strcmp(dsa->token, "FULL_MATRIX") == 0)

   333             tsp->edge_weight_format = TSP_FULL_MATRIX;

   334          else if (strcmp(dsa->token, "FUNCTION") == 0)

   335             tsp->edge_weight_format = TSP_FUNCTION;

   336          else if (strcmp(dsa->token, "LOWER_DIAG_ROW") == 0)

   337             tsp->edge_weight_format = TSP_LOWER_DIAG_ROW;

   338          else

   339          {  xprintf("%s:%d: edge weight format `%s' not recognized\n",

   340                dsa->fname, dsa->seqn, dsa->token);

   341             goto fail;

   342          }

   343          xprintf("tsp_read_data: EDGE_WEIGHT_FORMAT: %s\n", dsa->token);

   344          if (check_newline(dsa)) goto fail;

   345       }

   346       else if (strcmp(dsa->token, "DISPLAY_DATA_TYPE") == 0)

   347       {  if (tsp->display_data_type != TSP_UNDEF)

   348          {  xprintf("%s:%d: DISPLAY_DATA_TYPE entry multiply defined\n",

   349                dsa->fname, dsa->seqn);

   350             goto fail;

   351          }

   352          if (check_colon(dsa)) goto fail;

   353          if (scan_keyword(dsa)) goto fail;

   354          if (strcmp(dsa->token, "COORD_DISPLAY") == 0)

   355             tsp->display_data_type = TSP_COORD_DISPLAY;

   356          else if (strcmp(dsa->token, "TWOD_DISPLAY") == 0)

   357             tsp->display_data_type = TSP_TWOD_DISPLAY;

   358          else

   359          {  xprintf("%s:%d: display data type `%s' not recognized\n",

   360                dsa->fname, dsa->seqn, dsa->token);

   361             goto fail;

   362          }

   363          xprintf("tsp_read_data: DISPLAY_DATA_TYPE: %s\n", dsa->token);

   364          if (check_newline(dsa)) goto fail;

   365       }

   366       else if (strcmp(dsa->token, "NODE_COORD_SECTION") == 0)

   367       {  int n = tsp->dimension, k, node;

   368          if (n == 0)

   369          {  xprintf("%s:%d: DIMENSION entry not specified\n",

   370                dsa->fname, dsa->seqn);

   371             goto fail;

   372          }

   373          if (tsp->node_x_coord != NULL)

   374          {  xprintf("%s:%d: NODE_COORD_SECTION multiply specified\n",

   375                dsa->fname, dsa->seqn);

   376             goto fail;

   377          }

   378          if (check_newline(dsa)) goto fail;

   379          tsp->node_x_coord = xcalloc(1+n, sizeof(double));

   380          tsp->node_y_coord = xcalloc(1+n, sizeof(double));

   381          for (node = 1; node <= n; node++)

   382             tsp->node_x_coord[node] = tsp->node_y_coord[node] = DBL_MAX;

   383          for (k = 1; k <= n; k++)

   384          {  if (scan_integer(dsa, 0, &node)) goto fail;

   385             if (!(1 <= node && node <= n))

   386             {  xprintf("%s:%d: invalid node number %d\n", dsa->fname,

   387                   dsa->seqn, node);

   388                goto fail;

   389             }

   390             if (tsp->node_x_coord[node] != DBL_MAX)

   391             {  xprintf("%s:%d: node number %d multiply specified\n",

   392                   dsa->fname, dsa->seqn, node);

   393                goto fail;

   394             }

   395             if (scan_number(dsa, 0, &tsp->node_x_coord[node]))

   396                goto fail;

   397             if (scan_number(dsa, 0, &tsp->node_y_coord[node]))

   398                goto fail;

   399             if (check_newline(dsa)) goto fail;

   400          }

   401       }

   402       else if (strcmp(dsa->token, "DISPLAY_DATA_SECTION") == 0)

   403       {  int n = tsp->dimension, k, node;

   404          if (n == 0)

   405          {  xprintf("%s:%d: DIMENSION entry not specified\n",

   406                dsa->fname, dsa->seqn);

   407             goto fail;

   408          }

   409          if (tsp->dply_x_coord != NULL)

   410          {  xprintf("%s:%d: DISPLAY_DATA_SECTION multiply specified\n",

   411                dsa->fname, dsa->seqn);

   412             goto fail;

   413          }

   414          if (check_newline(dsa)) goto fail;

   415          tsp->dply_x_coord = xcalloc(1+n, sizeof(double));

   416          tsp->dply_y_coord = xcalloc(1+n, sizeof(double));

   417          for (node = 1; node <= n; node++)

   418             tsp->dply_x_coord[node] = tsp->dply_y_coord[node] = DBL_MAX;

   419          for (k = 1; k <= n; k++)

   420          {  if (scan_integer(dsa, 0, &node)) goto fail;

   421             if (!(1 <= node && node <= n))

   422             {  xprintf("%s:%d: invalid node number %d\n", dsa->fname,

   423                   dsa->seqn, node);

   424                goto fail;

   425             }

   426             if (tsp->dply_x_coord[node] != DBL_MAX)

   427             {  xprintf("%s:%d: node number %d multiply specified\n",

   428                   dsa->fname, dsa->seqn, node);

   429                goto fail;

   430             }

   431             if (scan_number(dsa, 0, &tsp->dply_x_coord[node]))

   432                goto fail;

   433             if (scan_number(dsa, 0, &tsp->dply_y_coord[node]))

   434                goto fail;

   435             if (check_newline(dsa)) goto fail;

   436          }

   437       }

   438       else if (strcmp(dsa->token, "TOUR_SECTION") == 0)

   439       {  int n = tsp->dimension, k, node;

   440          if (n == 0)

   441          {  xprintf("%s:%d: DIMENSION entry not specified\n",

   442                dsa->fname, dsa->seqn);

   443             goto fail;

   444          }

   445          if (tsp->tour != NULL)

   446          {  xprintf("%s:%d: TOUR_SECTION multiply specified\n",

   447                dsa->fname, dsa->seqn);

   448             goto fail;

   449          }

   450          if (check_newline(dsa)) goto fail;

   451          tsp->tour = xcalloc(1+n, sizeof(int));

   452          for (k = 1; k <= n; k++)

   453          {  if (scan_integer(dsa, 1, &node)) goto fail;

   454             if (!(1 <= node && node <= n))

   455             {  xprintf("%s:%d: invalid node number %d\n", dsa->fname,

   456                   dsa->seqn, node);

   457                goto fail;

   458             }

   459             tsp->tour[k] = node;

   460          }

   461          if (scan_integer(dsa, 1, &node)) goto fail;

   462          if (node != -1)

   463          {  xprintf("%s:%d: extra node(s) detected\n", dsa->fname,

   464                dsa->seqn);

   465             goto fail;

   466          }

   467          if (check_newline(dsa)) goto fail;

   468       }

   469       else if (strcmp(dsa->token, "EDGE_WEIGHT_SECTION") == 0)

   470       {  int n = tsp->dimension, i, j, temp;

   471          if (n == 0)

   472          {  xprintf("%s:%d: DIMENSION entry not specified\n",

   473                dsa->fname, dsa->seqn);

   474             goto fail;

   475          }

   476          if (tsp->edge_weight_format == TSP_UNDEF)

   477          {  xprintf("%s:%d: EDGE_WEIGHT_FORMAT entry not specified\n",

   478                dsa->fname, dsa->seqn);

   479             goto fail;

   480          }

   481          if (tsp->edge_weight != NULL)

   482          {  xprintf("%s:%d: EDGE_WEIGHT_SECTION multiply specified\n",

   483                dsa->fname, dsa->seqn);

   484             goto fail;

   485          }

   486          if (check_newline(dsa)) goto fail;

   487          tsp->edge_weight = xcalloc(1+n*n, sizeof(int));

   488          switch (tsp->edge_weight_format)

   489          {  case TSP_FULL_MATRIX:

   490                for (i = 1; i <= n; i++)

   491                {  for (j = 1; j <= n; j++)

   492                   {  if (scan_integer(dsa, 1, &temp)) goto fail;

   493                      tsp->edge_weight[(i - 1) * n + j] = temp;

   494                   }

   495                }

   496                break;

   497             case TSP_UPPER_ROW:

   498                for (i = 1; i <= n; i++)

   499                {  tsp->edge_weight[(i - 1) * n + i] = 0;

   500                   for (j = i + 1; j <= n; j++)

   501                   {  if (scan_integer(dsa, 1, &temp)) goto fail;

   502                      tsp->edge_weight[(i - 1) * n + j] = temp;

   503                      tsp->edge_weight[(j - 1) * n + i] = temp;

   504                   }

   505                }

   506                break;

   507             case TSP_LOWER_DIAG_ROW:

   508                for (i = 1; i <= n; i++)

   509                {  for (j = 1; j <= i; j++)

   510                   {  if (scan_integer(dsa, 1, &temp)) goto fail;

   511                      tsp->edge_weight[(i - 1) * n + j] = temp;

   512                      tsp->edge_weight[(j - 1) * n + i] = temp;

   513                   }

   514                }

   515                break;

   516             default:

   517                goto fail;

   518          }

   519          if (check_newline(dsa)) goto fail;

   520       }

   521       else if (strcmp(dsa->token, "EOF") == 0)

   522       {  if (check_newline(dsa)) goto fail;

   523          goto done;

   524       }

   525       else

   526       {  xprintf("%s:%d: keyword `%s' not recognized\n", dsa->fname,

   527             dsa->seqn, dsa->token);

   528          goto fail;

   529       }

   530       goto loop;

   531 done: xprintf("tsp_read_data: %d lines were read\n", dsa->seqn-1);

   532       fclose(dsa->fp);

   533       return tsp;

   534 fail: if (tsp != NULL)

   535       {  if (tsp->name != NULL) xfree(tsp->name);

   536          if (tsp->comment != NULL) xfree(tsp->comment);

   537          if (tsp->node_x_coord != NULL) xfree(tsp->node_x_coord);

   538          if (tsp->node_y_coord != NULL) xfree(tsp->node_y_coord);

   539          if (tsp->dply_x_coord != NULL) xfree(tsp->dply_x_coord);

   540          if (tsp->dply_y_coord != NULL) xfree(tsp->dply_y_coord);

   541          if (tsp->tour != NULL) xfree(tsp->tour);

   542          if (tsp->edge_weight != NULL) xfree(tsp->edge_weight);

   543          xfree(tsp);

   544       }

   545       if (dsa->fp != NULL) fclose(dsa->fp);

   546       return NULL;

   547 }

   549 /*----------------------------------------------------------------------

   550 -- tsp_free_data - free TSP instance data.

   551 --

   552 -- *Synopsis*

   553 --

   554 -- #include "glptsp.h"

   555 -- void tsp_free_data(TSP *tsp);

   556 --

   557 -- *Description*

   558 --

   559 -- The routine tsp_free_data frees all the memory allocated to the TSP

   560 -- instance data block, which the parameter tsp points to. */

   562 void tsp_free_data(TSP *tsp)

   563 {     if (tsp->name != NULL) xfree(tsp->name);

   564       if (tsp->comment != NULL) xfree(tsp->comment);

   565       if (tsp->node_x_coord != NULL) xfree(tsp->node_x_coord);

   566       if (tsp->node_y_coord != NULL) xfree(tsp->node_y_coord);

   567       if (tsp->dply_x_coord != NULL) xfree(tsp->dply_x_coord);

   568       if (tsp->dply_y_coord != NULL) xfree(tsp->dply_y_coord);

   569       if (tsp->tour != NULL) xfree(tsp->tour);

   570       if (tsp->edge_weight != NULL) xfree(tsp->edge_weight);

   571       xfree(tsp);

   572       return;

   573 }

   575 /*----------------------------------------------------------------------

   576 -- tsp_distance - compute distance between two nodes.

   577 --

   578 -- *Synopsis*

   579 --

   580 -- #include "glptsp.h"

   581 -- int tsp_distance(TSP *tsp, int i, int j);

   582 --

   583 -- *Description*

   584 --

   585 -- The routine tsp_distance computes the distance between i-th and j-th

   586 -- nodes for the TSP instance, which tsp points to.

   587 --

   588 -- *Returns*

   589 --

   590 -- The routine tsp_distance returns the computed distance. */

   592 #define nint(x) ((int)((x) + 0.5))

   594 static double rad(double x)

   595 {     /* convert input coordinate to longitude/latitude, in radians */

   596       double pi = 3.141592, deg, min;

   597       deg = (int)x;

   598       min = x - deg;

   599       return pi * (deg + 5.0 * min / 3.0) / 180.0;

   600 }

   602 int tsp_distance(TSP *tsp, int i, int j)

   603 {     int n = tsp->dimension, dij;

   604       if (!(tsp->type == TSP_TSP || tsp->type == TSP_ATSP))

   605          xfault("tsp_distance: invalid TSP instance\n");

   606       if (!(1 <= i && i <= n && 1 <= j && j <= n))

   607          xfault("tsp_distance: node number out of range\n");

   608       switch (tsp->edge_weight_type)

   609       {  case TSP_UNDEF:

   610             xfault("tsp_distance: edge weight type not specified\n");

   611          case TSP_EXPLICIT:

   612             if (tsp->edge_weight == NULL)

   613                xfault("tsp_distance: edge weights not specified\n");

   614             dij = tsp->edge_weight[(i - 1) * n + j];

   615             break;

   616          case TSP_EUC_2D:

   617             if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)

   618                xfault("tsp_distance: node coordinates not specified\n");

   619             {  double xd, yd;

   620                xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];

   621                yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];

   622                dij = nint(sqrt(xd * xd + yd * yd));

   623             }

   624             break;

   625          case TSP_CEIL_2D:

   626             if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)

   627                xfault("tsp_distance: node coordinates not specified\n");

   628             {  double xd, yd;

   629                xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];

   630                yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];

   631                dij = (int)ceil(sqrt(xd * xd + yd * yd));

   632             }

   633             break;

   634          case TSP_GEO:

   635             if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)

   636                xfault("tsp_distance: node coordinates not specified\n");

   637             {  double rrr = 6378.388;

   638                double latitude_i = rad(tsp->node_x_coord[i]);

   639                double latitude_j = rad(tsp->node_x_coord[j]);

   640                double longitude_i = rad(tsp->node_y_coord[i]);

   641                double longitude_j = rad(tsp->node_y_coord[j]);

   642                double q1 = cos(longitude_i - longitude_j);

   643                double q2 = cos(latitude_i - latitude_j);

   644                double q3 = cos(latitude_i + latitude_j);

   645                dij = (int)(rrr * acos(0.5 * ((1.0 + q1) * q2 -

   646                   (1.0 - q1) *q3)) + 1.0);

   647             }

   648             break;

   649          case TSP_ATT:

   650             if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)

   651                xfault("tsp_distance: node coordinates not specified\n");

   652             {  int tij;

   653                double xd, yd, rij;

   654                xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];

   655                yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];

   656                rij = sqrt((xd * xd + yd * yd) / 10.0);

   657                tij = nint(rij);

   658                if (tij < rij) dij = tij + 1; else dij = tij;

   659             }

   660             break;

   661          default:

   662             xassert(tsp->edge_weight_type != tsp->edge_weight_type);

   663       }

   664       return dij;

   665 }

   667 /* eof */

author	Alpar Juttner <alpar@cs.elte.hu>
	Mon, 06 Dec 2010 13:09:21 +0100
changeset 1	c445c931472f
permissions	-rw-r--r--