nn.w,v

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

head	1.134;
access
	david
	neto;
symbols
	zero-five-zero:1.134
	zero-four-seventeen:1.134
	zero-four-ten:1.129
	zero-four-nine:1.129
	zero-four-eight:1.129
	zero-four-five:1.129
	zero-four-zero:1.129;
locks
	neto:1.134;


1.134
date	98.10.10.19.27.39;	author neto;	state Exp;
branches;
next	1.133;

1.133
date	98.10.09.21.53.25;	author neto;	state Exp;
branches;
next	1.132;

1.132
date	98.10.09.21.34.52;	author neto;	state Exp;
branches;
next	1.131;

1.131
date	98.10.09.19.21.19;	author neto;	state Exp;
branches;
next	1.130;

1.130
date	98.10.09.16.47.34;	author neto;	state Exp;
branches;
next	1.129;

1.129
date	98.07.16.21.58.55;	author neto;	state Exp;
branches;
next	1.128;

1.128
date	98.04.16.15.40.03;	author neto;	state Exp;
branches;
next	1.127;

1.127
date	98.04.11.14.34.09;	author neto;	state Exp;
branches;
next	1.126;

1.126
date	98.04.10.21.20.23;	author neto;	state Exp;
branches;
next	1.125;

1.125
date	97.10.28.21.23.19;	author neto;	state Exp;
branches;
next	1.124;

1.124
date	97.10.28.20.41.08;	author neto;	state Exp;
branches;
next	1.123;

1.123
date	97.10.28.20.27.50;	author neto;	state Exp;
branches;
next	1.122;

1.122
date	97.10.25.17.43.34;	author neto;	state Exp;
branches;
next	1.121;

1.121
date	97.10.18.20.39.43;	author neto;	state Exp;
branches;
next	1.120;

1.120
date	97.10.18.17.26.28;	author neto;	state Exp;
branches;
next	1.119;

1.119
date	97.10.17.21.27.34;	author neto;	state Exp;
branches;
next	1.118;

1.118
date	97.09.27.18.06.21;	author neto;	state Exp;
branches;
next	1.117;

1.117
date	97.08.15.20.18.25;	author neto;	state Exp;
branches;
next	1.116;

1.116
date	97.05.16.21.16.24;	author neto;	state Exp;
branches;
next	1.115;

1.115
date	97.05.16.18.11.41;	author neto;	state Exp;
branches;
next	1.114;

1.114
date	97.05.16.18.09.40;	author neto;	state Exp;
branches;
next	1.113;

1.113
date	97.02.11.15.58.26;	author neto;	state Exp;
branches;
next	1.112;

1.112
date	97.01.22.15.18.31;	author david;	state Exp;
branches;
next	1.111;

1.111
date	97.01.21.21.55.55;	author david;	state Exp;
branches;
next	1.110;

1.110
date	96.12.02.15.31.37;	author neto;	state Exp;
branches;
next	1.109;

1.109
date	96.08.23.16.36.44;	author david;	state Exp;
branches;
next	1.108;

1.108
date	96.08.15.14.13.21;	author neto;	state Exp;
branches;
next	1.107;

1.107
date	96.08.15.13.32.02;	author neto;	state Exp;
branches;
next	1.106;

1.106
date	96.08.14.13.36.08;	author neto;	state Exp;
branches;
next	1.105;

1.105
date	96.08.07.15.20.35;	author neto;	state Exp;
branches;
next	1.104;

1.104
date	96.07.29.17.10.35;	author neto;	state Exp;
branches;
next	1.103;

1.103
date	96.07.15.18.32.56;	author david;	state Exp;
branches;
next	1.102;

1.102
date	96.07.15.16.50.10;	author david;	state Exp;
branches;
next	1.101;

1.101
date	96.05.30.13.24.38;	author neto;	state Exp;
branches;
next	1.100;

1.100
date	96.05.29.11.13.19;	author neto;	state Exp;
branches;
next	1.2;

1.2
date	96.03.15.16.00.02;	author neto;	state Exp;
branches;
next	1.1;

1.1
date	96.03.04.13.54.52;	author neto;	state Exp;
branches;
next	;


desc
@Nearest neighbour list construction.
@


1.134
log
@Fixed the code for quadrant zero.  It *can* check the quadrant counts.
@
text
@


\noindent Copyright \copyright 1994, 1995, 1996, 1997, 1998 David Neto
\smallskip

\noindent 
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.
\smallskip

\noindent 
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.
\smallskip

\noindent   
   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the
   Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA  02111-1307, USA.
\smallskip

