meditationatae

Just another WordPress.com site

newtabuzf99a.c for DIMACS DSJC500.5.col

This is my best effort at implementing Galinier and Hao’s Tabu Search algoritm from their 1999 paper:

“Hybrid Evolutionary Algorithms for Graph Coloring”.

It produces 50-colorings of DSJC500.5.col after a few hours.

Filename:   newtabuzf99a.c

 

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

#define MAX_VERTEX 1000
#define MAX_COLORS 500

int adj_mat[MAX_VERTEX][MAX_VERTEX];

int Gamma[MAX_VERTEX][MAX_COLORS];

int Fast_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;
int color;
int init_coloring[MAX_VERTEX];
int old_init_coloring[MAX_VERTEX];
int conflict_count;
int sum_Gamma;
int best_delta;
int delta;
int best_vertex;
int best_color;
int iter_counter;
int A;
float alpha;
int tl;
int b_tabu_rnd;
int tabu_rand;
int color_tabu;
int min_conflicts;
int job_done;
int differences;
FILE *out;
int is_round_one;
int problem_solved;
// FILE *in2;
int cnodes;
int select;
int temp;
int max_iter;
int candidate_count;
int b_candidate;
int can_number;

select = 2;

 

is_round_one = 1;

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

// in2 = fopen(“newcol53”, “r”);

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

seed = 10000845109132110031ULL;

 

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] = 0;
}
}

 

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

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] == 1) && (i!=j) )
{
sum_adj_mat++;
}
}
}

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

printf(“\n”);

 

 

while( job_done == 0)
{

 

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

min_conflicts = 1000000;

 

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

 

printf(“\n”);

 

printf(“First select a random %d coloring of the %d vertices…\n”, num_colors, num_vertex);

b = ((int) mask)/num_colors;
b = b+1;

 

if(is_round_one == 1)
{
for(i = 0; i< num_vertex; i++)
{
kiss1 = KISS;
kiss1 = KISS;
kiss1 = KISS;
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
color = ru/b;
// fscanf(in2, “%d”, &ru);
// fscanf(in2, “%d”, &color);
init_coloring[i] = color ;
}
// fclose(in2);
}

 

if(is_round_one == 0)
{
for(i = 0; i< num_vertex; i++)
{
init_coloring[i] = old_init_coloring[i];
}

select = select + 1;
select = select%num_colors;

 

 

for(i = 0; i< num_vertex; i++)
{
if( (init_coloring[i] == select) || (init_coloring[i] == num_colors) )
{
temp = init_coloring[i];

if(temp == select)
{
init_coloring[i]=num_colors;
}

if(temp == num_colors)
{
init_coloring[i]=select ;
}

 

}
}

 

for(i = 0; i< num_vertex; i++)
{
if( init_coloring[i] == num_colors )
{
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
color = ru/b;
init_coloring[i] = color ;
}
}

}

if(num_colors > 51)
{
max_iter = 100000;
}
else
{
max_iter = 200000;
}

if(num_colors <= 50)
{
max_iter = 20000000;
}

 

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

problem_solved = 0;

 

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

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

for(i = 0; i < num_vertex; i++)
{
for(j = 0; j < num_colors; j++)
{
conflict_count = 0;

for(k = 0; k< num_vertex; k++)
{
if( (i != k) && (adj_mat[i][k] == 1) && ( j == init_coloring[k]) )
{
conflict_count++;
}
}

Gamma[i][j] = conflict_count;
Fast_Gamma[i][j] = Gamma[i][j];
}
num_conflicts = num_conflicts + Gamma[i][init_coloring[i]];
}
num_conflicts = num_conflicts/2;
}

 

cnodes = 0;

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

 

if( num_conflicts < min_conflicts )
{
min_conflicts = num_conflicts;
if(num_conflicts < 20)
{
printf(“%d conflicts and CN = %d at %d iterations\n”, num_conflicts, cnodes, iter_counter);
}
if(num_conflicts == 0)
{
problem_solved = 1;
break;
}
}

 

 

 

best_delta = 1000000;

 

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;
tl = 32;

 

 

 

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

matches_best_delta[i][j] = 0;

if(j != init_coloring[i])
{
delta = Fast_Gamma[i][j] – Fast_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++)
{
for(j = 0; j < num_colors; j++)
{
if(j != init_coloring[i])
{
delta = Fast_Gamma[i][j] – Fast_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++)
{
for(j = 0; j < num_colors; j++)
{
if(matches_best_delta[i][j] == 1)
{
if(candidate_count == can_number)
{
best_vertex = i;
best_color = j;
}
candidate_count++;
}
}
}

 

 

num_conflicts = num_conflicts + best_delta;

 

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] == 1)
{
Fast_Gamma[i][color_tabu] = Fast_Gamma[i][color_tabu]-1;
Fast_Gamma[i][best_color] = Fast_Gamma[i][best_color]+1;
}
}

 

 

}

 

if( problem_solved == 1)
{

fprintf(out, “solution for %d colors:\n”, num_colors);

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

fprintf(out, “\n”);

fflush(out);

num_colors = num_colors – 1;

is_round_one = 0;

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

 

 

 

}

 

 

fclose(out);

 
return 0;

}

Advertisements

Written by meditationatae

June 22, 2017 at 11:37 am

Posted in History

%d bloggers like this: