decluster.c

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

}
T->edge[next_edge]= *short_bridge;
total_len+= short_bridge->cost;
E2_hide(out);
is_in_component[out]= 1;

bridge[in].city[1]= E2_nn(in);
bridge[in].cost= cost(in,bridge[in].city[1]);
pq_insert(bridge_pq,bridge+in);
bridge[out].city[0]= out;
bridge[out].city[1]= E2_nn(out);
bridge[out].cost= cost(out,bridge[out].city[1]);
pq_insert(bridge_pq,bridge+out);
}
pq_destroy(bridge_pq);
free_mem(is_in_component);mem_deduct(n*sizeof(char));
free_mem(bridge);mem_deduct(n*sizeof(decluster_edge_t));
E2_unhide_all();
}

/*:26*/
#line 773 "./decluster.w"

}else{
int*from= new_arr_of(int,n);
length_t*dist= new_arr_of(length_t,n);
total_len= 
decluster_mst_custom(T,from,dist,cost);
free_mem(from);mem_deduct(n*sizeof(int));
free_mem(dist);mem_deduct(n*sizeof(length_t));
}
return total_len;
}

/*:22*//*23:*/
#line 805 "./decluster.w"

length_t
decluster_mst_custom(
decluster_tree_t*T,int*from,length_t*dist,length_t(*cost)(int,int))
{
int i,next_edge,short_to,n;
length_t short_len,total_len= 0;
from[0]= -1;
errorif(T==NULL||T->n<0,"Bug!");
n= T->n+1;
for(i= 1,short_len= INFINITY,short_to= -1;i<n;i++){
from[i]= 0;
dist[i]= cost(0,i);
if(short_len>dist[i]){
short_len= dist[i];
short_to= i;
}
}
for(next_edge= 0;next_edge<n-1;next_edge++){
/*24:*/
#line 832 "./decluster.w"

if(verbose>=1000)printf("decluster_mst_plain: adding edge (%d,%d) "length_t_spec"\n",
from[short_to],short_to,length_t_pcast(short_len));
T->edge[next_edge].city[0]= short_to;
T->edge[next_edge].city[1]= from[short_to];
T->edge[next_edge].cost= short_len;
total_len+= short_len;
from[short_to]= -1;

/*:24*/
#line 824 "./decluster.w"

/*25:*/
#line 856 "./decluster.w"

{
const int new_inside_city= short_to;
short_len= INFINITY;
for(i= 1;i<n;i++){
length_t d;
if(from[i]==-1)continue;
d= cost(new_inside_city,i);
if(d<dist[i]){
dist[i]= d;
from[i]= new_inside_city;
}
if(dist[i]<short_len){
short_len= dist[i];
short_to= i;
}
}
}

/*:25*/
#line 825 "./decluster.w"

}
return total_len;
}


/*:23*//*29:*/
#line 985 "./decluster.w"

/*28:*/
#line 970 "./decluster.w"

int
decluster_edge_cmp(const void*a,const void*b)
{
length_t len_diff= ((const decluster_edge_t*)a)->cost
-((const decluster_edge_t*)b)->cost;
return len_diff<0?-1:
(len_diff>0?
1:
((int)(((const decluster_edge_t*)a)-((const decluster_edge_t*)b))));
}

/*:28*/
#line 986 "./decluster.w"



/*:29*//*35:*/
#line 1064 "./decluster.w"