\noindent   
   You may contact David Neto via email at {\tt netod@@@@acm.org}, or with
   greater latency at
\smallskip
\noindent{\obeylines
     Department of Computer Science
     University of Toronto
     10 King's College Rd.
     Toronto, Ontario
     M5S 3G4
     Canada
}
\medskip


\noindent\hbox{}\hrule\hbox{}\penalty-1000
\vskip0.5cm\relax



@@i webdefs.w
@@i types.w


{\obeylines
$Log: nn.w,v $
Revision 1.133  1998/10/09 21:53:25  neto
Must always look for quadrant 0 cities...

Revision 1.132  1998/10/09 21:34:52  neto
Report number of vertices found.

Revision 1.131  1998/10/09 19:21:19  neto
This works with bulk load

Revision 1.130  1998/10/09 16:47:34  neto
Added changes need for bulk neighbour searches.

Revision 1.129  1998/07/16 21:58:55  neto
Added the LGPL notice in each file.

Revision 1.128  1998/04/16 15:40:03  neto
Need to include dsort.h to get the select range prototype.

Revision 1.127  1998/04/11 14:34:09  neto
Duh.  select is a Unix system call.  Renamed my select to select\_range

Revision 1.126  1998/04/10 21:20:23  neto
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.

Revision 1.125  1997/10/28  21:23:19  neto
It now runs ok with nn.  It was reallocating improperly and not
initializing work next

Revision 1.124  1997/10/28  20:41:08  neto
Now it compiles.
and links.

Revision 1.123  1997/10/28  20:27:50  neto
Removed FINISH signal to finish coding.
Removed old balanced quadrant material.
Added maintenance of nn max bound, that jbmr requires.

Revision 1.122  1997/10/25 17:43:34  neto
Done coding the quadrants.
Will remove old stuff.

Revision 1.121  1997/10/18 20:39:43  neto
Restructuring so that we really do use multiple criteria.
Also, change to a single list structure with variable sublists.

Revision 1.120  1997/10/18 17:26:28  neto
Added support for CEIL 2D.

Revision 1.119  1997/10/17  21:27:34  neto
Convert coord2d to x[0] and x[1].
Fixed an apparent initialization bug in quadrant search.

Revision 1.118  1997/09/27 18:06:21  neto
Fixed RCS log behaviour.

Revision 1.117  1997/08/15  20:18:25  neto
Added Index major section.

Revision 1.116  1997/05/16  21:16:24  neto
Got rid of an unused variable and scope.

Revision 1.115  1997/05/16  18:11:41  neto
Break locks by david and neto.
Include <config.h> and "lkconfig.h"

Revision 1.114  1997/05/16  18:09:40  neto
Include <config.h> and lkconfig.h

Revision 1.113  1997/02/11  15:58:26  neto
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.

Revision 1.112  1997/01/22  15:18:31  david
Simplified wording. Fixed a wordo.

Revision 1.111  1997/01/21  21:55:55  david
Added standard copyright notice by including copyrt.w

Revision 1.110  96/12/02  15:31:37  neto
Add copyright notice.

Revision 1.109  1996/08/23  16:36:44  david
Changed "Module types" to "Module type definitions" for consistency
with other modules.

Revision 1.108  96/08/15  14:13:21  neto
Fixed usage to match prototype of sort()

Revision 1.107  96/08/15  13:32:02  neto
Must export nn\_build

Revision 1.106  96/08/14  13:36:08  neto
Use sort instead of qsort.

Revision 1.105  96/08/07  15:20:35  neto
Make qsort optionally perserve the order of equals

Revision 1.104  96/07/29  17:10:35  neto
Added an RCS id, and it compiles.

}

@@*Nearest neighbour lists.
This module constructs the nearest neighbour lists that are used by
efficient implementations of the Lin-Kernighan algorithm.  
For a discussion of this feature, see the chapter by Johnson and McGeoch.
In the next few paragraphs I will describe the ideas contained in that
discussion.

The LK algorithm often looks for a nearest neighbour tour to switch an
edge to.  For efficiency's sake, it would like to examine the neighbours
of a given city in increasing distance order from that city.  The most
natural structure for this is an array of neighbours of that city,
sorted by distance.  Then the LK algorithm searches sequentially from
the beginning of the array looking for candidates.

@@ The above scheme takes quadratic space, which is not practical for
very large instances.  So we compromise, storing only the first $k$
nearest neighbours.  Once the near neighbour search exhausts this
list, we just give up.   This also saves us time: we don't waste time
searching in unlikely places.

