lk.c

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

if(r+1<argc&&is_number(argv[r+1]))max_generic_flips= atoi(argv[++r]);
continue;
}

/*:37*//*42:*/
#line 1325 "./lk.w"

if(strcmp(argv[r],"--seed")==0){
random_seed= RIGHT_NOW;
if(r+1<argc){
if(is_number(argv[r+1]))random_seed= atol(argv[++r]);
else if(strcmp("now",argv[r+1])==0)r++;
}
continue;
}


/*:42*//*43:*/
#line 1339 "./lk.w"

if(strcmp(argv[r],"-s")==0||strcmp(argv[r],"--start")==0){
if(r+1>=argc){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1342 "./lk.w"

fprintf(stderr,"Need one of {canonical,greedy,greedydet,random [seed]}\n");
exit(1);
}
r++;

if(strcmp(argv[r],"greedy")==0)construction_algorithm= CONSTRUCT_GREEDY_RANDOM;
else if(strcmp(argv[r],"greedydet")==0)construction_algorithm= CONSTRUCT_GREEDY;
else if(strcmp(argv[r],"canonical")==0)construction_algorithm= CONSTRUCT_CANONICAL;
else if(strcmp(argv[r],"random")==0){
construction_algorithm= CONSTRUCT_RANDOM;
if(r+1<argc&&is_number(argv[r+1]))start_heuristic_param= atol(argv[++r]);
}else{
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1355 "./lk.w"

fprintf(stderr,"Need one of {canonical,greedy,greedydet,random [seed],best}\n");
exit(1);
}
continue;
}

/*:43*//*44:*/
#line 1364 "./lk.w"

if(strcmp(argv[r],"-S")==0||strcmp(argv[r],"--sort")==0){
if(r+1>=argc){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1367 "./lk.w"

fprintf(stderr,"Need one of {dsort,qsort}\n");
exit(1);
}
r++;

if(strcmp(argv[r],"qsort")==0)
sort= (void(*)(void*,size_t,size_t,int(*)(const void*,const void*)))qsort;
else if(strcmp(argv[r],"dsort")==0)sort= dsort;
else{
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1377 "./lk.w"

fprintf(stderr,"Need one of {dsort,qsort}\n");
exit(1);
}
continue;
}

/*:44*//*46:*/
#line 1391 "./lk.w"

if(strcmp(argv[r],"-r")==0||strcmp(argv[r],"--representation")==0){
if(r+1>=argc){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1394 "./lk.w"

fprintf(stderr,"Need one of {array,splay [level],two-level,tld}\n");
exit(1);
}
r++;
if(strcmp(argv[r],"array")==0){
representation= REP_ARRAY;
}else if(strcmp(argv[r],"two-level")==0){
representation= REP_TWO_LEVEL;
}else if(strcmp(argv[r],"tld")==0){
representation= REP_TWO_LEVEL_DEBUG;
}else if(strcmp(argv[r],"splay")==0){
int level= 0;
if(r+1<argc&&is_number(argv[r+1]))level= atoi(argv[++r]);
if(level<0||level>3){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1409 "./lk.w"

fprintf(stderr,"Splay level must be 0, 1, 2, or 3\n");
exit(1);
}
representation= REP_SPLAY_0+level;
}else{
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1415 "./lk.w"

fprintf(stderr,"Need one of {array,splay [level],two-level,tld}\n");
exit(1);
}
continue;
}

/*:46*//*47:*/
#line 1423 "./lk.w"

if(strcmp(argv[r],"-P")==0||strcmp(argv[r],"--postscript")==0){
if(r+1>=argc){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1426 "./lk.w"

fprintf(stderr,"Need a file name\n");
exit(1);
}
r++;
if(postscript_filecount){
fprintf(stderr,
"Warning: %s already specified as PostScript output file; "
"%s overrides\n",
PostScript_filename,argv[r]);
}
postscript_filecount++;
PostScript_filename= argv[r];
continue;
}

/*:47*//*48:*/
#line 1445 "./lk.w"

if(strcmp(argv[r],"-l")==0||strcmp(argv[r],"--lower-bound")==0){
if(r+1>=argc){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1448 "./lk.w"

fprintf(stderr,"Need a lower bound name\n");
exit(1);
}
if(r+2>=argc){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1453 "./lk.w"

fprintf(stderr,"Need a lower bound on length\n");
exit(1);
}
r++;
lower_bound_name= dup_string(argv[r]);
r++;
lower_bound_value= atof(argv[r]);
continue;
}

