nn.w,v

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

@
text
@d8 3
d159 1
a159 1
const char *nn_rcs_id="$Id: nn.w,v 1.126 1998/04/10 21:20:23 neto Exp neto $";
d528 5
@


1.126
log
@Checked that this module is safe for use by TSPs with arbitrary cost
functions.  It is.
Also, made the non-Euclidean case more efficient by using the select
function from module DSORT.  That's a lazy sorting function that only
does enough to select the appropriate subrange.
@
text
@d8 7
d156 1
a156 1
const char *nn_rcs_id="$Id: nn.w,v 1.125 1997/10/28 21:23:19 neto Exp neto $";
d514 1
a514 1
@@  We use the handy-dandy partial sorting selection function |select| from
d523 1
a523 1
select((void *)work,(size_t)n-1,sizeof(nn_entry_t),cmp_entry_compress,
@


1.125
log
@It now runs ok with nn.  It was reallocating improperly and not
initializing work next
@
text
@d8 4
d149 1
a149 1
const char *nn_rcs_id="$Id: nn.w,v 1.124 1997/10/28 20:41:08 neto Exp neto $";
d453 1
a453 1
In the future we may want to smart partitioning, like a truncated
d463 2
a464 3
		@@<Compute all the distances@@>@@;
		@@<Sort the entries@@>@@;
		@@<Copy the first |num_pure| cities@@>@@;
d494 1
a494 1
@@<Compute all the distances@@>=
d496 1
a496 1
	for (j=0;j<n;j++) {
d500 4
d507 4
a510 10
@@ Again we use a sorting function, and we may as well reuse the previous
comparison function.
@@<Sort the entries@@>=
sort((char *)work,(size_t)n,sizeof(nn_entry_t),cmp_entry_compress);


@@  Now we copy the cities from the work array to the output array.

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|.
d515 3
a517 7
@@<Copy the first |num_pure| cities@@>=
{ int r,w;
	for ( r=w=start_work; w<start_work+num_pure; r++ ) { 
		if ( work[r].city != i ) work[w++] = work[r];
	}
	work_next = w;
}
@


1.124
log
@Now it compiles.
and links.
@
text
@d8 4
d145 1
a145 1
const char *nn_rcs_id="$Id: nn.w,v 1.123 1997/10/28 20:27:50 neto Exp neto $";
d287 1
a288 1
	n = tsp_instance->n;
d293 2
d313 1
d405 1
a405 1
@@<|nn_build| variables@@>=
d408 1
a437 1
	mem_realloc(list,sizeof(int)*new_size);
d439 1
d614 19
a632 3
if ( verbose >= 25 ) {
	printf("nn: Resize list from %d elements to %d elements", 
		list_size, new_size);
@


1.123
log
@Removed FINISH signal to finish coding.
Removed old balanced quadrant material.
Added maintenance of nn max bound, that jbmr requires.
@
text
@d8 5
d141 1
a141 1
const char *nn_rcs_id="$Id: nn.w,v 1.121 1997/10/18 20:39:43 neto Exp neto $";
d234 1
a234 1
begin = new_arr_of(int *,n+1);
d316 1
a316 1
	"%d nearest neighbours specified, but there are only %d cities",num_pure,n;
d319 2
a320 1
@@<Module headers@@>=
a321 1
#include "read.h"
d387 1
a387 1
sort(work,work_next,sizeof(nn_entry_t),cmp_entry_compress);
d447 1
a447 1
	int start_work = next_work;
d472 3
a474 3
		work[next_work].city = city;
		work[next_work].len = cost(i,city);
		next_work++;
d477 1
a477 1
	for (j=start_work;j<next_work;j++) E2_unhide(work[j].city);
d511 1
a511 1
	next_work = w;
d566 1
a566 1
{ int j, start_work=next_work;
d570 3
a572 3
		work[next_work].city = city;
		work[next_work].len = cost(i,city);
		next_work++;
d575 1
a575 1
	for (j=start_work;j<next_work;j++) E2_unhide(work[j].city);
@


1.122
log
@Done coding the quadrants.
Will remove old stuff.
@
text
@d8 4
d120 3
d131 1
d151 1
d159 9
d270 2
d282 1
d288 1
a290 12


#if FINISH 


		/* Build the list for city |i| */
			/*Build a pure list for city |i|*/

			errorif(!E2_supports(tsp_instance), 
				"NN_QUADRANT requires 2D instance");
			/* Build a quadrant-balanced list for city |i|*/
#endif
a322 1
@@d min(A,B) ((A)<(B) ? (A) : (B))
d533 1
a533 1
if ( num_pure ) {
d552 1
a552 1
to be balanced; they are congruent.
d557 3
d563 1
a563 1
		const int city = E2_nn_quadrant(i,quadrant);
d578 1
a578 1
We cheat a little by redefining the |num_quadrant| variable temporarily.
d586 4
d591 3
a593 11
	for (j=0;j<num_pure;j++) {
		city = E2_nn(i);
		if ( city == -1 ) break; /* No such neighbour. */
		work[next_work].city = city;
		work[next_work].len = cost(i,city);
		next_work++;
		E2_hide(city);
	}
@@<Find up to |num_quadrant| neighbours in quadrant |quadrant|@@>@@;
{ int quadrant
}
d595 2
a596 114

@@ Building quadrant-balanced lists is more interesting.
We'd like the nearest representatives from each of the four 
quadrants surrounding city |i|, but we want equal representation from
all four quadrants.

We'd like to find them efficiently, \ie, without too many passes over the data.
The tricky part comes in the case when a quadrant doesn't have
|nn_bound/4| members.


@@<Build a quadrant-balanced list for city |i|@@>=
@@<Compute all the distances@@>@@;
@@<Sort the entries@@>@@;
{ int j, w[5], r[5], wsum;
double ix = tsp_instance->coord[i].x[0];
double iy = tsp_instance->coord[i].x[1];
@@<Copy the first |nn_bound| entries from each quadrant to their own lists@@>@@;
@@<Copy the entries from each of the lists in a balanced manner@@>@@;
@@<Sort the short list@@>@@;
@@<Copy the first |nn_bound| cities from the |work| array into |nn_list[i]|@@>@@;
}

@@ We need arrays for {\it five} regions: the four quadrants, and all cities
that lie on the same coordinates as city |i|.

@@<Module variables@@>=
static nn_entry_t **q;

@@ We need to allocate space for these quadrant arrays.
@@<Set up the array data structures@@>=
{ int j;
q = new_arr_of(nn_entry_t *,5);
for ( j=0;j<5;j++ ) {
	q[j] = new_arr_of(nn_entry_t,max_bound);
}
}

@@ 
|wsum| allows us to terminate early in the common case.  
It is always defined as |wsum = +w[1]+w[2]+w[3]+w[4]|.  

We don't count |w[0]| in this because there are likely no `zero-quadrant' 
cities.  If we did count it, then we wouldn't get early termination in
this common case:  we'd never satisfy |w[0] == nn_bound|.

We're also careful to define the quadrants in a half-closed/half-open manner.
We've partitioned the plane (and hence there is no overlap and there
are no missing pieces).

@@<Copy the first |nn_bound| entries from each quadrant to their own lists@@>=
w[0] = w[1] = w[2] = w[3] = w[4] = wsum = 0;
for ( j=0; wsum < nn_bound * 4 && j<n ; j++ ) {
	double jx = tsp_instance->coord[work[j].city].x[0];
	double jy = tsp_instance->coord[work[j].city].x[1];
	if ( jx == ix && jy == iy ) {
		if ( work[j].city != i && w[0] < nn_bound ) {
			q[0][w[0]++] = work[j];
		}
	} else if ( jx > ix && jy >= iy ) {
		if ( w[1] < nn_bound ) {
			q[1][w[1]++] = work[j];
			wsum++;
		}
	} else if ( jx <= ix && jy > iy ) {
		if ( w[2] < nn_bound ) {
			q[2][w[2]++] = work[j];
			wsum++;
		}
	} else if ( jx < ix && jy <= iy ) {
		if ( w[3] < nn_bound ) {
			q[3][w[3]++] = work[j];
			wsum++;
		}
	} else if ( jx >= ix && jy < iy ) {
		if ( w[3] < nn_bound ) {
			q[4][w[4]++] = work[j];
			wsum++;
		}
	} else {
		errorif(1,"Bad quadrant checking code!\n");
	}
}

@@ First priority goes to the zero quadrant cities.  Then we take cities
in a balanced manner from each of the other four quadrants.  

We copy them back into the |work| array.

Think of |l| as a radar sweeping beam.

@@<Copy the entries from each of the lists in a balanced manner@@>=
{ int l;
r[0] = r[1] = r[2] = r[3] = r[4] = 0;
for ( j=0;j<w[0] ; j++ ) {
	work[j] = q[0][j];
}
l=1;
while ( j < nn_bound ) {
	if ( r[l] < w[l] ) {
		work[j] = q[l][r[l]];
		r[l]++;
		j++;
	}
	l++; if ( l==5 ) l=1;
}
}

@@ The merged entres may not be in sorted order because we biased their
selection in favour of quadrant balance.  So we need to sort them in
ascending order.

@@<Sort the short list@@>=
sort((char *)work,(size_t)nn_bound,sizeof(nn_entry_t),cmp_entry);
a605 3
@@*TODO.
@@
		@@<Build a Delauney work list for city |i|@@>=
d607 1
@


1.121
log
@Restructuring so that we really do use multiple criteria.
Also, change to a single list structure with variable sublists.
@
text
@d8 4
a125 1
@@<Global variables@@>@@;
d128 1
a128 1
const char *nn_rcs_id="$Id: nn.w,v 1.120 1997/10/18 17:26:28 neto Exp neto $";
d211 1
a211 1
begin = new_arr_of(int *,n);
d230 1
a230 1
if ( begin ) { free_mem(begin);mem_deduct(sizeof(int)*n); }
d241 1
a241 1
in a particular quadrant, or a city near in the Delauney triangulation.
d247 4
a250 1
in the Delauney triangulation of the instance.
d258 1
a258 3
	errorif(num_pure==0 && num_quadrant==0 && num_delauney==0,
		"Must specify some candidates");

a259 2

	errorif(num_pure >= n-1, "num_pure = % > %d = n-1", num_pure, n-1);
d274 2
a275 2
		@@<Build the list for city |i|@@>@@;
			@@<Build a pure list for city |i|@@>@@;
d279 1
a279 1
			@@<Build a quadrant-balanced list for city |i|@@>@@;
d287 16
d366 2
a367 1
Module \module{LK} sets the |sort| pointer.
d388 1
a388 1
We promise to put nearer
d403 3
a405 1
@@ We use repeated doubling to expand the |list| array.  
d409 1
a409 1
There is no performance penalty because we access the memory we don't
d414 1
a414 1
	int new_size = last_size;
d421 1
a421 1
@@*1 The pure list.
d424 1
a424 1
Otherwise, for now we're going to use a quick and dirty method to calculate
d427 2
d447 2
a448 2
@@ Let's do the fast way first.
It uses the $k$-d search structure implemented in \module{KDTREE}.
d463 1
a463 3
	for (j=start_work;j<next_work;j++) {
		E2_unhide(work[j].city);
	}
d501 86
a586 1
#if FINISH
a587 1
#endif
d710 3
@


1.120
log
@Added support for CEIL 2D.
@
text
@d8 3
d100 1
a100 1
via a parameter passed to the construction routine.
d107 1
a107 2
Procedure |nn_build| builds the nearest neighbour arrays.  This is stored
in the global array variable |nn_list| which is indexed by city number.
d109 2
d125 1
a125 1
const char *nn_rcs_id="$Id: nn.w,v 1.119 1997/10/17 21:27:34 neto Exp neto $";
a133 1
#include <assert.h>
a139 2
@@<Exported constants@@>@@;
@@<Exported variables@@>@@;
d151 3
a153 2
The exported array, |nn_list| stores only the neighbouring cities.  This
saves a lot on space.  (For most 32-bit architectures, it saves 2/3 of
d155 2
a156 1
usually 8 bytes.)
d170 23
a192 2
@@ We need to declare the |nn_list| array.  It is an array of arrays of 
integers.
d194 3
a196 16
We also want |nn_bound|, which is the number of entries
in each city's array.
Every city will have the same number of neighbours in its |nn_list| entry,
namely |nn_bound|.

The neighbour lists themselves are stored contiguously
in the array |nn_list_pool|.

@@<Global variables@@>=
int **nn_list, *nn_list_pool;
int nn_bound;

@@ We export these variables.
@@<Exported variables@@>=
extern int **nn_list;
extern int nn_bound;
d198 2
a199 2
@@ It will be convenient to store |n|, the number of cities, and |max_bound|,
the maximum number of entries in each city's list.
d202 1
a202 1
static int n, max_bound=-1;
d204 2
a205 2
@@ These variables get allocated in the setup routine.  We will be adding
to this code later, so we separate it out in a new named section.
d207 3
a209 15
@@<Subroutines@@>=
void
nn_setup(int num_vertices, int the_max_bound) {
	@@<Set up the array data structure@@>@@;
}

@@
@@<Set up the array data structure@@>=
n = num_vertices;
max_bound = the_max_bound;
errorif(max_bound <= 0, "NN list min bound too low: %d", max_bound);
errorif(max_bound > n, "NN list max bound too high: max_bound == %d > n == %d",
	max_bound, n);
nn_list = new_arr_of(int *,n);
nn_list_pool = new_arr_of(int,n*max_bound);
d222 1
a222 1
	@@<Clean up the array data structure@@>@@;
d226 2
a227 7
@@<Clean up the array data structure@@>=
if ( nn_list ) {
	free_mem(nn_list);mem_deduct(sizeof(int *)*n);
	free_mem(nn_list_pool);mem_deduct(sizeof(int)*n*max_bound);
}
max_bound = -1;
nn_bound = -1;
d229 1
a229 1
@@ Both these procedures must be declared externally.
a230 1
void nn_setup(int num_vertices, int the_max_bound);
d236 9
a244 2
The first parameter tells it how long each city's list should be.
The second tells it whether to build a pure list or a region-oriented list.
d248 3
a250 1
nn_build(int list_len, int kind) {
d252 6
a257 4
	errorif( max_bound < 0, "nn_setup must be called before nn_build" );
	errorif( list_len > max_bound, "list_len == %d > max_bound == %d!",
		list_len, max_bound);
	nn_bound = list_len;
d259 1
d261 12
a272 3
		nn_list[i]=nn_list_pool + list_len*i;
		switch( kind ) {
		case NN_PURE:
d274 1
a274 2
			break;
		case NN_QUADRANT:
d278 1
a278 5
			break;
		default :
			errorif(1,"Invalid kind value == %d\n",kind);
		}
	}
d281 1
a281 6
@@ We need to export the special values |NN_PURE| and |NN_QUADRANT|.
@@<Exported constants@@>=
#define NN_PURE (0)