#define make_mates(u,v) ((mate[(u) ]= (v) ) ,(mate[(v) ]= (u) ) ) #define dump_core(x) ((verbose%2) ?*(int*) 0= (x) :(s_x= (x) ) ) #define basic_swap_mates(a,b,c,d) (make_mates((a) ,(d) ) ,make_mates((b) ,(c) ) ) #define cautious_swap_mates(a,b,c,d) { \s_a= a; \s_b= b; \s_c= c; \s_d= d; \if(a<0||a>=n) dump_core(41) ; \if(b<0||b>=n) dump_core(42) ; \if(c<0||c>=n) dump_core(43) ; \if(d<0||d>=n) dump_core(44) ; \if((mate[a]!=b&&mate[b]!=a) ||(mate[c]!=d&&mate[d]!=c) ) dump_core(45) ; \errorif((mate[a]!=b&&mate[b]!=a) ||(mate[c]!=d&&mate[d]!=c) , \"swap_mates(%d,%d,%d,%d) aren't pairwise mates",a,b,c,d) ; \basic_make_mates(a,b,c,d) ; \} \#define city_name(I) (1+(original_city_num?original_city_num[I]:I) )  \#define USE_DECLUSTER (JBMR_DECLUSTER_IN_ELIGIBILITY_TEST||JBMR_DECLUSTER_IN_GREEDY \)  \#define mark_dirty(CITY) (dirty_add(dirty_set,(CITY) ) )  \#define DEPTHS_BOUND (n/2+8)  \#define write_log(A) (change_log[change_log_next++]= (A) )  \/*4:*/#line 228 "./match.w"#include <config.h> #include "declevel.h"#include "lkconfig.h"/*16:*/#line 415 "./match.w"#include <stddef.h> #include <stdio.h> #include <stdlib.h> /*:16*//*37:*/#line 747 "./match.w"#include <limits.h> /*:37*/#line 232 "./match.w"/*13:*/#line 368 "./match.w"#include "error.h"#include "memory.h"#include "length.h"#include "read.h"#include "match.h"/*:13*//*23:*/#line 554 "./match.w"#include "lk.h"/*:23*//*26:*/#line 585 "./match.w"#include "construct.h"/*:26*//*46:*/#line 902 "./match.w"#include "nn.h"/*:46*//*51:*/#line 977 "./match.w"#include "dirty.h"/*:51*//*63:*/#line 1164 "./match.w"#include "decluster.h"/*:63*//*93:*/#line 1659 "./match.w"#include "milestone.h"/*:93*//*116:*/#line 1892 "./match.w"#include "resource.h"/*:116*/#line 233 "./match.w"/*6:*/#line 283 "./match.w"#if defined(MATCH_DEBUG)#define swap_mates(a,b,c,d) cautious_swap_mates(a,b,c,d)#else#define swap_mates(a,b,c,d) basic_swap_mates(a,b,c,d)#endif/*:6*//*33:*/#line 673 "./match.w"#define SPLIT_GAIN_VAR (!(LENGTH_TYPE_IS_EXACT))/*:33*//*34:*/#line 703 "./match.w"#if !SPLIT_GAIN_VAR#define CAREFUL_OP(LHS,OP,RHS) ((LHS) OP (RHS))#else#define CAREFUL_OP(LHS,OP,RHS) ((LHS##_pos) OP (RHS##_with_slop + LHS##_neg))#endif/*:34*/#line 235 "./match.w"/*44:*/#line 861 "./match.w"typedef struct{length_t gain_for_comparison;length_t cluster_distance;#if SPLIT_GAIN_VARlength_t gain_1_pos,gain_1_neg;length_t gain_pos,gain_neg;#elselength_t gain_1;length_t gain;#endifint t2ip1,t2ip2;int two_i;}eligible_t;/*:44*/#line 236 "./match.w"/*5:*/#line 250 "./match.w"static int*mate= NULL;static int n= 0;/*:5*//*28:*/#line 607 "./match.w"int*t;/*:28*/#line 237 "./match.w"/*7:*/#line 294 "./match.w"#if defined(MATCH_DEBUG)static int s_a= -1,s_b= -1,s_c= -1,s_d= -1,s_x= -1;#endifstatic void(*prev_cleanup_fn)(void);staticvoiddump_ds(void){#if MATCH_DEBUGint i;printf("dumping core: %d\n",s_x);printf("possibly swapping (%d,%d,%d,%d)\n",s_a,s_b,s_c,s_d);for(i= 0;i<n;i++){printf("  mate[%d] = %d\n",i,mate[i]);}#endifif(prev_cleanup_fn)prev_cleanup_fn();}/*:7*//*67:*/#line 1232 "./match.w"static int cmp_eligible(const void*a,const void*b);static intcmp_eligible(const void*a,const void*b){const eligible_t*ea= (const eligible_t*)a;const eligible_t*eb= (const eligible_t*)b;length_t diff= ea->gain_for_comparison-eb->gain_for_comparison;return diff<0?1:(diff> 0?-1:0);}/*:67*//*109:*/#line 1809 "./match.w"static voidshow_entry_with_string_at_verbose(const eligible_t*e_entry,const char*str,int the_verbose){if(verbose>=the_verbose){printf("\n%s: %p two_i %d  t2ip1 = %d  t2ip2 = %d "length_t_spec" -> "length_t_spec,str,e_entry,e_entry->two_i,e_entry->t2ip1,e_entry->t2ip2,#if SPLIT_GAIN_VARlength_t_pcast(e_entry->gain_pos-e_entry->gain_neg),#elselength_t_pcast(e_entry->gain),#endiflength_t_pcast(e_entry->gain_for_comparison));fflush(stdout);}}/*:109*/#line 238 "./match.w"/*9:*/#line 321 "./match.w"voidmatch_setup(int the_n){errorif(the_n%2,"Perfect matchings require an even number of vertices; given %d\n",the_n);n= the_n;mate= new_arr_of(int,n);mate[0]= -1;/*29:*/#line 611 "./match.w"t= new_arr_of(int,n+1);/*:29*/#line 330 "./match.w"}/*:9*//*10:*/#line 335 "./match.w"voidmatch_cleanup(void){if(mate){free_mem(mate);mem_deduct(n*sizeof(int));}/*30:*/#line 615 "./match.w"if(t){free_mem(t);mem_deduct(sizeof(int)*(n+1));}/*:30*/#line 340 "./match.w"n= 0;}/*:10*//*15:*/#line 390 "./match.w"voidmatch_show(FILE*out){length_t weight= 0;int i;errorif(mate==NULL||mate[0]==-1,"Tried to print a matching before it is initialized");fprintf(out,"Perfect matching:\n");for(i= 0;i<n;i++){const int i_mate= mate[i];if(i_mate> i){fprintf(out,"%d %d\n",city_name(i),city_name(i_mate));weight+= cost(i,i_mate);}}fprintf(out,"Length: "length_t_spec"\n",length_t_pcast(weight));}/*:15*//*17:*/#line 425 "./match.w"voidmatch_ps_out(FILE*ps_out,const char*name){length_t weight= 0;int i;errorif(mate==NULL||mate[0]==-1,"Tried to print a matching before it is initialized");fprintf(ps_out,"%%Here's a weighted perfect matching\n");for(i= 0;i<n;i++){const int i_mate= mate[i];if(i_mate> i){weight+= cost(i,i_mate);fprintf(ps_out,"%f x %f y %f x %f y rawedge\n",tsp_instance->coord[i].x[0],tsp_instance->coord[i].x[1],tsp_instance->coord[i_mate].x[0],tsp_instance->coord[i_mate].x[1]);}}fprintf(ps_out,"(%s matching, weight "length_t_native_spec") title\n",name,length_t_native_pcast(weight));fprintf(ps_out,"(%s) comment\n",tsp_instance->comment);fprintf(ps_out,"showpage\n");fflush(ps_out);}/*:17*//*19:*/#line 466 "./match.w"voidmatch_validate(length_t*validate_len,double*double_validate_len,double*ordered_double_len,double*raw_len){length_t my_validate_len= 0;double my_double_validate_len= 0,my_ordered_double_len= 0,my_raw_len= 0;double*length= new_arr_of(double,n/2);double*raw_length= new_arr_of(double,n/2);length_t*length_t_length= new_arr_of(length_t,n/2);int i,w;errorif(mate==NULL||mate[0]==-1,"Tried to validate a matching before it is initialized");/*21:*/#line 517 "./match.w"{int i,*visited= new_arr_of_zero(int,n);for(i= 0;i<n;i++){const int i_mate= mate[i];errorif(i_mate<0||i_mate>=n,"Mate of %d is %d, out of range\n",i_mate);visited[i]++;visited[i_mate]++;}for(i= 0;i<n;i++){errorif(visited[i]!=2,"Vertex %d visited %d times, not 2 times",i,visited[i]);}free_mem(visited);}/*:21*/#line 481 "./match.w"for(i= 0,w= 0;i<n;i++){const int i_mate= mate[i];if(i_mate> i){length_t_length[w]= cost(i,i_mate);length[w]= (double)length_t_length[w];my_double_validate_len+= length[w];switch(tsp_instance->edge_weight_type){case EUC_2D:case CEIL_2D:raw_length[w]= cost_from_euc2d_raw(i,i_mate);break;default:raw_length[w]= length[w];}w++;}}/*22:*/#line 539 "./match.w"sort(length,(unsigned)n/2,sizeof(double),lk_double_cmp);sort(raw_length,(unsigned)n/2,sizeof(double),lk_double_cmp);sort(length_t_length,(unsigned)n/2,sizeof(length_t),lk_length_t_cmp);my_validate_len= 0;my_ordered_double_len= my_raw_len= 0.0;for(i= 0;i<n/2;i++){my_validate_len+= length_t_length[i];my_ordered_double_len+= length[i];my_raw_len+= raw_length[i];}/*:22*/#line 499 "./match.w"free_mem(length);free_mem(raw_length);free_mem(length_t_length);mem_deduct((n/2)*sizeof(length_t)+sizeof(double)+sizeof(double));*validate_len= my_validate_len;*double_validate_len= my_double_validate_len;*ordered_double_len= my_ordered_double_len;*raw_len= my_raw_len;}/*:19*//*24:*/#line 570 "./match.w"length_tmatch_construct(int alg,long alg_param,const long random_seed){errorif(mate==NULL,"Tried to construct a matching before space is allocated");return construct_matching(n,mate,alg,alg_param,random_seed);}/*:24*//*49:*/#line 940 "./match.w"void match_run(const int backtracking_levels,const int iterations,prng_t*random_stream){int iteration;/*31:*/#line 628 "./match.w"int two_i;/*:31*//*32:*/#line 662 "./match.w"#if SPLIT_GAIN_VARlength_t cum_gain_pos,cum_gain_neg;#elselength_t cum_gain;#endif/*:32*//*35:*/#line 736 "./match.w"length_t best_gain;int best_two_i,best_exit_a,best_exit_b;/*:35*//*38:*/#line 760 "./match.w"#if !LENGTH_TYPE_IS_EXACTlength_t best_gain_with_slop;length_t instance_epsilon;#endif/*:38*//*45:*/#line 897 "./match.w"eligible_t**e;int*en,*ei;/*:45*//*58:*/#line 1049 "./match.w"int keep_going;/*:58*//*71:*/#line 1315 "./match.w"const int max_two_i= (max_generic_flips==INT_MAX?INT_MAX:2*(backtracking_levels+max_generic_flips));/*:71*//*77:*/#line 1418 "./match.w"#if MATCH_REPORT_DEPTHSint probe_depth_less_2,move_depth;#endif/*:77*//*78:*/#line 1435 "./match.w"#if MATCH_REPORT_DEPTHSint*m_depths= new_arr_of_zero(int,DEPTHS_BOUND);int*p_depths= new_arr_of_zero(int,DEPTHS_BOUND);#endif/*:78*//*86:*/#line 1536 "./match.w"int*change_log= NULL,change_log_max_alloc,change_log_next= 0;/*:86*//*88:*/#line 1560 "./match.w"length_t previous_incumbent_len= 0;/*:88*//*92:*/#line 1654 "./match.w"milestone_state_t ms_lower_bound;milestone_state_t ms_upper_bound;/*:92*/#line 945 "./match.w"dirty_set_t*dirty_set;/*54:*/#line 995 "./match.w"dirty_set= dirty_create(n,1,prng_unif_int(random_stream,n),__FILE__,__LINE__);/*:54*/#line 947 "./match.w"/*8:*/#line 315 "./match.w"prev_cleanup_fn= error_precleanup_stats;error_precleanup_stats= dump_ds;/*:8*//*40:*/#line 775 "./match.w"/*39:*/#line 769 "./match.w"#if !LENGTH_TYPE_IS_EXACTinstance_epsilon= incumbent_len*LENGTH_MACHINE_EPSILON;#endif/*:39*/#line 776 "./match.w"/*:40*//*47:*/#line 906 "./match.w"{int l;e= new_arr_of(eligible_t*,1+2*backtracking_levels);en= new_arr_of(int,1+2*backtracking_levels);ei= new_arr_of(int,1+2*backtracking_levels);for(l= 2;l<=2*backtracking_levels;l+= 2)e[l]= new_arr_of(eligible_t,nn_max_bound);}/*:47*//*84:*/#line 1524 "./match.w"change_log_max_alloc= 10000;change_log= new_arr_of(int,change_log_max_alloc);/*:84*//*94:*/#line 1663 "./match.w"milestone_initialize(&ms_lower_bound,lower_bound_name,(length_t)lower_bound_value,begin_data_structures_mark);milestone_initialize(&ms_upper_bound,upper_bound_name,(length_t)upper_bound_value,begin_data_structures_mark);milestone_show_initial(&ms_lower_bound,incumbent_len);milestone_show_initial(&ms_upper_bound,incumbent_len);/*:94*/#line 949 "./match.w"for(iteration= 0;iteration<iterations;iteration++){int dirty;while((dirty= dirty_remove(dirty_set))>=0){t[1]= dirty;t[2]= mate[t[1]];two_i= 2;/*36:*/#line 741 "./match.w"best_gain= 0;best_two_i= 0;best_exit_a= best_exit_b= INT_MAX;/*:36*//*41:*/#line 779 "./match.w"#if SPLIT_GAIN_VARbest_gain_with_slop= instance_epsilon;#endif/*:41*//*52:*/#line 981 "./match.w"#if SPLIT_GAIN_VARcum_gain_pos= cost(t[1],t[2]);cum_gain_neg= 0;#elsecum_gain= cost(t[1],t[2]);#endif/*:52*//*76:*/#line 1411 "./match.w"#if MATCH_REPORT_DEPTHSprobe_depth_less_2= -2;move_depth= 0;#endif/*:76*/#line 956 "./match.w"/*57:*/#line 1024 "./match.w"/*110:*/#line 1832 "./match.w"#if MATCH_MAX_VERBOSE >= 105if(verbose>=105){printf("*");}#endif/*:110*/#line 1025 "./match.w"ei[two_i]= -2;en[two_i]= -1;{keep_going= 1;while(keep_going){if(two_i<=2*backtracking_levels){if(ei[two_i]==-2){/*59:*/#line 1060 "./match.w"{int j,num_candidates,*candidates;candidates= nn_list(t[two_i],&num_candidates);for(en[two_i]= j= 0;j<num_candidates;j++){const int t2ip1= candidates[j],t2ip2= mate[t2ip1];eligible_t*e_entry= &e[two_i][en[two_i]];/*61:*/#line 1122 "./match.w"{int j,tabu= 0;if(t2ip2==t[two_i]){/*104:*/#line 1772 "./match.w"#if MATCH_MAX_VERBOSE >= 500if(verbose>=500){printf("X");fflush(stdout);}#endif/*:104*/#line 1125 "./match.w"continue;}for(j= 2;j<two_i;j+= 2){if((t2ip1==t[j]&&t2ip2==t[j+1])||(t2ip1==t[j+1]&&t2ip2==t[j])){tabu= 1;break;}}if(tabu){/*104:*/#line 1772 "./match.w"#if MATCH_MAX_VERBOSE >= 500if(verbose>=500){printf("X");fflush(stdout);}#endif/*:104*/#line 1130 "./match.w"continue;}}/*:61*/#line 1066 "./match.w"/*62:*/#line 1138 "./match.w"{const length_t this_neg= cost(t[two_i],t2ip1),this_pos= cost(t2ip1,t2ip2),this_net= this_pos-this_neg;e_entry->t2ip1= t2ip1;e_entry->t2ip2= t2ip2;#if SPLIT_GAIN_VARe_entry->gain_1_neg= cum_gain_neg+this_neg;e_entry->gain_1_pos= cum_gain_pos;e_entry->gain_neg= cum_gain_neg+this_neg;e_entry->gain_pos= cum_gain_pos+this_pos;#elsee_entry->gain_1= cum_gain-this_neg;e_entry->gain= cum_gain+this_net;#endif#if USE_DECLUSTERe_entry->cluster_distance= decluster_d(t[1],t2ip2);e_entry->gain_for_comparison= this_net-e_entry->cluster_distance;#elsee_entry->gain_for_comparison= this_net;#endife_entry->two_i= two_i;}/*:62*/#line 1067 "./match.w"/*64:*/#line 1172 "./match.w"{const length_t cluster_dist= (USE_DECLUSTER?e_entry->cluster_distance:0);if(CAREFUL_OP(e_entry->gain,<=,cluster_dist+best_gain)||CAREFUL_OP(e_entry->gain_1,<=,best_gain)){/*105:*/#line 1781 "./match.w"#if MATCH_MAX_VERBOSE >= 500if(verbose>=500){printf("<");fflush(stdout);}#endif/*:105*/#line 1177 "./match.w"continue;}}/*:64*/#line 1068 "./match.w"/*106:*/#line 1790 "./match.w"#if MATCH_MAX_VERBOSE >= 500show_entry_with_string_at_verbose(e_entry,"accept",500);#endif/*:106*/#line 1069 "./match.w"/*65:*/#line 1195 "./match.w"{#if SPLIT_GAIN_VARconst length_t possible_best_gain_pos= e_entry->gain_pos,possible_best_gain_neg= e_entry->gain_neg+cost(t[1],e_entry->t2ip2);#elseconst length_t possible_best_gain= e_entry->gain-cost(t[1],e_entry->t2ip2);#endifif(CAREFUL_OP(possible_best_gain,> ,best_gain)){best_two_i= two_i;best_exit_a= t2ip1;best_exit_b= t2ip2;#if SPLIT_GAIN_VARbest_gain= possible_best_gain_pos-possible_best_gain_neg;#elsebest_gain= possible_best_gain;#endif#if !LENGTH_TYPE_IS_EXACTbest_gain_with_slop= best_gain+instance_epsilon;#endif/*99:*/#line 1710 "./match.w"#if MATCH_MAX_VERBOSE >= 125if(verbose>=125){printf(" verbose %d ===two_i %d best_two_i %d best_exit_a %d best_exit_b %d\n",verbose,two_i,best_two_i,best_exit_a,best_exit_b);fflush(stdout);}#endif/*:99*/#line 1216 "./match.w"}}/*:65*/#line 1070 "./match.w"en[two_i]++;}/*66:*/#line 1224 "./match.w"sort(e[two_i],(size_t)en[two_i],sizeof(eligible_t),cmp_eligible);/*:66*/#line 1073 "./match.w"ei[two_i]= 0;}/*:59*//*60:*/#line 1078 "./match.w"if(two_i<2*backtracking_levels){ei[two_i+2]= -2;en[two_i+2]= -1;}/*:60*/#line 1032 "./match.w"}if(ei[two_i]<en[two_i]){const eligible_t*e_entry= e[two_i]+ei[two_i];/*111:*/#line 1840 "./match.w"#if MATCH_MAX_VERBOSE >= 109if(verbose>=109){printf("g");}#endif/*:111*/#line 1036 "./match.w"ei[two_i]++;/*68:*/#line 1252 "./match.w"/*108:*/#line 1803 "./match.w"#if MATCH_MAX_VERBOSE >= 500show_entry_with_string_at_verbose(e_entry,"doing move",500);#endif/*:108*/#line 1253 "./match.w"#if SPLIT_GAIN_VARcum_gain_pos= e_entry->gain_pos;cum_gain_neg= e_entry->gain_neg;#elsecum_gain= e_entry->gain;#endif#if defined(MATCH_DEBUG)if(e_entry->two_i!=two_i)dump_core(96);#endift[two_i+1]= e_entry->t2ip1;