meditationatae

Just another WordPress.com site

Archive for the ‘History’ Category

Test message two

6677710098 2549045791 2581384979 0832320766 7792684161
0847043534 7733176903 3187321879 6880251085 8133893483
2192487449 8085802800 9048920339 5998723353 7957889928
7167981519 4400651069 1724452282 8002046774 2564970036
3873695664 0386461625 9186263741 8923755034 2172046856
9577923255 8533573348 4317934322 9047788820 2542152417
1649025199 8951044235 6020750866 6045227548 3495437139
1041098730 8305067090 6576373097 6982413438 4223786401
2886578081 7453997787 1054028190 0642019131 0909137921
0164111424 5574959549 2163103399 2727789295 0970212659
2221177034 9321491023 8440299797 2255588763 7038543801
7106382245 0932841817 7435280275 5324951152 0618836506
9186892004 314403

 

Advertisements

Written by meditationatae

December 31, 2017 at 4:40 am

Posted in History

Program for heuristic rope team graph coloring

So far, I haven’t found a 47-coloring of the 500-vertex graph known as DSJC500.5, part of the DIMACS challenge on cliques and coloring (1990’s)…

C source code (based on Moalic & Gondran paper):

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_VERTEX 600
#define MAX_COLORS 60
#define NUMITER 8007

unsigned char adj_mat[MAX_VERTEX][MAX_VERTEX];

int Gamma[MAX_VERTEX][MAX_COLORS];

int tabu_list[MAX_VERTEX][MAX_COLORS];
int matches_best_delta[MAX_VERTEX][MAX_COLORS];

static unsigned long long Q[2097152], carry=0;

unsigned long long B64MWC(void)
{ unsigned long long t,x; static int jm=2097151;
jm=(jm+1)&2097151;
x=Q[jm]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[jm]=t-x);
}

#define CNG ( cng=6906969069ULL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )

int main(int argc, char *argv[] )
{
FILE *in;
unsigned long long im,cng=123456789987654321ULL, xs=362436069362436069ULL;
unsigned long long mask = 2147483647ULL;
unsigned long long kiss1, kiss2, seed;
int num_colors;
int num_vertex;
int num_edges;
int num_conflicts;
int k;
int i;
int j;
int sum_adj_mat;
int ru;
int b;
char color;
char init_coloring[MAX_VERTEX];
char init_population[30][MAX_VERTEX];
char old_init_coloring[MAX_VERTEX];
int conflict_count;
int sum_Gamma;
int best_delta;
int delta;
int best_vertex;
char best_color;
long iter_counter;
int A;
float alpha;
int tl;
int b_tabu_rnd;
int tabu_rand;
char color_tabu;
int min_conflicts;
int job_done;
int differences;
FILE *out;
FILE *out2;
int is_round_one;
int problem_solved;
int cnodes;
int select;
int temp;
int candidate_count;
int b_candidate;
int can_number;
int num_try;
int ijk;
int answer;
FILE *insol;
int junk;
char initparent1[MAX_VERTEX];
char initparent2[MAX_VERTEX];
char parent1[MAX_VERTEX];
char parent2[MAX_VERTEX];
int count_classes[MAX_COLORS];
int count;
int maxcount;
int is_maxcount[MAX_COLORS];
int total_maxcount;
int b_total_maxcount;
char random_color_choice;
char index_maxcolor;
char chosen_partition;
char gp;
int taken[MAX_VERTEX];
int total_taken;
char child[MAX_VERTEX];
int b_color_classes;
char child1[MAX_VERTEX];
char child2[MAX_VERTEX];
char best_coloring1[MAX_VERTEX];
char best_coloring2[MAX_VERTEX];
int num_generation;
int j1;
int j2;
int ps1[MAX_COLORS];
int ps2[MAX_COLORS];
int diff;
int tmatch;
int is_perfectmatch;
int itmatch[47];
int oksofar;
int quit_do;
int b_sol;
int j3;
int j4;
int ps1b[MAX_COLORS];
int ps2b[MAX_COLORS];
char initparent1b[MAX_VERTEX];
char initparent2b[MAX_VERTEX];
char parent1b[MAX_VERTEX];
char parent2b[MAX_VERTEX];
char child3[MAX_VERTEX];
char child4[MAX_VERTEX];
int itmatchb[47];
char best_coloring1b[MAX_VERTEX];
char best_coloring2b[MAX_VERTEX];
int realfall;

int tmatchark;
int arkdup;
int tark;
int runs;
unsigned char one;
unsigned char zero;
int clg;
int iter_Tcol;
int reponse;
int noshow;

 

one = (unsigned char) 1;

zero = (unsigned char) 0;

 

select = 2;

 

is_round_one = 1;

out = fopen(“varsol97A”, “w”);

out2 = fopen(“newdecember02at0421A”, “w”);

 

insol = fopen(“newjuly22sol1152”, “r”);

 

alpha = 0.60;
A = 10;
job_done = 0;

 

seed = 15825028261250004972ULL;
// seed = 12699433125966644163ULL;
// seed = 12306818872584100781ULL;
// seed = 18097514362980850667ULL;

seed = 10202155028307188519ULL;
seed = 15031984341198941017ULL;
seed = 15055042048304412413ULL;
seed = 12450716545678999097ULL;
seed = 13559028408021572526ULL;
seed = 16348815711880680099ULL;

 

 

 

num_colors = atoi(argv[2]);
printf(“num_colors = %d\n” , num_colors);

in = fopen(argv[1], “r”);

fscanf(in, “%d %d”, &num_vertex, &num_edges);

printf(“num_vertex = %d\n”, num_vertex);
printf(“num_edges = %d\n”, num_edges);

for(i = 0 ; i < MAX_VERTEX; i++)
{
for(j = 0 ; j < MAX_VERTEX; j++)
{
adj_mat[i][j] = zero;
}
}

 

for(k = 0; k < num_edges; k++)
{
fscanf(in, “%d %d”, &j, &i);
if( i != j )
{
adj_mat[i-1][j-1] = one;
adj_mat[j-1][i-1] = one;
}

if(i == j)
{
printf(“warning: edge %d is = %d %d\n”, k+1, i, j);
}
}

fclose(in);

sum_adj_mat = 0;

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_vertex; j++)
{
if( (adj_mat[i][j] == one) && (i!=j) )
{
sum_adj_mat++;
}
}
}

printf(“sum_adj_mat = %d\n”, sum_adj_mat);

printf(“\n”);

 

printf(“now, read in initial population …\n\n”);

printf(“ok?\n”);

for(k = 0; k< 30 ; k++)
{
for(i = 0 ; i < num_vertex; i++)
{
fscanf(insol, “%d”, &junk);
fscanf(insol, “%d”, &color);
init_population[k][i] = color-1;
}
}

fclose(insol);

 

 

printf(“initial population read in …\n\n”);

printf(“ok?\n”);

 

b_sol = ((int) mask)/30;
b_sol = b_sol + 1;

 

 

printf(“now, select the two initial parents from 100…\n”);

printf(“ok?\n”);

for(runs = 0; runs < 1000000; runs++)
{

 

ru = (int) ((KISS^seed)&mask);
j1 = ru/b_sol;

ru = (int) ((KISS^seed)&mask);
j2 = ru/b_sol;

ru = (int) ((KISS^seed)&mask);
j3 = ru/b_sol;

ru = (int) ((KISS^seed)&mask);
j4 = ru/b_sol;

 

/**********
0
4
11
15
************/

if( (j1!=j2)&&(j1!=j3)&&(j1!=j4)&&(j2!=j3)&&(j2!=j4)&&(j3!=j4) )
{

clg = 1000000;

 

for(i = 0 ; i < num_vertex; i++)
{
initparent1[i] = init_population[j1][i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
initparent2[i] = init_population[j2][i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
initparent1b[i] = init_population[j3][i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
initparent2b[i] = init_population[j4][i];
}

 

// printf(“selection of the two initial parents done…\n”);

// printf(“ok?\n”);

 
// printf(“set parent1 and parent2 and prepare for GPX algorithm…\n”);

 

// printf(“ok?\n”);

printf(“\n”);

 

for(i = 0 ; i < num_vertex; i++)
{
parent1[i] = initparent1[i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
parent2[i] = initparent2[i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
parent1b[i] = initparent1b[i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
parent2b[i] = initparent2b[i];
}

 

// printf(“parent1 and parent2 set.\n”);

quit_do = 0;

realfall = 0;

 

for( num_generation = 1; num_generation <= 700 ; num_generation++)
{

noshow = 1;

 

 

// printf(“clg = %d “, clg);

if( realfall > 40 )
{
quit_do = 1 ;
}

 

 

 

 

if( quit_do == 1)
{
break;
}

 

for(i = 0; i< num_vertex; i++)
{
taken[i] = 0;
}

 

for(i = 0; i< num_vertex; i++)
{
child[i] = -1;
}

 

for( gp = 0; gp < 47; gp++)
{

 

 

if( 0 == (gp%2) )
{

for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

 

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == ((char) i) )&&(taken[j] == 0) )
{
count++;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

 

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount += is_maxcount[i];
}

 

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) ( ru/b_total_maxcount);
random_color_choice++;

 

 

index_maxcolor = 0;

 

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

 

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == chosen_partition) && ( taken[j] == 0) )
{
child[j] = gp;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent1[j] == chosen_partition )
{
taken[j] = 1;
}
}

}
/*************************************

if( 0 == (gp%2) )
{

end of loop…
*************************************/

 

 

if( 1 == (gp%2) )
{
for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == ((char) i) ) &&(taken[j] == 0) )
{
count++;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

 

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

}

 

 

 

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == chosen_partition)&&(taken[j] == 0) )
{
child[j] = gp;
}
}

 

