nn.c

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

#define max(A,B) ((A) >(B) ?(A) :(B) )  \

/*5:*/
#line 214 "./nn.w"

#include <config.h>
#include "lkconfig.h"
/*6:*/
#line 230 "./nn.w"

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

/*:6*/
#line 217 "./nn.w"

/*12:*/
#line 277 "./nn.w"

#include "length.h"

/*:12*//*24:*/
#line 407 "./nn.w"

#include "read.h"
#include "lk.h"


/*:24*//*36:*/
#line 531 "./nn.w"

#include "kdtree.h"

/*:36*/
#line 218 "./nn.w"

/*8:*/
#line 245 "./nn.w"

#include "nn.h"

/*:8*//*17:*/
#line 324 "./nn.w"

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

/*:17*//*40:*/
#line 573 "./nn.w"

#include "dsort.h"


/*:40*/
#line 219 "./nn.w"


/*9:*/
#line 249 "./nn.w"

int nn_max_bound;

/*:9*/
#line 221 "./nn.w"

/*11:*/
#line 268 "./nn.w"

typedef struct{
length_t len;
int city;
}nn_entry_t;

/*:11*/
#line 222 "./nn.w"

/*15:*/
#line 311 "./nn.w"

static int*list,*begin,n;

/*:15*//*28:*/
#line 442 "./nn.w"

static int list_size;

/*:28*/
#line 223 "./nn.w"

/*13:*/
#line 295 "./nn.w"

int*
nn_list(int city,int*list_len)
{
*list_len= begin[city+1]-begin[city];
return list+begin[city];
}


/*:13*//*18:*/
#line 329 "./nn.w"

void
nn_cleanup(void){
/*19:*/
#line 336 "./nn.w"

if(begin){free_mem(begin);mem_deduct(sizeof(int)*(n+1));}

/*:19*//*27:*/
#line 436 "./nn.w"

if(list){free_mem(begin);mem_deduct(sizeof(int)*list_size);}

/*:27*/
#line 332 "./nn.w"

}

/*:18*//*21:*/
#line 361 "./nn.w"

void
nn_build(int num_pure,int num_quadrant,int num_delauney)
{
/*31:*/
#line 458 "./nn.w"

kd_bin_t*work;

/*:31*/
#line 365 "./nn.w"

int i;
n= tsp_instance->n;
/*23:*/
#line 393 "./nn.w"

/*50:*/
#line 687 "./nn.w"

if(verbose>=500){
printf("nn: build nn %d nq %d del %d\n",num_pure,num_quadrant,num_delauney);
fflush(stdout);
}

/*:50*/
#line 394 "./nn.w"

errorif(num_pure<0,
"Need positive number of nearest neighbours; %d specified",num_pure);
errorif(num_quadrant<0,
"Need positive number of quadrant neighbours; %d specified",num_quadrant);
errorif(num_delauney<0,
"Need positive Delauney depth; %d specified",num_delauney);
errorif(num_pure<=0&&num_quadrant<=0&&num_delauney<=0,
"Must specify some candidates");
errorif(num_pure>=n,
"%d nearest neighbours specified, but there are only %d cities",num_pure,n);

/*:23*//*41:*/
#line 583 "./nn.w"

errorif(num_quadrant>0&&!E2_supports(tsp_instance),
"Quadrant lists supported only when 2-d trees supported",num_pure);

/*:41*//*47:*/
#line 671 "./nn.w"

errorif(num_delauney,"Delauney neighbours not supported (yet)");

/*:47*/
#line 368 "./nn.w"


/*16:*/
#line 317 "./nn.w"

begin= new_arr_of(int,n+1);
begin[0]= 0;

/*:16*//*26:*/
#line 428 "./nn.w"

{int guess_avg;
/*25:*/
#line 417 "./nn.w"

if(num_pure)
guess_avg= num_pure+num_quadrant+num_delauney;
else if(num_quadrant)
guess_avg= 4*num_quadrant+num_delauney;
else
guess_avg= 3*num_delauney*num_delauney;

/*:25*/
#line 430 "./nn.w"

list_size= guess_avg*n;
list= new_arr_of(int,list_size);
}

/*:26*//*29:*/
#line 449 "./nn.w"

work= new_arr_of(kd_bin_t,3*n);

/*:29*/
#line 370 "./nn.w"

nn_max_bound= 0;
for(i= 0;i<n;i++){
/*33:*/
#line 486 "./nn.w"

int work_next= 0;


/*:33*/
#line 373 "./nn.w"

/*52:*/
#line 702 "./nn.w"

if(verbose>=1250){
printf("nn: about to build for %d; work_next=%d list_size=%d\n",
i,work_next,list_size);
fflush(stdout);
}

/*:52*/
#line 374 "./nn.w"

/*35:*/
#line 519 "./nn.w"

if(num_pure){
int start_work= work_next;
if(E2_supports(tsp_instance)){
/*37:*/
#line 540 "./nn.w"

work_next+= E2_nn_bulk(i,num_pure,work+work_next);

/*:37*/
#line 523 "./nn.w"

}else{
/*38:*/
#line 546 "./nn.w"

{int j;
for(j= 0;j<i;j++){
kd_bin_city(&work[start_work+j])= j;
kd_bin_monotonic_len(&work[start_work+j])= cost(i,j);
}
for(j= i+1;j<n;j++){
kd_bin_city(&work[start_work+j-1])= j;
kd_bin_monotonic_len(&work[start_work+j-1])= cost(i,j);
}
}


/*:38*/
#line 525 "./nn.w"

/*39:*/
#line 567 "./nn.w"

select_range((void*)work,(size_t)n-1,sizeof(kd_bin_t),kd_bin_cmp_increasing,
0,num_pure,0);
work_next+= num_pure;

/*:39*/
#line 526 "./nn.w"

}
}

/*:35*/
#line 375 "./nn.w"

/*42:*/
#line 604 "./nn.w"

if(num_quadrant){
int quadrant;
int q_count[5]= {0,0,0,0,0};
/*43:*/
#line 632 "./nn.w"

{int j;
coord_2d*coord= tsp_instance->coord;
for(j= 0;j<work_next;j++){
const double diff_x= coord[i].x[0]-coord[j].x[0];
const double diff_y= coord[i].x[1]-coord[j].x[1];
q_count[E2_quadrant(diff_x,diff_y)]++;
}
}


/*:43*/
#line 608 "./nn.w"

if(0==q_count[1]+q_count[2]+q_count[3]+q_count[4]){
/*45:*/
#line 659 "./nn.w"

{const int num_quadrant= n-1,quadrant= 0;
/*44:*/
#line 649 "./nn.w"

work_next+= E2_nn_quadrant_bulk(i,num_quadrant,work+work_next,1<<quadrant);

/*:44*/
#line 661 "./nn.w"

}


/*:45*/
#line 610 "./nn.w"

}
for(quadrant= 1;quadrant<=4;quadrant++){
if(q_count[quadrant]<num_quadrant){
/*44:*/
#line 649 "./nn.w"

work_next+= E2_nn_quadrant_bulk(i,num_quadrant,work+work_next,1<<quadrant);

/*:44*/
#line 614 "./nn.w"

}
}
}

/*:42*/
#line 376 "./nn.w"

/*48:*/
#line 675 "./nn.w"


/*:48*/
#line 377 "./nn.w"

/*32:*/
#line 471 "./nn.w"

errorif(work_next<1,"Must have nonempty candidate list");
{
int r,w,last_city;
sort(work,(size_t)work_next,sizeof(kd_bin_t),kd_bin_cmp_increasing);
for(r= w= 0,last_city= kd_bin_city(&work[r])-1;r<work_next;r++){
if(kd_bin_city(&work[r])!=last_city)
last_city= kd_bin_city(&work[w++])= kd_bin_city(&work[r]);
}
/*34:*/
#line 499 "./nn.w"

if(begin[i]+w>list_size){
int new_size= list_size;
while(begin[i]+w>new_size)new_size*= 2;
/*49:*/
#line 679 "./nn.w"

if(verbose>=750){
printf("nn: Resize list from %d elements to %d elements; begin[i]=%d, w=%d\n",
list_size,new_size,begin[i],w);
fflush(stdout);
}

/*:49*/
#line 503 "./nn.w"

list= mem_realloc(list,sizeof(int)*new_size);
mem_deduct(sizeof(int)*list_size);
list_size= new_size;
}

/*:34*/
#line 480 "./nn.w"

for(r= 0;r<w;r++)list[begin[i]+r]= kd_bin_city(&work[r]);
begin[i+1]= begin[i]+w;
}

/*:32*/
#line 378 "./nn.w"

nn_max_bound= max(nn_max_bound,begin[i+1]-begin[i]);
}
/*30:*/
#line 454 "./nn.w"

free_mem(work);mem_deduct(sizeof(kd_bin_t)*3*n);

/*:30*/
#line 381 "./nn.w"

/*51:*/
#line 694 "./nn.w"

if(verbose>=75){
printf("nn: build nn %d nq %d del %d got %d total neighbours\n",
num_pure,num_quadrant,num_delauney,begin[n]);
fflush(stdout);
}

/*:51*/
#line 382 "./nn.w"

}

/*:21*/
#line 224 "./nn.w"

const char*nn_rcs_id= "$Id: nn.w,v 1.134 1998/10/10 19:27:39 neto Exp neto $";

/*:5*/