read.w,v

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

head	1.143;
access
	david
	neto;
symbols
	zero-five-zero:1.143
	zero-four-seventeen:1.142
	zero-four-ten:1.140
	zero-four-nine:1.140
	zero-four-eight:1.140
	zero-four-five:1.140
	zero-four-three:1.140
	zero-four-zero:1.135;
locks
	neto:1.143;


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.120
date	97.01.21.21.55.55;	author david;	state Exp;
branches;
next	1.119;

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

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

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

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

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

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

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

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

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

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

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

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

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

1.106
date	96.07.15.21.20.37;	author david;	state Exp;
branches;
next	1.105;

1.105
date	96.07.04.16.19.25;	author david;	state Exp;
branches;
next	1.104;

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

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

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

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

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

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

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


desc
@Read TSPLIB files.
@


1.143
log
@Added forced write in matrix form.
@
text
@@@i myboiler.w

\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: read.w,v $
Revision 1.142  1998/10/10 19:26:20  neto
Support DSJ RANDOM, ATT, and GEO
Better error messages.

Revision 1.141  1998/10/08 15:14:47  neto
Allow clipping of last point on output too.

Revision 1.140  1998/07/31 17:56:24  neto
Doh!  needed a break too.

Revision 1.139  1998/07/31 17:51:53  neto
added default: to satisfy GCC's complaint about missing RANDOM EDGES
in a switch.

Revision 1.138  1998/07/25 22:10:34  neto
Remove the lexicographically last vertex.

Revision 1.137  1998/07/25 18:10:50  neto
Some of forcing even number of vertic3s.

Revision 1.136  1998/07/24 20:38:33  neto
Added changes to allow truncating the odd vertex out.
Not finished.

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

Revision 1.134  1998/05/08 22:23:57  neto
Better comment.
Also, added writing abilities for matrix forms.

Revision 1.133  1997/12/13 20:05:45  neto
Ok, so I got the name of write... wrong

Revision 1.132  1997/12/13 20:03:05  neto
Added first (compiling) draft of write tsp instance

Revision 1.131  1997/12/13 17:25:18  neto
Stripped the newlines off the error messages.

Revision 1.130  1997/10/18 15:16:19  neto
More readability (matchword).
Hopefully fix garbage output on error (move keyword[0]=0).
Added support for CEIL 2D

Revision 1.129  1997/10/17  21:47:44  neto
Fixed to compile.

Revision 1.128  1997/10/17  21:00:25  neto
Made coordinates indexed by number, not name, i.e. x[0] and x[1] instead
of x and y.  This reduces the code size in kdtree by removing
the CUTDIMEN kludge.

Revision 1.127  1997/09/27 18:04:39  neto
Fixed RCS log behaviour

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

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

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

Revision 1.123  1997/02/10  19:25:03  neto
Limit the size of the PostScript arrays.

Revision 1.122  1997/02/10  19:16:26  neto
Fixed printf spec.

Revision 1.121  1997/02/10  19:13:51  neto
Changed debugging PostScript output so that we don't depend on
large (>8191 element) arrays.

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

Revision 1.119  96/12/20  14:02:47  neto
Make EOF optional. 

Revision 1.118  96/12/13  17:11:23  neto
Make hypot optional.

Revision 1.117  96/12/13  14:44:43  neto
Used hypot instead of sqrt.
Also, added cost\_from\_euc2d\_raw.

Revision 1.116  96/12/05  14:43:16  neto
Added support for no rounding.

Revision 1.115  96/09/12  15:25:37  neto
Empty input doesn't print a garbage keyword now.

Revision 1.114  96/08/16  13:05:01  neto
Added fixincludes.

Revision 1.113  96/08/15  14:01:29  neto
Make it pass all flags, except for error problem.

Revision 1.112  96/08/15  12:34:25  neto
Make it pass -Wall

Revision 1.111  96/07/29  17:07:58  neto
Fixed to compile.