for(j = 0; j< num_vertex; j++)
{
if( parent2[j] == chosen_partition )
{
taken[j] = 1;
}
}

 

}
/*************************************
if( 1 == (gp%2) )
{
end of loop…
*************************************/

 

}
/*************************************
for( gp = 0; gp < 49; gp++)
{
end of loop…
*************************************/

 

 

b_color_classes = ((int) mask)/47;
b_color_classes = b_color_classes + 1;

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_color_classes);
child[i] = random_color_choice;
}
}

 

for(j=0; j < num_vertex; j++)
{
child1[j] = child[j] ;
}

 

/*** child2 below … ***/

 

 

for(i = 0; i< num_vertex; i++)
{
taken[i] = 0;
}

 

for(i = 0; i< num_vertex; i++)
{
child[i] = -1;
}

 

 

for( gp = 0; gp < 47; gp++)
{

if( 0 == (gp%2) )
{

for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

 

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == ((char) i) )&&(taken[j] == 0) )
{
count++;
}
}
count_classes[i] = count;
}

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

 

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

index_maxcolor = 0;

 

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}
}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == chosen_partition) && ( taken[j] == 0) )
{
child[j] = gp;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent2[j] == chosen_partition )
{
taken[j] = 1;
}
}

}
/*************************************

if( 0 == (gp%2) )
{

end of loop…
*************************************/

 

if( 1 == (gp%2) )
{
for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == ((char) i) ) &&(taken[j] == 0) )
{
count++;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == chosen_partition)&&(taken[j] == 0) )
{
child[j] = gp;
}
}

 

for(j = 0; j< num_vertex; j++)
{
if( parent1[j] == chosen_partition )
{
taken[j] = 1;
}
}

 

}
/*************************************
if( 1 == (gp%2) )
{
end of loop…
*************************************/

 

}
/*************************************
for( gp = 0; gp < 49; gp++)
{
end of loop…
*************************************/

 

b_color_classes = ((int) mask)/47;
b_color_classes = b_color_classes + 1;

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_color_classes);
child[i] = random_color_choice;
}
}

 

for(j=0; j < num_vertex; j++)
{
child2[j] = child[j] ;
}

 

/*** child 3 ***/

 

for(i = 0; i< num_vertex; i++)
{
taken[i] = 0;
}

 

for(i = 0; i< num_vertex; i++)
{
child[i] = -1;
}

 

for( gp = 0; gp < 47; gp++)
{

 

if( 0 == (gp%2) )
{

for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

 

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent1b[j] == ((char)i) )&&(taken[j] == 0) )
{
count++;
}
}
count_classes[i] = count;
}

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

 

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}
}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent1b[j] == chosen_partition) && ( taken[j] == 0) )
{
child[j] = gp;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent1b[j] == chosen_partition )
{
taken[j] = 1;
}
}

}
/*************************************

if( 0 == (gp%2) )
{

end of loop…
*************************************/

 

if( 1 == (gp%2) )
{
for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent2b[j] == ((char)i) ) &&(taken[j] == 0) )
{
count++ ;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent2b[j] == chosen_partition)&&(taken[j] == 0) )
{
child[j] = gp;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent2b[j] == chosen_partition )
{
taken[j] = 1;
}
}

 

}
/*************************************
if( 1 == (gp%2) )
{
end of loop…
*************************************/

 

}
/*************************************
for( gp = 0; gp < 49; gp++)
{
end of loop…
*************************************/

 

b_color_classes = ((int) mask)/47;
b_color_classes = b_color_classes + 1;

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_color_classes);
child[i] = random_color_choice;
}
}

 

for(j=0; j < num_vertex; j++)
{
child3[j] = child[j] ;
}

/*** child 3 done ***/

 

 

/*** child 4 ***/

 

for(i = 0; i< num_vertex; i++)
{
taken[i] = 0;
}

 

for(i = 0; i< num_vertex; i++)
{
child[i] = -1;
}

 

for( gp = 0; gp < 47; gp++)
{

if( 0 == (gp%2) )
{

for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

 

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent2b[j] == ((char) i) )&&(taken[j] == 0) )
{
count++ ;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

 

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

 

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

 

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent2b[j] == chosen_partition) && ( taken[j] == 0) )
{
child[j] = gp;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent2b[j] == chosen_partition )
{
taken[j] = 1;
}
}

}
/*************************************

if( 0 == (gp%2) )
{

end of loop…
*************************************/

 

if( 1 == (gp%2) )
{
for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent1b[j] == ((char) i) ) &&(taken[j] == 0) )
{
count++ ;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent1b[j] == chosen_partition)&&(taken[j] == 0) )
{
child[j] = gp;
}
}

 

for(j = 0; j< num_vertex; j++)
{
if( parent1b[j] == chosen_partition )
{
taken[j] = 1;
}
}

 

}
/*************************************
if( 1 == (gp%2) )
{
end of loop…
*************************************/

 

}
/*************************************
for( gp = 0; gp < 49; gp++)
{
end of loop…
*************************************/

 

b_color_classes = ((int) mask)/47;
b_color_classes = b_color_classes + 1;

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_color_classes);
child[i] = random_color_choice;
}
}

 

for(j=0; j < num_vertex; j++)
{
child4[j] = child[j] ;
}

/*** child 4 done ***/

 

num_colors = 47;

for(i = 0; i < num_vertex; i++)
{
init_coloring[i] = child1[i];
}

 

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 1;

 

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 0;
}
}

 

iter_Tcol = NUMITER;

 

 

 

 

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; iter_counter++)
{

problem_solved = 0;

 

if( iter_counter == 1)
{
num_conflicts = 0;

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_colors; k++)
{
Gamma[i][k] = 0;
}
}

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< i; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
Gamma[k][init_coloring[i]]++;

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
num_conflicts+= Gamma[i][init_coloring[i]];
}

num_conflicts = num_conflicts/2;
}

if( num_conflicts < min_conflicts )
{

for(i = 0; i < num_vertex; i++)
{
best_coloring1[i] = init_coloring[i];
}

 

min_conflicts = num_conflicts;

 

// if(num_conflicts < 3)
// {
// printf(“%d conflicts at %d iterations “, num_conflicts, iter_counter);
// }

if(num_conflicts <= 0)
{
problem_solved = 1;

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
printf(“num_generation = %d\n”, num_generation);

for(i = 0; i < num_vertex; i++)
{
fprintf(out2, “%d %d\n”, i+1, init_coloring[i]+1);
}
fflush(out2);

 

printf(“\n”);

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

for(i = 0; i < num_vertex; i++ )
{
fprintf(out, “%d %d\n”, i+1, init_coloring[i]+1);
}

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

if( min_conflicts < clg)
{
clg = min_conflicts;
noshow = 0;
}

 

best_delta = 1000000;

 

for(i = 0; i < num_vertex; i++)
{
if(Gamma[i][init_coloring[i]] > 0)
{

 

for(j = 0; j < num_colors; j++)
{

if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
best_delta = delta;
best_vertex = i;
best_color = (char) j;
}
}
}
}

}
}

 

 

num_conflicts+= best_delta;

cnodes = 0;

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{
cnodes++;
}
}

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = rand();
tabu_rand = ru/b_tabu_rnd;
tl = tl + tabu_rand;

 

color_tabu = init_coloring[best_vertex];

tabu_list[best_vertex][color_tabu] = tl + iter_counter;

init_coloring[best_vertex] = best_color;

 

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color] ++ ;
}
}

}
/*******************************************

for(iter_counter = 1; iter_counter < ; iter_counter++)
{

 

end loop …
**************************************/

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

/*** run tabu search on child2 ***/

 

if( problem_solved == 0 )
{

num_colors = 47;

 

for(i = 0; i < num_vertex; i++)
{
init_coloring[i] = child2[i];
}

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 1;

 

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 0;
}
}

 

iter_Tcol = NUMITER;

 

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; iter_counter++)
{

problem_solved = 0;

if( iter_counter == 1)
{
num_conflicts = 0;

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_colors; k++)
{
Gamma[i][k] = 0;
}
}

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< i; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
Gamma[k][init_coloring[i]]++;

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
num_conflicts+= Gamma[i][init_coloring[i]];
}

num_conflicts = num_conflicts/2;
}

