construct.c

Lin-Kernighan heuristic for the TSP and minimum weight perfect matching

length_t farthest_len;
/*81:*/
#line 1407 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"construct: Select fresh neighbours for %d, excepting %d\n",
x,not_me);fflush(stderr);
#endif
#endif

/*:81*/
#line 772 "./construct.w"

for(i= w= 0;i<num_unsaturated;i++){
const int c= unsaturated[i];
if(c==x||c==not_me)continue;
nn_work[w].this_end= x;
nn_work[w].other_end= c;
nn_work[w].len= cost(x,c);
w++;
}
num_chosen= min(w,init_max_per_city_nn_cache);
errorif(num_chosen==0,"Bug!");
(void)select_range(nn_work,w,sizeof(pq_edge_t),cmp_pq_edge,
0,num_chosen,0);
farthest_len= nn_work[num_chosen-1].len;
farthest_city= nn_work[num_chosen-1].other_end;
for(i= 0;i<num_chosen;i++){
pq_edge_t*e;
e= pool_alloc(nn_link_pool);
*e= nn_work[i];
pq_insert(pq_edge,e);
if(farthest_len<e->len){
farthest_city= e->other_end;
farthest_len= e->len;
}
}
farthest_in_queue[x]= farthest_city;
}

/*:41*/
#line 734 "./construct.w"
;
}else{
/*39:*/
#line 740 "./construct.w"

{int i;
/*78:*/
#line 1378 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 500
fprintf(stderr,"construct: All neighbours for %d, excepting %d\n",
x,not_me);fflush(stderr);
#endif
#endif


/*:78*/
#line 742 "./construct.w"

for(i= 0;i<num_unsaturated;i++){
const int y= unsaturated[i];
length_t len;
if(y==x||y==not_me)continue;
len= cost(x,y);
/*40:*/
#line 754 "./construct.w"

{
pq_edge_t*e;
e= pool_alloc(nn_link_pool);
e->len= len;
e->this_end= x;
e->other_end= y;
pq_insert(pq_edge,e);
/*80:*/
#line 1397 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"construct: alloc new link (%d,%d) "
length_t_native_spec"\n",
e->this_end,e->other_end,length_t_native_pcast(e->len));fflush(stderr);
#endif
#endif

/*:80*/
#line 762 "./construct.w"

}


/*:40*/
#line 748 "./construct.w"

}
}


/*:39*/
#line 736 "./construct.w"

}

/*:38*/
#line 1044 "./construct.w"

}
}

/*:60*/
#line 1004 "./construct.w"

}
/*77:*/
#line 1365 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 1000
if(verbose>=2000){
printf("Priority queue AFTER Get one short valid edge or NULL:\n");
pq_print(pq_edge,stdout);
printf("\n");
}
if(verbose>=1000)printf(" valid");
#endif
#endif

/*:77*/
#line 1006 "./construct.w"


/*:58*/
#line 930 "./construct.w"

