twolevel.c

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

#define normp(X) ((X) <num_groups?(X) :(X) -num_groups) 
#define normm(X) ((X) <0?(X) +num_groups:(X) ) 
/*3:*/
#line 293 "./twolevel.w"

#include <config.h>
#include "lkconfig.h"
/*4:*/
#line 308 "./twolevel.w"

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

/*:4*//*73:*/
#line 1729 "./twolevel.w"

#include <stdio.h>
#if defined(OS_HAS_BROKEN_HEADERS)
#include "fixincludes.h"
#endif


/*:73*/
#line 296 "./twolevel.w"

/*6:*/
#line 322 "./twolevel.w"

#include "twolevel.h"

/*:6*//*15:*/
#line 446 "./twolevel.w"

#include "error.h"
#include "memory.h"

/*:15*//*70:*/
#line 1603 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
#include "array.h"
#endif

/*:70*/
#line 297 "./twolevel.w"


/*9:*/
#line 382 "./twolevel.w"


#define LINK_PREV 0
#define LINK_NEXT 1
#define prev link[LINK_PREV]
#define next link[LINK_NEXT]
#define CITY_LINK_HEAD 0
#define CITY_LINK_TAIL 1
#define head city_link[CITY_LINK_HEAD]
#define tail city_link[CITY_LINK_TAIL]

typedef struct parent_node_s{
int seq;
int reverse;
struct parent_node_s*link[2];
struct city_node_s*city_link[2];
}parent_node_t;

typedef struct city_node_s{
struct parent_node_s*parent;
int seq;
struct city_node_s*link[2];
}city_node_t;

/*:9*/
#line 299 "./twolevel.w"

/*10:*/
#line 412 "./twolevel.w"

static parent_node_t*parent_node= NULL;
static city_node_t*city_node= NULL;


/*:10*//*17:*/
#line 480 "./twolevel.w"

static int groupsize,num_groups;

/*:17*//*20:*/
#line 506 "./twolevel.w"

static int n= 0;

/*:20*//*43:*/
#line 934 "./twolevel.w"

static int implicit_balance_threshhold;



/*:43*//*68:*/
#line 1565 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
static int reverse;
#endif

/*:68*//*71:*/
#line 1609 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
static int using_two_representations;
#endif

/*:71*//*88:*/
#line 1980 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
static int count_flips= -1,print_at_flips= -1;
extern int verbose;
#endif


/*:88*/
#line 300 "./twolevel.w"

/*78:*/
#line 1869 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
static int check_tours_match(void);
static int check_self_consistency(void);
static int print_two_tours(void);
#endif

/*:78*/
#line 301 "./twolevel.w"

/*11:*/
#line 420 "./twolevel.w"

void
twolevel_setup(const int num_vertices,const int start_seg_size){
/*14:*/
#line 440 "./twolevel.w"

city_node= new_arr_of(city_node_t,num_vertices);

/*:14*//*18:*/
#line 493 "./twolevel.w"

groupsize= start_seg_size;
num_groups= num_vertices/groupsize;
parent_node= new_arr_of(parent_node_t,num_groups);


/*:18*//*21:*/
#line 510 "./twolevel.w"

n= num_vertices;

/*:21*//*42:*/
#line 930 "./twolevel.w"

implicit_balance_threshhold= (3*groupsize)/4;

/*:42*/
#line 423 "./twolevel.w"

}

/*:11*//*12:*/
#line 427 "./twolevel.w"

void
twolevel_cleanup(void){
/*16:*/
#line 451 "./twolevel.w"

free_mem(city_node);


/*:16*//*19:*/
#line 501 "./twolevel.w"

free_mem(parent_node);

/*:19*//*22:*/
#line 514 "./twolevel.w"

n= 0;

/*:22*/
#line 430 "./twolevel.w"

}

/*:12*//*24:*/
#line 575 "./twolevel.w"