if( num_conflicts < min_conflicts )
{

for(i = 0; i < num_vertex; i++)
{
best_coloring2[i] = init_coloring[i];
}

min_conflicts = num_conflicts;

// if(num_conflicts < 3)
// {
// printf(“%d conflicts at %d iterations “, num_conflicts, iter_counter);
// }

 

if(num_conflicts <= 0)
{
problem_solved = 1;

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
printf(“num_generation = %d\n”, num_generation);

for(i = 0; i < num_vertex; i++)
{
printf(“%d %d\n”, i+1, init_coloring[i]+1);
}

printf(“\n”);

for(i = 0; i < num_vertex; i++)
{
fprintf(out2, “%d %d\n”, i+1, init_coloring[i]+1);
}
fflush(out2);

 

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

for(i = 0; i < num_vertex; i++ )
{
fprintf(out, “%d %d\n”, i+1, init_coloring[i]+1);
}

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

if( min_conflicts < clg)
{
clg = min_conflicts;
noshow = 0;
}

 

best_delta = 1000000;

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

for(j = 0; j < num_colors; j++)
{

 

if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
best_delta = delta;
best_vertex = i;
best_color = (char) j;
}
}
}
}

 

}
}

 

 

 

 

 

 

 

num_conflicts+= best_delta;

cnodes = 0;

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{
cnodes++;
}
}

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = rand();
tabu_rand = ru/b_tabu_rnd;
tl = tl + tabu_rand;

 

color_tabu = init_coloring[best_vertex];

tabu_list[best_vertex][color_tabu] = tl + iter_counter;

init_coloring[best_vertex] = best_color;

 

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color]++ ;
}
}

}
/*******************************************

for(iter_counter = 1; iter_counter < ; iter_counter++)
{

 

end loop …
**************************************/

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

/*** run tabu search on child2 done ***/

 

if( problem_solved == 0)
{

/*** tabu on child 3 ***/

num_colors = 47;

 

 

for(i = 0; i < num_vertex; i++)
{
init_coloring[i] = child3[i];
}

 

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 1;

 

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 0;
}
}

 

 

iter_Tcol = NUMITER;

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; iter_counter++)
{

problem_solved = 0;

 

if( iter_counter == 1)
{
num_conflicts = 0;

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_colors; k++)
{
Gamma[i][k] = 0;
}
}

 

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< i; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
Gamma[k][init_coloring[i]]++;

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
num_conflicts+= Gamma[i][init_coloring[i]];
}

num_conflicts = num_conflicts/2;
}

 

 

if( num_conflicts < min_conflicts )
{

for(i = 0; i < num_vertex; i++)
{
best_coloring1b[i] = init_coloring[i];
}

 

min_conflicts = num_conflicts;

// if(num_conflicts < 3)
// {
// printf(“%d conflicts at %d iterations “, num_conflicts, iter_counter);
// }

 

 

if(num_conflicts <= 0)
{
problem_solved = 1;

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
printf(“num_generation = %d\n”, num_generation);

for(i = 0; i < num_vertex; i++)
{
printf(“%d %d\n”, i+1, init_coloring[i]+1);
}

printf(“\n”);

 

for(i = 0; i < num_vertex; i++)
{
fprintf(out2, “%d %d\n”, i+1, init_coloring[i]+1);
}
fflush(out2);

 

 

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

for(i = 0; i < num_vertex; i++ )
{
fprintf(out, “%d %d\n”, i+1, init_coloring[i]+1);
}

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

if( min_conflicts < clg)
{
clg = min_conflicts;
noshow = 0;
}

 

 

best_delta = 1000000;

 

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

 

for(j = 0; j < num_colors; j++)
{

if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
best_delta = delta;
best_vertex = i;
best_color = (char) j;
}
}
}
}

 

}
}

 

num_conflicts+= best_delta;

cnodes = 0;

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{
cnodes++;
}
}

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = rand();
tabu_rand = ru/b_tabu_rnd;
tl = tl + tabu_rand;

 

 

color_tabu = init_coloring[best_vertex];

tabu_list[best_vertex][color_tabu] = tl + iter_counter;

init_coloring[best_vertex] = best_color;

 

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color]++ ;
}
}

 

 

}
/*******************************************

for(iter_counter = 1; iter_counter < ; iter_counter++)
{

 

end loop …
**************************************/

 

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

/*** run tabu search on child 3 done ***/

/*** run tabu search on child 4 ***/

 

 

 

 

if( problem_solved == 0 )
{

 

/*** tabu on child 4 ***/

num_colors = 47;

 

for(i = 0; i < num_vertex; i++)
{
init_coloring[i] = child4[i];
}

 

 

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 1;

 

 

 

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 0;
}
}

 

 

iter_Tcol = NUMITER;

 

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; iter_counter++)
{

problem_solved = 0;

 

if( iter_counter == 1)
{
num_conflicts = 0;

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_colors; k++)
{
Gamma[i][k] = 0;
}
}

 

 

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< i; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
Gamma[k][init_coloring[i]]++;

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
num_conflicts+= Gamma[i][init_coloring[i]];
}

num_conflicts = num_conflicts/2;
}

 

 

if( num_conflicts < min_conflicts )
{

for(i = 0; i < num_vertex; i++)
{
best_coloring2b[i] = init_coloring[i];
}

 

min_conflicts = num_conflicts;

// if(num_conflicts < 3)
// {
// printf(“%d conflicts at %d iterations “, num_conflicts, iter_counter);
// }

 

 

if(num_conflicts <= 0)
{
problem_solved = 1;

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
printf(“num_generation = %d\n”, num_generation);

for(i = 0; i < num_vertex; i++)
{
printf(“%d %d\n”, i+1, init_coloring[i]+1);
}

printf(“\n”);

 

for(i = 0; i < num_vertex; i++)
{
fprintf(out2, “%d %d\n”, i+1, init_coloring[i]+1);
}
fflush(out2);

 

 

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

for(i = 0; i < num_vertex; i++ )
{
fprintf(out, “%d %d\n”, i+1, init_coloring[i]+1);
}

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

if( min_conflicts < clg)
{
clg = min_conflicts;
noshow = 0;
}

 

 

best_delta = 1000000;

 

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

 

for(j = 0; j < num_colors; j++)
{
if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
best_delta = delta;
best_vertex = i;
best_color = (char) j;
}
}
}
}

 

}
}

 

num_conflicts = num_conflicts + best_delta;

cnodes = 0;

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{
cnodes++;
}
}

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = rand();
tabu_rand = ru/b_tabu_rnd;
tl = tl + tabu_rand;

 

 

color_tabu = init_coloring[best_vertex];

tabu_list[best_vertex][color_tabu] = tl + iter_counter;

init_coloring[best_vertex] = best_color;

 

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color]++ ;
}
}

 

 

}
/*******************************************

for(iter_counter = 1; iter_counter < ; iter_counter++)
{

 

end loop …
**************************************/

 

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

/*** run tabu search on child 4 done ***/

 

 

}
/************************************

if( problem_solved == 0 )
{

 

end of loop ….
*************************************/

 

 

 

 

 

 

}
/********************************
if( problem_solved == 0)
{

end loop …

****************************/

 

 

 

 

}
/*********************************

if( problem_solved == 0 )
{

end of loop …
*******************************/

 

 

 

 

 

 

 

 

 

/*****************************************

 

int fall_archives_size[47];

 

**************************************/

 

 

for(i = 0 ; i < num_vertex; i++)
{
parent1[i] = best_coloring1[i];
}

for(i = 0 ; i < num_vertex; i++)
{
parent2[i] = best_coloring2[i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
parent1b[i] = best_coloring1b[i];
}

for(i = 0 ; i < num_vertex; i++)
{
parent2b[i] = best_coloring2b[i];
}

 

 

 

for(i = 0; i < 47; i++)
{
ps1[i] = 0;
ps2[i] = 0;
}

 

for(j = 0; j < num_vertex; j++)
{
ps1[parent1[j]]++;
ps2[parent2[j]]++;
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps1[i-1]< ps1[i] )
{
temp = ps1[i];
ps1[i] = ps1[i-1];
ps1[i-1] = temp;
}
}
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps2[i-1]< ps2[i] )
{
temp = ps2[i];
ps2[i] = ps2[i-1];
ps2[i-1] = temp;
}
}
}

 

 

diff = 0;

for(i = 0; i< 47; i++)
{
diff = diff + abs(ps1[i]-ps2[i]);
}

// printf(“diff = %d\n”, diff);

 

if( diff == 0 )
{

for(i = 0; i< 47; i++)
{
itmatch[i] = 0;
}

 

for(i = 0; i< 47; i++)
{
for(j = 0; j<47; j++)
{
if( ps1[i] == ps2[j] )
{
is_perfectmatch = 1;

for(k = 0; k< num_vertex; k++)
{
if( ((parent1[k] == ((char)i) )&&(parent2[k] == ((char)j) )) || ((parent1[k] != ((char)i) )&&(parent2[k] != ((char)j) )) )
{
oksofar = 1;
}
else
{
is_perfectmatch = 0;
break;
}
}

if( is_perfectmatch == 1 )
{
itmatch[i] = 1;
}
else
{
itmatch[i] = 0;
}
}

if( itmatch[i] == 1 )
{
break;
}
}
}

tmatch = 0;

for(i = 0; i< 47; i++)
{
tmatch = tmatch + itmatch[i];
}

if( tmatch >= 45 )
{
realfall++;
}

 

// printf(“%d matches\n”, tmatch);

if(tmatch >= 45)
{
// printf(“perfect match\n”);

/*** compare to archives for size ***/

 

 

arkdup = 0;

for(tark = 0; tark< realfall-1; tark++)
{
diff = 0;

if( diff == 0)
{
for(i = 0; i< 47; i++)
{
itmatch[i] = 0;
}

 

tmatchark = 0;

for(i = 0; i< 47; i++)
{
tmatchark = tmatchark + itmatch[i];
}
}
}

 

 

// printf(“%d matches\n”, tmatch);

for(i = 0 ; i < num_vertex; i++)
{
parent2[i] = parent2b[i];
}
}
// else
// {
// printf(“no perfect match\n”);
// }
}
/************************************
if( diff == 0 )
{
block of code
**************************************/

 

 

