twolevel.c

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

}

/*:51*/
#line 1080 "./twolevel.w"

}
}
/*86:*/
#line 1952 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the left of |ca|, a=%d end\n",ca-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:86*/
#line 1083 "./twolevel.w"


/*:49*/
#line 1294 "./twolevel.w"

}else{
city_node_t*cc= l;
/*52:*/
#line 1176 "./twolevel.w"

/*83:*/
#line 1928 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the right of |cc|, c=%d begin\n",cc-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:83*/
#line 1177 "./twolevel.w"

{parent_node_t*p= cc->parent;
city_node_t*rc= p->tail;
city_node_t*lc= cc->next;
city_node_t*rrc= rc->next;
parent_node_t*rp= rrc->parent;
int rpr= rp->reverse,pr= p->reverse;
errorif(rp==p,"Bug");
if(rc!=cc){
/*53:*/
#line 1194 "./twolevel.w"

p->tail= cc;
rp->city_link[(pr==rpr)?CITY_LINK_HEAD:CITY_LINK_TAIL]= lc;

/*:53*/
#line 1186 "./twolevel.w"

/*54:*/
#line 1216 "./twolevel.w"

{
city_node_t*i,*u= lc,*v= rc;
int succ_link,seq_inc,seq_num;
if(rpr==pr){
succ_link= LINK_NEXT;
seq_inc= 1;
seq_num= rrc->seq+u->seq-v->seq-1;
}else{
succ_link= LINK_PREV;
seq_inc= -1;
seq_num= rrc->seq+v->seq-u->seq+1;
/*47:*/
#line 1029 "./twolevel.w"

{
city_node_t*i= u,*done= v->next;
for(i= u;i!=done;i= i->prev){
SWAP(i->next,i->prev,tcn);
}
}

/*:47*/
#line 1228 "./twolevel.w"

}
for(i= lc;i!=rc;i= i->link[succ_link],seq_num+= seq_inc){

i->parent= rp;
i->seq= seq_num;
}
i->parent= rp;
i->seq= seq_num;
}


/*:54*/
#line 1187 "./twolevel.w"

}
}
/*84:*/
#line 1936 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the right of |cc|, c=%d end\n",cc-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:84*/
#line 1190 "./twolevel.w"


/*:52*/
#line 1297 "./twolevel.w"

}
}
/*58:*/
#line 1312 "./twolevel.w"

psa= ca->parent->seq;
psb= cb->parent->seq;
psc= cc->parent->seq;
psd= cd->parent->seq;

/*:58*/
#line 1300 "./twolevel.w"


/*:57*//*59:*/
#line 1328 "./twolevel.w"

/*38:*/
#line 848 "./twolevel.w"

/*79:*/
#line 1877 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(print_at_flips!=-1&&print_at_flips<=count_flips){
if(verbose>=200)printf(" Handle case 1\n");
if(using_two_representations){
check_tours_match();
print_two_tours();
}
}
#endif

/*:79*/
#line 849 "./twolevel.w"

if(psb==psd){
SWAP(ca,cb,tcn);SWAP(cc,cd,tcn);
SWAP(psa,psb,ti);SWAP(psc,psd,ti);

}
if(psa==psc){
/*39:*/
#line 880 "./twolevel.w"

/*40:*/
#line 905 "./twolevel.w"

if(ca==cc)return;
if(ca->seq>cc->seq)SWAP(ca,cc,tcn),SWAP(cb,cd,tcn);
if(ca->next==cb)ca= cb,cc= cd;

/*:40*/
#line 881 "./twolevel.w"

/*41:*/
#line 919 "./twolevel.w"

if(abs(ca->seq-cc->seq)>implicit_balance_threshhold){
/*48:*/
#line 1049 "./twolevel.w"

/*49:*/
#line 1069 "./twolevel.w"

/*85:*/
#line 1944 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the left of |ca|, a=%d begin\n",ca-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:85*/
#line 1070 "./twolevel.w"

{parent_node_t*p= ca->parent;
city_node_t*lc= p->head;
city_node_t*rc= ca->prev;
city_node_t*llc= lc->prev;
parent_node_t*lp= llc->parent;
int lpr= lp->reverse,pr= p->reverse;
errorif(lp==p,"Bug");
if(lc!=ca){
/*50:*/
#line 1108 "./twolevel.w"

p->head= ca;
lp->city_link[(pr==lpr)?CITY_LINK_TAIL:CITY_LINK_HEAD]= rc;


/*:50*/
#line 1079 "./twolevel.w"

/*51:*/
#line 1142 "./twolevel.w"

{
city_node_t*i,*u= lc,*v= rc;
int succ_link,seq_inc,seq_num;
if(lpr==pr){
succ_link= LINK_NEXT;
seq_inc= 1;
seq_num= llc->seq+1;
}else{
succ_link= LINK_PREV;
seq_inc= -1;
seq_num= llc->seq-1;
/*47:*/
#line 1029 "./twolevel.w"

{
city_node_t*i= u,*done= v->next;
for(i= u;i!=done;i= i->prev){
SWAP(i->next,i->prev,tcn);
}
}

/*:47*/
#line 1154 "./twolevel.w"

}
for(i= lc;i!=rc;i= i->link[succ_link],seq_num+= seq_inc){

i->parent= lp;
i->seq= seq_num;
}
i->parent= lp;
i->seq= seq_num;
}

/*:51*/
#line 1080 "./twolevel.w"

}
}
/*86:*/
#line 1952 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the left of |ca|, a=%d end\n",ca-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:86*/
#line 1083 "./twolevel.w"


/*:49*/
#line 1050 "./twolevel.w"

/*52:*/
#line 1176 "./twolevel.w"

/*83:*/
#line 1928 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the right of |cc|, c=%d begin\n",cc-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:83*/
#line 1177 "./twolevel.w"

{parent_node_t*p= cc->parent;
city_node_t*rc= p->tail;
city_node_t*lc= cc->next;
city_node_t*rrc= rc->next;
parent_node_t*rp= rrc->parent;
int rpr= rp->reverse,pr= p->reverse;
errorif(rp==p,"Bug");
if(rc!=cc){
/*53:*/
#line 1194 "./twolevel.w"

p->tail= cc;
rp->city_link[(pr==rpr)?CITY_LINK_HEAD:CITY_LINK_TAIL]= lc;

/*:53*/
#line 1186 "./twolevel.w"

/*54:*/
#line 1216 "./twolevel.w"

{
city_node_t*i,*u= lc,*v= rc;
int succ_link,seq_inc,seq_num;
if(rpr==pr){
succ_link= LINK_NEXT;
seq_inc= 1;
seq_num= rrc->seq+u->seq-v->seq-1;
}else{
succ_link= LINK_PREV;
seq_inc= -1;
seq_num= rrc->seq+v->seq-u->seq+1;
/*47:*/
#line 1029 "./twolevel.w"

{
city_node_t*i= u,*done= v->next;
for(i= u;i!=done;i= i->prev){
SWAP(i->next,i->prev,tcn);
}
}

/*:47*/
#line 1228 "./twolevel.w"

}
for(i= lc;i!=rc;i= i->link[succ_link],seq_num+= seq_inc){

i->parent= rp;
i->seq= seq_num;
}
i->parent= rp;
i->seq= seq_num;
}


/*:54*/
#line 1187 "./twolevel.w"

}
}
/*84:*/
#line 1936 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the right of |cc|, c=%d end\n",cc-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:84*/
#line 1190 "./twolevel.w"


/*:52*/
#line 1051 "./twolevel.w"

/*55:*/
#line 1255 "./twolevel.w"

{
city_node_t*l= ca->prev,*r= cc->next;
parent_node_t*lp= l->parent,*rp= r->parent;
const int ac_rev= ca->parent->reverse;
city_node_t**inbound_l= &l->link[LINK_NEXT^lp->reverse^ac_rev],
**inbound_r= &r->link[LINK_PREV^rp->reverse^ac_rev];
errorif(*inbound_l!=ca,
"Inbound left %d != ca %d",
*inbound_l-city_node,ca-city_node);
errorif(*inbound_r!=cc,
"Inbound right %d != cc %d",
*inbound_r-city_node,cc-city_node);
SWAP(*inbound_l,*inbound_r,tcn);
SWAP(ca->prev,cc->next,tcn);
}

/*:55*/
#line 1052 "./twolevel.w"

ca->parent->reverse^= 1;
/*87:*/
#line 1960 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)printf("\t\t\tImplicit rebalance done\n");

{
const int old_reverse= reverse;
if(using_two_representations){
reverse= array_next(0)!=twolevel_next(0);
if(verbose>=200)
printf("\t\treverse %d == (an0=%d != tn0=%d)\n",reverse,array_next(0),
twolevel_next(0));
}
check_self_consistency();
if(using_two_representations){
reverse= old_reverse;
}
}
#endif

/*:87*/
#line 1054 "./twolevel.w"



/*:48*/
#line 921 "./twolevel.w"

}else{
/*44:*/
#line 962 "./twolevel.w"

{city_node_t*u= ca,*v= cc;
/*45:*/
#line 976 "./twolevel.w"

{city_node_t*i= u,*done= v->next;
int s;
for(s= v->seq,i= u;i!=done;i= i->next,s--){
i->seq= s;
}
}

/*:45*/
#line 964 "./twolevel.w"

/*46:*/
#line 1006 "./twolevel.w"

{parent_node_t*p= u->parent;
const int upn_to_v= u->prev->next==u,upp_to_v= u->prev->prev==u,
vnp_to_u= v->next->prev==v,vnn_to_u= v->next->next==v;
if(upn_to_v)u->prev->next= v;
if(upp_to_v)u->prev->prev= v;
if(vnp_to_u)v->next->prev= u;
if(vnn_to_u)v->next->next= u;
if(p->head==ca)p->head= cc;
else if(p->head==cc)p->head= ca;
if(p->tail==ca)p->tail= cc;
else if(p->tail==cc)p->tail= ca;
}


/*:46*/
#line 965 "./twolevel.w"

SWAP(u->prev,v->next,tcn);
/*47:*/
#line 1029 "./twolevel.w"

{
city_node_t*i= u,*done= v->next;
for(i= u;i!=done;i= i->prev){
SWAP(i->next,i->prev,tcn);
}
}

/*:47*/
#line 967 "./twolevel.w"

}

/*:44*/
#line 923 "./twolevel.w"

}

/*:41*/
#line 882 "./twolevel.w"


/*:39*/
#line 856 "./twolevel.w"

return;
}

