construct.w,v

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

head	1.141;
access
	david
	neto;
symbols
	zero-five-zero:1.141
	zero-four-seventeen:1.141
	zero-four-ten:1.139
	zero-four-nine:1.139
	zero-four-eight:1.139
	zero-four-five:1.132
	zero-four-zero:1.132;
locks
	neto:1.141;


1.141
date	98.10.10.19.26.57;	author neto;	state Exp;
branches;
next	1.140;

1.140
date	98.09.25.23.15.51;	author neto;	state Exp;
branches;
next	1.139;

1.139
date	98.08.09.20.53.12;	author neto;	state Exp;
branches;
next	1.138;

1.138
date	98.08.09.20.36.27;	author neto;	state Exp;
branches;
next	1.137;

1.137
date	98.08.09.19.09.42;	author neto;	state Exp;
branches;
next	1.136;

1.136
date	98.08.09.18.06.35;	author neto;	state Exp;
branches;
next	1.135;

1.135
date	98.08.08.22.45.38;	author neto;	state Exp;
branches;
next	1.134;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.116
date	97.01.21.21.55.55;	author david;	state Exp;
branches;
next	1.115;

1.115
date	97.01.21.16.43.37;	author david;	state Exp;
branches;
next	1.114;

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

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

1.112
date	96.08.16.13.04.35;	author neto;	state Exp;
branches;
next	1.111;

1.111
date	96.08.15.14.42.25;	author neto;	state Exp;
branches;
next	1.110;

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

1.109
date	96.08.15.13.00.11;	author neto;	state Exp;
branches;
next	1.108;

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

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

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

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

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

1.103
date	96.08.01.14.25.29;	author neto;	state Exp;
branches;
next	1.102;

1.102
date	96.07.29.17.09.55;	author neto;	state Exp;
branches;
next	1.101;

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

1.100
date	96.05.29.11.13.05;	author neto;	state Exp;
branches;
next	1.4;

1.4
date	96.05.22.17.10.10;	author neto;	state Exp;
branches;
next	1.3;

1.3
date	96.05.22.17.08.30;	author neto;	state Exp;
branches;
next	1.2;

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

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


desc
@Construct an initial tour.
@


1.141
log
@Put the non-E2 case matching construction into verbose section.
@
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: construct.w,v $
Revision 1.140  1998/09/25 23:15:51  neto
Fixed two bugs:
1) I wasn't updating inv unsaturated properly.
2) I fixed a subtle bug with getting maximum weight city in the queue for
a given start point x.  (The max value was initialized wrong.)
Check values of e->len.

Revision 1.139  1998/08/09 20:53:12  neto
Removed some debugging output.
Made random vs. deterministic a compile-time difference rather than
a runtime test.

