twolevel.c

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

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 1355 "./twolevel.w"


/*:61*/
#line 824 "./twolevel.w"

}
/*62:*/
#line 1363 "./twolevel.w"

/*82:*/
#line 1915 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(print_at_flips!=-1&&print_at_flips<=count_flips){
if(verbose>=125)printf(" flip a sequence of segments\n");
if(using_two_representations){
check_tours_match();
print_two_tours();
}
}
#endif


/*:82*/
#line 1364 "./twolevel.w"

errorif((psa==psb||psc==psd),"psa %d==psb %d or psc %d == psd %d",psa,psb,psc,psd);
/*63:*/
#line 1403 "./twolevel.w"

if(psb==psd){
SWAP(a,b,ti),SWAP(c,d,ti),
SWAP(ca,cb,tcn),SWAP(cc,cd,tcn),
SWAP(psa,psb,ti),SWAP(psc,psd,ti);
}else if(psa!=psc){
if(normp(psa+1)==psb){
const int dmb= psd-psb,amc= psa-psc;
if(normm(dmb)<normm(amc))
SWAP(a,b,ti),SWAP(c,d,ti),
SWAP(ca,cb,tcn),SWAP(cc,cd,tcn),
SWAP(psa,psb,ti),SWAP(psc,psd,ti);
}else{
const int bmd= psb-psd,cma= psc-psa;
if(normm(bmd)<normm(cma))
SWAP(a,b,ti),SWAP(c,d,ti),
SWAP(ca,cb,tcn),SWAP(cc,cd,tcn),
SWAP(psa,psb,ti),SWAP(psc,psd,ti);
}
}

/*:63*/
#line 1366 "./twolevel.w"

/*64:*/
#line 1433 "./twolevel.w"

{
parent_node_t*u,*v;
if(normp(psa+1)==psb)u= cc->parent,v= ca->parent;
else u= ca->parent,v= cc->parent;
/*65:*/
#line 1455 "./twolevel.w"

{
parent_node_t*tpn;
int ur,vr;
city_node_t**u_outbound,**v_outbound,**u_inbound,**v_inbound,*u_first,*v_last;
ur= u->reverse;
vr= v->reverse;
u_first= u->city_link[ur^CITY_LINK_HEAD];
v_last= v->city_link[vr^CITY_LINK_TAIL];
u_outbound= u_first->link+(ur^LINK_PREV);
v_outbound= v_last->link+(vr^LINK_NEXT);
u_inbound= (*u_outbound)->link+
((*u_outbound)->link[LINK_NEXT]==u_first?LINK_NEXT:LINK_PREV);
v_inbound= (*v_outbound)->link+
((*v_outbound)->link[LINK_NEXT]==v_last?LINK_NEXT:LINK_PREV);

SWAP(*u_inbound,*v_inbound,tcn);
SWAP(*u_outbound,*v_outbound,tcn);
u->prev->next= v;
v->next->prev= u;
SWAP(u->prev,v->next,tpn);
}

/*:65*/
#line 1438 "./twolevel.w"

/*66:*/
#line 1511 "./twolevel.w"

{
const int upv= u->seq+v->seq,upvn= normp(upv);
parent_node_t*i,*done= v->next,*tpn;
errorif(upv<u->seq||upv<v->seq,
"We've overflowed the integer representation");
for(i= u;i!=done;i= i->prev){
const int new_seq= upvn-i->seq;
i->seq= normm(new_seq);
i->reverse^= 1;
SWAP(i->next,i->prev,tpn);
}
}

/*:66*/
#line 1439 "./twolevel.w"

}


/*:64*/
#line 1367 "./twolevel.w"


/*:62*/
#line 826 "./twolevel.w"

}

/*:36*//*69:*/
#line 1573 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
void
twolevel_debug_setup(const int num_vertices,const int start_seg_size){
array_setup(num_vertices);
twolevel_setup(num_vertices,start_seg_size);
using_two_representations= 1;
}

void
twolevel_debug_cleanup(void){
twolevel_cleanup();
array_cleanup();
using_two_representations= 0;
}