/*:38*/
#line 1329 "./twolevel.w"


/*:59*/
#line 821 "./twolevel.w"

}
if(psc==psd){
/*60:*/
#line 1334 "./twolevel.w"

/*81:*/
#line 1902 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(print_at_flips!=-1&&print_at_flips<=count_flips){
if(verbose>=200)
printf(" Split the c-d segment, a=%d b=%d c=%d d=%d\n",a,b,c,d);
if(using_two_representations){
check_tours_match();
print_two_tours();
}
}
#endif

/*:81*/
#line 1335 "./twolevel.w"

{city_node_t*l,*r;parent_node_t*p= cc->parent;
if(cc->seq<cd->seq)l= cc,r= cd;
else l= cd,r= cc;
if(l->seq-p->head->seq<p->tail->seq-r->seq){
city_node_t*ca= r;
/*49:*/
#line 1069 "./twolevel.w"

/*85:*/
#line 1944 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the left of |ca|, a=%d begin\n",ca-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:85*/
#line 1070 "./twolevel.w"

{parent_node_t*p= ca->parent;
city_node_t*lc= p->head;
city_node_t*rc= ca->prev;
city_node_t*llc= lc->prev;
parent_node_t*lp= llc->parent;
int lpr= lp->reverse,pr= p->reverse;
errorif(lp==p,"Bug");
if(lc!=ca){
/*50:*/
#line 1108 "./twolevel.w"

p->head= ca;
lp->city_link[(pr==lpr)?CITY_LINK_TAIL:CITY_LINK_HEAD]= rc;


/*:50*/
#line 1079 "./twolevel.w"

/*51:*/
#line 1142 "./twolevel.w"

{
city_node_t*i,*u= lc,*v= rc;
int succ_link,seq_inc,seq_num;
if(lpr==pr){
succ_link= LINK_NEXT;
seq_inc= 1;
seq_num= llc->seq+1;
}else{
succ_link= LINK_PREV;
seq_inc= -1;
seq_num= llc->seq-1;
/*47:*/
#line 1029 "./twolevel.w"

{
city_node_t*i= u,*done= v->next;
for(i= u;i!=done;i= i->prev){
SWAP(i->next,i->prev,tcn);
}
}

/*:47*/
#line 1154 "./twolevel.w"

}
for(i= lc;i!=rc;i= i->link[succ_link],seq_num+= seq_inc){

i->parent= lp;
i->seq= seq_num;
}
i->parent= lp;
i->seq= seq_num;
}

/*:51*/
#line 1080 "./twolevel.w"

}
}
/*86:*/
#line 1952 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the left of |ca|, a=%d end\n",ca-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:86*/
#line 1083 "./twolevel.w"


/*:49*/
#line 1341 "./twolevel.w"

}else{
city_node_t*cc= l;
/*52:*/
#line 1176 "./twolevel.w"

/*83:*/
#line 1928 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the right of |cc|, c=%d begin\n",cc-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:83*/
#line 1177 "./twolevel.w"

{parent_node_t*p= cc->parent;
city_node_t*rc= p->tail;
city_node_t*lc= cc->next;
city_node_t*rrc= rc->next;
parent_node_t*rp= rrc->parent;
int rpr= rp->reverse,pr= p->reverse;
errorif(rp==p,"Bug");
if(rc!=cc){
/*53:*/
#line 1194 "./twolevel.w"

p->tail= cc;
rp->city_link[(pr==rpr)?CITY_LINK_HEAD:CITY_LINK_TAIL]= lc;

/*:53*/
#line 1186 "./twolevel.w"

/*54:*/
#line 1216 "./twolevel.w"

{
city_node_t*i,*u= lc,*v= rc;
int succ_link,seq_inc,seq_num;
if(rpr==pr){
succ_link= LINK_NEXT;
seq_inc= 1;
seq_num= rrc->seq+u->seq-v->seq-1;
}else{
succ_link= LINK_PREV;
seq_inc= -1;
seq_num= rrc->seq+v->seq-u->seq+1;
/*47:*/
#line 1029 "./twolevel.w"

{
city_node_t*i= u,*done= v->next;
for(i= u;i!=done;i= i->prev){
SWAP(i->next,i->prev,tcn);
}
}

/*:47*/
#line 1228 "./twolevel.w"

}
for(i= lc;i!=rc;i= i->link[succ_link],seq_num+= seq_inc){

i->parent= rp;
i->seq= seq_num;
}
i->parent= rp;
i->seq= seq_num;
}


/*:54*/
#line 1187 "./twolevel.w"

}
}
/*84:*/
#line 1936 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(verbose>=150)
printf("\t\t\tSplit off the end to the right of |cc|, c=%d end\n",cc-city_node);
if(using_two_representations)check_tours_match();
#endif

/*:84*/
#line 1190 "./twolevel.w"


/*:52*/
#line 1344 "./twolevel.w"

}
}
/*58:*/
#line 1312 "./twolevel.w"

psa= ca->parent->seq;
psb= cb->parent->seq;
psc= cc->parent->seq;
psd= cd->parent->seq;

/*:58*/
#line 1347 "./twolevel.w"


/*:60*//*61:*/
#line 1354 "./twolevel.w"

/*38:*/
#line 848 "./twolevel.w"

/*79:*/
#line 1877 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(print_at_flips!=-1&&print_at_flips<=count_flips){
if(verbose>=200)printf(" Handle case 1\n");
if(using_two_representations){