@@ This truncated scheme works well on randomly distributed instances --- 
whether those with random edge lengths, or those which consist of
cities placed randomly in a Euclidean space.  However, on more structured
geometric instances, such as those taken from TSPLIB, we get better results
if we reflect some of that structure in the neighbour lists.

The main idea is to ensure that there is representation on this list
from the various regions that surround a particular city.  For example,
in a 2-D instance,
we might want to include the ten nearest neighbours from each of the
four surrounding quadrants.  This changes the makeup of the neighbour
list dramatically if the city is on the edge of a cluster.

This module supports both pure and region-oriented nearest neighbour lists
via parameters passed to the construction routine.

@@ This module provides the following interface.

Procedures 
|nn_setup| and |nn_cleanup| are the usual intialization and shutdown routines.

Procedure |nn_build| builds the nearest neighbour arrays. 

Procedure |nn_list| returns the nearest neighbour list for a given 
city.

Global variable |nn_max_bound| is the length of the longest neighbour
list.

@@ The outline of this module is as follows:
@@c
#include <config.h>
#include "lkconfig.h"
@@<System headers@@>@@;
@@<Early module headers@@>@@;
@@<Module headers@@>@@;

@@<Global variables@@>@@;
@@<Module type definitions@@>@@;
@@<Module variables@@>@@;
@@<Subroutines@@>@@;
const char *nn_rcs_id="$Id: nn.w,v 1.133 1998/10/09 21:53:25 neto Exp neto $";

@@ We will be using many routines from external libraries.  The interfaces
to those routines are described in the following headers.

@@<System headers@@>=
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

@@ The exported interface is contained in the \file{nn.h} header file,
which has the following form.

@@(nn.h@@>=
extern const char *nn_rcs_id;
@@<Exported variables@@>@@;
@@<Exported subroutines@@>@@;

@@ To ensure consistency between the interface and the implementation,
we include our own header.
@@<Module headers@@>=
#include "nn.h"

@@ Variable |nn_max_bound| is an integer.
@@<Global variables@@>=
int nn_max_bound;

@@
@@<Exported variables@@>=
extern int nn_max_bound;


@@ When making up the nearest neighbour lists, this module needs to associate
a neighbouring city with the distance to that city.
We declare a local type for this purpose.

However, during actual use
we store only the neighbouring cities.  
This saves a lot on space.  For most 32-bit architectures, it saves 2/3 of
the space, because the city number is 4 bytes, and the length is 
usually 8 bytes.  In fact the nearest neighbour lists take up more
space than any other data structure in LK.

@@<Module type definitions@@>=
typedef struct {
	length_t len;
	int city;
} nn_entry_t;

@@ We've used the |length_t| type which is defined in the \file{length.h}
module.

@@<Early module headers@@>=
#include "length.h"

@@ Because there are multiple disjoint criteria for a city to belong
to a neighbour list, the lengths of the lists will vary.  
We save space by not having dummy entries.  

Variable |list|  is an array of integers into which all the lists
of neighbours are stored, one after another.  To mark the list boundaries,
we use array |begin|. 
In particular |begin[i]| is the index into |list|
at which the candidate list for city $i$ begins.  Array |begin| has |n+1|
entries: |begin[n]| points to just past the end of the list for the last 
city.  In other words, the candidate list for city |i| runs from
|list[begin[i]]| through |list[begin[i+1]-1]|, inclusive.

Without going farther, we can already code the |nn_list| function.

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


@@
@@<Exported subroutines@@>=
int *nn_list(int city, int *list_len);

@@ We need to declare the |list| and |begin| arrays.  
It will be convenient to store |n|, the number of cities.

@@<Module variables@@>=
static int *list, *begin, n;

@@ Array |begin| has |n+1| entries. We'll see later how to allocate
the |list| array.

@@<Set up the array data structures@@>=
begin = new_arr_of(int,n+1);
begin[0]=0;

@@ We need the interface to the memory module.  
While we're at it, let's get the error module as well.

@@<Module headers@@>=
#include "error.h"
#include "memory.h"

@@ These arrays should be deallocated when we clean up.
@@<Subroutines@@>=
void
nn_cleanup(void) {
	@@<Clean up the array data structures@@>@@;
}

@@
@@<Clean up the array data structures@@>=
if ( begin ) { free_mem(begin);mem_deduct(sizeof(int)*(n+1)); }

@@ The cleanup procedure must be declared externally.
@@<Exported subroutines@@>=
void nn_cleanup(void);

@@*Building the neighbour lists.
Procedure |nn_build| builds the nearest neighbour arrays.  

There is one parameter for each kind of neighbour we might be