/*** check n = 2 ***/

for(i = 0; i < 47; i++)
{
ps1b[i] = 0;
ps2b[i] = 0;
}

 

for(j = 0; j < num_vertex; j++)
{
ps1b[parent1b[j]]++;
ps2b[parent2b[j]]++;
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps1b[i-1]< ps1b[i] )
{
temp = ps1b[i];
ps1b[i] = ps1b[i-1];
ps1b[i-1] = temp;
}
}
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps2b[i-1]< ps2b[i] )
{
temp = ps2[i];
ps2b[i] = ps2b[i-1];
ps2b[i-1] = temp;
}
}
}

 

 

diff = 0;

for(i = 0; i< 47; i++)
{
diff = diff + abs(ps1b[i]-ps2b[i]);
}

// printf(“diff = %d\n”, diff);

 

if( diff == 0 )
{

 

for(i = 0; i< 47; i++)
{
itmatchb[i] = 0;
}

 

for(i = 0; i< 47; i++)
{
for(j = 0; j<47; j++)
{
if( ps1b[i] == ps2b[j] )
{
is_perfectmatch = 1;

for(k = 0; k< num_vertex; k++)
{
if( ((parent1b[k] == ((char)i) )&&(parent2b[k] == ((char)j) )) || ((parent1b[k] != ((char)i) )&&(parent2b[k] != ((char)j) )) )
{
oksofar = 1;
}
else
{
is_perfectmatch = 0;
break;
}
}

if( is_perfectmatch == 1 )
{
itmatchb[i] = 1;
}
else
{
itmatchb[i] = 0;
}
}

if( itmatchb[i] == 1 )
{
break;
}
}
}

tmatch = 0;

for(i = 0; i< 47; i++)
{
tmatch = tmatch + itmatchb[i];
}

if( tmatch >= 45 )
{
realfall++;
}

 

 

// printf(“%d matches\n”, tmatch);

if(tmatch >= 45)
{
// printf(“perfect match\n”);

 

/**** insert ***/

arkdup = 0;

for(tark = 0; tark< realfall-1; tark++)
{
diff = 0;

if( diff == 0)
{
for(i = 0; i< 47; i++)
{
itmatch[i] = 0;
}
tmatchark = 0;

for(i = 0; i< 47; i++)
{
tmatchark = tmatchark + itmatch[i];
}
}
}

for(i = 0 ; i < num_vertex; i++)
{
parent1b[i] = parent1[i];
}
}
// else
// {
// printf(“no perfect match\n”);
// }
}
/************************************
if( diff == 0 )
{
block of code
**************************************/

 

if(noshow == 0)
{
printf(“clg = %d “, clg);
printf(“%d real falls “, realfall);
}

 

 

 

if( 0 == (num_generation%35) )
{

for(i = 0 ; i < num_vertex; i++)
{
parent1b[i] = parent1[i];
}
}

 

if(noshow == 0)
{
printf(“runs = %d “, runs);
printf(“generation %d done … \n”, num_generation);
}

 

// printf(“\n”);

if( problem_solved == 1)
{
break;
}

}
/******************************************************************

for( num_generation = 1; num_generation <= 10000; num_generation++)
{

end of loop …

*******************************************************************/

 

 

}

/*********************
if( j1 != j2)
{
loop end
***********************/

 

 

}

 

fclose(out);

 
return 0;

}

Written by meditationatae

December 30, 2017 at 12:23 am

Posted in History

Plaintext of previous post, 72 characters, values in octal (base 8)…

111 040 155 141 144
145 040 155 171 040
146 151 162 163 164
040 122 123 101 040
153 145 171 055 160
141 151 162 040 165
163 151 156 147 040
120 101 122 111 057
147 160 040 146 162
157 155 040 125 156
151 166 145 162 163
151 164 145 040 144
145 040 102 157 162
144 145 141 165 170
056 012

 

Written by meditationatae

December 29, 2017 at 10:39 pm

Posted in History

Test private message using RSA 2048 bits…

113788756549087568700298874193068178517122873049808881611473216898110843887183087665882667024658858411061741567834305090452854466390660423286581815032972569250761144881099667179478483943062727765437563809406717743900369951830799647409637489664178997344780615545816219565973393879834094510193407248340701859396420918607576191457272154549306892564447375991172578297494613939775719716779133382180185259768896080366273610046344912151205204158136067558855332575200273968293120461888870520935375783940209071939891008907426478601372319623478644520364565566575182385606592911770970996192836990804925595045493054045006694117

 

Written by meditationatae

December 29, 2017 at 10:06 pm

Posted in History

“Helena” started a conversation with me via Twitter and…

“Helena” started a conversation with me via Twitter, that moved in part to cellphone/smartphone SMS messages (not included), and this over a period of three days.
At one point, she wanted to pawn antiquities to me in exchange for $35,000 .
I asked to speak with her in person, but this couldn’t be arranged. I blocked her.

 

These are the Twitter direct messages from “Helena”:

——————–

Hello david

——————–

I am Originally from omaha nebraska, Move to Boston Massachusetts States some yrs ago due to my work.. and you know life is too short to be lonley…

——————–

That’s why I told you to get a smart phone

———————

Well my ex was not honest with me and he was caught on bed with HIS Boss at a Hotel and ever since then i have vowed never to get married again because i have been hurts badly and that gives me bad impression about all men but my best friend make me to understand that all men are not the same and i do believe in soul mate…

———–

I know dear

———–

We are having the same issue

———–

Trust issues

———–

Am scared to fall in any relationship now

———–

Hey

———–

Good morning 🌞☀️ dear

———–

Hey you change your mind

———–

I don’t want your money 💰

———–

This is business issue

———–

Good morning ☀️🌞

———–

Am good and you?

———–

Where are you?

———–

 

Written by meditationatae

December 6, 2017 at 6:27 pm

Posted in History

Update on Parallel Rope Team coloring algorithm

Moalic and Gondran’s Parallel Rope Team coloring algorithm is quite competitive with simulated Quantum Annealing coloring of Titiloye and Crispin, which in the hands of its inventors, broke new records in 2012 on some hard coloring problems on benchmark random graphs:

“Parameter Tuning Patterns for Random Graph Coloring with Quantum Annealing“, Olawale Titiloye and Alan Crispin,

Digital Object Identification (DOI) numbers:

https://doi.org/10.1371/journal.pone.0050060

For a random benchmark graph on 500 vertices with over 62,000 edges, both teams have found valid 47-colorings.