if(e&&e->this_end==candidate[0]->other_end
&&e->other_end==candidate[0]->this_end){
pq_edge_t*push_back= e;
/*58:*/
#line 993 "./construct.w"

/*75:*/
#line 1338 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 2000
if(verbose>=2000){
printf("Priority queue before Get one short valid edge or NULL:\n");
pq_print(pq_edge,stdout);
printf("\n");
}
#endif
#endif

/*:75*/
#line 994 "./construct.w"

while(1){
e= pq_delete_min(pq_edge);
if(e==NULL)break;
/*76:*/
#line 1350 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 2000
if(verbose>=2000){
printf("Extract ");
pq_edge_print(stdout,e);

printf("\nPriority queue just after extract:\n");
pq_print(pq_edge,stdout);
printf("\n");
}
#endif
#endif

/*:76*/
#line 998 "./construct.w"

x= e->this_end;y= e->other_end;
if(adj[x].count==2){
continue;
}
if(adj[y].count<2&&y!=tail[x])break;
/*60:*/
#line 1032 "./construct.w"

if(E2_case){
E2_hide(tail[x]);
e->other_end= E2_nn(x);
e->len= cost(x,e->other_end);
E2_unhide(tail[x]);
pq_insert(pq_edge,e);
}else{
pool_free(nn_link_pool,e);
if(farthest_in_queue[x]==y){
const int not_me= tail[x];
/*82:*/
#line 1416 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"Need to refresh because I got x=%d %d y=%d %d "
length_t_native_spec"\n",
x,e->this_end,y,e->other_end,length_t_native_pcast(e->len));
#endif
#endif

/*:82*/
#line 1043 "./construct.w"

/*38:*/
#line 732 "./construct.w"

if(num_unsaturated>sqrt_n){
/*41:*/
#line 767 "./construct.w"

{
int i,num_chosen,farthest_city;
size_t w;
length_t farthest_len;
/*81:*/
#line 1407 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"construct: Select fresh neighbours for %d, excepting %d\n",
x,not_me);fflush(stderr);
#endif
#endif

/*:81*/
#line 772 "./construct.w"

for(i= w= 0;i<num_unsaturated;i++){
const int c= unsaturated[i];
if(c==x||c==not_me)continue;
nn_work[w].this_end= x;
nn_work[w].other_end= c;
nn_work[w].len= cost(x,c);
w++;
}
num_chosen= min(w,init_max_per_city_nn_cache);
errorif(num_chosen==0,"Bug!");
(void)select_range(nn_work,w,sizeof(pq_edge_t),cmp_pq_edge,
0,num_chosen,0);
farthest_len= nn_work[num_chosen-1].len;
farthest_city= nn_work[num_chosen-1].other_end;
for(i= 0;i<num_chosen;i++){
pq_edge_t*e;
e= pool_alloc(nn_link_pool);
*e= nn_work[i];
pq_insert(pq_edge,e);
if(farthest_len<e->len){
farthest_city= e->other_end;
farthest_len= e->len;
}
}
farthest_in_queue[x]= farthest_city;
}

/*:41*/
#line 734 "./construct.w"
;
}else{
/*39:*/
#line 740 "./construct.w"

{int i;
/*78:*/
#line 1378 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 500
fprintf(stderr,"construct: All neighbours for %d, excepting %d\n",
x,not_me);fflush(stderr);
#endif
#endif


/*:78*/
#line 742 "./construct.w"

for(i= 0;i<num_unsaturated;i++){
const int y= unsaturated[i];
length_t len;
if(y==x||y==not_me)continue;
len= cost(x,y);
/*40:*/
#line 754 "./construct.w"

{
pq_edge_t*e;
e= pool_alloc(nn_link_pool);
e->len= len;
e->this_end= x;
e->other_end= y;
pq_insert(pq_edge,e);
/*80:*/
#line 1397 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"construct: alloc new link (%d,%d) "
length_t_native_spec"\n",
e->this_end,e->other_end,length_t_native_pcast(e->len));fflush(stderr);
#endif
#endif

/*:80*/
#line 762 "./construct.w"

}


/*:40*/
#line 748 "./construct.w"

}
}


/*:39*/
#line 736 "./construct.w"

}

/*:38*/
#line 1044 "./construct.w"

}
}

/*:60*/
#line 1004 "./construct.w"

}
/*77:*/
#line 1365 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 1000
if(verbose>=2000){
printf("Priority queue AFTER Get one short valid edge or NULL:\n");
pq_print(pq_edge,stdout);
printf("\n");
}
if(verbose>=1000)printf(" valid");
#endif
#endif

/*:77*/
#line 1006 "./construct.w"


/*:58*/
#line 934 "./construct.w"

pq_insert(pq_edge,push_back);
}
candidate[1]= e;
e= candidate[0];
if(candidate[1]){
const int chosen= (prng_unif_int(random_stream,3)==0);

e= candidate[chosen];
pq_insert(pq_edge,candidate[1-chosen]);
}
}
#endif

/*:53*//*54:*/
#line 949 "./construct.w"

#if !defined(DO_RANDOM)
/*58:*/
#line 993 "./construct.w"

/*75:*/
#line 1338 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 2000
if(verbose>=2000){
printf("Priority queue before Get one short valid edge or NULL:\n");
pq_print(pq_edge,stdout);
printf("\n");
}
#endif
#endif

