nn.w,v

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

#define NN_QUADRANT (1)

@@ We also export the subroutine.
d283 1
a283 1
void nn_build(int list_len, int kind);
d285 1
a285 1
@@ We need to import the instance |tsp_instance|.
d288 56
d345 57
a401 3
@@ If the cost function is based on coordinates, then
we can use the $k$-d search structure that we've already built 
elsewhere.  This speeds things up considerably.
d408 10
a417 7
@@<Build a pure list for city |i|@@>=
if (E2_supports(tsp_instance)) {
	@@<Use $k$-d tree to find nearest neighbours@@>@@;
} else {
	@@<Compute all the distances@@>@@;
	@@<Sort the entries@@>@@;
	@@<Copy the first |nn_bound| cities from the |work| array into |nn_list[i]|@@>@@;
d420 1
a420 2
@@ The instance type |tsp_instance_t| is defined by the \module{READ} module.
The |E2| routines for 2-d trees are in the \module{KDTREE} module.
a421 1
#include "read.h"
d429 1
a429 1
@@<Use $k$-d tree to find nearest neighbours@@>=
d431 8
a438 3
	int j;
	for (j=0;j<nn_bound;j++) {
		E2_hide(nn_list[i][j]=E2_nn(i));
d440 2
a441 2
	for (j=0;j<nn_bound;j++) {
		E2_unhide(nn_list[i][j]);
d445 2
a446 18

@@*Brute force.
We need to declare the |work| array.
@@<Module variables@@>=
static nn_entry_t *work;

@@ And allocate space for it.
@@<Set up the array data structure@@>=
work = new_arr_of(nn_entry_t,n);

@@ And deallocate it.
@@<Clean up the array data structure@@>=
free_mem(work);

@@ Computing all the distances is easy.

The |cost| function is provided by 
the \module{read} module.  We've already included that interface.
d451 2
a452 2
		work[j].city = j;
		work[j].len = cost(i,j);
a455 4
@@ 
We use the sorting routine pointed to by |sort|; it must have
the same signature as the |qsort| standard library function.
Module \module{LK} sets the |sort| pointer.
d457 2
d460 1
a460 1
sort((char *)work,(size_t)n,sizeof(nn_entry_t),cmp_entry);
a461 16
@@ We do have to provide a comparison function.
@@<Module subroutines@@>=
static int 
cmp_entry(const void *a, const void *b) {
	length_t ad = ((const nn_entry_t *)a)->len;
	length_t bd = ((const nn_entry_t *)b)->len;
	if ( ad < bd ) return -1;
	else if ( ad > bd ) return 1;
	else return 
#if defined(QSORT_DETERMINATE)
		(int)(((nn_entry_t *)a)-((nn_entry_t *)b))
#else
				0
#endif
				;
}
d468 4
a471 1
@@<Copy the first |nn_bound| cities from the |work| array into |nn_list[i]|@@>=
d473 2
a474 3
	for ( r=w=0 ;w<nn_bound; r++ ) {
		if ( work[r].city != i )
			nn_list[i][w++] = work[r].city;
d476 1
d479 4
d512 1
a512 1
@@<Set up the array data structure@@>=
d596 8
@


1.119
log
@Convert coord2d to x[0] and x[1].
Fixed an apparent initialization bug in quadrant search.
@
text
@d8 4
d121 1
a121 1
const char *nn_rcs_id="$Id: nn.w,v 1.118 1997/09/27 18:06:21 neto Exp neto $";
d262 2
a263 2
			errorif(tsp_instance->edge_weight_type != EUC_2D,
				"NN_QUADRANT requires EUC_2D instance");
d295 1
a295 2
switch ( tsp_instance->edge_weight_type ) {
case EUC_2D:
d297 1
a297 2
	break;
default:
d303 2
a304 1
@@ The constant |EUC_2D| is defined by the \module{READ} module.
d307 1
a324 3
@@ We need the interface to the $k$-d tree routines.
@@<Module headers@@>=
#include "kdtree.h"
@


1.118
log
@Fixed RCS log behaviour.
@
text
@d8 3
d117 1
a117 1
const char *nn_rcs_id="$Id: nn.w,v 1.117 1997/08/15 20:18:25 neto Exp neto $";
d403 2
a404 2
double ix = tsp_instance->coord[i].x;
double iy = tsp_instance->coord[i].x;
d441 2
a442 2
	double jx = tsp_instance->coord[work[j].city].x;
	double jy = tsp_instance->coord[work[j].city].y;
@


1.117
log
@Added Index major section.
@
text
@d6 5
a10 1
{\obeylines$Log: nn.w,v $
d114 1
a114 1
const char *nn_rcs_id="$Id: nn.w,v 1.116 1997/05/16 21:16:24 neto Exp neto $";
@


1.116
log
@Got rid of an unused variable and scope.
@
text
@d7 3
d110 1
a110 1
const char *nn_rcs_id="$Id: nn.w,v 1.115 1997/05/16 18:11:41 neto Exp neto $";
d495 2
@


1.115
log
@Break locks by david and neto.
Include <config.h> and "lkconfig.h"
@
text
@d7 4
d107 1
a107 1
const char *nn_rcs_id="$Id: nn.w,v 1.114 1997/05/16 18:09:40 neto Exp neto $";
a213 1
{ int i;
a219 1
}
@


1.114
log
@Include <config.h> and lkconfig.h
@
text
@d7 3
d103 1
a103 1
const char *nn_rcs_id="$Id: nn.w,v 1.113 1997/02/11 15:58:26 neto Exp neto $";
@


1.113
log
@Reduced the number of calls to malloc.  This is also a bit
smarter about compacting the memory used when list\_len < max\_bound.
Luk pointed out the problem with malloc to me.
@
text
@d7 5
d89 2
d100 1
a100 1
const char *nn_rcs_id="$Id: nn.w,v 1.112 1997/01/22 15:18:31 david Exp david $";
@


1.112
log
@Simplified wording. Fixed a wordo.
@
text
@d7 3
d93 1
a93 1
const char *nn_rcs_id="$Id: nn.w,v 1.111 1997/01/21 21:55:55 david Exp david $";
d147 3
d151 1
a151 1
int **nn_list;
d182 1
a182 5
{ int i;
for ( i=0; i<n ; i++ ) {
	nn_list[i] = new_arr_of(int,max_bound);
}
}
d202 2
a203 4
	for ( i=0;i<n;i++ ) {
		free_mem(nn_list[i]);
	}
	free_mem(nn_list);
d224 1
a224 1
	errorif ( max_bound < 0, "nn_setup must be called before nn_build" );
d230 1
@


1.111
log
@Added standard copyright notice by including copyrt.w
@
text
@d6 4
a9 1
{\obeylines$Log:	nn.w,v $
d44 1
a44 1
natural structure for this is build an array of neighbours of that city,
d60 1
a60 1
The principle idea is to ensure that there is representation on this list
d90 1
a90 1
const char *nn_rcs_id="$Id: nn.w,v 1.110 96/12/02 15:31:37 neto Exp $";
@


1.110
log
@Add copyright notice.
@
text
@d1 1
a4 1
\copyright 1996 David Neto
d6 3
a8 1
All rights reserved, etc.
a9 1
{\obeylines$Log: nn.w,v $
d87 1
a87 1
const char *nn_rcs_id="$Id: nn.w,v 1.109 1996/08/23 16:36:44 david Exp david $";
@


1.109
log
@Changed "Module types" to "Module type definitions" for consistency
with other modules.
@
text
@d4 9
a12 1
{\obeylines$Log:	nn.w,v $
d86 1
a86 1
const char *nn_rcs_id="$Id: nn.w,v 1.108 96/08/15 14:13:21 neto Exp $";
@


1.108
log
@Fixed usage to match prototype of sort()
@
text
@d5 3
d73 1
a73 1
@@<Module types@@>@@;
d78 1
a78 1
const char *nn_rcs_id="$Id: nn.w,v 1.107 96/08/15 13:32:02 neto Exp $";
d112 1
a112 1
@@<Module types@@>=
@


1.107
log
@Must export nn\_build
@
text
@d5 3
d75 1
a75 1
const char *nn_rcs_id="$Id: nn.w,v 1.106 96/08/14 13:36:08 neto Exp $";
d319 1
a319 1
sort((char *)work,n,sizeof(nn_entry_t),cmp_entry);
d325 2
a326 2
	length_t ad = ((nn_entry_t *)a)->len;
	length_t bd = ((nn_entry_t *)b)->len;
d463 1
a463 1
qsort((char *)work,nn_bound,sizeof(nn_entry_t),cmp_entry);
@


1.106
log
@Use sort instead of qsort.
@
text
@d5 3
d72 1
a72 1
const char *nn_rcs_id="$Id: nn.w,v 1.105 96/08/07 15:20:35 neto Exp $";
d231 4
@


1.105
log
@Make qsort optionally perserve the order of equals
@
text
@d5 3
d69 1
a69 1
const char *nn_rcs_id="$Id: nn.w,v 1.104 96/07/29 17:10:35 neto Exp $";
d303 5
a307 1
@@ We'll just use the |qsort| library routine.
d309 1
a309 1
qsort((char *)work,n,sizeof(nn_entry_t),cmp_entry);
@


1.104
log
@Added an RCS id, and it compiles.
@
text
@d4 4
a7 1
{\obeylines$Log$
d66 1
a66 1
const char *nn_rcs_id="$Id$";
d312 7
a318 1
	else return 0;
@


1.103
log
@Fixed for compiling. I forgot the EUC\_2D case label.
@
text
@a0 1

d4 3
d63 1
d78 1
@


1.102
log
@Added smart kd search tree .
@
text
@d234 1
d243 3
a245 1

a280 2
But we do need access to the |cost| function,
which is provided by the \module{read} module.
d282 2
a283 3

@@<Early module headers@@>=
#include "read.h"
d285 1
a285 1
@@ @@<Compute all the distances@@>=
@


1.101
log
@Only free the nn_list array elements if nn_list itself is non-null.
@
text
@d3 1
d31 1
a31 1
The principal idea is to ensure that there is representation on this list
d223 5
a227 1
@@ For now, we're going to use a quick and dirty method for calculating 
d233 30
a262 3
@@<Compute all the distances@@>@@;
@@<Sort the entries@@>@@;
@@<Copy the first |nn_bound| cities from the |work| array into |nn_list[i]|@@>@@;
d264 2
a265 1
@@ We need to declare the |work| array.
@


1.100
log
@This version works.  
Needs improvement:
	command-line switches
	faster tabu check
	allow Papadimitriou tabu rule
	faster preprocessing
	different candidate lists
@
text
@d140 1
d167 5
a171 2
for ( i=0;i<n;i++ ) {
	free_mem(nn_list[i]);
a172 1
free_mem(nn_list);
@


1.2
log
@Initial implementation of LK.  This is buggy.
@
text
@@


1.1
log
@Initial revision
@
text
@d55 1
a73 1
@@<Exported types@@>@@;
d83 3
a85 4
@@ The procedure that searches the nearest neigbhour lists needs both the
city number and the distance from the given city to that city.  The nearest
neighbour list for a given city is an array of these pairs.  We need to 
declare this type.
d87 6
a92 1
@@<Exported types@@>=
d105 1
a105 1
|nn_entry_t| entries.  
d113 1
a113 1
nn_entry_t **nn_list;
d118 1
a118 1
extern nn_entry_t **nn_list;
d142 1
a142 1
nn_list = new_arr_of(nn_entry_t *,n);
d145 1
a145 1
	nn_list[i] = new_arr_of(nn_entry_t,max_bound);
a222 2
The only tricky part is to skip city |i| itself.  This is only tricky
because there may be multiple cities with distance zero to city |i|.
d227 1
a227 6
{ int r,w;
	for ( r=w=0 ;w<nn_bound; r++ ) {
		if ( work[r].city != i )
			nn_list[i][w++] = work[r];
	}
}
d272 13
d304 1
d371 2
d379 1
a379 1
	nn_list[i][j] = q[0][j];
d384 1
a384 1
		nn_list[i][j] = q[l][r[l]];
d397 1
a397 1
qsort((char *)nn_list[i],nn_bound,sizeof(nn_entry_t),cmp_entry);
@