read.w,v

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

text
@d52 3
d180 1
d184 1
a184 1
#include "read.h"@@;
d188 1
d191 1
a191 1
const char *read_rcs_id="$Id: read.w,v 1.140 1998/07/31 17:56:24 neto Exp neto $";
d282 3
d292 3
d305 1
d354 5
a358 1
		@@<Generate random edge lengths using the given seed@@>@@;
d409 6
d424 7
a430 1
typedef enum { EUC_2D, CEIL_2D, EXPLICIT, RANDOM_EDGES } edge_weight_type_t;
d436 1
a436 1
p->edge_weight_type = EUC_2D;
d457 1
a457 1
typedef enum { NONE, LOWER_DIAG_ROW, FULL_MATRIX, UPPER_ROW } 
d460 5
d469 1
a469 1
p->edge_weight_format = NONE;
d636 37
d674 2
a675 1
they fit.  This scheme saves space and time (because of cache effects).
d677 1
a677 2
@@<Get the rest of the line into |rest_of_line|, but skip the colon@@>@@;
gb_init_rand( atol(rest_of_line) );
d765 1
a765 2
to mean |nint(\alpha)=floor(0.5+\alpha)|.

d836 3
a852 6
@@ We need to include the interface definition for the numerical
functions
|floor|, |sqrt|, and |hypot|.

@@<Other includes@@>=
#include <math.h>
d869 124
d1018 12
d1035 4
d1082 2
d1109 4
a1112 2
		errorif(p->edge_weight_format != NONE,
			"Edge weight format should be NONE, but is %d",p->edge_weight_format);
d1116 2
a1117 1
		errorif(p->edge_weight_format==NONE,"Edge weight shouldn't be NONE, but it is");
d1120 1
d1209 9
d1228 4
@


1.140
log
@Doh!  needed a break too.
@
text
@d52 3
d186 1
a186 1
const char *read_rcs_id="$Id: read.w,v 1.139 1998/07/31 17:51:53 neto Exp neto $";
d859 1
a859 1
te $x,y$ coordinates and deleted the last point.'')
d865 6
d883 5
a887 1
	p->coord[lex_last] = p->coord[p->n];