Revision 1.138  1998/08/09 20:36:27  neto
Fixed the exhausted queue problem with matching.
(I forgot to break out of the loop!.

Revision 1.137  1998/08/09 19:09:42  neto
Better randomization through checking and discarding reversed copies
of same edge when withdrawing from queue.

Revision 1.136  1998/08/09 18:06:35  neto
I believe this is fixed now.
Now I will reorganized to remove run-time ``do random'' tests.

Revision 1.135  1998/08/08 22:45:38  neto
I believe I've got the bug.
But it must wait for Sunday.

Revision 1.134  1998/08/08 22:17:57  neto
Added better debuggging output.

Revision 1.133  1998/08/08 20:51:40  neto
First cut at implementing randomized greedy heuristic.
But this bombs on lin105 (both det and rand) with "exhausted priority
queue".

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

Revision 1.131  1998/06/19 14:55:53  neto
Use binary heap priority queue in place of heavier weight dictionaries.

Revision 1.130  1998/04/16 16:02:03  neto
webbug fixed:  the code for initializing nn work array came after its
first use.  Doh.

Revision 1.129  1998/04/16 15:23:20  neto
Now it ctangles and compiles with no warnings.  (But you ask, does it work?)

Revision 1.128  1998/04/11 17:39:52  neto
Possibly finished coding the non-Euclidean changes.
But company is coming, and I must go.

Revision 1.127  1998/04/11 17:24:40  neto
Added much queue handling for the non-Euclidean case, including refreshing
the list, maintaining the unsaturated cities, and the farthest in queue
array.

Revision 1.126  1998/04/11 15:43:28  neto
Convert nn link to nn link pool because non-Euclidean case is better
with multiple possible neighbours in the queue.  Still converting
to allow non-Euclidean.

Revision 1.125  1998/01/23  20:09:22  neto
The mate structure doesn't need to be initialized before it is initialized!

Revision 1.124  1998/01/23  19:30:56  neto
Fixed to compile.  Also match construct is now more appropriately
construct matching.

Revision 1.123  1997/12/20 22:33:02  neto
Fixed another preprocessor booboo.

Revision 1.122  1997/12/20 22:29:52  neto
Fixed preprocessor booboo.

Revision 1.121  1997/12/20 22:23:59  neto
First crack at greedy matching heuristic.

Revision 1.120  1997/09/27 18:05:36  neto
Fixed RCS log behaviour.

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

Revision 1.118  1997/06/17  21:23:52  neto
Added two index entries.

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

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

Revision 1.115  1997/01/21  16:43:37  david
Added canonical tour back in.

Revision 1.114  96/12/02  15:27:15  neto
Added copyright notice.

Revision 1.113  96/08/20  11:34:39  neto
tx, ty might have been used uninitialized if n<2.  Added an n<3 guard
and assignments of dummy values to tx, ty.

Revision 1.112  96/08/16  13:04:35  neto
Added fixincludes.

Revision 1.111  96/08/15  14:42:25  neto
Fixed a const-related warning.

Revision 1.110  96/08/15  14:20:08  neto
Mmore prototypes.

Revision 1.109  96/08/15  13:00:11  neto
Make it pass -Wall

Revision 1.108  96/08/02  16:28:00  neto
Make sure different edges with equal lengths are both inserted.
(Fix the comparison function).
If we add an edge from x and x isn't saturated, then we should insert
a new edge from x into the priority queue.

Revision 1.107  96/08/02  14:38:10  neto
Now it compiles.  But greedy does not work.  It exhausts the priority
queue.

Revision 1.106  96/08/02  14:10:35  neto
Made heur\_param a long.

Revision 1.105  96/08/02  13:59:38  neto
Finished coding greedy.  Must now compile and check.

Revision 1.104  96/08/01  16:26:02  neto
More on Greedy.

Revision 1.103  96/08/01  14:25:29  neto
Random tour in this module.
Don't use upper.w
Edited description of Greedy.

Revision 1.102  96/07/29  17:09:55  neto
Fixed to compile.

Revision 1.101  96/07/29  16:19:42  neto
Added *\_rcs\_id.
Made sure RCS log is activated within this file.

}

@@*Constructing a starting tour.
Lin-Kernighan is a local search procedure; it repeatedly looks to improve
a given tour.  It needs a starting tour to work on;  this module
builds one.

The outline of this module is as follows:

@@c 
#include <config.h>
#include "lkconfig.h"
@@<System headers@@>@@;
@@<Module headers@@>@@;
@@<Module type definitions@@>@@;
@@<Module subroutines@@>@@;
@@<Subroutines@@>@@;
const char *construct_rcs_id = "$Id: construct.w,v 1.140 1998/09/25 23:15:51 neto Exp neto $";

@@ The exported interface to is contained in the \file{construct.h} header
file.  It has the following form.

@@(construct.h@@>=
#if !defined(_CONSTRUCT_H_)
#define _CONSTRUCT_H_
@@<Headers we need to define our own interface@@>@@;
extern const char *construct_rcs_id;@@;
@@<Exported constants@@>@@;
@@<Exported subroutines@@>@@;
#endif

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

@@ The |construct| procedure does all the work.  Given 
the number of
cities 
$n$, 
and the globally-visible distance function |cost|, it builds
a tour and writes it into the preallocated buffer space that |tour| points
to.

The caller chooses from among several construction heuristics via the
|heuristic| parameter.  Some of these heuristics use the |long| integer-valued
parameter |heur_param|.

Some heuristics are randomized.  The random numbers are drawn from
a stream initialized with parameter |random_seed|.


@@<Subroutines@@>=
length_t
construct(const int n, int *tour, const int heuristic, const long heur_param,
const long random_seed)
{
	switch(heuristic) {
	@@<Heuristic alternatives@@>@@;
	default: errorif(1,"Unknown heuristic: %d",heuristic);
	}
	return (length_t)0;	/* Satisfy GCC's {\tt -Wall} option. */
}