construct.w,v

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

@@<Pick a new potential mate for |u|@@>=
if (E2_case) {
	next_edge->other_end = E2_nn(u);
	next_edge->len = cost(u,next_edge->other_end);
	pq_insert(pq_edge,next_edge);
} else { 
	pool_free(nn_link_pool,next_edge);
	if ( farthest_in_queue[u] == v ) {
		const int x = u, not_me = x;
		@@<Get fresh neighbours for |x|, excepting |not_me|@@>@@;
	}
}

@@ Verbose output.
Here are some sections of code I used to debug this code
the second time around.  (I goofed up my priority queue handling when
I added randomized construction heuristics.)

@@<Verbose: accept this edge@@>=
#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 1000
if ( verbose >= 1000 ) printf(" accept\n");
#endif
#endif


@@
@@<Verbose: PQ before getting an edge@@>=
#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 2000
if ( verbose >= 2000 ) {
printf("Priority queue before Get one short valid edge or NULL:\n");
pq_print(pq_edge,stdout);
printf("\n");
}
#endif
#endif

@@
@@<Verbose: extracted |e|@@>=
#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 2000
if ( verbose >= 2000 ) {
printf("Extract ");
pq_edge_print(stdout,e);

printf("\nPriority queue just after extract:\n");
pq_print(pq_edge,stdout);
printf("\n");
}
#endif
#endif

@@
@@<Verbose: got a valid edge@@>=
#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 1000
if ( verbose >= 2000 ) {
printf("Priority queue AFTER Get one short valid edge or NULL:\n");
pq_print(pq_edge,stdout);
printf("\n");
}
if ( verbose >= 1000 ) printf(" valid");
#endif
#endif

@@
@@<Verbose: All neighbours@@>=
#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 500
fprintf(stderr,"construct: All neighbours for %d, excepting %d\n",
	x,not_me);fflush(stderr);
#endif
#endif


@@
@@<Verbose: mark as saturated@@>=
#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 500
fprintf(stderr,"             Marking %d as saturated (inv= %d)\n",c,inv);
#endif
#endif


@@
@@<Verbose: allocate new link@@>=
#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"construct: alloc new link (%d,%d) "
	length_t_native_spec"\n",
	e->this_end,e->other_end,length_t_native_pcast(e->len));fflush(stderr);
#endif
#endif

@@
@@<Verbose: select fresh neighbours@@>=
#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"construct: Select fresh neighbours for %d, excepting %d\n",
	x,not_me);fflush(stderr);
#endif
#endif

@@
@@<Verbose: need to refresh@@>=
#if defined(CONSTRUCT_MAX_VERBOSE)
#if CONSTRUCT_MAX_VERBOSE >= 750
fprintf(stderr,"Need to refresh because I got x=%d %d y=%d %d "
		length_t_native_spec"\n",
	x, e->this_end, y, e->other_end, length_t_native_pcast(e->len));
#endif
#endif

@@*Index.
@


1.140
log
@Fixed two bugs:
1) I wasn't updating inv unsaturated properly.
2) I fixed a subtle bug with getting maximum weight city in the queue for
a given start point x.  (The max value was initialized wrong.)
Check values of e->len.
@
text
@d53 7
d218 1
a218 1
const char *construct_rcs_id = "$Id: construct.w,v 1.139 1998/08/09 20:53:12 neto Exp neto $";
d673 1
a673 1
fprintf(stderr,"             Marking %d as saturated (inv= %d)\n",c,inv);
d739 1
a739 2
fprintf(stderr,"construct: All neighbours for %d, excepting %d\n",
	x,not_me);fflush(stderr);
d759 1
a759 3
	fprintf(stderr,"construct: alloc new link (%d,%d) "
		length_t_native_spec"\n",
		e->this_end,e->other_end,length_t_native_pcast(e->len));fflush(stderr);
d769 1
a769 2
fprintf(stderr,"construct: Select fresh neighbours for %d, excepting %d\n",
		x,not_me);fflush(stderr);
d1040 1
a1040 3
fprintf(stderr,"Need to refresh because I got x=%d %d y=%d %d "
		length_t_native_spec"\n",
	x, e->this_end, y, e->other_end, length_t_native_pcast(e->len));
d1371 48
@


1.139
log
@Removed some debugging output.
Made random vs. deterministic a compile-time difference rather than
a runtime test.
@
text
@d53 5
d211 1
a211 1
const char *construct_rcs_id = "$Id: construct.w,v 1.138 1998/08/09 20:36:27 neto Exp neto $";
d662 6
a667 2
	if (inv<num_unsaturated && unsaturated[inv]==c) 
		unsaturated[inv]=unsaturated[--num_unsaturated];
