meditationatae

Just another WordPress.com site

HEA in Duet update (47 colors, DSJC500.5)

The program I wrote to search for 47-colorings of the 500-vertex graph DSJC500.5 has found a solution after 5200 runs. It took over three months.

The algorithm used is from Moalic and Gondran’s 2017 conference paper: “Heuristic rope team : a parallel algorithm for graph coloring”.

 

The coloring is given by the array below with vertex number and color for vertex number going from 1 to 500:

1 1
2 17
3 17
4 33
5 42
6 16
7 6
8 23
9 37
10 44
11 7
12 15
13 27
14 43
15 14
16 7
17 43
18 19
19 25
20 1
21 32
22 4
23 35
24 29
25 38
26 23
27 38
28 21
29 28
30 2
31 41
32 26
33 29
34 23
35 8
36 9
37 11
38 41
39 30
40 10
41 15
42 14
43 11
44 9
45 47
46 40
47 32
48 14
49 40
50 32
51 46
52 19
53 16
54 2
55 3
56 29
57 1
58 35
59 7
60 18
61 39
62 35
63 1
64 7
65 30
66 39
67 23
68 27
69 19
70 17
71 31
72 5
73 26
74 37
75 13
76 43
77 36
78 17
79 1
80 27
81 34
82 28
83 47
84 22
85 40
86 19
87 13
88 19
89 12
90 2
91 21
92 45
93 33
94 12
95 37
96 41
97 5
98 4
99 9
100 10
101 10
102 8
103 14
104 39
105 32
106 38
107 1
108 39
109 47
110 15
111 8
112 8
113 8
114 46
115 47
116 7
117 16
118 27
119 32
120 35
121 4
122 37
123 43
124 22
125 25
126 36
127 45
128 28
129 36
130 3
131 1
132 28
133 29
134 34
135 3
136 31
137 3
138 38
139 28
140 39
141 47
142 15
143 25
144 16
145 24
146 32
147 23
148 26
149 26
150 12
151 17
152 27
153 9
154 4
155 41
156 34
157 45
158 13
159 21
160 35
161 3
162 7
163 14
164 29
165 43
166 16
167 6
168 32
169 29
170 2
171 27
172 47
173 35
174 16
175 6
176 2
177 44
178 32
179 18
180 41
181 1
182 13
183 1
184 21
185 10
186 37
187 28
188 34
189 15
190 3
191 34
192 4
193 47
194 35
195 34
196 9
197 7
198 5
199 33
200 15
201 8
202 45
203 11
204 4
205 24
206 39
207 20
208 41
209 4
210 38
211 19
212 43
213 6
214 12
215 13
216 31
217 1
218 28
219 10
220 6
221 37
222 26
223 43
224 44
225 11
226 16
227 11
228 23
229 29
230 21
231 24
232 24
233 20
234 9
235 44
236 21
237 2
238 25
239 7
240 14
241 22
242 33
243 37
244 3
245 11
246 12
247 34
248 11
249 37
250 33
251 32
252 23
253 24
254 45
255 46
256 38
257 44
258 6
259 22
260 21
261 16
262 22
263 27
264 46
265 18
266 4
267 16
268 11
269 2
270 2
271 28
272 30
273 47
274 25
275 32
276 9
277 2
278 36
279 36
280 30
281 36
282 18
283 24
284 15
285 26
286 35
287 12
288 6
289 21
290 23
291 34
292 4
293 35
294 20
295 30
296 13
297 21
298 15
299 9
300 5
301 14
302 19
303 40
304 5
305 16
306 37
307 6
308 10
309 30
310 46
311 17
312 20
313 46
314 33
315 33
316 39
317 18
318 46
319 42
320 26
321 44
322 31
323 24
324 15
325 13
326 44
327 5
328 5
329 30
330 20
331 38
332 6
333 5
334 41
335 5
336 27
337 36
338 34
339 42
340 29
341 16
342 38
343 13
344 39
345 15
346 45
347 18
348 30
349 31
350 14
351 2
352 11
353 22
354 13
355 5
356 12
357 12
358 21
359 17
360 4
361 3
362 41
363 30
364 19
365 26
366 20
367 15
368 3
369 10
370 17
371 18
372 7
373 24
374 21
375 25
376 31
377 11
378 28
379 42
380 40
381 25
382 24
383 8
384 33
385 16
386 29
387 2
388 45
389 6
390 38
391 23
392 8
393 6
394 40
395 8
396 41
397 12
398 31
399 11
400 14
401 5
402 1
403 22
404 20
405 17
406 36
407 34
408 4
409 42
410 12
411 10
412 26
413 26
414 18
415 10
416 45
417 25
418 39
419 1
420 13
421 45
422 7
423 9
424 46
425 24
426 10
427 10
428 27
429 21
430 36
431 3
432 46
433 20
434 14
435 18
436 20
437 20
438 7
439 8
440 39
441 22
442 22
443 2
444 4
445 12
446 42
447 29
448 23
449 37
450 5
451 18
452 35
453 37
454 8
455 7
456 3
457 4
458 33
459 3
460 1
461 45
462 2
463 14
464 25
465 13
466 31
467 26
468 47
469 23
470 19
471 11
472 3
473 22
474 28
475 18
476 6
477 8
478 40
479 17
480 42
481 42
482 36
483 17
484 10
485 6
486 40
487 40
488 12
489 42
490 19
491 20
492 22
493 24
494 43
495 38
496 14
497 19
498 15
499 13
500 44

Written by meditationatae

February 23, 2020 at 8:56 pm

Posted in History

Large values of psi(x), Chebychev function

x = exp(2565855.5315) ;

psi(x) = Chebyshev function

https://en.wikipedia.org/wiki/Chebyshev_function

|psi(x)-x| ~= 1.14 sqrt(x) .

Using:

s1000 =
(U)->-sum(X=1,1000,exp((I*w[X])*U)/(1/2+I*w[X])+exp((-I*w[X])*U)/(1/2-I*w[X]))

 

w is a vector of the imaginary parts of the non-trivial zeta zeros with Im(rho)>0, i.e. rho_n = 1/2 + i*w[n] , n = 1… 100,000.

 

? rec = 0.1 ; for(X=0,0, z=2565855.5315 ; aa=real(s1000(z)); if(aa>rec, rec = aa; print(z,” “,aa)))
2565855.5315000000000000000000000000000 1.1428401689732402053681180039290926930

The function ψ(x) − x, for x < 104 at Wikipedia:

Chebyshev.svg

Source:

https://en.wikipedia.org/wiki/Chebyshev_function#/media/File:Chebyshev.svg

In green:  y = 0.5 sqrt(n) and y = – 0.5 sqrt(n).

Is |psi(x)-x|/sqrt(x)  bounded or unbounded ?

If  |psi(x)-x|/sqrt(x) were bounded, then

|psi(x)-x| = o(sqrt(x)log log log(x) ).

But Hardy and Littlewood showed

|psi(x)-x|/sqrt(x)  =/= o(sqrt(x)log log log(x) ),

therefore |psi(x)-x|/sqrt(x) is unbounded.

Source:

https://en.wikipedia.org/wiki/Chebyshev_function#Properties

in: Contributions to the theory of the riemann zeta-function and the theory of the distribution of primes, Acta Mathematica, Volume 41 (1916), 119-196, Section 5: On the order of psi(x)-x and Pi(x)-Li(x) ;

https://projecteuclid.org/euclid.acta/1485887467

Written by meditationatae

November 17, 2018 at 5:50 am

Posted in History

Checking the Riemann Hypothesis

To numerically verify R.H. up to some maximum height T, people often use the Riemann-Siegel formula

Wikipedia article on R.S. or Z function

for at least some of the Zeta/Z computations on zeros.

This method is faster than using a method called Euler-MacLaurin summation, although the latter is preferred for dozens or hundreds of digits accuracy.

I’m in the process of duplicating the results of R.P. Brent at ANU in Canberra, Australia.

It was published in Math. Comp. in 1979, vol. 33, no. 148 October 1979:

link to AMS page on the 1979 paper

It explains the details on Gram points, good and bad, the Gram blocks (as they have become known), Rosser’s rule and Gram blocks where Rosser’s rule fails with “missing zeros”, and so on.

My program is written in the C programming language, and is roughly 1200 lines long.

Sample output:

We didn’t find all the missing zeros in the next Gram block
index1 = 69784846
index2 = 69784847
success = 0
We now look in the preceding Gram Block
Gram point guess = 30461845.1127759444134426

