dirtytest.c

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

/*43:*/
#line 688 "./dirty.w"

#include <config.h> 
#include "lkconfig.h"
#include <stdio.h> 
#include <stdlib.h> 
#include <stddef.h> 
#include <string.h> 
#include "dirty.h"
#include "prng.h"

/*44:*/
#line 715 "./dirty.w"


void test_word(char const*word,prng_t*p);
void
test_word(char const*word,prng_t*p)
{
int len= strlen(word),r,size;
dirty_set_t*ds= dirty_create(256,0,prng_unif_int(p,32767),__FILE__,__LINE__);
printf("Start empty: ");
for(r= 0;r<len;r++){
while(prng_unif_int(p,len)<len/2)/*45:*/
#line 745 "./dirty.w"

{
const int ret= dirty_remove(ds);
printf("-%c",ret==-1?' ':ret);
}

/*:45*/
#line 725 "./dirty.w"

printf("+%c",word[r]);
dirty_add(ds,(int)word[r]);
}
while(dirty_has_elements(ds))/*45:*/
#line 745 "./dirty.w"

{
const int ret= dirty_remove(ds);
printf("-%c",ret==-1?' ':ret);
}

/*:45*/
#line 729 "./dirty.w"

dirty_destroy(ds);

printf("\nStart full:\n");
size= len> 26?26:len;
ds= dirty_create(size,1,prng_unif_int(p,32767),__FILE__,__LINE__);
for(r= 0;r<len;r++)
while(dirty_has_elements(ds)){
/*47:*/
#line 759 "./dirty.w"

{int i;
printf("\t\tSet includes: ");
for(i= 0;i<size;i++){
putchar(dirty_includes(ds,i)?'a'+i:' ');
}
putchar('\n');
}


/*:47*/
#line 737 "./dirty.w"

/*46:*/
#line 752 "./dirty.w"

{
const int ret= dirty_remove(ds);
printf("\tExtract %c\n",ret==-1?' ':ret+'a');
}

/*:46*/
#line 738 "./dirty.w"

}
/*47:*/
#line 759 "./dirty.w"

{int i;
printf("\t\tSet includes: ");
for(i= 0;i<size;i++){
putchar(dirty_includes(ds,i)?'a'+i:' ');
}
putchar('\n');
}


/*:47*/
#line 740 "./dirty.w"

printf("\n\n");
}

/*:44*/
#line 698 "./dirty.w"


int
main(int argc,char**argv)
{
int i;
prng_t*p= prng_new(PRNG_DEFAULT,21115);
test_word("David Neto was here",p);
for(i= 0;i<argc;i++){
test_word(argv[i],p);
}
test_word("Perl rocks!",p);
return 0;
}

/*:43*/