/*:48*//*49:*/
#line 1466 "./lk.w"

if(strcmp(argv[r],"-u")==0||strcmp(argv[r],"--upper-bound")==0){
if(r+1>=argc){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1469 "./lk.w"

fprintf(stderr,"Need an upper bound name\n");
exit(1);
}
if(r+2>=argc){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1474 "./lk.w"

fprintf(stderr,"Need an upper bound on length\n");
exit(1);
}
r++;
upper_bound_name= dup_string(argv[r]);
r++;
upper_bound_value= atof(argv[r]);
continue;
}

/*:49*//*51:*/
#line 1497 "./lk.w"

if(strcmp(argv[r],"-c")==0||strcmp(argv[r],"--candidate")==0){
int numeric_param;
candidate_expr= cand_nn_k= cand_nq_k= cand_del_d= 0;
r++;
do{
if(r>=argc||
(strcmp(argv[r],"nn")!=0&&strcmp(argv[r],"nq")!=0&&
strcmp(argv[r],"del")!=0)
){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1507 "./lk.w"

fprintf(stderr,"Need one of {nn,nq,del}\n");
exit(1);
}
if(r+1>=argc||!is_number(argv[r+1])){
r++;
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1513 "./lk.w"

fprintf(stderr,"Need a numeric parameter\n");
exit(1);
}else numeric_param= atoi(argv[r+1]);
if(strcmp(argv[r],"nn")==0){
candidate_expr|= CAND_NN;
if(cand_nn_k<numeric_param)cand_nn_k= numeric_param;
}else if(strcmp(argv[r],"nq")==0){
candidate_expr|= CAND_NQ;
if(cand_nq_k<numeric_param)cand_nq_k= numeric_param;
}else if(strcmp(argv[r],"del")==0){
candidate_expr|= CAND_DEL;
if(cand_del_d<numeric_param)cand_del_d= numeric_param;
}else{
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1527 "./lk.w"

fprintf(stderr,"Need one of {nn,nq,del}\n");
exit(1);
}
r++;
}while(r+1<argc&&strcmp(argv[r+1],"or")==0&&(r+= 2));
continue;
}

/*:51*/
#line 980 "./lk.w"

/*52:*/
#line 1541 "./lk.w"

/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 1542 "./lk.w"

fprintf(stderr,"Skipping unrecognized option %s\n",argv[r]);

/*:52*/
#line 981 "./lk.w"

}else{
if(filecount){
/*53:*/
#line 1557 "./lk.w"

{int chars_before_split= 0,i;
for(i= 0;i<=r&&i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
chars_before_split+= strlen(argv[i])+1;
}
fputc('\n',stderr);
for(i= 0;i<chars_before_split;i++){fputc(' ',stderr);}
for(i= r+1;i<argc;i++){
fprintf(stderr,"%s ",argv[i]);
}
fputc('\n',stderr);
}

/*:53*/
#line 984 "./lk.w"

fprintf(stderr,"Only one input file allowed\n");
exit(1);
}
if(!(more_options&&strcmp(argv[r],"-")==0))
filename= argv[r];

filecount++;
}
}
}
/*50:*/
#line 1488 "./lk.w"

errorif((held_karp_only||held_karp_lambda_only)&&do_weighted_perfect_matching,
"Held-Karp lower bound valid only for the TSP, not perfect matching\n");


/*:50*/
#line 995 "./lk.w"



/*:12*//*98:*/
#line 2283 "./lk.w"

switch(representation){
case REP_ARRAY:
tour_next= array_next;
tour_prev= array_prev;
tour_between= array_between;
tour_flip= array_flip;
tour_set= array_set;
tour_setup= array_setup;
tour_cleanup= array_cleanup;
break;
case REP_TWO_LEVEL:
tour_next= twolevel_next;
tour_prev= twolevel_prev;
tour_between= twolevel_between;
tour_flip= twolevel_flip;
tour_set= twolevel_set;
tour_setup= NULL;
tour_cleanup= twolevel_cleanup;
break;
case REP_TWO_LEVEL_DEBUG:
#if defined(TWOLEVEL_DEBUG)
tour_next= twolevel_debug_next;
tour_prev= twolevel_debug_prev;
tour_between= twolevel_debug_between;
tour_flip= twolevel_debug_flip;
tour_set= twolevel_debug_set;
tour_setup= NULL;
tour_cleanup= twolevel_debug_cleanup;
#else
errorif(1,"Two-level tree debugging (-DTWOLEVEL_DEBUG) wasn't compiled into the program");
#endif
break;
default:
errorif(1,"Only array, two-level, and tld representations are currently supported");
}