Gram point guess = 30461845.5209311383532622

We found the 2 missing zeros in the preceding Gram block
index1 = 69784843
index2 = 69784844
The updated zeros count is: 75000000

real 667m28.360s  // wall clock time.
user 667m15.456s
sys 0m3.475s

As I recall, I used the T value of 32,585,736.4 which corresponds to the location of Gram point g_{74,999,999};

Convention is that  g_0 ~= 18.0 , so that [g_0, g_1)

Nearest integer to the n-th Gram point

contains one zeta zero, the second, with the first at about 14.13 .  On average, one has k+1 zeta zeros from height 0 to the height of g_k . I’m confident my program is working quite well, as results are corroborated by the work of others, especially Brent and some co-authors on larger computations that were done later, in the 1980s .

 

I’m running a second job covering the Gram points g_{74,999,999} , where the zero count reached 75 million, to the Gram point G_{199,999,999} where the zeros count should be 200,000,000 +/- 1 at most.

cf.:  file riemannsiegel3.gp in  /home/david

https://www.ams.org/journals/mcom/1982-39-160/S0025-5718-1982-0669660-1/

The authors set T to be Gram point 200,000,000 and find

200,000,001 zeros up to height g_{200,000,000}.

For record verifications of RH (say to g_{10^13} ), it’s unwieldy to use nothing more sophisticated than the Riemann-Siegel forumula. Xavier Gourdon used the Odlydzko-Schonhage method in his unpublished (or not peer-reviewed) paper/work , as well as the fast multipole  (or Greengard-Rokhlin method). He also used the FFT and other devices.

So, my program’s goal is to give exact counts of zeta zeros on the critical line in 0< Im(s) < T, for T from 10^7 to 10^9, and beyond, if I can understand and implement the O.S. method or the Greengard-Rokhlin method.

email contact:

Screenshot from 2018-10-21 13-41-56

 

Below, I post user-defined functions in PARI/gp:

PARI/GP Development Headquarters

source: the file

N =
(X)->floor(u(X)^2)

Psi =
(Z)->cos(2*Pi*(Z^2-Z-1.0/16))/cos(2*Pi*Z)

R1 =
(X)->(-1)^(N(X)-1)*Psi(p(X))/u(X)

R2 =
(X)->(-1)^(N(X)-1)*(Psi(p(X))/u(X)-(1/(96*Pi^2))*d3psi(p(X))/(u(X)^3))

R3 =
(X)->(-1)^(N(X)-1)*(Psi(p(X))/u(X)-(1/(96*Pi^2))*d3psi(p(X))/(u(X)^3)+(d2psi(p(X))/(64*(Pi^2))+d6psi(p(X))/(18432*(Pi^4)))/(u(X)^5))

R4 =
(X)->(-1)^(N(X)-1)*(Psi(p(X))/u(X)-(1/(96*Pi^2))*d3psi(p(X))/(u(X)^3)+(d2psi(p(X))/(64*(Pi^2))+d6psi(p(X))/(18432*(Pi^4)))/(u(X)^5)-(d1psi(p(X))/(64*(Pi^2))+d5psi(p(X))/(3840*(Pi^4))+d9psi(p(X))/(5308416*(Pi^6)))/(u(X)^7))

Z =
(X)->2*sum(Y=1,floor(sqrt(X/(2*Pi))),cos(rstheta(X)-X*log(Y))/sqrt(Y))

d1psi =
(Z)->(-0.5*Psi(Z-epsilon)+0.5*Psi(Z+epsilon))/epsilon

d2psi =
(Z)->(Psi(Z-epsilon)-2*Psi(Z)+Psi(Z+epsilon))/(epsilon^2)

d3psi =
(Z)->(-0.5*Psi(Z-epsilon*2)+Psi(Z-epsilon)-Psi(Z+epsilon)+0.5*Psi(Z+epsilon*2))/(epsilon^3)

d5psi =
(Z)->(-0.5*Psi(Z-3*epsilon)+2*Psi(Z-2*epsilon)-2.5*Psi(Z-epsilon)+2.5*Psi(Z+epsilon)-2*Psi(Z+2*epsilon)+0.5*Psi(Z+3*epsilon))/(epsilon^5)

d6psi =
(Z)->(Psi(Z-3*epsilon)-6*Psi(Z-2*epsilon)+15*Psi(Z-epsilon)-20*Psi(Z)+15*Psi(Z+epsilon)-6*Psi(Z+2*epsilon)+Psi(Z+3*epsilon))/(epsilon^6)

d9psi =
(Z)->(-Psi(Z-5*epsilon)+8*Psi(Z-4*epsilon)-27*Psi(Z-3*epsilon)+48*Psi(Z-2*epsilon)-42*Psi(Z-epsilon)+42*Psi(Z+epsilon)-48*Psi(Z+2*epsilon)+27*Psi(Z+3*epsilon)-8*Psi(Z+4*epsilon)+Psi(Z+5*epsilon))/(2*(epsilon^9))

p =
(X)->u(X)^2-N(X)

rs1 =
(X)->Z(X)+R1(X)

rs2 =
(X)->Z(X)+R2(X)

rs3 =
(X)->Z(X)+R3(X)

rs4 =
(X)->Z(X)+R4(X)

rstheta =
(X)->(X/2.0)*log(X/(2.0*Pi))-X/2.0-Pi/8.0+1/(48.0*X)+7.0/(5760.0*X^3)+31.0/(80640*X^5)+381.0/(1290240*X^7)

u =
(X)->(X/(2*Pi))^(0.25)

?
====================================

? epsilon
%405 = 1.00000000000000000000000000000000000000000000 E-5

 

Written by meditationatae

October 21, 2018 at 5:46 pm

Posted in History

Chaos TM of Marxen and Buntrock

Previously I wrote about the 5-state TM #4 (Chaotic TM) of Marxen and Buntrock from around 1990. It certainly appears to produce a rather complex integer sequence over time at the left end of the tape, upon counting runs of consecutive 1’s and 0’s on the tape.

 

If s_k is the k’th term, then s_1 = 3 and it seems that s_k is at most k+2.

The start of the sequence s_k was exhibited in:

https://meditationatae.wordpress.com/2017/09/06/content-of-tape-of-tm-4-chaos-machine/

 

There is also a graph of s_k as a function of k:

 

rlc200k

I decided to look at the subsequence where s_k = k+2, which begins: 3, 5, 7, 9, …

Here it is with the number of binary bits per number:

3 2
5 3
7 3
9 4
13 4
15 4
17 5
21 5
25 5
29 5
31 5
33 6
37 6
45 6
49 6
53 6
57 6
61 6
63 6
65 7
77 7
85 7
93 7
97 7
101 7
109 7
113 7
117 7
121 7
125 7
127 7
129 8
149 8
161 8
173 8
181 8
189 8
193 8
205 8
213 8
221 8
225 8
229 8
237 8
241 8
245 8
249 8
253 8
255 8
257 9
289 9
309 9
321 9
341 9
353 9
365 9
373 9
381 9
385 9
405 9
417 9
429 9
437 9
445 9
449 9
461 9
469 9
477 9
481 9
485 9
493 9
497 9
501 9
505 9
509 9
511 9
513 10
545 10
577 10
609 10
629 10
641 10
673 10
693 10
705 10
725 10
737 10
749 10
757 10
765 10
769 10
801 10
821 10
833 10
853 10
865 10
877 10
885 10
893 10
897 10
917 10
929 10
941 10
949 10
957 10
961 10
973 10
981 10
989 10
993 10
997 10
1005 10
1009 10
1013 10
1017 10
1021 10
1023 10
1025 11

etc.

2 bits:  1 number

3 bits:  2

4 bits:  3

5 bits:  5

6 bits:  8

7 bits:  12

8 bits:  18

9 bits:  27

10 bits:  41

27 + ceiling(27/2) = 27 + ceiling(13.5) = 27+ 14 = 41 [10 bits]

 

18 + ceiling(18/2) = 18 + ceiling(9) = 18+9 = 27 [ 9 bits]

This means the number of subsequence terms with k+1 bits would always be very close to 1.5 times the number of terms with k bits.

 

Needless to say, this is just a guess. Analyzing complex Turing Machines is rather hard.

Heiner Marxen on Busy Beavers and Turing Machines:

https://www.drb.insel.de/~heiner/BB/

Written by meditationatae

March 13, 2018 at 7:09 am

Posted in History

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

 

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