#define matchword(STR) (0==strncmp(keyword,STR,strlen(STR) ) )  \#define min(X,Y) ((X) >(Y) ?(Y) :(X) ) #define max(X,Y) ((X) <(Y) ?(Y) :(X) ) #define check_num_read(R,K)  \errorif((R) !=(K) ,"Error: expected %d arguments, got %d",K,R)  \#define truncate_to_zero(x) ((double) (int) (x) ) #define PI (3.14159265358979323846)  \/*1:*/#line 181 "./read.w"#include <config.h>#include "lkconfig.h"#include <stdio.h>#include <stddef.h>#include <stdlib.h>#include <math.h>#include "fixincludes.h"/*7:*/#line 264 "./read.w"#include "memory.h"#include "error.h"/*:7*//*12:*/#line 376 "./read.w"#include <string.h>/*:12*//*14:*/#line 402 "./read.w"#include <ctype.h>/*:14*//*20:*/#line 445 "./read.w"#include "gb_flip.h"/*:20*//*27:*/#line 554 "./read.w"#include "length.h"/*:27*//*34:*/#line 629 "./read.w"#include <limits.h>/*:34*/#line 189 "./read.w"#include "read.h"/*3:*/#line 219 "./read.w"static tsp_instance_t*p;/*:3*//*43:*/#line 726 "./read.w"length_t(*cost)(const int,const int);length_t(*pseudo_cost)(const int,const int);/*:43*/#line 193 "./read.w"/*48:*/#line 815 "./read.w"#if defined(COST_USE_HYPOT)#define my_hypot(A,B) (hypot((A),(B)))#else#define my_hypot(A,B) (sqrt((A)*(A)+(B)*(B)))#endif/*:48*//*57:*/#line 990 "./read.w"#if SIZEOF_INT==4typedef int int32;#elif SIZEOF_SHORT==4typedef short int int32;#elif SIZEOF_LONG==4typedef long int32;#else#error "I need a 32 bit integer for consistent results with DSJ_RANDOM"#endif/*:57*/#line 194 "./read.w"/*17:*/#line 435 "./read.w"static const char edge_weight_type_name[]= {"NO_EDGE_TYPE","EUC_2D","CEIL_2D","GEO","ATT","DSJ_RANDOM","EXPLICIT","RANDOM_EDGES"};/*:17*//*23:*/#line 468 "./read.w"static const char edge_weight_format_name[]= {"NO_EDGE_FORMAT","LOWER_DIAG_ROW","FULL_MATRIX","UPPER_ROW"};/*:23*//*39:*/#line 676 "./read.w"static double dsj_random_factor= 1;static int32 dsj_random_param= 1;/*:39*/#line 195 "./read.w"/*45:*/#line 739 "./read.w"length_t cost_from_matrix(const int i,const int j);length_tcost_from_matrix(const int i,const int j){return(length_t)p->edge_weights[i][j];}length_t cost_from_short_matrix(const int i,const int j);length_tcost_from_short_matrix(const int i,const int j){return(length_t)p->short_edge_weights[i][j];}/*:45*//*46:*/#line 777 "./read.w"length_t cost_from_euc2d(const int i,const int j);length_tcost_from_euc2d(const int i,const int j){coord_2d*coord_array= p->coord;double xd= coord_array[i].x[0]-coord_array[j].x[0];double yd= coord_array[i].x[1]-coord_array[j].x[1];return(length_t)floor(0.5+my_hypot(xd,yd));}/*:46*//*47:*/#line 792 "./read.w"length_t cost_from_ceil2d(const int i,const int j);length_tcost_from_ceil2d(const int i,const int j){coord_2d*coord_array= p->coord;double xd= coord_array[i].x[0]-coord_array[j].x[0];double yd= coord_array[i].x[1]-coord_array[j].x[1];return(length_t)ceil(my_hypot(xd,yd));}/*:47*//*49:*/#line 825 "./read.w"length_t cost_from_euc2d_not_rounded(const int i,const int j);length_tcost_from_euc2d_not_rounded(const int i,const int j){coord_2d*coord_array= p->coord;double xd= coord_array[i].x[0]-coord_array[j].x[0];double yd= coord_array[i].x[1]-coord_array[j].x[1];return(length_t)my_hypot(xd,yd);}/*:49*//*52:*/#line 865 "./read.w"length_t pseudo_cost_from_euc2d(const int i,const int j);length_tpseudo_cost_from_euc2d(const int i,const int j){coord_2d*coord_array= p->coord;double xd= coord_array[i].x[0]-coord_array[j].x[0];double yd= coord_array[i].x[1]-coord_array[j].x[1];return(length_t)(xd*xd+yd*yd);}/*:52*//*53:*/#line 895 "./read.w"length_t cost_from_geo(const int i,const int j);length_tcost_from_geo(const int i,const int j){coord_2d*coord_array= p->coord;const double x1= coord_array[i].x[0],x2= coord_array[j].x[0];const double y1= coord_array[i].x[1],y2= coord_array[j].x[1];double degrees,minutes;double latitude1,latitude2,longitude1,longitude2;double q1,q2,q3;const double radius= 6378.388;degrees= truncate_to_zero(x1);minutes= x1-degrees;latitude1= (PI/180)*(degrees+minutes*(5.0/3.0));degrees= truncate_to_zero(x2);minutes= x2-degrees;latitude2= (PI/180)*(degrees+minutes*(5.0/3.0));degrees= truncate_to_zero(y1);minutes= y1-degrees;longitude1= (PI/180)*(degrees+minutes*(5.0/3.0));degrees= truncate_to_zero(y2);minutes= y2-degrees;longitude2= (PI/180)*(degrees+minutes*(5.0/3.0));q1= cos(longitude1-longitude2);q2= cos(latitude1-latitude2);q3= cos(latitude1+latitude2);return(length_t)truncate_to_zero(radius*acos(0.5*((1+q1)*q2-(1-q1)*q3))+1);}/*:53*//*54:*/#line 937 "./read.w"length_t cost_from_att(const int i,const int j);length_tcost_from_att(const int i,const int j){coord_2d*coord_array= p->coord;double xd= coord_array[i].x[0]-coord_array[j].x[0];double yd= coord_array[i].x[1]-coord_array[j].x[1];return(length_t)ceil(my_hypot(xd,yd)*0.31622776601683793319988935);}/*:54*//*55:*/#line 955 "./read.w"length_t cost_from_dsj_random(const int i,const int j);length_tcost_from_dsj_random(const int ii,const int jj){const int32 i= ii,j= jj;const int32 salt1= 0x12345672*(i+1)+1;const int32 salt2= 0x12345672*(j+1)+1;int32 x,y,z;x= salt1&salt2;y= salt1|salt2;z= dsj_random_param;x*= z;y*= x;z*= y;z^= dsj_random_param;x*= z;y*= x;z*= y;x= ((salt1+salt2)^z)&0x7fffffff;return(length_t)(x*dsj_random_factor);}/*:55*/#line 196 "./read.w"/*4:*/#line 227 "./read.w"tsp_instance_t*switch_to(tsp_instance_t*new_problem){tsp_instance_t*old_problem;old_problem= p;p= new_problem;/*56:*/#line 985 "./read.w"dsj_random_factor= p->dsj_random_factor;dsj_random_param= p->dsj_random_param;/*:56*//*58:*/#line 1005 "./read.w"switch(p->edge_weight_type){case EXPLICIT:cost= cost_from_matrix;pseudo_cost= cost_from_matrix;break;case EUC_2D:{extern int noround;cost= noround?cost_from_euc2d_not_rounded:cost_from_euc2d;}pseudo_cost= pseudo_cost_from_euc2d;break;case CEIL_2D:{extern int noround;cost= noround?cost_from_euc2d_not_rounded:cost_from_ceil2d;}pseudo_cost= pseudo_cost_from_euc2d;break;case GEO:cost= cost_from_geo;pseudo_cost= cost_from_geo;break;case ATT:cost= cost_from_att;pseudo_cost= cost_from_att;break;case DSJ_RANDOM:cost= cost_from_dsj_random;pseudo_cost= cost_from_dsj_random;break;case RANDOM_EDGES:errorif(p->short_edge_weights==NULL,"RANDOM_EDGES specified but no SEED given");cost= cost_from_short_matrix;pseudo_cost= cost_from_short_matrix;break;case NO_EDGE_TYPE:default:errorif(1,"Switching to an instance with unknown edge type %d",p->edge_weight_type);}/*:58*/#line 234 "./read.w"return old_problem;}/*:4*//*6:*/#line 249 "./read.w"tsp_instance_t*read_tsp_file(FILE*in,FILE*debug,const int force_even_num){p= new_of(tsp_instance_t);/*10:*/#line 308 "./read.w"p->name= NULL;p->comment= NULL;p->n= 0;p->scale= 1e6;/*:10*//*19:*/#line 442 "./read.w"p->edge_weight_type= NO_EDGE_TYPE;/*:19*//*25:*/#line 475 "./read.w"p->edge_weight_format= NO_EDGE_FORMAT;/*:25*//*29:*/#line 560 "./read.w"p->edge_weights= NULL;/*:29*//*33:*/#line 624 "./read.w"p->coord= NULL;p->xmin= p->ymin= INT_MAX;p->xmax= p->ymax= INT_MIN;/*:33*//*38:*/#line 670 "./read.w"p->seed= 1;p->dsj_random_factor= 1.0;p->dsj_random_param= 1;/*:38*//*42:*/#line 707 "./read.w"p->short_edge_weights= NULL;/*:42*/#line 254 "./read.w"/*11:*/#line 319 "./read.w"{#define MAX_KEYWORD_LEN (25)#define MAX_LINE_LEN (200)char keyword[MAX_KEYWORD_LEN],rest_of_line[MAX_LINE_LEN];int more_input= 1,lineno= 0;while(more_input){char*colon;int r;keyword[0]= 0;r= fscanf(in," %s ",keyword);if(r==EOF){more_input= 0;break;}errorif(r!=1,"%d: Couldn't read the word following \"%s\". (r==%d)",lineno+1,keyword,r);if(NULL!=(colon= strchr(keyword,':')))*colon= '\0';if(matchword("EOF")){more_input= 0;}else if(matchword("NAME")){/*13:*/#line 385 "./read.w"{int l;char*rcp;if(colon==NULL){int r= fscanf(in," : ");errorif(r!=0,"%d: Missed the colon.",lineno);}rcp= fgets(rest_of_line,MAX_LINE_LEN,in);errorif(NULL==rcp,"%d: Couldn't read after the colon; truncated file?",lineno);l= strlen(rest_of_line)-1;if(l>=0&&rest_of_line[l]=='\n'){rest_of_line[l--]= '\0';lineno++;}while(l>=0&&isspace(rest_of_line[l]))rest_of_line[l--]= '\0';if(feof(in))more_input= 0;}/*:13*/#line 336 "./read.w"p->name= dup_string(rest_of_line);}else if(matchword("COMMENT")){/*13:*/#line 385 "./read.w"{int l;char*rcp;if(colon==NULL){int r= fscanf(in," : ");errorif(r!=0,"%d: Missed the colon.",lineno);}rcp= fgets(rest_of_line,MAX_LINE_LEN,in);errorif(NULL==rcp,"%d: Couldn't read after the colon; truncated file?",lineno);l= strlen(rest_of_line)-1;if(l>=0&&rest_of_line[l]=='\n'){rest_of_line[l--]= '\0';lineno++;}while(l>=0&&isspace(rest_of_line[l]))rest_of_line[l--]= '\0';if(feof(in))more_input= 0;}/*:13*/#line 339 "./read.w"p->comment= dup_string(rest_of_line);}else if(matchword("TYPE")){/*13:*/#line 385 "./read.w"{int l;char*rcp;if(colon==NULL){int r= fscanf(in," : ");errorif(r!=0,"%d: Missed the colon.",lineno);}rcp= fgets(rest_of_line,MAX_LINE_LEN,in);errorif(NULL==rcp,"%d: Couldn't read after the colon; truncated file?",lineno);l= strlen(rest_of_line)-1;if(l>=0&&rest_of_line[l]=='\n'){rest_of_line[l--]= '\0';lineno++;}while(l>=0&&isspace(rest_of_line[l]))rest_of_line[l--]= '\0';if(feof(in))more_input= 0;}/*:13*/#line 342 "./read.w"errorif(strcmp(rest_of_line,"TSP"),"Can't read TSPLIB files of type %s.",rest_of_line);}else if(matchword("DIMENSION")){/*13:*/#line 385 "./read.w"{int l;char*rcp;if(colon==NULL){int r= fscanf(in," : ");errorif(r!=0,"%d: Missed the colon.",lineno);}rcp= fgets(rest_of_line,MAX_LINE_LEN,in);errorif(NULL==rcp,"%d: Couldn't read after the colon; truncated file?",lineno);l= strlen(rest_of_line)-1;if(l>=0&&rest_of_line[l]=='\n'){rest_of_line[l--]= '\0';lineno++;}while(l>=0&&isspace(rest_of_line[l]))rest_of_line[l--]= '\0';if(feof(in))more_input= 0;}/*:13*/#line 345 "./read.w"p->input_n= p->n= atoi(rest_of_line);}else if(matchword("DISPLAY_DATA_TYPE")){/*13:*/#line 385 "./read.w"{int l;char*rcp;if(colon==NULL){int r= fscanf(in," : ");errorif(r!=0,"%d: Missed the colon.",lineno);}rcp= fgets(rest_of_line,MAX_LINE_LEN,in);errorif(NULL==rcp,"%d: Couldn't read after the colon; truncated file?",lineno);l= strlen(rest_of_line)-1;if(l>=0&&rest_of_line[l]=='\n'){rest_of_line[l--]= '\0';lineno++;}while(l>=0&&isspace(rest_of_line[l]))rest_of_line[l--]= '\0';if(feof(in))more_input= 0;}/*:13*/#line 348 "./read.w"}else if(matchword("EDGE_WEIGHT_TYPE")){/*15:*/#line 410 "./read.w"/*13:*/#line 385 "./read.w"{int l;char*rcp;if(colon==NULL){int r= fscanf(in," : ");errorif(r!=0,"%d: Missed the colon.",lineno);}rcp= fgets(rest_of_line,MAX_LINE_LEN,in);errorif(NULL==rcp,"%d: Couldn't read after the colon; truncated file?",lineno);l= strlen(rest_of_line)-1;if(l>=0&&rest_of_line[l]=='\n'){rest_of_line[l--]= '\0';lineno++;}while(l>=0&&isspace(rest_of_line[l]))rest_of_line[l--]= '\0';if(feof(in))more_input= 0;}/*:13*/#line 411 "./read.w"if(0==strcmp(rest_of_line,"EUC_2D")){p->edge_weight_type= EUC_2D;}else if(0==strcmp(rest_of_line,"CEIL_2D")){p->edge_weight_type= CEIL_2D;}else if(0==strcmp(rest_of_line,"GEO")){p->edge_weight_type= GEO;}else if(0==strcmp(rest_of_line,"ATT")){p->edge_weight_type= ATT;}else if(0==strcmp(rest_of_line,"DSJ_RANDOM")){p->edge_weight_type= DSJ_RANDOM;}else if(0==strcmp(rest_of_line,"EXPLICIT")){p->edge_weight_type= EXPLICIT;}else if(0==strcmp(rest_of_line,"RANDOM_EDGES")){p->edge_weight_type= RANDOM_EDGES;}else{errorif(1,"%d: Apology: Unknown edge weight type \"%s\".",lineno,rest_of_line);}/*:15*/#line 351 "./read.w"}else if(matchword("EDGE_WEIGHT_FORMAT")){/*21:*/#line 451 "./read.w"/*13:*/#line 385 "./read.w"{int l;char*rcp;if(colon==NULL){int r= fscanf(in," : ");errorif(r!=0,"%d: Missed the colon.",lineno);}rcp= fgets(rest_of_line,MAX_LINE_LEN,in);errorif(NULL==rcp,"%d: Couldn't read after the colon; truncated file?",lineno);l= strlen(rest_of_line)-1;if(l>=0&&rest_of_line[l]=='\n'){rest_of_line[l--]= '\0';lineno++;}while(l>=0&&isspace(rest_of_line[l]))rest_of_line[l--]= '\0';if(feof(in))more_input= 0;}/*:13*/#line 452 "./read.w"if(0==strcmp(rest_of_line,"LOWER_DIAG_ROW")){p->edge_weight_format= LOWER_DIAG_ROW;}else if(0==strcmp(rest_of_line,"FULL_MATRIX")){p->edge_weight_format= FULL_MATRIX;}else if(0==strcmp(rest_of_line,"UPPER_ROW")){p->edge_weight_format= UPPER_ROW;}else{errorif(1,"%d: Unknown edge weight format \"%s\".",lineno,rest_of_line);}/*:21*/#line 353 "./read.w"}else if(matchword("EDGE_WEIGHT_SECTION")){/*26:*/#line 484 "./read.w"switch(p->edge_weight_format){long int long_dummy;case LOWER_DIAG_ROW:{int row,col;p->edge_weights= new_arr_of(length_t*,p->input_n);for(row= 0;row<p->input_n;row++){p->edge_weights[row]= new_arr_of(length_t,p->input_n);}for(row= 0;row<p->input_n;row++){for(col= 0;col<=row;col++){int r= fscanf(in," %ld ",&long_dummy);errorif(1!=r,"Couldn't convert an edge weight: %d to %d.",row+1,col+1);p->edge_weights[col][row]= p->edge_weights[row][col]= long_dummy;}}}break;case FULL_MATRIX:{int row,col;p->edge_weights= new_arr_of(length_t*,p->input_n);