/*:75*/
#line 994 "./construct.w"

while(1){
e= pq_delete_min(pq_edge);
if(e==NULL)break;
/*76:*/
#line 1350 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 2000
if(verbose>=2000){
printf("Extract ");
pq_edge_print(stdout,e);

printf("\nPriority queue just after extract:\n");
pq_print(pq_edge,stdout);
printf("\n");
}
#endif
#endif

/*:76*/
#line 998 "./construct.w"

x= e->this_end;y= e->other_end;
if(adj[x].count==2){
continue;
}
if(adj[y].count<2&&y!=tail[x])break;
/*60:*/
#line 1032 "./construct.w"

if(E2_case){
E2_hide(tail[x]);
e->other_end= E2_nn(x);
e->len= cost(x,e->other_end);
E2_unhide(tail[x]);
pq_insert(pq_edge,e);
}else{
pool_free(nn_link_pool,e);
if(farthest_in_queue[x]==y){
const int not_me= tail[x];
/*82:*/
#line 1416 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"Need to refresh because I got x=%d %d y=%d %d "
length_t_native_spec"\n",
x,e->this_end,y,e->other_end,length_t_native_pcast(e->len));
#endif
#endif

/*:82*/
#line 1043 "./construct.w"

/*38:*/
#line 732 "./construct.w"

if(num_unsaturated>sqrt_n){
/*41:*/
#line 767 "./construct.w"

{
int i,num_chosen,farthest_city;
size_t w;
length_t farthest_len;
/*81:*/
#line 1407 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"construct: Select fresh neighbours for %d, excepting %d\n",
x,not_me);fflush(stderr);
#endif
#endif

/*:81*/
#line 772 "./construct.w"

for(i= w= 0;i<num_unsaturated;i++){
const int c= unsaturated[i];
if(c==x||c==not_me)continue;
nn_work[w].this_end= x;
nn_work[w].other_end= c;
nn_work[w].len= cost(x,c);
w++;
}
num_chosen= min(w,init_max_per_city_nn_cache);
errorif(num_chosen==0,"Bug!");
(void)select_range(nn_work,w,sizeof(pq_edge_t),cmp_pq_edge,
0,num_chosen,0);
farthest_len= nn_work[num_chosen-1].len;
farthest_city= nn_work[num_chosen-1].other_end;
for(i= 0;i<num_chosen;i++){
pq_edge_t*e;
e= pool_alloc(nn_link_pool);
*e= nn_work[i];
pq_insert(pq_edge,e);
if(farthest_len<e->len){
farthest_city= e->other_end;
farthest_len= e->len;
}
}
farthest_in_queue[x]= farthest_city;
}

/*:41*/
#line 734 "./construct.w"
;
}else{
/*39:*/
#line 740 "./construct.w"

{int i;
/*78:*/
#line 1378 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 500
fprintf(stderr,"construct: All neighbours for %d, excepting %d\n",
x,not_me);fflush(stderr);
#endif
#endif


/*:78*/
#line 742 "./construct.w"

for(i= 0;i<num_unsaturated;i++){
const int y= unsaturated[i];
length_t len;
if(y==x||y==not_me)continue;
len= cost(x,y);
/*40:*/
#line 754 "./construct.w"

{
pq_edge_t*e;
e= pool_alloc(nn_link_pool);
e->len= len;
e->this_end= x;
e->other_end= y;
pq_insert(pq_edge,e);
/*80:*/
#line 1397 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"construct: alloc new link (%d,%d) "
length_t_native_spec"\n",
e->this_end,e->other_end,length_t_native_pcast(e->len));fflush(stderr);
#endif
#endif

/*:80*/
#line 762 "./construct.w"

}


/*:40*/
#line 748 "./construct.w"

}
}


/*:39*/
#line 736 "./construct.w"

}

/*:38*/
#line 1044 "./construct.w"

}
}

/*:60*/
#line 1004 "./construct.w"

}
/*77:*/
#line 1365 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 1000
if(verbose>=2000){
printf("Priority queue AFTER Get one short valid edge or NULL:\n");
pq_print(pq_edge,stdout);
printf("\n");
}
if(verbose>=1000)printf(" valid");
#endif
#endif