Revision 1.110  96/07/29  16:24:28  neto
oops.  TeX again.

Revision 1.109  96/07/29  16:22:58  neto
TeX barfed on the Log.

Revision 1.108  96/07/29  16:20:09  neto
Added *\_rcs\_id.
Made sure RCS log is activated within this file.

}

@@*Reading TSPLIB files.
The {\sc READ\_ME} included with {\sc TSPLIB} describes the file format.
We restrict our attention to the case where the arc lengths are given
in matrix form, or are assumed to be the Euclidean lengths in two dimensions.

Here is the outline of this module.

@@c
#include <config.h>
#include "lkconfig.h"
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <math.h>
#include "fixincludes.h"
@@<Other includes@@>@@;

#include "read.h"

@@<Global variables@@>@@;
@@<Module definitions@@>@@;
@@<Module variables@@>@@;
@@<Module subroutines@@>@@;
@@<Subroutines@@>@@;
const char *read_rcs_id="$Id: read.w,v 1.142 1998/10/10 19:26:20 neto Exp neto $";


@@ The header file for this module is also included into this module.
It provides type definitions and declarations of publicly accessible
variables and subroutines.

@@(read.h@@>=
extern const char *read_rcs_id;
@@<Type definitions@@>@@;
@@<Exported variables@@>@@;
@@<Exported subroutines@@>@@;


@@ These routines deal with only one problem at a time.  
We keep a pointer to the current problem in the variable |p|.
This is convenient to the users of these routines because that means
they don't have to pass an extra pointer on every function call.
This is also more efficient because we expect the edge cost function
to be evaluated thousands and maybe millions of times.

@@<Global variables@@>=
static tsp_instance_t *p;

@@ We provide a mechanism to switch contexts.  
The user supplies the
problem that becomes the new context, and receives the current
context.

@@<Subroutines@@>=
tsp_instance_t *
switch_to(tsp_instance_t *new_problem)
{
	tsp_instance_t *old_problem;
	old_problem = p;
	p = new_problem;
	@@<Set the |cost| function according to the current context@@>@@;
	return old_problem;
}

@@ The switching routine is made publicly available.
@@<Exported subroutines@@>=
tsp_instance_t *
switch_to(tsp_instance_t *new_problem);

@@ The routine that actually does the reading is passed the file name
and fills the current context.  If a previous context exists, then
it should be saved with a call such as |saved_problem = switch_to(NULL)|, 
or it should be freed.


@@<Subroutines@@>=
tsp_instance_t *
read_tsp_file(FILE *in, FILE *debug, const int force_even_num)
{
	p=new_of(tsp_instance_t);
	@@<Set the instance defaults@@>@@;
	@@<Read in the instance@@>@@;
	@@<Check consistency@@>@@;
	@@<Possibly remove a vertex@@>@@;
	@@<Debugging output@@>@@;
	return p;
}

@@ We've used an allocation macro, so we should include the header file
where it is defined.  We also need to know the error checking interface.
@@<Other includes@@>=
#include "memory.h"
#include "error.h"

@@ We make the reading routine publicly available.
@@<Exported subroutines@@>=
tsp_instance_t *read_tsp_file(FILE *in, FILE *out, const int remove_odd_vertex);


@@ The |tsp_instance_t| type contains fields that identify and 
specify the problem.

The |name| field is the name given by the TSPLIB maintainers to this problem.
It is useful as a basename for the file, though we don't enforce such
usage.  

The |comment| field is the one-line comment attached to this graph.

The |n| field is the number of cities in the instance.  
Some problems, such as weighted perfect matching, require the graph
to have an even number of vertices.  In that case after reading in the
full instance, we might remove one vertex.  We store the number of
vertices presented on the input in the field |input_n|:
it might be odd and 1 more than |n|.

The |scale| entry is used to scale random edge lengths.  So far it
is used only by |DSJ_RANDOM|-type instances.

@@<Type definitions@@>=