read.w,v

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

	double yd = coord_array[i].y - coord_array[j].y;
d671 2
a672 2
	double xd = coord_array[i].x - coord_array[j].x;
	double yd = coord_array[i].y - coord_array[j].y;
@


1.126
log
@Added Index major section.
@
text
@d5 5
a9 1
{\obeylines$Log: read.w,v $
d92 1
a92 1
const char *read_rcs_id="$Id: read.w,v 1.125 1997/05/16 18:11:41 neto Exp neto $";
@


1.125
log
@Break locks by david and neto.
Include <config.h> and "lkconfig.h"
@
text
@d6 4
d88 1
a88 1
const char *read_rcs_id="$Id: read.w,v 1.124 1997/05/16 18:09:40 neto Exp neto $";
d738 2
@


1.124
log
@Include <config.h> and lkconfig.h
@
text
@d6 3
d84 1
a84 1
const char *read_rcs_id="$Id: read.w,v 1.123 1997/02/10 19:25:03 neto Exp neto $";
@


1.123
log
@Limit the size of the PostScript arrays.
@
text
@d6 3
d67 2
d81 1
a81 1
const char *read_rcs_id="$Id: read.w,v 1.122 1997/02/10 19:16:26 neto Exp neto $";
@


1.122
log
@Fixed printf spec.
@
text
@d6 3
d76 1
a76 1
const char *read_rcs_id="$Id: read.w,v 1.121 1997/02/10 19:13:51 neto Exp neto $";
d685 6
d694 2
a695 1
	fprintf(debug,"/xs N 1 add array def\n/ys N 1 add array def\n");
@


1.121
log
@Changed debugging PostScript output so that we don't depend on
large (>8191 element) arrays.
@
text
@d6 4
d73 1
a73 1
const char *read_rcs_id="$Id: read.w,v 1.120 1997/01/21 21:55:55 david Exp neto $";
d711 1
a711 1
	fprintf(debug,"%f %f ts\n",i+1,p->coord[i].x,p->coord[i].y);
@


1.120
log
@Added standard copyright notice by including copyrt.w
@
text
@d5 4
a8 1
{\obeylines$Log:	read.w,v $
d69 1
a69 1
const char *read_rcs_id="$Id: read.w,v 1.119 96/12/20 14:02:47 neto Exp $";
d707 1
a707 1
	fprintf(debug,"%d %f %f s \n",i+1,p->coord[i].x,p->coord[i].y);
a708 1
fprintf(debug,"1 1 N { dup xs exch get exch ys exch get dot } for\n");
@


1.119
log
@Make EOF optional.
@
text
@d1 1
d6 3
d66 1
a66 1
const char *read_rcs_id="$Id: read.w,v 1.118 96/12/13 17:11:23 neto Exp $";
@


1.118
log
@Make hypot optional.
@
text
@d5 3
d62 1
a62 1
const char *read_rcs_id="$Id: read.w,v 1.117 96/12/13 14:44:43 neto Exp $";
d178 3
a180 2
	errorif( r != 1, "%d: Couldn't read the word following \"%s\".",
			 lineno+1,keyword);
d422 1
@


1.117
log
@Used hypot instead of sqrt.
Also, added cost\_from\_euc2d\_raw.
@
text
@d5 4
d56 1
d59 1
a59 1
const char *read_rcs_id="$Id: read.w,v 1.116 96/12/05 14:43:16 neto Exp $";
d552 1
a552 1
	return (length_t) floor(0.5+hypot(xd,yd));
d555 18
d584 1
a584 1
	return (length_t) hypot(xd,yd);
d601 1
a601 1
	return hypot(xd,yd);
d610 1
a610 1
|floor| and |hypot|.
@


1.116
log
@Added support for no rounding.
@
text
@d5 3
d54 1
a54 1
const char *read_rcs_id="$Id: read.w,v 1.115 96/09/12 15:25:37 neto Exp Locker: neto $";
d547 1
a547 1
	return (length_t) floor(0.5+sqrt(xd*xd+yd*yd));
d561 1
a561 1
	return (length_t) sqrt(xd*xd+yd*yd);
d564 6
d571 14
d587 1
a587 1
|floor| and |sqrt|.
@


1.115
log
@Empty input doesn't print a garbage keyword now.
@
text
@d5 3
d51 1
a51 1
const char *read_rcs_id="$Id: read.w,v 1.114 96/08/16 13:05:01 neto Exp Locker: neto $";
d534 1
a534 1
Maybe be more intelligent about integer square roots???
d547 2
d550 12
d586 2
a587 1
of the problem.
d596 4
a599 1
	cost = cost_from_euc2d;
@


1.114
log
@Added fixincludes.
@
text
@d5 3
d48 1
a48 1
const char *read_rcs_id="$Id: read.w,v 1.113 96/08/15 14:01:29 neto Exp $";
d160 1
@


1.113
log
@Make it pass all flags, except for error problem.
@
text
@d5 3
d37 1
d45 1
a45 1
const char *read_rcs_id="$Id: read.w,v 1.112 96/08/15 12:34:25 neto Exp $";
d457 1
a457 1
		putchar('\n');
@


1.112
log
@Make it pass -Wall
@
text
@d5 3
d39 1
a39 1
@@<Local subroutines@@>@@;
d41 1
a41 1
const char *read_rcs_id="$Id: read.w,v 1.111 96/07/29 17:07:58 neto Exp $";
d493 3
a495 1
@@<Local subroutines@@>=
d502 2
d510 1
d525 2
a526 1
@@<Local subroutines@@>=
d548 2
a549 1
@@<Local subroutines@@>=
@


1.111
log
@Fixed to compile.
@
text
@d5 3
d38 1
a38 1
const char *read_rcs_id="$Id: read.w,v 1.110 96/07/29 16:24:28 neto Exp $";
d155 1
a155 1
	if ( colon = strchr(keyword,':') ) *colon = '\0';
d286 1
a286 1
int long_dummy;
a387 1
	double dummy;
@


1.110
log
@oops.  TeX again.
@
text
@d5 3
a24 1
const char read_rcs_id="$Id: read.w,v 1.109 96/07/29 16:22:58 neto Exp $";
d35 1
@


1.109
log
@TeX barfed on the Log.
@
text
@d4 4
a7 1
{\obelyines$Log:$
d22 1
a22 1
const char read_rcs_id="$Id: read.w,v 1.108 96/07/29 16:20:09 neto Exp $";
@


1.108
log
@Added *\_rcs\_id.
Made sure RCS log is activated within this file.
@
text
@d4 5
a8 1
{\obelyines$Log$
d19 1
a19 1
const char read_rcs_id="$Id$";
@


1.107
log
@Took away side effects from the errorif calls.
@
text
@d4 3
d15 1
d33 1
@


1.106
log
@Shortened `stuffcoord' to `s'.
@
text
@d133 3
a135 3
	char *colon;
	errorif( 1 != fscanf(in," %s ", keyword),
			 "%d: Couldn't read the word following \"%s\".",
d188 7
a194 5
int l;
if ( colon == NULL )
	errorif( 0 != fscanf(in," : "), 
		"%d: Missed the colon.\n", lineno);
errorif( NULL == fgets(rest_of_line,MAX_LINE_LEN,in),
d279 2
a280 1
				errorif( 1 != fscanf(in," %ld ", &long_dummy),
d297 2
a298 1
				errorif( 1 != fscanf(in," %ld ", &long_dummy),
d324 2
a325 1
				errorif( 1 != fscanf(in," %ld ", &long_dummy),
@


1.105
log
@Fixed grammar.
@
text
@d588 1
a588 1
	fprintf(debug,"%d %f %f stuffcoord \n",i+1,p->coord[i].x,p->coord[i].y);
d591 1
@


1.104
log
@Changed range values to double from int.
@
text
@d181 1
a181 1
We're make sure that the colon is actually there, and that the line
@


1.103
log
@Leftrightarrow is now iff
Include webdefs.w and types.w
@
text
@d382 1
a382 1
int xmin, xmax, ymin, ymax;
d384 7
a390 1
@@ @@<Set the problem defaults@@>=
d575 4
a578 4
fprintf(debug,"/xmin {%d} def \n",p->xmin);
fprintf(debug,"/xmax {%d} def \n",p->xmax);
fprintf(debug,"/ymin {%d} def \n",p->ymin);
fprintf(debug,"/ymax {%d} def \n",p->ymax);
@


1.102
log
@*** empty log message ***
@
text
@d1 3
@


1.101
log
@Changed interface to read_tsp_file
@
text
@d441 1
a441 1
$${\mit cost}(i,j)\le {\mit cost}(k,l) \Leftrightarrow
d443 1
a443 1
%$$ |cost(i,j)|\le|cost(k,l)|\Leftrightarrow
@


1.100
log
@This version works.  
Needs improvement:
	command-line switches
	faster tabu check
	allow Papadimitriou tabu rule
	faster preprocessing
	different candidate lists
@
text
@d70 1
a70 1
read_tsp_file(const char *filename)
a71 2
	FILE *in;

a72 2
	in = fopen(filename,"r");
	errorif(in==NULL,"Couldn't open the file \"%s\" for reading.\n",filename);
d87 1
a87 1
tsp_instance_t * read_tsp_file(const char *filename);
d132 2
a133 2
			 "%s:%d: Couldn't read the word following \"%s\".",
			 filename,lineno+1,keyword);
d166 1
a166 1
		errorif(1,"%s:%d: Don't know what the keyword %s is!\n",filename,lineno,keyword);
d188 1
a188 1
		"%s:%d: Missed the colon.\n", filename,lineno);
d190 1
a190 1
	@@|"%s:%d: Couldn't read after the colon; truncated file?\n", filename,lineno);@@;
d215 1
a215 1
	errorif(1,"%s:%d: Apology: Unknown edge weight type \"%s\".\n",filename,lineno,rest_of_line);
d242 1
a242 1
	errorif(1,"%s:%d: Unknown edge weight format \"%s\".\n",filename,lineno,rest_of_line);
d539 1
a539 1
@@*Verbose output routines.
d541 1
a541 1
When debugging output is desired, |verbose>0|.
d544 2
a545 1
about its contents to a debugging file.  The file handle is |debug|.
a546 5

@@<Global variables@@>=
extern int verbose;
extern FILE *debug;

a581 29
}


@@*Testing the file reading routine.
@@(testread.c@@>=
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

#include "read.h"

int
main(int argc,char **argv)
{ tsp_instance_t *p;
errorif( argc!=2, "Usage: %s <tsp-filename>\n",argv[0] );
p = read_tsp_file(argv[1]);
printf("name:    \"%s\"\n",p->name);
printf("comment: \"%s\"\n",p->comment);
printf("cities:  %d\n",p->n);
	{int i,j;
	for(i=0;i<3; i++) {
		for(j=0;j<3; j++) {
			printf("cost(%d,%d)="length_t_spec"\n",
				i,j,(length_t_pcast(cost(i,j)));
		}
	}
	}
return 0;
@


1.2
log
@Initial implementation of LK.  This is buggy.
@
text
@@


1.1
log
@Initial revision
@
text
@@