void
twolevel_debug_set(int const*tour){
if(verbose>=100){printf("set\n");}
array_set(tour);
twolevel_set(tour);
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_tours_match();
}
#endif

/*:69*//*72:*/
#line 1622 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
static int
check_self_consistency(void)
{int i,c,cnt,an_error= 0,cnpt,gs,s,tail_s,lgs,ls,ng= 0,ph,pt;
const int first_city= 
parent_node[0].city_link[CITY_LINK_HEAD^parent_node[0].reverse]
-city_node;
parent_node_t*p;
if(verbose>=150)
printf("Checking twolevel tour consistency, reverse==%d\n",reverse);
tail_s= ls= city_node[twolevel_prev(first_city)].seq;
lgs= parent_node[0].seq-1;
for(i= 0,c= first_city;i<n&&!an_error;i++,c= cnt){
if(c==first_city&&i>0){an_error= 1;printf("Not a tour\n");}
cnt= twolevel_next(c);
cnpt= twolevel_prev(cnt);
if(cnpt!=c){
an_error= 1;
printf("twolevel next/prev inconsistent pos %d city %d next: %d, nextprev: %d\n",
i,c,cnt,cnpt);
}
p= city_node[c].parent;
if(lgs!=(gs= p->seq)){
ng++;
if(gs!=((lgs+1)%num_groups)){
an_error= 1;
printf("Parent sequence numbers %d to %d not consecutive\n",
lgs,gs);
}
lgs= gs;
if(tail_s!=ls){
an_error= 1;
printf("Seq of last city in segment %d doesn't seq of \"tail\"%d\n",
ls,tail_s);
}
tail_s= p->city_link[CITY_LINK_TAIL^p->reverse]->seq;
ls= city_node[c].seq;
if(c!=(ph= p->city_link[CITY_LINK_HEAD^p->reverse]-city_node)){
an_error= 1;
printf("First city in segment %d isn't \"head\"%d\n",
c,ph);
}
{const cp= twolevel_prev(c);
const parent_node_t*pp= city_node[cp].parent;
if(cp!=(pt= pp->city_link[CITY_LINK_TAIL^pp->reverse]-city_node)){
an_error= 1;
printf("Last city %d in previous segment isn't \"tail\" %d; step %d\n",
cp,pt,i);
}
}
}else{
const int s_should_be= ls+(p->reverse?-1:1);
s= city_node[c].seq;
if(s!=s_should_be){
an_error= 1;
printf("Sequence number %d of %d should be %d\n",
s,c,s_should_be);
}
ls= s;
}
}
if(ng!=num_groups){
an_error= 1;
printf("Only counted %d groups; should be %d groups\n",
ng,num_groups);
}
if(c!=first_city){
an_error= 1;
printf("Not a tour: didn't loop back from %d to itself\n",
first_city);
}
if(an_error)print_two_tours();
errorif(an_error,"Incorrect state for two-level trees.");
return 1;
}

static int
check_tours_match(void)
{int i,c,cna,cnt,an_error= 0;
const int first_city= 
parent_node[0].city_link[CITY_LINK_HEAD^parent_node[0].reverse]
-city_node;
check_self_consistency();
if(verbose>=150)printf("Checking tours match\n");
for(i= 0,c= first_city;i<n&&!an_error;i++,c= cnt){
if(c==first_city&&i>0){an_error= 1;printf("Not a tour\n");}
cna= reverse?array_prev(c):array_next(c);
cnt= twolevel_next(c);
if(cna!=cnt){
an_error= 1;
printf("next's don't match: position %d city %d array: %d, twolevel: %d\n",
i,c,cna,cnt);
}
}
if(c!=first_city){
an_error= 1;
printf("Not a tour: didn't loop back from %d to itself\n",
first_city);
}
if(an_error)print_two_tours();
errorif(an_error,"Tours don't match.");
return 1;
}
#endif