d674 3
d688 4
d703 2
a704 1
We choose to put in up to |max_per_city_nn_cache| neighbours at a time
d707 2
d718 1
a718 1
@@d max_per_city_nn_cache 30
d723 38
d765 2
d775 1
a775 1
	num_chosen=min(w,max_per_city_nn_cache);
d779 2
a780 2
	farthest_len = nn_work[i].len;
	farthest_city = nn_work[i].other_end;
d782 2
a783 1
		pq_edge_t *e=pool_alloc(nn_link_pool);
d786 1
a786 1
		if ( farthest_len < e->len ) { 
d1037 3
@


1.138
log
@Fixed the exhausted queue problem with matching.
(I forgot to break out of the loop!.
@
text
@d53 4
d206 1
a206 1
const char *construct_rcs_id = "$Id: construct.w,v 1.137 1998/08/09 19:09:42 neto Exp neto $";
d411 17
d432 1
a432 1
	const int do_random = heuristic == CONSTRUCT_GREEDY_RANDOM;
d439 1
a858 4
In the deterministic case, just choose one.  Now is that much simpler!



d860 2
a861 1
if ( do_random ) {
a878 2
} else { /* Deterministic choice */
	@@<Get one short valid edge or |NULL|@@>@@;
d880 7
a886 4
errorif(e==NULL,"Exhausted the priority queue of links.");
@@<Verbose: accept this edge@@>@@;
x=e->this_end;
y=e->other_end;
d892 1
d894 1
d904 3
a906 1
if ( do_random ) { random_stream = prng_new(PRNG_DEFAULT,random_seed^(6502*6510)); }
d910 3
a912 1
if ( do_random ) prng_free(random_stream);
d943 2
a944 1
First, we must add the length of the edge upon which we decided.
d947 2
d950 2
d1097 15
d1115 1
a1115 1
	const int do_random = alg == CONSTRUCT_GREEDY_RANDOM;
d1122 1
d1171 3
a1173 2
The randomized case looks the same.  It's a shame (and my fault)
that we couldn't just use the same code sequence.  Alas.
d1176 2
a1177 1
if ( do_random ) {
a1178 3
printf("About to extract two edges:\n");
pq_print(pq_edge,stdout);
printf("\n");
a1188 4
printf("\nHere are the two edges:\n");
pq_edge_print(stdout,candidate[0]);
pq_edge_print(stdout,candidate[1]);
printf("\n");
a1193 1
printf("chose %d\n",chosen);
a1195 2
} else { /* Deterministic choice */
	@@<Get one short |next_edge| for matching, or |NULL|@@>@@;
d1197 8
a1225 3
printf("About to extract an edge:\n");
pq_print(pq_edge,stdout);
printf("\n");
a1226 3
printf("Got edge: ");
pq_edge_print(stdout,next_edge);
printf("\n");
a1229 1
printf(" mate[%d]=%d mate[%d]=%d\n",u,mate[u],v,mate[v]);
@


1.137
log
@Better randomization through checking and discarding reversed copies
of same edge when withdrawing from queue.
@
text
@d53 4
d202 1
a202 1
const char *construct_rcs_id = "$Id: construct.w,v 1.136 1998/08/09 18:06:35 neto Exp neto $";
d551 2
a552 2
#The distance function is assumed to be symmetric.  So if we have $(u,v)$
#in the queue, there is no point in 
d853 1
d1104 5
a1108 3
	if (mate[u]>=0) continue; /* Node |u| is already saturated. */
	if (mate[v]>=0) { @@<Pick a new potential mate for |u|@@> continue;}@@;
	mate[u]=v; /* Otherwise, insert |(u,v)| into the matching. */
d1130 3
d1143 5
d1164 5
d1179 3
d1183 3
d1189 5
a1193 2
	if (mate[u]>=0) continue; /* Node |u| is already saturated. */
	if (mate[v]>=0) { @@<Pick a new potential mate for |u|@@> continue;}@@;
@


1.136
log
@I believe this is fixed now.
Now I will reorganized to remove run-time ``do random'' tests.
@
text
@d53 4
d198 1
a198 1
const char *construct_rcs_id = "$Id: construct.w,v 1.135 1998/08/08 22:45:38 neto Exp neto $";
d424 6
a429 3
@@ The first data structure we'll need is a priority queue of edges.  We'll
record at most one edge per  vertex in the graph.  It will be convenient
to store the edges in an array indexed by city number.  Each entry records
d451 2
a452 2
void pq_edge_print(FILE *out, void *edgep);
void
d458 1
a458 1
		fprintf(out,"{%x,%d,%d," length_t_spec "}",
d547 3
d553 1
a553 3
In the non-Euclidean case, we do a bulk search of 
I'll have to modify this for the case when the 
@@^unfinished code@@>
d823 11
a833 1
Otherwise, just choose one.
d840 7
a846 4
	int i;
	for (i=0;i<2;i++) {
		@@<Get one short valid edge or |NULL|@@>@@; 
		candidate[i]=e;
d848 1
d850 1
a850 1
		const int chosen = prng_unif_int(random_stream,3) == 0; 
d1124 1
a1124 1
		@@+ candidate[0]=next_edge;
d1126 7
a1132 1
		@@+ candidate[1]=next_edge;
d1137 1
@


1.135
log
@I believe I've got the bug.
But it must wait for Sunday.
@
text
@d53 4
d194 1
a194 1
const char *construct_rcs_id = "$Id: construct.w,v 1.134 1998/08/08 22:17:57 neto Exp $";
d800 1
a800 1
	else { @@<Insert a new link for |x|@@> }
d822 5
a826 2
	@@<Get one short valid edge or |NULL|@@>@@; @@+ candidate[0]=e;
	@@<Get one short valid edge or |NULL|@@>@@; @@+ candidate[1]=e;
d837 1
a837 1
printf(" accept\n");
d841 19
a873 1

d875 1
a875 3
printf("Priority queue before Get one short valid edge or NULL:\n");
pq_print(pq_edge,stdout);
printf("\n");
d879 1
a879 6
printf("Extract ");
pq_edge_print(stdout,e);

printf("Priority queue just after extract:\n");
pq_print(pq_edge,stdout);
printf("\n");
d885 1
a885 1
	dict_insert(unused,e);
d887 1
a887 25
printf("Priority queue AFTER Get one short valid edge or NULL:\n");
pq_print(pq_edge,stdout);
printf("\n");
printf(" valid");


@@ Of course, we need to define a random number stream for the randomized
choice$\ldots$

@@<Declare the data structures for Greedy@@>=
prng_t *random_stream=NULL;

@@ $\ldots$and initialize it too.
@@^Commodore PET@@>
@@^Commodore 64@@>
@@^C64@@>
@@^6502@@>
@@^6510@@>

@@<Build the data structures for Greedy.@@>=
if ( do_random ) { random_stream = prng_new(PRNG_DEFAULT,random_seed^(6502*6510)); }

@@ And when we're done, we should get rid of it too.
@@<Destroy the data structures for Greedy@@>=
if ( do_random ) prng_free(random_stream);
a893 1
@@<Re-insert unused edges@@>@@;
a894 9
@@ 
dict_delete(unused,e); 
{ pq_edge_t *e;
while ( (e=dict_delete_any(unused)) != NULL ) {
	int x = e->this_end;
	int y = e->other_end;
	@@<Insert a new link for |x|@@>@@;
}
}
d896 2
a897 1
@@ This section finds a new candidate link for city |x|.
d908 1
a908 1
@@<Insert a new link for |x|@@>=
d1158 53
@


1.134
log
@Added better debuggging output.
@
text
@d53 3
d190 1
a190 1
const char *construct_rcs_id = "$Id: construct.w,v 1.133 1998/08/08 20:51:40 neto Exp neto $";
d867 1
d896 1
a896 2
First, we must insert a new link for the key city |x|.
Second, we must add the length of the edge upon which we decided.
a898 1
@@<Insert a new link for |x|@@>@@;
d900 11
@


1.133
log
@First cut at implementing randomized greedy heuristic.
But this bombs on lin105 (both det and rand) with "exhausted priority
queue".
@
text
@d53 5
d187 1
a187 1
const char *construct_rcs_id = "$Id: construct.w,v 1.132 1998/07/16 21:58:55 neto Exp neto $";
d435 14
d475 1
a475 1
pq_set_print_func(pq_edge,nn_link_prn);
d827 1
d847 3
d853 6
d865 5
a937 9

@@
@@<Module subroutines@@>=
static void nn_link_prn(void *p);
void
nn_link_prn(void *p) {
	pq_edge_t *np=(pq_edge_t*)p;
	printf(" %d,%d ",np->this_end,np->other_end);
}
@


1.132
log
@Added the LGPL notice in each file.
@
text
@d53 3
d182 1
a182 1
const char *construct_rcs_id = "$Id: construct.w,v 1.131 1998/06/19 14:55:53 neto Exp neto $";
d210 1
a210 1
|heuristic| parameter.  Some of these heuristics use the integer-valued
d213 4