decluster.w,v

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

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


1.62
date	98.10.16.20.41.41;	author neto;	state Exp;
branches;
next	1.61;

1.61
date	98.10.10.21.27.40;	author neto;	state Exp;
branches;
next	1.60;

1.60
date	98.09.18.17.32.01;	author neto;	state Exp;
branches;
next	1.59;

1.59
date	98.07.16.21.58.55;	author neto;	state Exp;
branches;
next	1.58;

1.58
date	98.06.19.16.23.39;	author neto;	state Exp;
branches;
next	1.57;

1.57
date	98.06.19.15.01.50;	author neto;	state Exp;
branches;
next	1.56;

1.56
date	98.05.23.16.37.26;	author neto;	state Exp;
branches;
next	1.55;

1.55
date	97.12.17.20.01.11;	author neto;	state Exp;
branches;
next	1.54;

1.54
date	97.12.17.17.07.13;	author neto;	state Exp;
branches;
next	1.53;

1.53
date	97.12.13.21.30.07;	author neto;	state Exp;
branches;
next	1.52;

1.52
date	97.12.13.21.28.15;	author neto;	state Exp;
branches;
next	1.51;

1.51
date	97.12.06.20.06.05;	author neto;	state Exp;
branches;
next	1.50;

1.50
date	97.10.18.14.49.49;	author neto;	state Exp;
branches;
next	1.49;

1.49
date	97.10.17.21.47.55;	author neto;	state Exp;
branches;
next	1.48;

1.48
date	97.09.27.18.05.55;	author neto;	state Exp;
branches;
next	1.47;

1.47
date	97.09.05.20.11.31;	author neto;	state Exp;
branches;
next	1.46;

1.46
date	97.08.15.20.18.25;	author neto;	state Exp;
branches;
next	1.45;

1.45
date	97.06.26.19.26.14;	author neto;	state Exp;
branches;
next	1.44;

1.44
date	97.06.17.13.33.19;	author neto;	state Exp;
branches;
next	1.43;

1.43
date	97.06.16.20.08.24;	author neto;	state Exp;
branches;
next	1.42;

1.42
date	97.06.13.17.59.32;	author neto;	state Exp;
branches;
next	1.41;

1.41
date	97.06.13.15.44.49;	author neto;	state Exp;
branches;
next	1.40;

1.40
date	97.06.13.15.16.27;	author neto;	state Exp;
branches;
next	1.39;

1.39
date	97.06.12.19.55.19;	author neto;	state Exp;
branches;
next	1.38;

1.38
date	97.06.12.19.45.04;	author neto;	state Exp;
branches;
next	1.37;

1.37
date	97.06.12.18.50.21;	author neto;	state Exp;
branches;
next	1.36;

1.36
date	97.06.11.20.04.49;	author neto;	state Exp;
branches;
next	1.35;

1.35
date	97.06.11.19.37.37;	author neto;	state Exp;
branches;
next	1.34;

1.34
date	97.06.11.19.31.44;	author neto;	state Exp;
branches;
next	1.33;

1.33
date	97.06.11.19.19.06;	author neto;	state Exp;
branches;
next	1.32;

1.32
date	97.06.10.22.06.56;	author neto;	state Exp;
branches;
next	1.31;

1.31
date	97.06.10.20.51.47;	author neto;	state Exp;
branches;
next	1.30;

1.30
date	97.06.10.20.30.24;	author neto;	state Exp;
branches;
next	1.29;

1.29
date	97.06.04.22.27.08;	author neto;	state Exp;
branches;
next	1.28;

1.28
date	97.06.04.22.26.04;	author neto;	state Exp;
branches;
next	1.27;

1.27
date	97.06.04.21.37.33;	author neto;	state Exp;
branches;
next	1.26;

1.26
date	97.06.04.21.06.55;	author neto;	state Exp;
branches;
next	1.25;

1.25
date	97.06.03.22.40.38;	author neto;	state Exp;
branches;
next	1.24;

1.24
date	97.06.03.22.35.46;	author neto;	state Exp;
branches;
next	1.23;