Using PRTcol of Moalic and Gondran ( presented at the GECCO 2017 Conference in Berlin in July 2017, with DOI numbers :

https://doi.org/10.1145/3071178.3071291 ),

I’ve tried to do the same.

Currently, I’m running a program that searches for improper 47-colorings of “the” 500-vertex , density 0.5 graph catalogued as DSJC500.5 and sometimes DSJC500.5.col when in compressed format, so improper colorings with 1 edge conflict. To do this, I have a file that contains approximately 59 improper 47-colorings each having 2 edge conflicts. I essentially use PRTcol, except for the stopping condition, which decides when to “give up” on an evolutionary run, and move on to the next run. Another difference is that I chose at random 4 distinct candidates (improper 47-colorings) from the 59 available with 2 edge conflicts, at the start of a run. I’ve obtained 2 new improper colorings with 1 conflict in 8 hours.

Previously, I had used about 33 colorings with 3 conflicts to find the 59 colorings with 2 conflicts. Along the way, I wanted to optimize the maximum number of generations in a run, before quitting and going on to another run. I estimate this optimum at roughly 720 generattions. In the case of producing colorings with 1 edge conflict, I decided to try maximum = 1500 generations at first. Empirically,

53 57 45 7 num_generation = 358 real_falls = 17 num_conflicts = 1
29 18 47 30 num_generation = 11 real_falls = 0 num_conflicts = 1

is the summary data on the two colorings with just one edge conflict found so far.

In the first solution:

Candidates number 53, 57, 45, and 7 were assembled as a 4-man rope team to in a run, with the mission to search for colorings with <= 1 edge conflicts. After 358 generations, a solution was found during the local search, which is a Tabu search. The team experienced 17 climber falls before finding the solution. The solution has one edge conflict. The terminology is explained in Moalic and Gondran’s GECCO 2017 conference paper, referenced above.

In the second solution, we see it was found after only 11 generations. I will look for the optimum maximum number of generations, but solutions arrive at a rate of one every 4 hours, roughly; so it could take 2-3 days to optimize. Also, I want to have a suitable variety of candidates, i.e. solutions with 1 edge conflict, before I attempt the search for colorings with zero edge conflicts. This number could be 30 candidates, or 5 days at 6 solutions per day.

 

December 2, 2017 insert:

=============================

I’m currently at 29 47-colorings with precisely one edge conflict, an edge e with both vertices of the same color. I stop a “rope team evolution” after 750 generations, at most. When I reach 30 such colorings, I’ll be ready to search for zero-conflict 47-colorings, which is the hardest of all and could take several days for just one solution.

Below, I copy screen output on the 28 first 1-edge conflict solutions (improper 47-colorings of DSJC500.5):

53 57 45 7 num_generation = 358 real_falls = 17 num_conflicts = 1
29 18 47 30 num_generation = 11 real_falls = 0 num_conflicts = 1
33 25 26 39 num_generation = 526 real_falls = 13 num_conflicts = 1
23 38 12 27 num_generation = 718 real_falls = 35 num_conflicts = 1
47 25 8 46 num_generation = 439 real_falls = 13 num_conflicts = 1
50 18 44 42 num_generation = 574 real_falls = 21 num_conflicts = 1
9 46 42 56 num_generation = 625 real_falls = 18 num_conflicts = 1
32 36 43 29 num_generation = 481 real_falls = 10 num_conflicts = 1
29 21 46 31 num_generation = 267 real_falls = 10 num_conflicts = 1
6 28 51 8 num_generation = 590 real_falls = 28 num_conflicts = 1
39 29 28 45 num_generation = 182 real_falls = 0 num_conflicts = 1
3 0 40 30 num_generation = 190 real_falls = 3 num_conflicts = 1
31 53 50 0 num_generation = 57 real_falls = 0 num_conflicts = 1
29 50 12 40 num_generation = 765 real_falls = 24 num_conflicts = 1
36 56 50 45 num_generation = 2608 real_falls = 35 num_conflicts = 1
40 28 52 9 num_generation = 1047 real_falls = 17 num_conflicts = 1
5 52 22 0 num_generation = 220 real_falls = 1 num_conflicts = 1
7 35 49 39 num_generation = 545 real_falls = 18 num_conflicts = 1
34 9 58 48 num_generation = 428 real_falls = 18 num_conflicts = 1
42 47 35 44 num_generation = 725 real_falls = 26 num_conflicts = 1
4 23 46 10 num_generation = 450 real_falls = 9 num_conflicts = 1
6 54 50 13 num_generation = 243 real_falls = 24 num_conflicts = 1
17 41 1 40 num_generation = 391 real_falls = 8 num_conflicts = 1
28 38 45 43 num_generation = 170 real_falls = 4 num_conflicts = 1
33 11 53 37 num_generation = 345 real_falls = 22 num_conflicts = 1
3 10 54 16 num_generation = 329 real_falls = 11 num_conflicts = 1
57 47 25 41 num_generation = 194 real_falls = 1 num_conflicts = 1
4 50 18 39 num_generation = 495 real_falls = 27 num_conflicts = 1

_________________ END DEC 2ND INSERT _____________________

 

 

 

Below is the source code file, the_powzoomuzzjo97a68.c :

=====================================================================

/*******************

A C implementation of Parallel Rope Team Coloring of

Moalic and Gondran

****************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_VERTEX 600
#define MAX_COLORS 60

unsigned char adj_mat[MAX_VERTEX][MAX_VERTEX];

int Gamma[MAX_VERTEX][MAX_COLORS];

int tabu_list[MAX_VERTEX][MAX_COLORS];
int matches_best_delta[MAX_VERTEX][MAX_COLORS];

static unsigned long long Q[2097152], carry=0;

unsigned long long B64MWC(void)
{ unsigned long long t,x; static int jm=2097151;
jm=(jm+1)&2097151;
x=Q[jm]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[jm]=t-x);
}

#define CNG ( cng=6906969069ULL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )

int main(int argc, char *argv[] )
{
FILE *in;
unsigned long long im,cng=123456789987654321ULL, xs=362436069362436069ULL;
unsigned long long mask = 2147483647ULL;
unsigned long long kiss1, kiss2, seed;
int num_colors;
int num_vertex;
int num_edges;
int num_conflicts;
int k;
int i;
int j;
int sum_adj_mat;
int ru;
int b;
char color;
char init_coloring[MAX_VERTEX];
char init_population[59][MAX_VERTEX];
char old_init_coloring[MAX_VERTEX];
int conflict_count;
int sum_Gamma;
int best_delta;
int delta;
int best_vertex;
char best_color;
long iter_counter;
int A;
float alpha;
int tl;
int b_tabu_rnd;
int tabu_rand;
char color_tabu;
int min_conflicts;
int job_done;
int differences;
FILE *out;
FILE *out2;
int is_round_one;
int problem_solved;
int cnodes;
int select;
int temp;
int candidate_count;
int b_candidate;
int can_number;
int num_try;
int ijk;
int answer;
FILE *insol;
int junk;
char initparent1[MAX_VERTEX];
char initparent2[MAX_VERTEX];
char parent1[MAX_VERTEX];
char parent2[MAX_VERTEX];
int count_classes[MAX_COLORS];
int count;
int maxcount;
int is_maxcount[MAX_COLORS];
int total_maxcount;
int b_total_maxcount;
char random_color_choice;
char index_maxcolor;
char chosen_partition;
char gp;
int taken[MAX_VERTEX];
int total_taken;
char child[MAX_VERTEX];
int b_color_classes;
char child1[MAX_VERTEX];
char child2[MAX_VERTEX];
char best_coloring1[MAX_VERTEX];
char best_coloring2[MAX_VERTEX];
int num_generation;
int j1;
int j2;
int ps1[MAX_COLORS];
int ps2[MAX_COLORS];
int diff;
int tmatch;
int is_perfectmatch;
int itmatch[47];
int oksofar;
int quit_do;
int b_sol;
int j3;
int j4;
int ps1b[MAX_COLORS];
int ps2b[MAX_COLORS];
char initparent1b[MAX_VERTEX];
char initparent2b[MAX_VERTEX];
char parent1b[MAX_VERTEX];
char parent2b[MAX_VERTEX];
char child3[MAX_VERTEX];
char child4[MAX_VERTEX];
int itmatchb[47];
char best_coloring1b[MAX_VERTEX];
char best_coloring2b[MAX_VERTEX];
int realfall;

int tmatchark;
int arkdup;
int tark;
int runs;
unsigned char one;
unsigned char zero;
int clg;
int iter_Tcol;
int reponse;

 

one = (unsigned char) 1;

zero = (unsigned char) 0;

 

select = 2;

 

is_round_one = 1;

out = fopen(“varsol95A”, “w”);

out2 = fopen(“newnovember17at1545A”, “w”);

 

insol = fopen(“newjuly26at0548”, “r”);

 

alpha = 0.60;
A = 10;
job_done = 0;

 

seed = 17100878265236724972ULL;
seed = 14607519818599557672ULL;
seed = 16573800653132675660ULL;
seed = 12519423405243906132ULL;
seed = 17354323623922913637ULL;
seed = 13879391473350592641ULL;
seed = 16523780796786991467ULL;
seed = 11750700245178463264ULL;

 

 

 

 

num_colors = atoi(argv[2]);
printf(“num_colors = %d\n” , num_colors);

in = fopen(argv[1], “r”);

fscanf(in, “%d %d”, &num_vertex, &num_edges);

printf(“num_vertex = %d\n”, num_vertex);
printf(“num_edges = %d\n”, num_edges);

for(i = 0 ; i < MAX_VERTEX; i++)
{
for(j = 0 ; j < MAX_VERTEX; j++)
{
adj_mat[i][j] = zero;
}
}

 

for(k = 0; k < num_edges; k++)
{
fscanf(in, “%d %d”, &j, &i);
if( i != j )
{
adj_mat[i-1][j-1] = one;
adj_mat[j-1][i-1] = one;
}

if(i == j)
{
printf(“warning: edge %d is = %d %d\n”, k+1, i, j);
}
}

fclose(in);

sum_adj_mat = 0;

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_vertex; j++)
{
if( (adj_mat[i][j] == one) && (i!=j) )
{
sum_adj_mat++;
}
}
}

printf(“sum_adj_mat = %d\n”, sum_adj_mat);

printf(“\n”);

 

printf(“now, read in initial population …\n\n”);

printf(“ok?\n”);

for(k = 0; k< 59 ; k++)
{
for(i = 0 ; i < num_vertex; i++)
{
fscanf(insol, “%d”, &junk);
fscanf(insol, “%d”, &color);
init_population[k][i] = color-1;
}
}

fclose(insol);

 

 

printf(“initial population read in …\n\n”);

printf(“ok?\n”);

 

b_sol = ((int) mask)/59;
b_sol = b_sol + 1;

 

 

printf(“now, select the two initial parents from 100…\n”);

printf(“ok?\n”);

for(runs = 0; runs < 10000; runs++)
{

 

ru = (int) ((KISS^seed)&mask);
j1 = ru/b_sol;

ru = (int) ((KISS^seed)&mask);
j2 = ru/b_sol;

ru = (int) ((KISS^seed)&mask);
j3 = ru/b_sol;

ru = (int) ((KISS^seed)&mask);
j4 = ru/b_sol;

 

 

if( (j1!=j2)&&(j1!=j3)&&(j1!=j4)&&(j2!=j3)&&(j2!=j4)&&(j3!=j4) )
{

clg = 1000000;

 

for(i = 0 ; i < num_vertex; i++)
{
initparent1[i] = init_population[j1][i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
initparent2[i] = init_population[j2][i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
initparent1b[i] = init_population[j3][i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
initparent2b[i] = init_population[j4][i];
}

 

printf(“selection of the two initial parents done…\n”);

printf(“ok?\n”);
printf(“set parent1 and parent2 and prepare for GPX algorithm…\n”);

 

printf(“ok?\n”);

 

for(i = 0 ; i < num_vertex; i++)
{
parent1[i] = initparent1[i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
parent2[i] = initparent2[i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
parent1b[i] = initparent1b[i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
parent2b[i] = initparent2b[i];
}

 

printf(“parent1 and parent2 set.\n”);

quit_do = 0;

realfall = 0;

 

for( num_generation = 1; num_generation <= 1500 ; num_generation++)
{

 

 

printf(“clg = %d\n”, clg);

if( realfall > 30 )
{
quit_do = 1 ;
}

 

 

if( quit_do == 1)
{
break;
}

 

for(i = 0; i< num_vertex; i++)
{
taken[i] = 0;
}

 

for(i = 0; i< num_vertex; i++)
{
child[i] = -1;
}

 

for( gp = 0; gp < 47; gp++)
{

 

 

if( 0 == (gp%2) )
{

for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

 

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == ((char) i) )&&(taken[j] == 0) )
{
count++;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

 

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount += is_maxcount[i];
}

 

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) ( ru/b_total_maxcount);
random_color_choice++;

 

 

index_maxcolor = 0;

 

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

 

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == chosen_partition) && ( taken[j] == 0) )
{
child[j] = gp;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent1[j] == chosen_partition )
{
taken[j] = 1;
}
}

}
/*************************************

if( 0 == (gp%2) )
{

end of loop…
*************************************/

 

 

if( 1 == (gp%2) )
{
for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == ((char) i) ) &&(taken[j] == 0) )
{
count++;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

 

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

}

 

 

 

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == chosen_partition)&&(taken[j] == 0) )
{
child[j] = gp;
}
}

 

