meditationatae

Just another WordPress.com site

New evolutionary algorithm, implementation in C

At the GECCO 2017 Conference in Berlin in July, Moalic and Gondran gave a presentation with a conference paper entitled:

“Heuristic rope team : a parallel algorithm for graph coloring”.

It can be searched for along with ACM on Google, and it’s in PDF format.

It uses Tabu local search, the Greedy Partitioning Crossover operator GPX of Galinier and Hao, and a climbing “team” of ‘n’ couples, where each couple does GPX crossovers. They use n = 2, so 2 couples. When a couple’s diversity is reduced to zero because the two parents are “clones”, meaning that they partition the vertices into color classes exactly the same way, up to permuting the colors, then one individual in the couple copies the configuration of a paired individual in the other couple, to re-introduce diversity in the couple.

The conference paper on the Web:

omitted.

 

I have over 400 improper 47-colorings with about 45 conflicting vertices each. I used that and Heuristic rope team, with n = 2, to produce intermediate configurations with 47 colors and <= 3 vertex conflicts.

So far, I’ve managed to also produce configurations with 2 conflicts, but not 1 or zero conflicts, for 47 colors and the graph DSJC500.5 or DSJC500.5.col .

I did some optimization, such as using 8-bit integers some of the time. On a quad-core, Moalic and Gondran write that it takes 2 minutes to evolve a proper 47-coloring when it leads to success, which is 7 times out of 10,000. This would be 8 minutes on a single core, which is how I programmed it. After optimization, it goes at about 1 generation a second so about 1 hour or 60 minutes for 3500 generations, which is the average for successful 47-colorings. Unsuccessful attempts usually take less time, because they “block”. At the moment, I’m combining 4 individuals at random from 20 improper 47-colorings, to attempt to get improper 47-colorings with 1 conflict. If that works, I may try to change from 1 to zero conflicts, although that should be a lot harder, and take much more time. The jump in difficulty from 3 conflicts to 2 conflicts was obvious.

The 3-conflicts program has been running for 15 hours, and I expect to let it run a while longer to produce many varied 3-conflict configurations. The source code file is:

pnewtbuzzi97a.c :

 

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

Please refer to the conference paper

Heuristic rope team : a parallel algorithm for graph coloring

by Laurent Moalic and Alexandre Gondran from

GECCO 2017 Conference in Berlin.

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

#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[404][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;
int is_round_one;
int problem_solved;
int cnodes;
int select;
int temp;
long max_iter;
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 fall_archives_size[250][47];
char arkparent[250][MAX_VERTEX];
int tmatchark;
int arkdup;
int tark;
int runs;
unsigned char one;
unsigned char zero;

one = (unsigned char) 1;

zero = (unsigned char) 0;

 

select = 2;

 

is_round_one = 1;

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

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

 

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

 

seed = 18374146278035435545ULL;
seed = 18017113809711968460ULL;
seed = 15087295764204510305ULL;

 

 

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< 404 ; 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)/404;
b_sol = b_sol + 1;

 

 

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

printf(“ok?\n”);

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

 

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

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

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

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

 

 

 

 

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

 

 

 

 

 

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 <= 3000; num_generation++)
{

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;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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)
{
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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)
{
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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)
{
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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)
{
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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;

max_iter = 8000 ;

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;
}
}

 

for(iter_counter = 1; iter_counter < max_iter ; 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< num_vertex; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
}
}
}

 

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 <= 3)
{
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”);

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
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;
}
}

 

 

 

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));
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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 < max_iter ; 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;

max_iter = 8000 ;

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;
}
}

 

 

 

 

for(iter_counter = 1; iter_counter < max_iter ; 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< num_vertex; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
}
}
}

 

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 <= 3)
{
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”);

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
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;
}
}

 

 

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&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));
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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 < max_iter ; 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;

max_iter = 8000 ;

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;
}
}

 

 

 

 

for(iter_counter = 1; iter_counter < max_iter ; 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< num_vertex; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
}
}
}

 

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 <= 3)
{
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”);

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
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;
}
}

 

 

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&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));
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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 < max_iter ; 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;

max_iter = 8000 ;

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;
}
}

 

 

 

 

for(iter_counter = 1; iter_counter < max_iter ; 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< num_vertex; k++)
{
if(adj_mat[i][k] == one)
{
Gamma[i][init_coloring[k]]++;
}
}
}

 

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 <= 3)
{
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”);

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
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;
}
}

 

 

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&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));
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&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 < max_iter ; 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 >= 47 )
{
realfall++;

for(i = 0; i< 47; i++)
{
fall_archives_size[realfall-1][i] = ps1[i];
}

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

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

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

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

arkdup = 0;

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

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

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] == fall_archives_size[tark][j] )
{
is_perfectmatch = 1;

for(k = 0; k< num_vertex; k++)
{
if( ((parent1[k] == ((char)i) )&&(arkparent[tark][k] == ((char)j) )) || ((parent1[k] != ((char)i) )&&(arkparent[tark][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;
}
}
}

tmatchark = 0;

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

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

 

 

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++)
{
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] == i)&&(parent2[k] == j)) || ((parent1[k] != i)&&(parent2[k] != 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 >= 47 )
{
realfall++;

for(i = 0; i< 47; i++)
{
fall_archives_size[realfall-1][i] = ps1[i];
}

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

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

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

arkdup = 0;

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

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

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] == fall_archives_size[tark][j] )
{
is_perfectmatch = 1;

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

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

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

tmatchark = 0;

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

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

 

 

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

if(tmatch == 47)
{

 

 

for(i = 0 ; i < num_vertex; i++)
{
parent2[i] = parent2b[i];
}
}
else
{
printf(“no perfect match\n”);
}

 

 

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

 

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 >= 47 )
{
realfall++;

 

for(i = 0; i< 47; i++)
{
fall_archives_size[realfall-1][i] = ps1b[i];
}

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

}

 

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

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

 

/**** insert ***/

arkdup = 0;

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

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

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( ps1b[i] == fall_archives_size[tark][j] )
{
is_perfectmatch = 1;

for(k = 0; k< num_vertex; k++)
{
if( ((parent1b[k] == ((char)i) )&&(arkparent[tark][k] == ((char)j) )) || ((parent1b[k] != ((char)i) )&&(arkparent[tark][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;
}
}
}

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%30) )
{

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;

}

Advertisements

Written by meditationatae

July 24, 2017 at 9:07 pm

Posted in History

%d bloggers like this: