kdtree.h

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

/*2:*/
#line 370 "./kdtree.w"

#if !defined(_KDTREE_H_)
#define _KDTREE_H_
extern const char*kdtree_rcs_id;
/*73:*/
#line 1711 "./kdtree.w"

typedef struct{
double cost_squared;
int city;
}kd_bin_t;

/*:73*/
#line 374 "./kdtree.w"

/*11:*/
#line 617 "./kdtree.w"

extern int kd_bucket_cutoff;




/*:11*//*19:*/
#line 751 "./kdtree.w"

extern int kd_bbox_skip;

/*:19*/
#line 375 "./kdtree.w"

/*74:*/
#line 1718 "./kdtree.w"

#define kd_bin_city(bin_pointer) ((bin_pointer)->city)
#define kd_bin_monotonic_len(bin_pointer) ((bin_pointer)->cost_squared)

/*:74*//*81:*/
#line 1829 "./kdtree.w"

static const int E2_qmask_array[3][3]= {{0x02,0x02,0x10},{0x04,0x01,0x10},{0x04,0x08,0x08}};
static const int E2_quadrant_array[3][3]= {{1,1,4},{2,0,4},{2,3,3}};
#define kd_sgn(X) ((X)<0?0:((X)>0?2:1))

#define E2_quadrant(diffx,diffy) (E2_quadrant_array[kd_sgn(diffx)][kd_sgn(diffy)])
#define E2_quadrant_mask(diffx,diffy) (E2_qmask_array[kd_sgn(diffx)][kd_sgn(diffy)])

/*:81*//*90:*/
#line 2066 "./kdtree.w"

#define E2_nn(c) (E2_nn_quadrant(c,0x1f))

/*:90*//*94:*/
#line 2129 "./kdtree.w"

#define E2_nn_bulk(c,num_wanted,buffer) (E2_nn_quadrant_bulk(c,num_wanted,buffer,0x1f))

/*:94*/
#line 376 "./kdtree.w"

/*4:*/
#line 468 "./kdtree.w"

void E2_create(tsp_instance_t*tsp);
void E2_destroy(void);
void E2_hide(int i);
void E2_unhide(int i);
void E2_hide_all(void);
void E2_unhide_all(void);
int E2_nn_func(int i);
int E2_nn_quadrant(int i,const int qmask);
int E2_nn_bulk_func(int i,int num_wanted,kd_bin_t*buffer);
int E2_nn_quadrant_bulk(int i,int num_wanted,kd_bin_t*buffer,int qmask);
int kd_bin_cmp_increasing(const void*a,const void*b);
int kd_bin_cmp_decreasing(const void*a,const void*b);
void E2_frnn(int i,double rad,void(*proc)(int j));
void E2_set_radius(int i,double r);
void E2_ball_search(int i,void(*proc)(int j));


/*:4*//*5:*/
#line 489 "./kdtree.w"

int E2_supports(tsp_instance_t*tsp);


/*:5*//*106:*/
#line 2363 "./kdtree.w"

void E2_postscript_show(FILE*);

/*:106*/
#line 377 "./kdtree.w"

#endif

/*:2*/