for(j = 0; j< num_vertex; j++)
{
if( parent2[j] == chosen_partition )
{
taken[j] = 1;
}
}

 

}
/*************************************
if( 1 == (gp%2) )
{
end of loop…
*************************************/

 

}
/*************************************
for( gp = 0; gp < 49; gp++)
{
end of loop…
*************************************/

 

 

b_color_classes = ((int) mask)/47;
b_color_classes = b_color_classes + 1;

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_color_classes);
child[i] = random_color_choice;
}
}

 

for(j=0; j < num_vertex; j++)
{
child1[j] = child[j] ;
}

 

/*** child2 below … ***/

 

 

for(i = 0; i< num_vertex; i++)
{
taken[i] = 0;
}

 

for(i = 0; i< num_vertex; i++)
{
child[i] = -1;
}

 

 

for( gp = 0; gp < 47; gp++)
{

if( 0 == (gp%2) )
{

for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

 

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == ((char) i) )&&(taken[j] == 0) )
{
count++;
}
}
count_classes[i] = count;
}

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

 

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

index_maxcolor = 0;

 

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}
}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == chosen_partition) && ( taken[j] == 0) )
{
child[j] = gp;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent2[j] == chosen_partition )
{
taken[j] = 1;
}
}

}
/*************************************

if( 0 == (gp%2) )
{

end of loop…
*************************************/

 

if( 1 == (gp%2) )
{
for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == ((char) i) ) &&(taken[j] == 0) )
{
count++;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == chosen_partition)&&(taken[j] == 0) )
{
child[j] = gp;
}
}

 

for(j = 0; j< num_vertex; j++)
{
if( parent1[j] == chosen_partition )
{
taken[j] = 1;
}
}

 

}
/*************************************
if( 1 == (gp%2) )
{
end of loop…
*************************************/

 

}
/*************************************
for( gp = 0; gp < 49; gp++)
{
end of loop…
*************************************/

 

b_color_classes = ((int) mask)/47;
b_color_classes = b_color_classes + 1;

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_color_classes);
child[i] = random_color_choice;
}
}

 

for(j=0; j < num_vertex; j++)
{
child2[j] = child[j] ;
}

 

/*** child 3 ***/

 

for(i = 0; i< num_vertex; i++)
{
taken[i] = 0;
}

 

for(i = 0; i< num_vertex; i++)
{
child[i] = -1;
}

 

for( gp = 0; gp < 47; gp++)
{

 

if( 0 == (gp%2) )
{

for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

 

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent1b[j] == ((char)i) )&&(taken[j] == 0) )
{
count++;
}
}
count_classes[i] = count;
}

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

 

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}
}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent1b[j] == chosen_partition) && ( taken[j] == 0) )
{
child[j] = gp;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent1b[j] == chosen_partition )
{
taken[j] = 1;
}
}

}
/*************************************

if( 0 == (gp%2) )
{

end of loop…
*************************************/

 

if( 1 == (gp%2) )
{
for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent2b[j] == ((char)i) ) &&(taken[j] == 0) )
{
count++ ;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent2b[j] == chosen_partition)&&(taken[j] == 0) )
{
child[j] = gp;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent2b[j] == chosen_partition )
{
taken[j] = 1;
}
}

 

}
/*************************************
if( 1 == (gp%2) )
{
end of loop…
*************************************/

 

}
/*************************************
for( gp = 0; gp < 49; gp++)
{
end of loop…
*************************************/

 

b_color_classes = ((int) mask)/47;
b_color_classes = b_color_classes + 1;

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_color_classes);
child[i] = random_color_choice;
}
}

 

for(j=0; j < num_vertex; j++)
{
child3[j] = child[j] ;
}

/*** child 3 done ***/

 

 

/*** child 4 ***/

 

for(i = 0; i< num_vertex; i++)
{
taken[i] = 0;
}

 

for(i = 0; i< num_vertex; i++)
{
child[i] = -1;
}

 

for( gp = 0; gp < 47; gp++)
{

if( 0 == (gp%2) )
{

for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

 

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent2b[j] == ((char) i) )&&(taken[j] == 0) )
{
count++ ;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

 

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

 

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

 

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent2b[j] == chosen_partition) && ( taken[j] == 0) )
{
child[j] = gp;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent2b[j] == chosen_partition )
{
taken[j] = 1;
}
}

}
/*************************************

if( 0 == (gp%2) )
{

end of loop…
*************************************/

 

if( 1 == (gp%2) )
{
for(i = 0; i < 47; i++)
{
count_classes[i] = 0;
}

for( i =0; i < 47; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent1b[j] == ((char) i) ) &&(taken[j] == 0) )
{
count++ ;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 47; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 47; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

total_maxcount = 0;

for( i=0; i<47; i++)
{
total_maxcount+= is_maxcount[i];
}

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_total_maxcount);
random_color_choice++;

 

index_maxcolor = 0;

for( i =0; i < 47; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = (char) i;
}
}

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent1b[j] == chosen_partition)&&(taken[j] == 0) )
{
child[j] = gp;
}
}

 

for(j = 0; j< num_vertex; j++)
{
if( parent1b[j] == chosen_partition )
{
taken[j] = 1;
}
}

 

}
/*************************************
if( 1 == (gp%2) )
{
end of loop…
*************************************/

 

}
/*************************************
for( gp = 0; gp < 49; gp++)
{
end of loop…
*************************************/

 

b_color_classes = ((int) mask)/47;
b_color_classes = b_color_classes + 1;

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (ru/b_color_classes);
child[i] = random_color_choice;
}
}

 

for(j=0; j < num_vertex; j++)
{
child4[j] = child[j] ;
}

/*** child 4 done ***/

 

num_colors = 47;

for(i = 0; i < num_vertex; i++)
{
init_coloring[i] = child1[i];
}

 

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 1;

 

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 0;
}
}

 

iter_Tcol = 9000;

 

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; iter_counter++)
{

problem_solved = 0;

 

if( iter_counter == 1)
{
num_conflicts = 0;

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_colors; k++)
{
Gamma[i][k] = 0;
}
}

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< i; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
Gamma[k][init_coloring[i]]++;

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
num_conflicts+= Gamma[i][init_coloring[i]];
}

num_conflicts = num_conflicts/2;
}

if( num_conflicts < min_conflicts )
{

for(i = 0; i < num_vertex; i++)
{
best_coloring1[i] = init_coloring[i];
}

 

min_conflicts = num_conflicts;

 

if(num_conflicts < 10)
{
printf(“%d conflicts at %d iterations\n”, num_conflicts, iter_counter);
}

if(num_conflicts <= 1)
{
problem_solved = 1;

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
printf(“num_generation = %d\n”, num_generation);

for(i = 0; i < num_vertex; i++)
{
fprintf(out2, “%d %d\n”, i+1, init_coloring[i]+1);
}
fflush(out2);

 

printf(“\n”);

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

for(i = 0; i < num_vertex; i++ )
{
fprintf(out, “%d %d\n”, i+1, init_coloring[i]+1);
}

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

if( min_conflicts < clg)
{
clg = min_conflicts;
}

 

best_delta = 1000000;

 

for(i = 0; i < num_vertex; i++)
{
if(Gamma[i][init_coloring[i]] > 0)
{

 

for(j = 0; j < num_colors; j++)
{

matches_best_delta[i][j] = 0;

if(j != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
best_delta = delta;
}
}
}
}

}
}