/*:72*//*74:*/
#line 1737 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
static int
print_two_tours(void){
int i,ca,ct,amore= 1,tmore= 1,
first_city= parent_node[0].city_link[CITY_LINK_HEAD^parent_node[0].reverse]
-city_node;
char a[100],t[100];
for(i= 0,ca= ct= first_city;i<n;i++){
if(i==0)printf("Tour: Array Two-level\n");
sprintf(a,"%d",ca);
sprintf(t,"%d",ct);
printf("\t%4d %7s %7s",i,amore?a:" ",tmore?t:" ");
if(tmore){
printf("\tseq=%3d p=%p g=%2d %s h=%4d t=%4d",
city_node[ct].seq,
city_node[ct].parent,
city_node[ct].parent->seq,
city_node[ct].parent->reverse?"r":" ",
city_node[ct].parent->head-city_node,
city_node[ct].parent->tail-city_node);
}
printf("\n");
ca= reverse?array_prev(ca):array_next(ca);
ct= twolevel_next(ct);
amore&= ca!=first_city;
tmore&= ct!=first_city;
}
return 1;
}
#endif

/*:74*//*75:*/
#line 1773 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
int
twolevel_debug_next(int a){
const int tn= twolevel_next(a);
const int an= reverse?array_prev(a):array_next(a);
const int tnp= twolevel_prev(tn);
if(verbose>=125)printf("next(%d)\n",a);
errorif(tn!=an&&check_tours_match(),
"next: twolevel_next(%d)=%d, array_%s(%d)=%d",
a,tn,reverse?"prev":"next",an);
errorif(tnp!=a&&check_tours_match(),
"next(%d)=%d, prev(%d)=%d",a,tn,tn,tnp);
return tn;
}

int
twolevel_debug_prev(int a){
const int tp= twolevel_prev(a);
const int ap= reverse?array_next(a):array_prev(a);
const int tpn= twolevel_next(tp);
if(verbose>=125)printf("prev(%d)\n",a);
errorif(tp!=ap&&check_tours_match(),
"next: twolevel_next(%d)=%d, array_%s(%d)=%d",
a,tp,reverse?"next":"prev",ap);
errorif(tpn!=a&&check_tours_match(),
"prev(%d)=%d, next(%d)=%d",a,tp,tp,tpn);
return tp;
}
#endif

/*:75*//*76:*/
#line 1811 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
int
twolevel_debug_between(int a,int b,int c){
const int ab= reverse?array_between(c,b,a):array_between(a,b,c);
const int tb= twolevel_between(a,b,c);
if(verbose>=125)printf("between(%d,%d,%d)\n",a,b,c);
errorif(ab!=tb&&check_tours_match()&&print_two_tours(),
"between(%d,%d,%d) don't match: twolevel=%d array=%d",
a,b,c,tb,ab);
return tb;
}
#endif

/*:76*//*77:*/
#line 1832 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
void
twolevel_debug_flip(int a,int b,int c,int d){
if(verbose>=110)printf("flip(%d,%d,%d,%d) %d\n",a,b,c,d,++count_flips);
twolevel_flip(a,b,c,d);
if(reverse)array_flip(b,a,d,c);
else array_flip(a,b,c,d);
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_tours_match();
{int an_error= 0;
const int an= twolevel_next(a),ap= twolevel_prev(a);
const int bn= twolevel_next(b),bp= twolevel_prev(b);
const int cn= twolevel_next(c),cp= twolevel_prev(c);
const int dn= twolevel_next(d),dp= twolevel_prev(d);
if(an==d){
if(dp!=a)an_error= 1,printf("dp!=a\n");
if(bn!=c)an_error= 1,printf("bn!=c\n");
if(cp!=b)an_error= 1,printf("cp!=b\n");
}else if(ap==d){
if(dn!=a)an_error= 1,printf("dn!=a\n");
if(bp!=c)an_error= 1,printf("bp!=c\n");
if(cn!=b)an_error= 1,printf("cn!=b\n");
}
if(an_error){
print_two_tours();
errorif(1,"Bug");
}
}
}
#endif


/*:77*/
#line 302 "./twolevel.w"

const char*twolevel_rcs_id= "$Id: twolevel.w,v 1.145 1998/07/16 21:58:55 neto Exp neto $";

/*:3*/