/*:98*/
#line 692 "./lk.w"

/*54:*/
#line 1582 "./lk.w"

if(verbose>=10){
extern const char*compile_compile,*compile_link;
/*55:*/
#line 1631 "./lk.w"

printf("LK %s",VERSION_STRING);
#if JBMR_DECLUSTER_IN_ELIGIBILITY_TEST
printf("de");
# if JBMR_DECLUSTER_IN_GREEDY
printf("g");
# endif
#endif
printf("\n");

/*:55*/
#line 1585 "./lk.w"

if(verbose>=10)/*56:*/
#line 1642 "./lk.w"

printf(
"LK approximately solves the traveling salesman problem.\n"
"\nCopyright (C) 1998 David M. Neto\n"
"LK comes with NO WARRANTY, to the extent permitted by law.\n"
"You may redistribute and/or modify copies of LK under the terms of the\n"
"GNU Library General Public License, version 2 or any later version.\n"
"For more information about these matters, see the file named COPYING.LIB.\n"

);

/*:56*/
#line 1586 "./lk.w"

if(verbose>=100){
extern const char*dirty_rcs_id,*pq_rcs_id,*tabuhash_rcs_id;
printf("%s\n",compile_compile);
printf("%s\n",compile_link);
printf("%s\n",array_rcs_id);
printf("%s\n",ascend_rcs_id);
printf("%s\n",construct_rcs_id);
printf("%s\n",decluster_rcs_id);
printf("%s\n",dict_rcs_id);
printf("%s\n",dirty_rcs_id);
printf("%s\n",dsort_rcs_id);
printf("%s\n",error_rcs_id);
#if defined(OS_HAS_BROKEN_HEADERS)
printf("%s\n",fixincludes_rcs_id);
#endif
printf("%s\n",jbmr_rcs_id);
printf("%s\n",kdtree_rcs_id);
printf("%s\n",length_rcs_id);
printf("%s\n",lk_rcs_id);
printf("%s\n",match_rcs_id);
printf("%s\n",memory_rcs_id);
printf("%s\n",nn_rcs_id);
printf("%s\n",pool_rcs_id);
printf("%s\n",prng_rcs_id);
printf("%s\n",pq_rcs_id);
printf("%s\n",read_rcs_id);
printf("%s\n",resource_rcs_id);
printf("%s\n",tabuhash_rcs_id);
printf("%s\n",twolevel_rcs_id);
}
printf("Command line equivalent: ");/*58:*/
#line 1665 "./lk.w"

if(verbose>=10){
printf("%s ",argv[0]);
if(verbose!=DEFAULT_VERBOSE)printf("-v %d ",verbose);
printf("--seed %ld ",random_seed);
if(should_show_version)printf("--version ");
if(do_weighted_perfect_matching)printf("-m ");
if(mst_only)printf("-M ");
if(held_karp_only)printf("--held-karp ");
if(held_karp_lambda_only)printf("--held-karp-lambda ");
if(should_show_tour)printf("-p ");
if(noround)printf("--no-round ");
if(extra_backtrack)printf("--extra-backtrack ");
else printf("--no-extra-backtrack ");
if(NULL!=PostScript_filename)printf("-P %s ",PostScript_filename);
if(iterations!=1)printf("-i %d ",iterations);
switch(construction_algorithm){
case CONSTRUCT_CANONICAL:printf("-s canonical ");break;
case CONSTRUCT_GREEDY:printf("-s greedydet ");break;
case CONSTRUCT_GREEDY_RANDOM:printf("-s greedy ");break;
case CONSTRUCT_RANDOM:printf("-s random %ld ",start_heuristic_param);break;
default:errorif(1,"Bad construction_algorithm == %d\n",construction_algorithm);
}

if(sort==dsort)printf("-S dsort ");

printf("-c ");
if(candidate_expr&CAND_NN)
printf("nn %d %s",cand_nn_k,
candidate_expr&(CAND_NQ|CAND_DEL)?"or ":"");
if(candidate_expr&CAND_NQ)
printf("nq %d %s",cand_nq_k,
candidate_expr&CAND_DEL?"or ":"");
if(candidate_expr&CAND_DEL)
printf("del %d ",cand_del_d);

switch(representation){