/*:77*/
#line 1006 "./construct.w"


/*:58*/
#line 951 "./construct.w"

#endif

/*:54*//*59:*/
#line 1012 "./construct.w"

errorif(e==NULL,"Exhausted the priority queue of links.");
/*74:*/
#line 1329 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 1000
if(verbose>=1000)printf(" accept\n");
#endif
#endif


/*:74*/
#line 1014 "./construct.w"

len+= e->len;
x= e->this_end;
y= e->other_end;


/*:59*/
#line 893 "./construct.w"

adj[x].city[adj[x].count++]= y;
adj[y].city[adj[y].count++]= x;
if(adj[y].count==2){if(E2_case)E2_hide(y);else{const int c= y;
/*35:*/
#line 670 "./construct.w"

{const int inv= inv_unsaturated[c];
if(inv<num_unsaturated&&unsaturated[inv]==c){
const int move_city= unsaturated[--num_unsaturated];
unsaturated[inv]= move_city;
inv_unsaturated[move_city]= inv;
/*79:*/
#line 1388 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 500
fprintf(stderr,"             Marking %d as saturated (inv= %d)\n",c,inv);
#endif
#endif


/*:79*/
#line 676 "./construct.w"

}
}

/*:35*/
#line 897 "./construct.w"
}}
if(adj[x].count==2){if(E2_case)E2_hide(x);else{const int c= x;
/*35:*/
#line 670 "./construct.w"

{const int inv= inv_unsaturated[c];
if(inv<num_unsaturated&&unsaturated[inv]==c){
const int move_city= unsaturated[--num_unsaturated];
unsaturated[inv]= move_city;
inv_unsaturated[move_city]= inv;
/*79:*/
#line 1388 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 500
fprintf(stderr,"             Marking %d as saturated (inv= %d)\n",c,inv);
#endif
#endif


/*:79*/
#line 676 "./construct.w"

}
}

/*:35*/
#line 899 "./construct.w"
}}
else{/*60:*/
#line 1032 "./construct.w"

if(E2_case){
E2_hide(tail[x]);
e->other_end= E2_nn(x);
e->len= cost(x,e->other_end);
E2_unhide(tail[x]);
pq_insert(pq_edge,e);
}else{
pool_free(nn_link_pool,e);
if(farthest_in_queue[x]==y){
const int not_me= tail[x];
/*82:*/
#line 1416 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"Need to refresh because I got x=%d %d y=%d %d "
length_t_native_spec"\n",
x,e->this_end,y,e->other_end,length_t_native_pcast(e->len));
#endif
#endif

/*:82*/
#line 1043 "./construct.w"

/*38:*/
#line 732 "./construct.w"

if(num_unsaturated>sqrt_n){
/*41:*/
#line 767 "./construct.w"

{
int i,num_chosen,farthest_city;
size_t w;
length_t farthest_len;
/*81:*/
#line 1407 "./construct.w"

#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"construct: Select fresh neighbours for %d, excepting %d\n",
x,not_me);fflush(stderr);
#endif
#endif

/*:81*/
#line 772 "./construct.w"

for(i= w= 0;i<num_unsaturated;i++){
const int c= unsaturated[i];
if(c==x||c==not_me)continue;
nn_work[w].this_end= x;
nn_work[w].other_end= c;
nn_work[w].len= cost(x,c);
w++;
}
num_chosen= min(w,init_max_per_city_nn_cache);
errorif(num_chosen==0,"Bug!");
(void)select_range(nn_work,w,sizeof(pq_edge_t),cmp_pq_edge,
0,num_chosen,0);
farthest_len= nn_work[num_chosen-1].len;
farthest_city= nn_work[num_chosen-1].other_end;
for(i= 0;i<num_chosen;i++){
pq_edge_t*e;
e= pool_alloc(nn_link_pool);
*e= nn_work[i];
pq_insert(pq_edge,e);
if(farthest_len<e->len){
farthest_city= e->other_end;
farthest_len= e->len;
}
}
farthest_in_queue[x]= farthest_city;
}

/*:41*/
#line 734 "./construct.w"