candidate_count = 0;

for(i = 0; i < num_vertex; i++)
{
if(Gamma[i][init_coloring[i]] > 0)
{
for(j = 0; j < num_colors; j++)
{
if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta == best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
matches_best_delta[i][j] = 1;
candidate_count++;
}
}
}
}

 

}
}

b_candidate = ((int) mask)/candidate_count;
b_candidate = b_candidate + 1;
ru = (int) (KISS&mask);
can_number = ru/b_candidate;

candidate_count = 0;

for(i = 0; i < num_vertex; i++)
{
if(Gamma[i][init_coloring[i]] > 0)
{

 

for(j = 0; j < num_colors; j++)
{
if(matches_best_delta[i][j] == 1)
{
if(candidate_count == can_number)
{
best_vertex = i;
best_color = (char) j;
}
candidate_count++;
}
}

}
}

 

 

num_conflicts+= best_delta;

cnodes = 0;

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{
cnodes++;
}
}

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = (int) ((KISS^seed)&mask);
tabu_rand = ru/b_tabu_rnd;
tl = tl + tabu_rand;

 

color_tabu = init_coloring[best_vertex];

tabu_list[best_vertex][color_tabu] = tl + iter_counter;

init_coloring[best_vertex] = best_color;

 

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color] ++ ;
}
}

}
/*******************************************

for(iter_counter = 1; iter_counter < ; iter_counter++)
{

 

end loop …
**************************************/

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

/*** run tabu search on child2 ***/

 

if( problem_solved == 0 )
{

num_colors = 47;

 

for(i = 0; i < num_vertex; i++)
{
init_coloring[i] = child2[i];
}

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 1;

 

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 0;
}
}

 

iter_Tcol = 9000;

 

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; iter_counter++)
{

problem_solved = 0;

if( iter_counter == 1)
{
num_conflicts = 0;

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_colors; k++)
{
Gamma[i][k] = 0;
}
}

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< i; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
Gamma[k][init_coloring[i]]++;

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
num_conflicts+= Gamma[i][init_coloring[i]];
}

num_conflicts = num_conflicts/2;
}

if( num_conflicts < min_conflicts )
{

for(i = 0; i < num_vertex; i++)
{
best_coloring2[i] = init_coloring[i];
}

min_conflicts = num_conflicts;

if(num_conflicts < 10)
{
printf(“%d conflicts at %d iterations\n”, num_conflicts, iter_counter);
}

 

if(num_conflicts <= 1)
{
problem_solved = 1;

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
printf(“num_generation = %d\n”, num_generation);

for(i = 0; i < num_vertex; i++)
{
printf(“%d %d\n”, i+1, init_coloring[i]+1);
}

printf(“\n”);

for(i = 0; i < num_vertex; i++)
{
fprintf(out2, “%d %d\n”, i+1, init_coloring[i]+1);
}
fflush(out2);

 

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

for(i = 0; i < num_vertex; i++ )
{
fprintf(out, “%d %d\n”, i+1, init_coloring[i]+1);
}

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

if( min_conflicts < clg)
{
clg = min_conflicts;
}

 

best_delta = 1000000;

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

for(j = 0; j < num_colors; j++)
{

matches_best_delta[i][j] = 0;

if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
best_delta = delta;
}
}
}
}

 

}
}

 

candidate_count = 0;

 

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

for(j = 0; j < num_colors; j++)
{
if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta == best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
matches_best_delta[i][j] = 1;
candidate_count++;
}
}
}
}

 

}
}

 

b_candidate = ((int) mask)/candidate_count;
b_candidate = b_candidate + 1;
ru = (int) ((KISS^seed)&mask);
can_number = ru/b_candidate;

candidate_count = 0;

 

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

for(j = 0; j < num_colors; j++)
{
if(matches_best_delta[i][j] == 1)
{
if(candidate_count == can_number)
{
best_vertex = i;
best_color = (char) j;
}
candidate_count++;
}
}

}
}

 

num_conflicts+= best_delta;

cnodes = 0;

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{
cnodes++;
}
}

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = (int) ((KISS^seed)&mask);
tabu_rand = ru/b_tabu_rnd;
tl = tl + tabu_rand;

 

color_tabu = init_coloring[best_vertex];

tabu_list[best_vertex][color_tabu] = tl + iter_counter;

init_coloring[best_vertex] = best_color;

 

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color]++ ;
}
}

}
/*******************************************

for(iter_counter = 1; iter_counter < ; iter_counter++)
{

 

end loop …
**************************************/

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

/*** run tabu search on child2 done ***/

 

if( problem_solved == 0)
{

/*** tabu on child 3 ***/

num_colors = 47;

 

 

for(i = 0; i < num_vertex; i++)
{
init_coloring[i] = child3[i];
}

 

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 1;

 

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 0;
}
}

 

 

iter_Tcol = 9000;

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; iter_counter++)
{

problem_solved = 0;

 

if( iter_counter == 1)
{
num_conflicts = 0;

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_colors; k++)
{
Gamma[i][k] = 0;
}
}

 

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< i; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
Gamma[k][init_coloring[i]]++;

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
num_conflicts+= Gamma[i][init_coloring[i]];
}

num_conflicts = num_conflicts/2;
}

 

 

if( num_conflicts < min_conflicts )
{

for(i = 0; i < num_vertex; i++)
{
best_coloring1b[i] = init_coloring[i];
}

 

min_conflicts = num_conflicts;

if(num_conflicts < 10)
{
printf(“%d conflicts at %d iterations\n”, num_conflicts, iter_counter);
}

 

 

if(num_conflicts <= 1)
{
problem_solved = 1;

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
printf(“num_generation = %d\n”, num_generation);

for(i = 0; i < num_vertex; i++)
{
printf(“%d %d\n”, i+1, init_coloring[i]+1);
}

printf(“\n”);

 

for(i = 0; i < num_vertex; i++)
{
fprintf(out2, “%d %d\n”, i+1, init_coloring[i]+1);
}
fflush(out2);

 

 

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

for(i = 0; i < num_vertex; i++ )
{
fprintf(out, “%d %d\n”, i+1, init_coloring[i]+1);
}

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

if( min_conflicts < clg)
{
clg = min_conflicts;
}

 

 

best_delta = 1000000;

 

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

 

for(j = 0; j < num_colors; j++)
{

matches_best_delta[i][j] = 0;

if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
best_delta = delta;
}
}
}
}

 

}
}

 

candidate_count = 0;

 

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

 

for(j = 0; j < num_colors; j++)
{
if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta == best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
matches_best_delta[i][j] = 1;
candidate_count++;
}
}
}
}

 

}
}

 

b_candidate = ((int) mask)/candidate_count;
b_candidate = b_candidate + 1;
ru = (int) ((KISS^seed)&mask);
can_number = ru/b_candidate;

candidate_count = 0;

 

 

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

 

for(j = 0; j < num_colors; j++)
{
if(matches_best_delta[i][j] == 1)
{
if(candidate_count == can_number)
{
best_vertex = i;
best_color = (char) j;
}
candidate_count++;
}
}

}
}

 

 

num_conflicts+= best_delta;

cnodes = 0;

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{
cnodes++;
}
}

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = (int) ((KISS^seed)&mask);
tabu_rand = ru/b_tabu_rnd;
tl = tl + tabu_rand;

 

 

color_tabu = init_coloring[best_vertex];

tabu_list[best_vertex][color_tabu] = tl + iter_counter;

init_coloring[best_vertex] = best_color;

 

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color]++ ;
}
}

 

 

}
/*******************************************

for(iter_counter = 1; iter_counter < ; iter_counter++)
{

 

end loop …
**************************************/

 

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

/*** run tabu search on child 3 done ***/

/*** run tabu search on child 4 ***/

 

 

 

 

if( problem_solved == 0 )
{

 

/*** tabu on child 4 ***/

num_colors = 47;

 

for(i = 0; i < num_vertex; i++)
{
init_coloring[i] = child4[i];
}

 

 

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 1;

 

 

 

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 0;
}
}

 

 

iter_Tcol = 9000;

 

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; iter_counter++)
{

problem_solved = 0;

 

if( iter_counter == 1)
{
num_conflicts = 0;

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_colors; k++)
{
Gamma[i][k] = 0;
}
}

 

 

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< i; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
Gamma[k][init_coloring[i]]++;

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
num_conflicts+= Gamma[i][init_coloring[i]];
}

num_conflicts = num_conflicts/2;
}

 

 

if( num_conflicts < min_conflicts )
{

for(i = 0; i < num_vertex; i++)
{
best_coloring2b[i] = init_coloring[i];
}

 

min_conflicts = num_conflicts;

if(num_conflicts < 10)
{
printf(“%d conflicts at %d iterations\n”, num_conflicts, iter_counter);
}

 

 

if(num_conflicts <= 1)
{
problem_solved = 1;

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
printf(“num_generation = %d\n”, num_generation);

for(i = 0; i < num_vertex; i++)
{
printf(“%d %d\n”, i+1, init_coloring[i]+1);
}

printf(“\n”);

 

for(i = 0; i < num_vertex; i++)
{
fprintf(out2, “%d %d\n”, i+1, init_coloring[i]+1);
}
fflush(out2);

 

 

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

for(i = 0; i < num_vertex; i++ )
{
fprintf(out, “%d %d\n”, i+1, init_coloring[i]+1);
}

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

if( min_conflicts < clg)
{
clg = min_conflicts;
}

 

 

best_delta = 1000000;

 

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

 

for(j = 0; j < num_colors; j++)
{

matches_best_delta[i][j] = 0;

if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
best_delta = delta;
}
}
}
}

 

}
}

 