void
decluster_preprocess(decluster_tree_t*T)
{
errorif(T->n!=n-1,"decluster_preprocess: MST size %d should be %d",T->n,n-1);
if(T_prime==NULL)/*30:*/
#line 1017 "./decluster.w"

if(T_prime==NULL||T_prime->n!=n+n-1){
int i;
/*32:*/
#line 1036 "./decluster.w"

if(T_prime){
const int n= T_prime->n;
free_mem(T_prime->edge);mem_deduct(n*sizeof(decluster_edge_t));
free_mem(T_prime);mem_deduct(sizeof(decluster_tree_t));
T_prime= NULL;
}

/*:32*/
#line 1020 "./decluster.w"

T_prime= new_of(decluster_tree_t);
T_prime->n= n+n-1;
T_prime->edge= new_arr_of(decluster_edge_t,n+n-1);
for(i= 0;i<n;i++){
T_prime->edge[i].child[0]= NO_CHILD;
T_prime->edge[i].child[1]= NO_CHILD;
T_prime->edge[i].cost= 0;
}
}

/*:30*/
#line 1069 "./decluster.w"

/*38:*/
#line 1113 "./decluster.w"

{int r,w,i,*component= new_arr_of(int,n+n);

for(i= 0;i<n;i++)component[i]= NO_PARENT;
sort(T->edge,(size_t)(n-1),sizeof(decluster_edge_t),decluster_edge_cmp);
print_tree(T,"T");
for(r= 0,w= n;r<n-1;r++,w++){
T_prime->edge[w]= T->edge[r];
/*40:*/
#line 1146 "./decluster.w"

{int i,here,parent;
component[w]= NO_PARENT;
for(i= 0;i<2;i++){
here= T_prime->edge[w].city[i];
while((parent= component[here])!=NO_PARENT){
component[here]= w;
here= parent;
}
component[here]= w;
T_prime->edge[w].child[i]= here;
}
}

/*:40*/
#line 1121 "./decluster.w"

}
free_mem(component);mem_deduct((n+n)*sizeof(int));
}

/*:38*/
#line 1070 "./decluster.w"

print_tree(T_prime,"T_prime");
/*52:*/
#line 1446 "./decluster.w"

{
int i;
for(i= n;i<n+n-1;i++)digest[i].cost= T_prime->edge[i].cost;
}

/*:52*/
#line 1072 "./decluster.w"

/*53:*/
#line 1459 "./decluster.w"

{int*queue= new_arr_of(int,n+n-1),r,w,i,ch;
digest[n+n-2].level= 0;
queue[0]= n+n-2;
for(r= 0,w= 1;r<w;r++){
const int here= queue[r],cur_level= digest[here].level+1;
for(i= 0;i<2;i++)if((ch= T_prime->edge[here].child[i])!=NO_CHILD){
digest[ch].level= cur_level;
queue[w++]= ch;
}
}
free_mem(queue);mem_deduct((n+n-1)*sizeof(int));
}


/*:53*/
#line 1073 "./decluster.w"

/*54:*/
#line 1482 "./decluster.w"

{
int*preorder= new_arr_of(int,n+n-1),*size= new_arr_of(int,n+n-1);
int preorder_number= 0;
#define DFS_INLABEL
/*55:*/
#line 1512 "./decluster.w"

{
int*in= new_arr_of(int,n+n-1),*cur_child= new_arr_of(int,n+n-1);
int top,here,next_child;

top= 0;
in[top]= n+n-2;
cur_child[top]= -1;

while(top>=0){
here= in[top];
switch(cur_child[top]){
case-1:
/*56:*/
#line 1547 "./decluster.w"

#if defined(DFS_INLABEL)
preorder[here]= ++preorder_number;
#endif

/*:56*//*59:*/
#line 1599 "./decluster.w"

#if defined(DFS_ASCENDANT)
if(top==0){
digest[here].ascendant= digest[here].inlabel;
}else{
const int p= in[top-1],ap= digest[p].ascendant,ip= digest[p].inlabel;
if(digest[here].inlabel==ip)digest[here].ascendant= ap;
else{
const int ih= digest[here].inlabel;
digest[here].ascendant= ap+((ih^(ih-1))&ih);
}
}
#endif

/*:59*/
#line 1525 "./decluster.w"

case 0:
next_child= T_prime->edge[here].child[++cur_child[top]];
if(next_child!=NO_CHILD){

in[++top]= next_child;
cur_child[top]= -1;
}
break;
default:
/*57:*/
#line 1573 "./decluster.w"

#if defined(DFS_INLABEL)
{const int child0= T_prime->edge[here].child[0],
child1= T_prime->edge[here].child[1];
size[here]= 1+(child0==NO_CHILD?0:size[child0])
+(child1==NO_CHILD?0:size[child1]);
}
{
const unsigned int last= preorder[here]+size[here]-1,
i= floor_log_2((preorder[here]-1)^last);
digest[here].inlabel= hi_mask(i)&last;
}
#endif

/*:57*/
#line 1535 "./decluster.w"


top--;
}
}
free_mem(in);free_mem(cur_child);
mem_deduct(2*(n+n-1)*sizeof(int));
}

/*:55*/
#line 1487 "./decluster.w"

#undef DFS_INLABEL

free_mem(preorder);free_mem(size);
mem_deduct(2*(n+n-1)*sizeof(int));
}


/*:54*/
#line 1074 "./decluster.w"

/*58:*/
#line 1590 "./decluster.w"

#define DFS_ASCENDANT
/*55:*/
#line 1512 "./decluster.w"

{
int*in= new_arr_of(int,n+n-1),*cur_child= new_arr_of(int,n+n-1);
int top,here,next_child;

top= 0;
in[top]= n+n-2;
cur_child[top]= -1;

while(top>=0){
here= in[top];
switch(cur_child[top]){
case-1:
/*56:*/
#line 1547 "./decluster.w"

#if defined(DFS_INLABEL)
preorder[here]= ++preorder_number;
#endif

/*:56*//*59:*/
#line 1599 "./decluster.w"

#if defined(DFS_ASCENDANT)
if(top==0){
digest[here].ascendant= digest[here].inlabel;
}else{
const int p= in[top-1],ap= digest[p].ascendant,ip= digest[p].inlabel;
if(digest[here].inlabel==ip)digest[here].ascendant= ap;
else{
const int ih= digest[here].inlabel;
digest[here].ascendant= ap+((ih^(ih-1))&ih);
}
}
#endif

/*:59*/
#line 1525 "./decluster.w"

case 0:
next_child= T_prime->edge[here].child[++cur_child[top]];
if(next_child!=NO_CHILD){

in[++top]= next_child;
cur_child[top]= -1;
}
break;
default:
/*57:*/
#line 1573 "./decluster.w"

#if defined(DFS_INLABEL)
{const int child0= T_prime->edge[here].child[0],
child1= T_prime->edge[here].child[1];
size[here]= 1+(child0==NO_CHILD?0:size[child0])
+(child1==NO_CHILD?0:size[child1]);
}
{
const unsigned int last= preorder[here]+size[here]-1,
i= floor_log_2((preorder[here]-1)^last);
digest[here].inlabel= hi_mask(i)&last;
}
#endif

/*:57*/
#line 1535 "./decluster.w"


top--;
}
}
free_mem(in);free_mem(cur_child);
mem_deduct(2*(n+n-1)*sizeof(int));
}

/*:55*/
#line 1592 "./decluster.w"

#undef DFS_ASCENDANT

/*:58*/
#line 1075 "./decluster.w"

/*60:*/
#line 1632 "./decluster.w"

{
int i,j,*head= new_arr_of(int,n+n),*parent= new_arr_of(int,n+n-1);
for(i= 0;i<n+n;i++)head[i]= -1;
for(i= 0;i<n+n-1;i++){
const int ii= digest[i].inlabel,hii= head[ii];
if(hii==-1||digest[i].level<digest[hii].level)head[ii]= i;
}
for(i= 0;i<n+n-1;i++)parent[i]= NO_PARENT,parent_of_head[i]= NO_PARENT;

for(i= 0;i<n+n-1;i++)
for(j= 0;j<2;j++){
const int child= T_prime->edge[i].child[j];
if(child!=NO_CHILD)parent[child]= i;
}
for(i= 0;i<n+n-1;i++)
parent_of_head[digest[i].inlabel]= parent[head[digest[i].inlabel]];
/*89:*/
#line 2228 "./decluster.w"

#if DECLUSTER_DEBUG
{
int i;
printf("parent list:\n");
for(i= 0;i<n+n-1;i++)
printf(" %5d   %12d\n",i,parent[i]);
}
#endif

/*:89*/
#line 1649 "./decluster.w"

/*90:*/
#line 2239 "./decluster.w"

#if DECLUSTER_DEBUG
{
int i;
printf("head list:\n");
for(i= 1;i<n+n;i++)
printf(" %5d   %12d\n",i,head[i]);
}
#endif

/*:90*/
#line 1650 "./decluster.w"


free_mem(head);mem_deduct((n+n)*sizeof(int));
free_mem(parent);mem_deduct((n+n-1)*sizeof(int));
}

/*:60*/
#line 1076 "./decluster.w"

/*88:*/
#line 2209 "./decluster.w"

#if DECLUSTER_DEBUG
{
int i;
printf("digest:   %12s %12s %12s %s\n",
"level","inlabel","ascendant","cost");
for(i= 0;i<n+n-1;i++){
printf("%9d %12d %12d %12d "length_t_spec"\n",
i,digest[i].level,digest[i].inlabel,digest[i].ascendant,
length_t_pcast(digest[i].cost));
}
printf("parent_of_head: (indexed by inlabel number)\n");
for(i= 1;i<n+n;i++){
printf(" %5d   %12d\n",i,parent_of_head[i]);
}
}
#endif

/*:88*/
#line 1077 "./decluster.w"

if(decluster_discard_topology_tree){
/*32:*/
#line 1036 "./decluster.w"

if(T_prime){
const int n= T_prime->n;
free_mem(T_prime->edge);mem_deduct(n*sizeof(decluster_edge_t));
free_mem(T_prime);mem_deduct(sizeof(decluster_tree_t));
T_prime= NULL;
}

/*:32*/
#line 1079 "./decluster.w"

}
}

