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<p->input_n;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[row][col]= long_dummy;}}for(row= 0;row<p->input_n;row++){for(col= 0;col<row;col++){errorif(p->edge_weights[row][col]!=p->edge_weights[col][row],"Asymmetric FULL_MATRIX:  (%d,%d) does not match (%d,%d)",row,col,col,row);}}}break;case UPPER_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);p->edge_weights[row][row]= 0;}for(row= 0;row<p->input_n;row++){for(col= row+1;col<p->input_n;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;default:break;}/*:26*/#line 355 "./read.w"}else if(matchword("NODE_COORD_SECTION")){/*30:*/#line 586 "./read.w"{int i,j,r;p->coord= new_arr_of(coord_2d,p->input_n);for(i= 0;i<p->input_n;i++){r= fscanf(in," %d ",&j);check_num_read(r,1);r= fscanf(in," %lf %lf ",&p->coord[j-1].x[0],&p->coord[j-1].x[1]);check_num_read(r,2);p->xmin= min(p->xmin,p->coord[j-1].x[0]);p->ymin= min(p->ymin,p->coord[j-1].x[1]);p->xmax= max(p->xmax,p->coord[j-1].x[0]);p->ymax= max(p->ymax,p->coord[j-1].x[1]);lineno++;}}/*:30*/#line 357 "./read.w"}else if(matchword("DISPLAY_DATA_SECTION")){/*35:*/#line 634 "./read.w"{int i;double dummy;for(i= 0;i<p->input_n;i++){fscanf(in," %lf %lf %lf ",&dummy,&dummy,&dummy);}}/*:35*/#line 359 "./read.w"}else if(matchword("SEED")){/*36:*/#line 651 "./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 652 "./read.w"p->seed= atol(rest_of_line);switch(p->edge_weight_type){case DSJ_RANDOM:p->dsj_random_param= 1+104*p->seed;break;case RANDOM_EDGES:/*40:*/#line 683 "./read.w"gb_init_rand(p->seed);{int i,j;p->short_edge_weights= new_arr_of(short*,p->input_n);for(i= 0;i<p->input_n;i++){p->short_edge_weights[i]= new_arr_of(short,p->input_n);p->short_edge_weights[i][i]= 0;}for(i= 0;i<p->input_n;i++)for(j= 0;j<i;j++)p->short_edge_weights[i][j]= p->short_edge_weights[j][i]= (short)(1+gb_unif_rand(1000L));if(p->input_n<=10){printf("Cost matrix:\n");for(i= 0;i<p->input_n;i++){for(j= 0;j<p->input_n;j++)printf(" %4d",p->short_edge_weights[i][j]);printf("\n");}}}/*:40*/#line 659 "./read.w"break;default:errorif(1,"SEED directive used for edge type %s",edge_weight_type_name[p->edge_weight_type]);}/*:36*/#line 361 "./read.w"}else if(matchword("SCALE")){/*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 363 "./read.w"p->scale= atof(rest_of_line);p->dsj_random_factor= p->scale/2147483648.0;}else{/*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 367 "./read.w"errorif(1,"%d: Don't know what the keyword %s is!",lineno,keyword);}}/*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 371 "./read.w"}/*:11*/#line 255 "./read.w"/*61:*/#line 1111 "./read.w"if(p->n){switch(p->edge_weight_type){case EUC_2D:case CEIL_2D:case GEO:errorif(p->edge_weight_format!=NO_EDGE_FORMAT,"Edge weight format should be NO_EDGE_FORMAT, but is %s",edge_weight_format_name[p->edge_weight_format]);errorif(p->coord==NULL,"No coordinates were read");break;case EXPLICIT:errorif(p->edge_weight_format==NO_EDGE_FORMAT,"Edge weight shouldn't be NO_EDGE_FORMAT, but it is");errorif(p->edge_weights==NULL,"No edge weights were read");break;case DSJ_RANDOM:default:break;}}/*:61*/#line 256 "./read.w"/*59:*/#line 1053 "./read.w"if(force_even_num&&(p->input_n%2)){/*60:*/#line 1084 "./read.w"p->n--;switch(p->edge_weight_type){case EUC_2D:case CEIL_2D:case GEO:case ATT:{int i,lex_last= 0;for(i= 1;i<p->input_n;i++){if(p->coord[i].x[0]>p->coord[lex_last].x[0]||(p->coord[i].x[0]==p->coord[lex_last].x[0]&&p->coord[i].x[1]>=p->coord[lex_last].x[1]))lex_last= i;}{coord_2d t= p->coord[p->n];p->coord[p->n]= p->coord[lex_last];p->coord[lex_last]= t;}}default:break;}/*:60*/#line 1055 "./read.w"}/*:59*/#line 257 "./read.w"/*63:*/#line 1150 "./read.w"if(debug){fprintf(debug,"/N {%d} def        %% number of nodes\n",p->input_n);if(p->input_n<8191)fprintf(debug,"/xs N 1 add array def\n/ys N 1 add array def\n");}/*:63*//*64:*/#line 1160 "./read.w"if(debug){const double xdiff= ((double)p->xmax)-((double)p->xmin);const double ydiff= ((double)p->ymax)-((double)p->ymin);const double maxrange= max(xdiff,ydiff);const double xoffset= xdiff<ydiff?(maxrange-xdiff)/2:0.0;const double yoffset= ydiff<xdiff?(maxrange-ydiff)/2:0.0;fprintf(debug,"/xmin {%f} def \n",p->xmin);fprintf(debug,"/xmax {%f} def \n",p->xmax);fprintf(debug,"/ymin {%f} def \n",p->ymin);fprintf(debug,"/ymax {%f} def \n",p->ymax);fprintf(debug,"/maxrange {%f} def \n",maxrange);fprintf(debug,"/xoffset  {%f} def \n",xoffset);fprintf(debug,"/yoffset  {%f} def \n",yoffset);}/*:64*//*65:*/#line 1177 "./read.w"if(debug){int i;for(i= 0;i<p->input_n;i++){fprintf(debug,"%f %f ts\n",p->coord[i].x[0],p->coord[i].x[1]);}fflush(debug);}/*:65*/#line 258 "./read.w"return p;}/*:6*//*50:*/#line 846 "./read.w"doublecost_from_euc2d_raw(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 my_hypot(xd,yd);}/*:50*//*66:*/#line 1190 "./read.w"voidwrite_tsp_file(tsp_instance_t*tsp,FILE*out){write_tsp_file_clip(tsp,out,0);}void write_tsp_file_clip(tsp_instance_t*tsp,FILE*out,int force_even_num){write_tsp_file_clip_matrix(tsp,out,force_even_num,0);}void write_tsp_file_clip_matrix(tsp_instance_t*tsp,FILE*out,int force_even_num,int force_matrix){int n= tsp->input_n;if((n%2)&&force_even_num)n--;if(out){fprintf(out,"NAME: %s\n",tsp->name);fprintf(out,"TYPE: TSP\n");fprintf(out,"COMMENT: %s%s\n",(tsp->comment?tsp->comment:""),(n<tsp->input_n?"| clip":""));fprintf(out,"DIMENSION: %d\n",n);if(force_matrix){int format= UPPER_ROW;fprintf(out,"EDGE_WEIGHT_TYPE: EXPLICIT\n");/*69:*/#line 1274 "./read.w"{int row,col;tsp_instance_t*old_p= switch_to(tsp);switch(format){case LOWER_DIAG_ROW:fprintf(out,"EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW\n");fprintf(out,"EDGE_WEIGHT_SECTION\n");for(row= 0;row<n;row++){for(col= 0;col<=row;col++){fprintf(out," %ld",(long)cost(row,col));}fprintf(out,"\n");}break;case FULL_MATRIX:fprintf(out,"EDGE_WEIGHT_FORMAT: FULL_MATRIX\n");fprintf(out,"EDGE_WEIGHT_SECTION:\n");for(row= 0;row<n;row++){for(col= 0;col<n;col++){fprintf(out," %ld",(long)cost(row,col));}fprintf(out,"\n");}break;case UPPER_ROW:fprintf(out,"EDGE_WEIGHT_FORMAT: UPPER_ROW\n");fprintf(out,"EDGE_WEIGHT_SECTION:\n");for(row= 0;row<n;row++){for(col= row+1;col<n;col++){fprintf(out," %ld",(long)cost(row,col));}fprintf(out,"\n");}break;default:errorif(1,"Unknown explicit format %d\n",format);}switch_to(old_p);}/*:69*/#line 1218 "./read.w"}else{switch(tsp->edge_weight_type){case CEIL_2D:fprintf(out,"EDGE_WEIGHT_TYPE: CEIL_2D\n");/*68:*/#line 1264 "./read.w"fprintf(out,"NODE_COORD_SECTION\n");{int i;for(i= 0;i<n;i++){fprintf(out,"%d %g %g\n",i+1,tsp->coord[i].x[0],tsp->coord[i].x[1]);}}/*:68*/#line 1222 "./read.w"break;case EUC_2D:fprintf(out,"EDGE_WEIGHT_TYPE: EUC_2D\n");/*68:*/#line 1264 "./read.w"fprintf(out,"NODE_COORD_SECTION\n");{int i;for(i= 0;i<n;i++){fprintf(out,"%d %g %g\n",i+1,tsp->coord[i].x[0],tsp->coord[i].x[1]);}}/*:68*/#line 1225 "./read.w"break;case GEO:fprintf(out,"EDGE_WEIGHT_TYPE: GEO\n");/*68:*/#line 1264 "./read.w"fprintf(out,"NODE_COORD_SECTION\n");{int i;for(i= 0;i<n;i++){fprintf(out,"%d %g %g\n",i+1,tsp->coord[i].x[0],tsp->coord[i].x[1]);}}/*:68*/#line 1228 "./read.w"break;case ATT:fprintf(out,"EDGE_WEIGHT_TYPE: ATT\n");/*68:*/#line 1264 "./read.w"fprintf(out,"NODE_COORD_SECTION\n");{int i;for(i= 0;i<n;i++){fprintf(out,"%d %g %g\n",i+1,tsp->coord[i].x[0],tsp->coord[i].x[1]);}}/*:68*/#line 1231 "./read.w"break;case DSJ_RANDOM:fprintf(out,"EDGE_WEIGHT_TYPE: DSJ_RANDOM\n");fprintf(out,"SCALE: %f\nSEED: %ld",tsp->scale,tsp->seed);break;case EXPLICIT:fprintf(out,"EDGE_WEIGHT_TYPE: EXPLICIT\n");{int format= tsp->edge_weight_format;/*69:*/#line 1274 "./read.w"{int row,col;tsp_instance_t*old_p= switch_to(tsp);switch(format){case LOWER_DIAG_ROW:fprintf(out,"EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW\n");fprintf(out,"EDGE_WEIGHT_SECTION\n");for(row= 0;row<n;row++){for(col= 0;col<=row;col++){fprintf(out," %ld",(long)cost(row,col));}fprintf(out,"\n");}break;case FULL_MATRIX:fprintf(out,"EDGE_WEIGHT_FORMAT: FULL_MATRIX\n");fprintf(out,"EDGE_WEIGHT_SECTION:\n");for(row= 0;row<n;row++){for(col= 0;col<n;col++){fprintf(out," %ld",(long)cost(row,col));}fprintf(out,"\n");}break;case UPPER_ROW:fprintf(out,"EDGE_WEIGHT_FORMAT: UPPER_ROW\n");fprintf(out,"EDGE_WEIGHT_SECTION:\n");for(row= 0;row<n;row++){for(col= row+1;col<n;col++){fprintf(out," %ld",(long)cost(row,col));}fprintf(out,"\n");}break;default:errorif(1,"Unknown explicit format %d\n",format);}switch_to(old_p);}/*:69*/#line 1238 "./read.w"}break;case RANDOM_EDGES:fprintf(out,"EDGE_WEIGHT_TYPE: EXPLICIT\n");{int format= UPPER_ROW;/*69:*/#line 1274 "./read.w"{int row,col;tsp_instance_t*old_p= switch_to(tsp);switch(format){case LOWER_DIAG_ROW:fprintf(out,"EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW\n");fprintf(out,"EDGE_WEIGHT_SECTION\n");for(row= 0;row<n;row++){for(col= 0;col<=row;col++){fprintf(out," %ld",(long)cost(row,col));}fprintf(out,"\n");}break;case FULL_MATRIX:fprintf(out,"EDGE_WEIGHT_FORMAT: FULL_MATRIX\n");fprintf(out,"EDGE_WEIGHT_SECTION:\n");for(row= 0;row<n;row++){for(col= 0;col<n;col++){fprintf(out," %ld",(long)cost(row,col));}fprintf(out,"\n");}break;case UPPER_ROW:fprintf(out,"EDGE_WEIGHT_FORMAT: UPPER_ROW\n");fprintf(out,"EDGE_WEIGHT_SECTION:\n");for(row= 0;row<n;row++){for(col= row+1;col<n;col++){fprintf(out," %ld",(long)cost(row,col));}fprintf(out,"\n");}break;default:errorif(1,"Unknown explicit format %d\n",format);}switch_to(old_p);}/*:69*/#line 1243 "./read.w"}break;case NO_EDGE_TYPE:default:errorif(1,"No edge type specified by instance: have %d instead",tsp->edge_weight_type);}}fprintf(out,"EOF\n");}}/*:66*/#line 197 "./read.w"const char*read_rcs_id= "$Id: read.w,v 1.143 1998/12/05 22:37:29 neto Exp neto $";/*:1*/