twolevel.w,v

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

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


1.145
date	98.07.16.21.58.55;	author neto;	state Exp;
branches;
next	1.144;

1.144
date	97.09.27.18.04.13;	author neto;	state Exp;
branches;
next	1.143;

1.143
date	97.08.15.20.19.30;	author neto;	state Exp;
branches;
next	1.142;

1.142
date	97.05.16.20.37.46;	author neto;	state Exp;
branches;
next	1.141;

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

1.140
date	97.01.21.21.55.55;	author david;	state Exp;
branches;
next	1.139;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.104
date	96.08.30.21.28.38;	author david;	state Exp;
branches;
next	1.103;

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

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

1.101
date	96.08.23.20.55.43;	author david;	state Exp;
branches;
next	;


desc
@Two-level tree implmentation of the oriented tour ADT.
@


1.145
log
@Added the LGPL notice in each file.
@
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: twolevel.w,v $
Revision 1.144  1997/09/27 18:04:13  neto
Fixed RCS log behaviour.

Revision 1.143  1997/08/15  20:19:30  neto
Added Index major section.

Revision 1.142  1997/05/16  20:37:46  neto
Change FIX INCLUDES to OS HAS BROKEN HEADERS.

Revision 1.141  1997/05/16  18:13:25  neto
Include <config.h> and "lkconfig.h"

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

Revision 1.139  1996/10/29  17:27:11  neto
add copyright notice.

Revision 1.138  96/09/19  15:41:07  neto
Removed useless const qualifiers.  Remember C passes arguments by value,
so integers are safe.

Revision 1.137  96/09/19  15:33:25  neto
Removed conflict with definition of |abs| in stdlib.h for IRIX.

Revision 1.136  96/09/18  11:40:32  neto
There is no em in CWEB, only it.
This module appears to work now.

Revision 1.135  96/09/17  14:16:34  neto
Fixed a conflict with the definition of prev and a structure in
stdio under AIX.

Revision 1.134  96/09/17  14:03:43  neto
Fixed the self-consistency check.  The group sequence numbers were assumed
to start at 0.  They can start anywhere and wrap around to 0.
Also, made using\_two\_representations conditionally compiled.

Revision 1.133  96/09/17  12:53:38  neto
Made debugging output conditional.

Revision 1.132  96/09/17  12:39:31  neto
Fixed bug 10.
Sequence numbers were screwed up on split right when current segment
was reversed but right segment was not.  

Revision 1.131  96/09/17  12:09:55  neto
Fixed the descriptions on sequence numbers for splitting left and right.
Still buggy.

Revision 1.130  96/09/17  11:55:58  neto
Fixed Bug 9.
9a: head/tail wasn't being set properly when current seg was reversed.
9a: seq numbers not set properly under same condition.

Revision 1.129  96/09/17  11:17:21  neto
Fixed bug 8a, 8b.
8a: split segment while that segment is reversed fouled up the inbound
sibling poitner.
8b: split segment while reversed set the sequence numbers rwrogng.

Revision 1.128  96/09/16  17:11:21  neto
Quashed bug 7, failure at flip number 159.
The inbound pointer addresses depend on the orientation of the ac segment.

Revision 1.127  96/09/13  17:21:39  neto
Quashed bugs 5 and 6.
5: off-by-one in splitting left and right.
6: implicit rebalancing for case 1; It was splitting right, but not
fixing the city sibling pointers, both inbound and outbound.
Now it fails on lin105 at flip number 159.

Revision 1.126  96/09/13  15:40:55  neto
Was splitting one-off, for case 3.  Ooops.

Revision 1.125  96/09/13  15:35:54  neto
Split right now updates sequence numbers properly.  I've made