1.23
date	97.06.03.22.32.39;	author neto;	state Exp;
branches;
next	1.22;

1.22
date	97.06.03.22.13.02;	author neto;	state Exp;
branches;
next	1.21;

1.21
date	97.06.03.22.01.17;	author neto;	state Exp;
branches;
next	1.20;

1.20
date	97.06.03.21.58.40;	author neto;	state Exp;
branches;
next	1.19;

1.19
date	97.06.03.19.00.17;	author neto;	state Exp;
branches;
next	1.18;

1.18
date	97.06.03.18.54.04;	author neto;	state Exp;
branches;
next	1.17;

1.17
date	97.06.03.18.50.14;	author neto;	state Exp;
branches;
next	1.16;

1.16
date	97.06.02.15.50.47;	author neto;	state Exp;
branches;
next	1.15;

1.15
date	97.05.28.17.31.24;	author neto;	state Exp;
branches;
next	1.14;

1.14
date	97.05.28.17.28.25;	author neto;	state Exp;
branches;
next	1.13;

1.13
date	97.05.27.23.57.02;	author neto;	state Exp;
branches;
next	1.12;

1.12
date	97.05.23.22.46.52;	author neto;	state Exp;
branches;
next	1.11;

1.11
date	97.05.23.22.46.14;	author neto;	state Exp;
branches;
next	1.10;

1.10
date	97.05.23.22.37.46;	author neto;	state Exp;
branches;
next	1.9;

1.9
date	97.05.23.22.34.55;	author neto;	state Exp;
branches;
next	1.8;

1.8
date	97.05.23.20.35.20;	author neto;	state Exp;
branches;
next	1.7;

1.7
date	97.05.23.20.12.00;	author neto;	state Exp;
branches;
next	1.6;

1.6
date	97.05.23.19.13.54;	author neto;	state Exp;
branches;
next	1.5;

1.5
date	97.05.23.19.08.07;	author neto;	state Exp;
branches;
next	1.4;

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

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

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

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


desc
@Efficiently compute cluster distances.
@


1.62
log
@Export the edge comparison function too.
@
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

\def\Txprime{T'}
\def\LCA{\hbox{\it LCA}}

{\obeylines
$Log: decluster.w,v $
Revision 1.61  1998/10/10 21:27:40  neto
Updated the test code to use newer name for NONE edge type.

Revision 1.60  1998/09/18 17:32:01  neto
Added references to Bentley et al work in geometric MSTs.

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

Revision 1.58  1998/06/19 16:23:39  neto
Fixed call to pq create (to pq create size)

Revision 1.57  1998/06/19 15:01:50  neto
Used pq instead of dict for priority queues.

Revision 1.56  1998/05/23 16:37:26  neto
Factor out the plain MST algorithm (MST)
so it can be used with custom cost functions, e.g. by Held-Karp
lower bounding process in module ascend.

Revision 1.55  1997/12/17 20:01:11  neto
Removed const qualifier on tree returned by decluster topology tree.

Revision 1.54  1997/12/17 17:07:13  neto
Changed compile-time DECLUSTER CONSERVE MEMORY to runtime variable
decluster discard topology tree.
Fixed a date from 1998
(duh!) to 1988.

Revision 1.53  1997/12/13 21:30:07  neto
Fixed a copyo.

Revision 1.52  1997/12/13 21:28:15  neto
decluster mst now takes the tsp instance argument instead of relying on
a global variable.

Revision 1.51  1997/12/06 20:06:05  neto
Be a little defensive when freeing the tree.

Revision 1.50  1997/10/18 14:49:49  neto
Now use E2 supports() to know when we can use a kd-tree.

Revision 1.49  1997/10/17  21:47:55  neto
Changed coord2d structure.

Revision 1.48  1997/09/27 18:05:55  neto
Fixed RCS log behaviour.

Revision 1.47  1997/09/05  20:11:31  neto
Change augmenting chain to augmenting cycle.
improve the comments in the introduction a little bit.