candidate_count = 0;

 

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

 

for(j = 0; j < num_colors; j++)
{
if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – Gamma[i][init_coloring[i]];

if( delta == best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
matches_best_delta[i][j] = 1;
candidate_count++;
}
}
}
}

 

}
}

 

b_candidate = ((int) mask)/candidate_count;
b_candidate = b_candidate + 1;
ru = (int) ((KISS^seed)&mask);
can_number = ru/b_candidate;

candidate_count = 0;

 

 

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{

 

 

for(j = 0; j < num_colors; j++)
{
if(matches_best_delta[i][j] == 1)
{
if(candidate_count == can_number)
{
best_vertex = i;
best_color = (char) j;
}
candidate_count++;
}
}

}
}

 

 

num_conflicts = num_conflicts + best_delta;

cnodes = 0;

for(i = 0; i < num_vertex; i++)
{
if( Gamma[i][init_coloring[i]] > 0)
{
cnodes++;
}
}

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = (int) ((KISS^seed)&mask);
tabu_rand = ru/b_tabu_rnd;
tl = tl + tabu_rand;

 

 

color_tabu = init_coloring[best_vertex];

tabu_list[best_vertex][color_tabu] = tl + iter_counter;

init_coloring[best_vertex] = best_color;

 

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color]++ ;
}
}

 

 

}
/*******************************************

for(iter_counter = 1; iter_counter < ; iter_counter++)
{

 

end loop …
**************************************/

 

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

/*** run tabu search on child 4 done ***/

 

 

}
/************************************

if( problem_solved == 0 )
{

 

end of loop ….
*************************************/

 

 

 

 

 

 

}
/********************************
if( problem_solved == 0)
{

end loop …

****************************/

 

 

 

 

}
/*********************************

if( problem_solved == 0 )
{

end of loop …
*******************************/

 

 

 

 

 

 

 

 

 

/*****************************************

 

int fall_archives_size[47];

 

**************************************/

 

 

for(i = 0 ; i < num_vertex; i++)
{
parent1[i] = best_coloring1[i];
}

for(i = 0 ; i < num_vertex; i++)
{
parent2[i] = best_coloring2[i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
parent1b[i] = best_coloring1b[i];
}

for(i = 0 ; i < num_vertex; i++)
{
parent2b[i] = best_coloring2b[i];
}

 

 

 

for(i = 0; i < 47; i++)
{
ps1[i] = 0;
ps2[i] = 0;
}

 

for(j = 0; j < num_vertex; j++)
{
ps1[parent1[j]]++;
ps2[parent2[j]]++;
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps1[i-1]< ps1[i] )
{
temp = ps1[i];
ps1[i] = ps1[i-1];
ps1[i-1] = temp;
}
}
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps2[i-1]< ps2[i] )
{
temp = ps2[i];
ps2[i] = ps2[i-1];
ps2[i-1] = temp;
}
}
}

 

 

diff = 0;

for(i = 0; i< 47; i++)
{
diff = diff + abs(ps1[i]-ps2[i]);
}

printf(“diff = %d\n”, diff);

 

if( diff == 0 )
{

for(i = 0; i< 47; i++)
{
itmatch[i] = 0;
}

 

for(i = 0; i< 47; i++)
{
for(j = 0; j<47; j++)
{
if( ps1[i] == ps2[j] )
{
is_perfectmatch = 1;

for(k = 0; k< num_vertex; k++)
{
if( ((parent1[k] == ((char)i) )&&(parent2[k] == ((char)j) )) || ((parent1[k] != ((char)i) )&&(parent2[k] != ((char)j) )) )
{
oksofar = 1;
}
else
{
is_perfectmatch = 0;
break;
}
}

if( is_perfectmatch == 1 )
{
itmatch[i] = 1;
}
else
{
itmatch[i] = 0;
}
}

if( itmatch[i] == 1 )
{
break;
}
}
}

tmatch = 0;

for(i = 0; i< 47; i++)
{
tmatch = tmatch + itmatch[i];
}

if( tmatch >= 45 )
{
realfall++;
}

printf(“%d matches\n”, tmatch);

if(tmatch >= 45)
{
printf(“perfect match\n”);

/*** compare to archives for size ***/

 

 

arkdup = 0;

for(tark = 0; tark< realfall-1; tark++)
{
diff = 0;

if( diff == 0)
{
for(i = 0; i< 47; i++)
{
itmatch[i] = 0;
}

 

tmatchark = 0;

for(i = 0; i< 47; i++)
{
tmatchark = tmatchark + itmatch[i];
}
}
}

 

 

printf(“%d matches\n”, tmatch);

for(i = 0 ; i < num_vertex; i++)
{
parent2[i] = parent2b[i];
}
}
else
{
printf(“no perfect match\n”);
}
}
/************************************
if( diff == 0 )
{
block of code
**************************************/

 

 

/*** check n = 2 ***/

for(i = 0; i < 47; i++)
{
ps1b[i] = 0;
ps2b[i] = 0;
}

 

for(j = 0; j < num_vertex; j++)
{
ps1b[parent1b[j]]++;
ps2b[parent2b[j]]++;
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps1b[i-1]< ps1b[i] )
{
temp = ps1b[i];
ps1b[i] = ps1b[i-1];
ps1b[i-1] = temp;
}
}
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps2b[i-1]< ps2b[i] )
{
temp = ps2[i];
ps2b[i] = ps2b[i-1];
ps2b[i-1] = temp;
}
}
}

 

 

diff = 0;

for(i = 0; i< 47; i++)
{
diff = diff + abs(ps1b[i]-ps2b[i]);
}

printf(“diff = %d\n”, diff);

 

if( diff == 0 )
{

 

for(i = 0; i< 47; i++)
{
itmatchb[i] = 0;
}

 

for(i = 0; i< 47; i++)
{
for(j = 0; j<47; j++)
{
if( ps1b[i] == ps2b[j] )
{
is_perfectmatch = 1;

for(k = 0; k< num_vertex; k++)
{
if( ((parent1b[k] == ((char)i) )&&(parent2b[k] == ((char)j) )) || ((parent1b[k] != ((char)i) )&&(parent2b[k] != ((char)j) )) )
{
oksofar = 1;
}
else
{
is_perfectmatch = 0;
break;
}
}

if( is_perfectmatch == 1 )
{
itmatchb[i] = 1;
}
else
{
itmatchb[i] = 0;
}
}

if( itmatchb[i] == 1 )
{
break;
}
}
}

tmatch = 0;

for(i = 0; i< 47; i++)
{
tmatch = tmatch + itmatchb[i];
}

if( tmatch >= 45 )
{
realfall++;

 

 

}

 

printf(“%d matches\n”, tmatch);

if(tmatch >= 45)
{
printf(“perfect match\n”);

 

/**** insert ***/

arkdup = 0;

for(tark = 0; tark< realfall-1; tark++)
{
diff = 0;

if( diff == 0)
{
for(i = 0; i< 47; i++)
{
itmatch[i] = 0;
}
tmatchark = 0;

for(i = 0; i< 47; i++)
{
tmatchark = tmatchark + itmatch[i];
}

// if( tmatchark >= 47 )
// {
// arkdup = 1;
// quit_do = 1;
// }
}
}

for(i = 0 ; i < num_vertex; i++)
{
parent1b[i] = parent1[i];
}
}
else
{
printf(“no perfect match\n”);
}
}
/************************************
if( diff == 0 )
{
block of code
**************************************/
printf(“%d real falls\n”, realfall);

 

 

 

if( 0 == (num_generation%29) )
{

for(i = 0 ; i < num_vertex; i++)
{
parent1b[i] = parent1[i];
}
}

printf(“runs = %d\n”, runs);

printf(“generation %d done … \n”, num_generation);

 

printf(“\n”);

if( problem_solved == 1)
{
break;
}

}
/******************************************************************

for( num_generation = 1; num_generation <= 10000; num_generation++)
{

end of loop …

*******************************************************************/

 

 

}

/*********************
if( j1 != j2)
{
loop end
***********************/

 

 

}

 

fclose(out);
return 0;

}

Written by meditationatae

November 18, 2017 at 7:34 am

Posted in History

The b-numbers below 256

The numbers k with k == 5 (mod 8), and s(k-2) = k with s(.) the hypothetical sequence generated by Turing Machine #4, are what I’ve called “b-numbers” for basic numbers.

I haven’t succeeded in finding any rule that determines the whole sequence. Below, I copy the 26 b-numbers below 256. I’ve found this to be a hard problem.

b-numbers below 256:

5
13
21
29
37
45
53
61
77
85
93
101
109
117
125
149
173
181
189
205
213
221
229
237
245
253

 

Written by meditationatae

September 27, 2017 at 11:35 pm

Posted in History