construct.w,v

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

d219 3
a221 1
construct(const int n, int *tour, const int heuristic, const long heur_param) {
d224 1
a225 1
	errorif(1,"Unknown heuristic: %d",heuristic);
d232 2
a233 1
construct(const int n, int *tour, const int heuristic, const long heur_param);
d245 1
a245 1
@@ For a warmup, let's implement the canoncial tour, \ie~ordering 0, 1, 2, \etc.
d276 1
d282 1
a282 1
	gb_init_rand(heur_param);
d284 1
a284 1
		const int next = gb_unif_rand(n-i);
d289 1
d304 1
a304 5
@@ And we must import the interface to the random number generator.  We've
used the generator from Knuth's Stanford GraphBase.
@@^Stanford GraphBase@@>
@@^Knuth, Donald Ervin@@>

d308 1
a308 1
#include "gb_flip.h"
d352 6
d384 1
d386 3
a388 1
case CONSTRUCT_GREEDY: {
d391 1
d402 2
a403 1
@@ We need to export the constant |CONSTRUCT_GREEDY|.
d405 2
a406 1
#define CONSTRUCT_GREEDY 2
d478 1
d480 1
d567 1
a567 1
is unsaturated, then |unsaturated[inv_unsaturated[i]]==i|.
d767 1
a767 1
	@@<Find a shortest valid edge $e=(x,y)$@@>@@;
d786 28
a813 2
@@ Here's where we pick a shortest remaining valid edge.
It is eligible if both ends are
d825 2
a826 1
@@<Find a shortest valid edge $e=(x,y)$@@>=
d829 1
a829 1
	errorif(e==NULL,"Exhausted the priority queue of links.");
a834 1
	@@<Insert a new link for |x|@@>@@;
d836 27
d936 2
a937 1
construct_matching(int n, int *mate, int alg,long alg_param) 
d955 2
a956 1
length_t construct_matching(int n, int *mate, int alg,long alg_param);
d990 1
a991 1
    gb_init_rand(alg_param);
d993 1
a993 1
		ui = gb_unif_rand(num_unmated);
d995 1
a995 1
		vi = gb_unif_rand(num_unmated);
d1001 1
d1016 2
a1017 1
	{ 
d1019 1
a1041 6
In the perfect matching case, a node is saturated if it has even a single
edge incident upon it.  We maintain the invariant that a city is hidden
in the $k$-d tree if and only if it is saturated.

You'll have to agree this is much simpler than the greedy algorithm
for tours.
d1048 2
a1049 1
	pq_edge_t *next_edge = pq_delete_min(pq_edge);
d1067 48
@


1.131
log
@Use binary heap priority queue in place of heavier weight dictionaries.
@
text
@d1 46
a46 1
@@i copyrt.w
d53 3
d179 1
a179 1
const char *construct_rcs_id = "$Id: construct.w,v 1.130 1998/04/16 16:02:03 neto Exp neto $";
@


1.130
log
@webbug fixed:  the code for initializing nn work array came after its
first use.  Doh.
@
text
@d8 4
d131 1
a131 1
const char *construct_rcs_id = "$Id: construct.w,v 1.129 1998/04/16 15:23:20 neto Exp neto $";
d379 1
a379 2
We will use the dictionary routines from module \module{DICT} because 
they provide an efficient priority queue implementation.
d383 6
a388 1
dict_t *pq_edge = dict_create(cmp_pq_edge,nn_link_prn);
d393 1
a393 1
dict_destroy(pq_edge,NULL);
d396 1
a396 1
dictionary, and to the pool manager.
d400 1
a400 1
#include "dict.h"
d412 1
a412 1
@@ We've had to provide a comparison function for the dictionary routines.
d427 1
a427 1
be able to insert two edges of the same length: the dictionary requires
d459 1
a459 1
		dict_insert(pq_edge,e);
d595 1
a595 1
		dict_insert(pq_edge,e);
d731 1
a731 1
	e = dict_delete(pq_edge,dict_min(pq_edge),NULL);
d759 1
a759 1
	dict_insert(pq_edge,e);
d926 1
a926 1
	pq_edge_t *next_edge = dict_delete(pq_edge,dict_min(pq_edge),NULL);
d956 1
a956 1
	dict_insert(pq_edge,next_edge);
@


1.129
log
@Now it ctangles and compiles with no warnings.  (But you ask, does it work?)
@
text
@d8 3
d127 1
a127 1
const char *construct_rcs_id = "$Id: construct.w,v 1.128 1998/04/11 17:39:52 neto Exp neto $";
d530 1
a604 4

@@
@@<Build the data structures for Greedy, non-Euclidean case@@>=
nn_work = new_arr_of(pq_edge_t,n);
@


1.128
log
@Possibly finished coding the non-Euclidean changes.
But company is coming, and I must go.
@
text
@d8 4
d124 1
a124 1
const char *construct_rcs_id = "$Id: construct.w,v 1.127 1998/04/11 17:24:40 neto Exp neto $";
d321 1
a321 1
	@@<Build the data structures for Greedy@@>@@;
d377 1
a377 1
dict_t *pq_edge = dict_create(cmp_pq_edge,NULL);
d440 1
a440 1
@@<Build the data structures for Greedy@@>=
d468 1
a468 1
int *farthest_in_queue;
d489 1
a489 1
int *unsaturated, num_unsaturated, *inv_unsaturated;
d563 2
a564 1
	int i,w,num_chosen, farthest_city;
d592 6
a597 1
@@ Array |nn_work| is just an array of at most |n| edges.
d599 1
a599 1
pq_edge_t *nn_work;
d883 1
d886 1
a886 1
	@@<Build the data structures for Greedy@@>@@;
@


1.127
log
@Added much queue handling for the non-Euclidean case, including refreshing
the list, maintaining the unsaturated cities, and the farthest in queue
array.
@
text
@d8 5
d120 1
a120 1
const char *construct_rcs_id = "$Id: construct.w,v 1.126 1998/04/11 15:43:28 neto Exp neto $";
d570 1
a570 1
	erroif(num_chosen==0,"Bug!");
d682 4
a685 2
	if ( adj[y].count == 2) E2_hide(y);
	if ( adj[x].count == 2) E2_hide(x);
d694 1
a694 1
E2_unhide_all();
d916 4
a919 2
	E2_hide(u);
	E2_hide(v);
d924 1
a924 1
E2_unhide_all();
d929 4
d934 11
a944 3
next_edge->other_end = E2_nn(u);
next_edge->len = cost(u,next_edge->other_end);
dict_insert(pq_edge,next_edge);
@


1.126
log
@Convert nn link to nn link pool because non-Euclidean case is better
with multiple possible neighbours in the queue.  Still converting
to allow non-Euclidean.
@
text
@d8 5
d115 1
a115 1
const char *construct_rcs_id = "$Id: construct.w,v 1.125 1998/01/23 20:09:22 neto Exp neto $";
d443 1
a443 5
	int x;
	@@<Initialize the |unsaturated| list@@>@@;
	for (x=0;x<n;x++) {
		@@<Get fresh neighbours for |x|@@>@@;
	}
d451 145
d673 2
a674 1
	@@<Find a shortest valid edge $(x,y)$@@>@@;
d704 1
a704 3
@@<Find a shortest valid edge $(x,y)$@@>=
{
pq_edge_t *e;
a715 1
}
d736 1
d738 2
a739 2
		const int i=x;
		@@<Get fresh neighbours for |x|@@>@@;
@


1.125
log
@The mate structure doesn't need to be initialized before it is initialized!
@
text
@d8 3
d110 1
a110 1
const char *construct_rcs_id = "$Id: construct.w,v 1.124 1998/01/23 19:30:56 neto Exp neto $";
d288 12
d304 1
d337 1
d341 4
a344 2
@@ The array of edges in the priority queue is called |nn_link|, and is allocated
at the same time that it is declared.  Bentley says  ``|nn_link[i]| contains
d348 7
a354 1
inserted into the tour.''
d356 1
a356 1
The entries of |nn_link| serve as the domain over which
d362 1
a362 1
pq_edge_t *nn_link = the_nn_link = new_arr_of(pq_edge_t,n);
d367 1
a367 1
free_mem(nn_link);
d370 2
a371 2
@@ We need the interface to both the memory allocation routines and to the
dictionary.
d376 1
d414 2
a415 1
in the |nn_link| array, and then inserting that entry into the priority queue.
d422 1
d427 2
a428 2
errorif(!E2_supports(tsp_instance),"Finish the code, David. ");
{@@+ int i;
d430 5
a434 3
		nn_link[i].other_end = E2_nn(i);
		nn_link[i].len = cost(i,nn_link[i].other_end);
		dict_insert(pq_edge,nn_link+i);
d437 6
d558 2
d561 3
a563 3
	pq_edge_t *px= dict_delete(pq_edge,dict_min(pq_edge),NULL);
	errorif(px==NULL,"Exhausted the priority queue of links.");
	x = px-nn_link; y=px->other_end;
d570 9
a578 1
len += nn_link[x].len;
d580 2
a581 1
@@ In finding a new candidate link for |x|, we must first hide the
d583 1
d585 1
d587 2
a588 2
	nn_link[x].other_end = E2_nn(x);
	nn_link[x].len = cost(x,nn_link[x].other_end);
d590 7
a596 1
	dict_insert(pq_edge,nn_link+x);
d614 1
a614 3
pq_edge_t *the_nn_link;
int count;
void nn_link_prn(void *p);
d618 1
a618 2
	printf(" %d,%d ",np-the_nn_link,np->other_end);
	count++;
d758 1
a758 1
	u = next_edge - nn_link;
d776 3
a778 3
nn_link[u].other_end = E2_nn(u);
nn_link[u].len = cost(u,nn_link[u].other_end);
dict_insert(pq_edge,nn_link+u);
@


1.124
log
@Fixed to compile.  Also match construct is now more appropriately
construct matching.
@
text
@d8 4
d107 1
a107 1
const char *construct_rcs_id = "$Id: construct.w,v 1.123 1997/12/20 22:33:02 neto Exp neto $";
d597 1
a597 1
	errorif(mate==NULL || mate[0]==-1,
@


1.123
log
@Fixed another preprocessor booboo.
@
text
@d8 3
d103 1
a103 1
const char *construct_rcs_id = "$Id: construct.w,v 1.122 1997/12/20 22:29:52 neto Exp neto $";
d405 1
a405 1
@@  We need the interface to $k$-d trees.
d407 1
d567 1
a567 1
Procedure |match_construct| builds a weighted perfect matching.
d587 1
a587 1
match_construct(const int n, int *mate, int alg,long alg_param) 
d593 1
a593 1
	errorif(match==NULL || match[0]==-1,
d603 5
d649 2
@


1.122
log
@Fixed preprocessor booboo.
@
text
@d8 3
d100 1
a100 1
const char *construct_rcs_id = "$Id: construct.w,v 1.121 1997/12/20 22:23:59 neto Exp neto $";
d659 1
a659 1
#endif
@


1.121
log
@First crack at greedy matching heuristic.
@
text
@d8 3
d97 1
a97 1
const char *construct_rcs_id = "$Id: construct.w,v 1.120 1997/09/27 18:05:36 neto Exp neto $";
d419 1
a419 1
#if DO_TOUR
d425 1
a425 1
#if DO_TOUR
d431 1
a431 1
#if DO_TOUR
d448 1
a448 1
#if DO_TOUR
d454 1
a454 1
#if DO_TOUR
d460 1
a460 1
#if DO_TOUR
d665 1
a665 1
#if DO_MATCHING
@


1.120
log
@Fixed RCS log behaviour.
@
text
@d8 3
d94 1
a94 1
const char *construct_rcs_id = "$Id: construct.w,v 1.119 1997/08/15 20:18:25 neto Exp neto $";
d276 1
d281 1
d382 3
d386 1
d416 1
d418 1
d422 1
d424 1
d428 1
d430 1
d445 1
d447 1
d451 3
a453 1
free_mem(tail);
d457 1
d459 1
d554 152
@


1.119
log
@Added Index major section.
@
text
@d6 5
a10 1
{\obeylines$Log: construct.w,v $
d91 1
a91 1
const char *construct_rcs_id = "$Id: construct.w,v 1.118 1997/06/17 21:23:52 net