void
twolevel_set(int const*tour){
int i,j,group,num_big_groups= n%num_groups,base_group_size= n/num_groups;
for(i= 0,group= 0;i<n;group++){
const int this_group_size= base_group_size+(group<num_big_groups);
parent_node[group].head= city_node+tour[i];
parent_node[group].tail= city_node+tour[i+this_group_size-1];
parent_node[group].reverse= 0;
parent_node[group].seq= group;
parent_node[group].prev= parent_node+((group-1+num_groups)%num_groups);
parent_node[group].next= parent_node+((group+1)%num_groups);
for(j= 0;j<this_group_size;j++,i++){
city_node[tour[i]].parent= parent_node+group;
city_node[tour[i]].seq= j;
city_node[tour[i]].prev= city_node+tour[(i-1+n)%n];
city_node[tour[i]].next= city_node+tour[(i+1)%n];
}
}
errorif(i!=n||group!=num_groups,"Bug in my 'rithmetic");
}

/*:24*//*31:*/
#line 659 "./twolevel.w"

int
twolevel_next(int a){
const city_node_t*ca= city_node+a;
return(ca->link[LINK_NEXT^ca->parent->reverse])-city_node;
}

int
twolevel_prev(int a){
const city_node_t*ca= city_node+a;
return(ca->link[LINK_PREV^ca->parent->reverse])-city_node;
}

/*:31*//*33:*/
#line 729 "./twolevel.w"

int
twolevel_between(int a,int b,int c){
const city_node_t*ca= city_node+a,*cb= city_node+b,*cc= city_node+c;
const parent_node_t*pa= ca->parent,*pb= cb->parent,*pc= cc->parent;
const int sa= ca->seq-pa->head->seq,sb= cb->seq-pb->head->seq,sc= cc->seq-pc->head->seq;

if(pa==pb)
if(pa==pc)
if(pa->reverse)
return(sa>=sb?((sb>=sc)|(sc>sa)):((sb>=sc)&(sc>sa)));
else return(sa<=sb?((sb<=sc)|(sc<sa)):((sb<=sc)&(sc<sa)));
else
return(sa==sb)|(pa->reverse^(sa<sb));
else
if(pa==pc)
return(sa!=sc)&(pa->reverse^(sa>sc));
else
if(pb==pc)
return(sb==sc)|((pb->reverse)^(sb<sc));
else{
const int psa= pa->seq,psb= pb->seq,psc= pc->seq;
return(psa<=psb?((psb<=psc)|(psc<psa)):((psb<=psc)&(psc<psa)));
}
}

/*:33*//*36:*/
#line 805 "./twolevel.w"

#define SWAP(x,y,t)  ((t)= (x),(x)= (y),(y)= (t))
#define abs(x) ((x)<0?-(x):(x))
void
twolevel_flip(int a,int b,int c,int d){
city_node_t*ca= city_node+a,*cb= city_node+b,
*cc= city_node+c,*cd= city_node+d,*tcn;
int psa= ca->parent->seq,psb= cb->parent->seq,
psc= cc->parent->seq,psd= cd->parent->seq,ti;
#if defined(TWOLEVEL_FLIP_CHECK_PRECONDITION)
errorif(a!=twolevel_next(b),"a != twolevel_next(b)");
errorif(d!=twolevel_next(c),"d != twolevel_next(c)");
#endif

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

if(psa==psb){
/*57:*/
#line 1287 "./twolevel.w"

/*80:*/
#line 1889 "./twolevel.w"

#if defined(TWOLEVEL_DEBUG)
if(print_at_flips!=-1&&print_at_flips<=count_flips){
if(verbose>=200)
printf(" Split the a-b 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

/*:80*/
#line 1288 "./twolevel.w"

{city_node_t*l,*r;parent_node_t*p= ca->parent;
if(ca->seq<cb->seq)l= ca,r= cb;
else l= cb,r= ca;
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;