/*:35*//*68:*/
#line 1815 "./decluster.w"

length_t
decluster_d(int u,int v)
{
return digest[decluster_lca(u,v)].cost;
}

/*:68*//*70:*/
#line 1830 "./decluster.w"

decluster_tree_t*
decluster_topology_tree(void)
{
return T_prime;
}

/*:70*//*71:*/
#line 1838 "./decluster.w"

void
decluster_print_tree(FILE*out,decluster_tree_t const*t,const char*name)
{
if(t){
int n= t->n,i;
const char*print_name= name?name:"";
errorif(t==NULL,"decluster_print_tree: given a NULL tree\n");
errorif(n<0,"decluster_print_tree: tree %s size %d < 0\n",print_name,n);
fprintf(out,"%s->n==%d\n",print_name,t->n);
for(i= 0;i<n;i++){
fprintf(out," %d (%d,%d) "length_t_spec"\n",
i,
t->edge[i].city[0],t->edge[i].city[1],
length_t_pcast(t->edge[i].cost));
}
}else{
fprintf(out,"Tree %s is NULL\n",name);
fprintf(out,"For more data, make sure variable decluster_discard_topology_tree is zero)\n");
}
}

/*:71*/
#line 542 "./decluster.w"

const char*decluster_rcs_id= "$Id: decluster.w,v 1.62 1998/10/16 20:41:41 neto Exp neto $";


/*:9*/