/*2:*/#line 75 "./infill.w"const char*prog_name= "infill";const char*infill_rcs_id= "$Id: infill.w,v 1.1 1998/12/05 22:04:07 neto Exp neto $";#include <config.h>#include "lkconfig.h"#include <stddef.h>#include <stdio.h>#include <stdlib.h>#include "error.h"#include "length.h"#include "read.h"#include "decluster.h"#include "kdtree.h"#include "dsort.h"int noround= 0;int verbose= 0;long seed= -1998;void(*sort)(void*base,size_t nmemb,size_t size,int(*compar)(const void*,const void*))= dsort;/*3:*/#line 109 "./infill.w"static double fill_fraction= 0.1;static decluster_edge_t*long_edges= NULL;/*:3*//*6:*/#line 164 "./infill.w"static int n= 0;/*:6*/#line 97 "./infill.w"/*8:*/#line 184 "./infill.w"static inline length_tmin_len(length_t a,length_t b){if(a<=b)return a;else return b;}/*:8*//*9:*/#line 203 "./infill.w"static length_textended_cost(int w,int uv){decluster_edge_t e;if(w<n&&uv<n)return cost(w,uv);if(uv<n)return extended_cost(uv,w);e= long_edges[uv-n];return e.cost/2+min_len(((w<n?cost:extended_cost)(e.city[0],w)),((w<n?cost:extended_cost)(e.city[1],w)));}/*:9*/#line 98 "./infill.w"/*4:*/#line 114 "./infill.w"int main(int argc,char**argv){tsp_instance_t*tsp;decluster_tree_t*mst;int num_extra,new_n;if(argc>=2){fill_fraction= atof(argv[1]);}errorif(fill_fraction<0||fill_fraction>=1,"Fill fraction should be between 0 and 1\n");tsp= read_tsp_file(stdin,NULL,0);n= tsp->n;num_extra= n*fill_fraction,new_n= n+num_extra;errorif(num_extra<0||num_extra>n-1,"Number of extra points must be between 0 and %s: adjust fill fraction",n-1);if(E2_supports(tsp)){E2_create(tsp);}mst= decluster_setup(tsp->n);decluster_mst(tsp,mst);select_range(mst->edge,(size_t)(n-1),sizeof(decluster_edge_t),decluster_edge_cmp,((n-1)-num_extra),n-1,1);long_edges= mst->edge+((n-1)-num_extra);/*5:*/#line 147 "./infill.w"{FILE*out= stdout;int row,col;fprintf(out,"NAME: infill.%d.%s\n",num_extra,tsp->name);fprintf(out,"TYPE: TSP\n");fprintf(out,"COMMENT: %s | infill %f\n",(tsp->comment?tsp->comment:""),fill_fraction);fprintf(out,"DIMENSION: %d\n",new_n);if(E2_supports(tsp)){/*10:*/#line 222 "./infill.w"switch(tsp->edge_weight_type){case CEIL_2D:fprintf(out,"EDGE_WEIGHT_TYPE: CEIL_2D\n");break;case EUC_2D:fprintf(out,"EDGE_WEIGHT_TYPE: EUC_2D\n");break;case GEO:fprintf(out,"EDGE_WEIGHT_TYPE: GEO\n");break;case ATT:fprintf(out,"EDGE_WEIGHT_TYPE: GEO\n");break;default:errorif(1,"Doh! what's that edge weight type again?");break;}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]);}for(i= n;i<new_n;i++){const decluster_edge_t e= long_edges[i-n];if(verbose>0){fprintf(out,"   Halfway between %d (%g,%g) and %d (%g,%g) len "length_t_spec"\n",e.city[0],tsp->coord[e.city[0]].x[0],tsp->coord[e.city[0]].x[1],e.city[1],tsp->coord[e.city[1]].x[0],tsp->coord[e.city[1]].x[1],e.cost);}fprintf(out,"%d %g %g\n",i+1,(tsp->coord[e.city[0]].x[0]+tsp->coord[e.city[1]].x[0])/2,(tsp->coord[e.city[0]].x[1]+tsp->coord[e.city[1]].x[1])/2);}}/*:10*/#line 156 "./infill.w"}else{/*7:*/#line 169 "./infill.w"fprintf(out,"EDGE_WEIGHT_TYPE: EXPLICIT\n");fprintf(out,"EDGE_WEIGHT_FORMAT: UPPER_ROW\n");fprintf(out,"EDGE_WEIGHT_SECTION:\n");for(row= 0;row<new_n;row++){for(col= row+1;col<new_n;col++){fprintf(out," %ld",(long)extended_cost(row,col));}fprintf(out,"\n");}/*:7*/#line 158 "./infill.w"}fprintf(out,"EOF\n");}/*:5*/#line 137 "./infill.w"return 0;}/*:4*/#line 99 "./infill.w"/*:2*/