d969 2
d973 1
a973 1
write_tsp_file(tsp_instance_t *tsp,FILE *out) 
d975 9
a983 1
if(out) { 
d986 4
a989 2
if (tsp->comment) {fprintf(out,"COMMENT: %s\n",tsp->comment);}
fprintf(out,"DIMENSION: %d\n",tsp->n);
d1007 1
a1010 1
}
d1015 1
d1021 2
a1022 2
for (i=0;i<tsp->n;i++) {
fprintf(out,"%d %20g %20g\n",i+1,tsp->coord[i].x[0],tsp->coord[i].x[1]);
d1034 1
a1034 1
		for (row=0;row<tsp->n;row++) {
d1044 2
a1045 2
		for (row=0;row<tsp->n;row++) {
			for (col=0;col<tsp->n;col++) {
d1054 2
a1055 2
		for (row=0;row<tsp->n;row++) {
			for (col=row+1;col<tsp->n;col++) {
@


1.139
log
@added default: to satisfy GCC's complaint about missing RANDOM EDGES
in a switch.
@
text
@d52 4
d183 1
a183 1
const char *read_rcs_id="$Id: read.w,v 1.138 1998/07/25 22:10:34 neto Exp neto $";
d895 1
d897 1
@


1.138
log
@Remove the lexicographically last vertex.
@
text
@d52 3
d179 1
a179 1
const char *read_rcs_id="$Id: read.w,v 1.137 1998/07/25 18:10:50 neto Exp neto $";
d891 1
@


1.137
log
@Some of forcing even number of vertic3s.
@
text
@d52 3
d176 1
a176 1
const char *read_rcs_id="$Id: read.w,v 1.136 1998/07/24 20:38:33 neto Exp neto $";
a317 1
		if ( force_even_num && (p->n % 2) ) p->n--;
d826 3
a829 1
@@
d831 40
d873 2
a874 1

d881 2
a882 1
		errorif(p->edge_weight_format != NONE,"Edge weight format should be NONE, but is %d",edge_weight_format);
@


1.136
log
@Added changes to allow truncating the odd vertex out.
Not finished.
@
text
@d52 4
d173 1
a173 1
const char *read_rcs_id="$Id: read.w,v 1.135 1998/07/16 21:58:55 neto Exp neto $";
d825 2
a826 2
@@c
...
@


1.135
log
@Added the LGPL notice in each file.
@
text
@d1 1
a1 2


d52 3
d169 1
a169 1
const char *read_rcs_id="$Id: read.w,v 1.134 1998/05/08 22:23:57 neto Exp neto $";
d222 1
a222 1
read_tsp_file(FILE *in, FILE *debug)
d225 4
a228 2
	@@<Set the problem defaults@@>@@;
	@@<Read in the problem@@>@@;
d241 1
a241 1
tsp_instance_t * read_tsp_file(FILE *in, FILE *out);
d253 6
a258 2
The |n| field is the number of cities in the problem.  

d266 1
d273 1
a273 1
@@<Set the problem defaults@@>=
d283 1
a283 1
@@<Read in the problem@@>=
d310 2
a311 1
		p->n = atoi(rest_of_line);
d391 1
a391 1
@@ @@<Set the problem defaults@@>=
d419 1
a419 1
@@ @@<Set the problem defaults@@>=
d434 1
a434 1
		p->edge_weights = new_arr_of(length_t*,p->n);
d436 2
a437 2
		for ( row = 0 ; row < p->n ; row++ ) {
			p->edge_weights[row] = new_arr_of(length_t,p->n);
d439 1
a439 1
		for ( row = 0 ; row < p->n ; row++ ) { /* Now actually read the weights. */
d452 1
a452 1
		p->edge_weights = new_arr_of(length_t*,p->n);
d454 2
a455 2
		for ( row = 0 ; row < p->n ; row++ ) {
			p->edge_weights[row] = new_arr_of(length_t,p->n);
d457 2
a458 2
		for ( row = 0 ; row < p->n ; row++ ) { /* Now actually read the weights. */
			for ( col = 0 ; col < p->n ; col++ ) {
d465 1
a465 1
		for ( row = 0; row < p->n ; row++ ) {
d477 1
a477 1
		p->edge_weights = new_arr_of(length_t*,p->n);
d479 2
a480 2
		for ( row = 0 ; row < p->n ; row++ ) {
			p->edge_weights[row] = new_arr_of(length_t,p->n);
d483 1
a483 1
		for ( row = 0 ; row < p->n ; row++ ) { 
d485 1
a485 1
			for ( col = row+1 ; col < p->n ; col++ ) {
d504 1
a504 1
@@ @@<Set the problem defaults@@>=
d527 2
d531 8
a538 7
{ 	

	int i,j;
	p->coord = new_arr_of(coord_2d,p->n);	/* Allocate the space for the coordinates. */
	for ( i=0; i<p->n; i++ ) {
		fscanf(in," %d ",&j);
		fscanf(in," %lf %lf ",&p->coord[j-1].x[0],&p->coord[j-1].x[1]);
d568 1
a568 1
@@<Set the problem defaults@@>=
d577 1
a577 1
We may want to output PostScript in the future.
d582 1
a582 1
	for ( i=0; i<p->n; i++ ) {
d593 3
a595 3
p->short_edge_weights = new_arr_of(short*,p->n);
for (i=0;i<p->n;i++) {
	p->short_edge_weights[i]  = new_arr_of(short,p->n);
d598 1
a598 1
for (i=0;i<p->n;i++)
d602 1
a602 1
if ( p->n <=10 ) {
d604 2
a605 2
	for (i=0;i<p->n;i++) {
		for (j=0;j<p->n;j++) printf(" %4d",p->short_edge_weights[i][j]);
d614 1
a614 1
@@ @@<Set the problem defaults@@>=
d819 22
d860 2
a861 2
	fprintf(debug,"/N {%d} def        %% number of nodes\n",p->n);
	if ( p->n < 8191 )
d887 1
a887 1
for (i=0; i<p->n ; i++) {
@


1.134
log
@Better comment.
Also, added writing abilities for matrix forms.
@
text
@d1 47
a47 1
@@i copyrt.w
d53 4
d167 1
a167 1
const char *read_rcs_id="$Id: read.w,v 1.133 1997/12/13 20:05:45 neto Exp neto $";
@


1.133
log
@Ok, so I got the name of write... wrong
@
text
@d7 3
d117 1
a117 1
const char *read_rcs_id="$Id: read.w,v 1.132 1997/12/13 20:03:05 neto Exp neto $";
d604 2
a605 1
The TSPLIB documentation uses the |aint| function in place of the |floor| 
d614 6
d633 5
a819 1
fprintf(out,"DIMENSION: %d\n",tsp->n);
d827 11
a837 1
default: errorif(1,"Finish the code, David!");
a838 1
fprintf(out,"EOF\n");
d854 40
@


1.132
log
@Added first (compiling) draft of write tsp instance
@
text
@d7 3
d114 1
a114 1
const char *read_rcs_id="$Id: read.w,v 1.131 1997/12/13 17:25:18 neto Exp neto $";
d798 1
a798 1
write_tsp_instance(tsp_instance_t *tsp,FILE *out) 
d821 1
a821 1
void write_tsp_instance(tsp_instance_t *tsp,FILE *out);
@


1.131
log
@Stripped the newlines off the error messages.
@
text
@d7 3
d111 1
a111 1
const char *read_rcs_id="$Id: read.w,v 1.130 1997/10/18 15:16:19 neto Exp neto $";
d122 1
a122 1
@@<Exported routines@@>@@;
d152 1
a152 1
@@<Exported routines@@>=
d180 1
a180 1
@@<Exported routines@@>=
d681 1
a681 1
@@<Exported routines@@>=
d790 38
@


1.130
log
@More readability (matchword).
Hopefully fix garbage output on error (move keyword[0]=0).
Added support for CEIL 2D
@
text
@d7 5
d108 1
a108 1
const char *read_rcs_id="$Id: read.w,v 1.129 1997/10/17 21:47:44 neto Exp neto $";
d260 1
a260 1
		errorif(1,"%d: Don't know what the keyword %s is!\n",lineno,keyword);
d282 1
a282 1
	errorif( r != 0, "%d: Missed the colon.\n", lineno);
d286 1
a286 1
	@@|"%d: Couldn't read after the colon; truncated file?\n", lineno);@@;
d313 1
a313 1
	errorif(1,"%d: Apology: Unknown edge weight type \"%s\".\n",lineno,rest_of_line);
d340 1
a340 1
	errorif(1,"%d: Unknown edge weight format \"%s\".\n",lineno,rest_of_line);
@


1.129
log
@Fixed to compile.
@
text
@d7 3
d103 1
a103 1
const char *read_rcs_id="$Id: read.w,v 1.128 1997/10/17 21:00:25 neto Exp neto $";
d208 1
a215 1
keyword[0]=0;
d218 1
d220 1
a220 1
	if ( r==EOF ) {more_input=0;break;}
d224 1
a224 1
	if ( 0==strcmp(keyword,"EOF") ) {
d226 1
a226 1
	}@@+ else if ( 0==strcmp(keyword,"NAME") ) {
d229 2
a230 2
	}@@+ else if ( 0==strcmp(keyword,"COMMENT") ) {
		@@<Get the rest of the line into |rest_of_line|, but skip the colon@@>
d232 1
a232 1
	}@@+ else if ( 0==strcmp(keyword,"TYPE") ) {
d235 1
a235 1
	}@@+ else if ( 0==strcmp(keyword,"DIMENSION") ) {
d238 1
a238 1
	}@@+ else if ( 0==strcmp(keyword,"DISPLAY_DATA_TYPE") ) {
d241 1
a241 1
	}@@+ else if ( 0==strcmp(keyword,"EDGE_WEIGHT_TYPE") ) {
d243 1
a243 1
	}@@+ else if ( 0==strcmp(keyword,"EDGE_WEIGHT_FORMAT") ) {
d245 1
a245 1
	}@@+ else if ( 0==strcmp(keyword,"EDGE_WEIGHT_SECTION") ) {
d247 1
a247 1
	}@@+ else if ( 0==strcmp(keyword,"NODE_COORD_SECTION") ) {
d249 1
a249 1
	}@@+ else if ( 0==strcmp(keyword,"DISPLAY_DATA_SECTION") ) {
d251 1
a251 1
	}@@+ else if ( 0==strcmp(keyword,"SEED") ) {
d301 2
d312 1
a312 1
typedef enum { EUC_2D, EXPLICIT, RANDOM_EDGES } edge_weight_type_t;
d612 10
d623 2
a624 1
about 15% slower on an SGI Challenge, even using the native C compiler
d685 1
a685 1
on an Intel 486.
d713 7
@


1.128
log
@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.
@
text
@d7 5
d100 1
a100 1
const char *read_rcs_id="$Id: read.w,v 1.127 1997/09/27 18:04:39 neto Exp neto $";
d455 1
a455 1
		fscanf(in," %lf %lf ",&p->coord[j-1].x,&p->coord[j-1].y);
d753 1
a753 1
	fprintf(debug,"%f %f ts\n",p->coord[i].x,p->coord[i].y);
@


1.127
log
@Fixed RCS log behaviour
@
text
@d7 3
d95 1
a95 1
const char *read_rcs_id="$Id: read.w,v 1.126 1997/08/15 20:18:25 neto Exp neto $";
d451 4
a454 4
		p->xmin = min(p->xmin,p->coord[j-1].x);
		p->ymin = min(p->ymin,p->coord[j-1].y);
		p->xmax = max(p->xmax,p->coord[j-1].x);
		p->ymax = max(p->ymax,p->coord[j-1].y);
d459 10
a468 2
@@ @@<Early type definitions@@>=
typedef struct { double x, y; } coord_2d;
d596 2
a597 2
	double xd = coord_array[i].x - coord_array[j].x;
	double yd = coord_array[i].y - coord_array[j].y;
d628 2
a629 2
	double xd = coord_array[i].x - coord_array[j].x;
	double yd = coord_array[i].y - coord_array[j].y;
d645 2
a646 2
	double xd = coord_array[i].x - coord_array[j].x;