meditationatae

Just another WordPress.com site

On asymptotics of some large character sums

leave a comment »

On asymptotics of some large character sums.

Continued from sci.math disussion thread:
“large deviations in sums of Legendre symbols (a,p) for fixed prime p”.

For q = 7,462,642,151 Max(Chi_q) = 235920.
Indeed, | sum_{k=1… 3589625338} (k/q) | = 235920.

Then:

2*((exp(Euler)/Pi)^2)*sqrt(q)*( log(log(q)) + log(log(log(q))) ) =
236724.49

and

Max(Chi_q)/236724.49 = 235920/236724.49 = 0.996601576.

===

The sources I consulted are mentioned in the sci.math discussion thread. Among these are articles of Andrew Granville and K. Soundararajan on large values of L(1, Chi_d), some on character sums. Others by mathematicians at the University of Calgary include tables on record values of L(1, Chi_d) for very large |d| .

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

Added: Friday August 18, 2017 at 2:45 pm :

The mathematicians are M.J. Jacobson, Jr., S. Ramachandran, and H.C. Williams with the Department of Computer Science at the University of Calgary.They have published a document/paper entitled:

“Supplementary Tables for “Numerical Results on Class Groups of Imaginary Quadratic Fields” ” , and in it Table 1 gives successive discriminants | Delta | with record L(1, Delta) for Delta with Delta == 1 (mod 8).

For the prime 7979490791 with (-7979490791) = 1 (mod 8) , I find that Max(Chi_d) = 243561 with d = 7979490791 and Chi_d(n) = (n/d).

Indeed, sum_{n = 1… 3958330077} Chi_d(n) = 243561.

The formula under testing is

Max(Chi_d) ~< 2*((exp(Euler)/Pi)^2)*sqrt(d)*( log(log(d)) + log(log(log(d))) )  .

For d = 7979490791, this gives

Max(Chi_d) ~= 245007.758796 with

243561/245007.758796 = 0.994095, so a good fit.

 

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

Added: Friday August 18, 11:15 pm

 

12,123,145,319 5,480,325,966 304302

d = q = 12,123,145,319 .

Max(Chi_d) = 304302

sum_{k = 1… 5480325966} (k/q) = 304302.

? 304302/(2*sqrt(q)*((exp(Euler)/Pi)^2)*( log(log(q)) + log(log(log(q))) ))
= 1.0020087094650505195701326191442298267

P.S.: The least quadratic non-residue of 12123145319 is 73.

P.P.S. :

Astonishingly,

? round((33/73.0)*12123145319)
= 5480325966

with d = q = 12123145319,

5480325966 the largest ‘k’ to include in the character sum so as to

get Max(Chi_d),

73 being the least quadratic nonredidue of q.

Where does 33 come from ?

 

 

Written by meditationatae

August 18, 2017 at 1:05 pm

Posted in History

An improved PARI/gp script for solving the Lorenz ODE system

leave a comment »

Today, I’m posting a variant of the PARI/gp script
to solve the Lorenz system of differential equations.

The use of factorials and binomial coefficients has been
eliminated, so I’d expect it to run somewhat faster than
the script from an earlier post.

 

The lorenzy4.gp PARI/gp script:

 

Lorenz(X0, Y0, Z0) =
{
order = 300;
fa=vector(order);
xp=vector(order+1);
yp=vector(order+1);
zp=vector(order+1);
dt = 1.0/250 ;
for(J=1,order, fa[J] = factorial(J));
x0 = X0; y0 = Y0; z0 = Z0;
xc=x0;
yc = y0;
zc = z0;
sig = 10.0;
rho = 28.0;
beta = 8.0/3 ;
for(Q = 1,1000,
for(L = 1, 250,
xp[1]=xc;
yp[1] = yc;
zp[1] = zc;
for(J=2, order+1,
xp[J] = (sig*(yp[J-1]-xp[J-1]))/(J-1) ;
yp[J] = (rho*xp[J-1] – sum(K=0,J-2, xp[K+1]*zp[J-1-K]) -yp[J-1])/(J-1);
zp[J] = (sum(K=0,J-2, xp[K+1]*yp[J-1-K]) – beta*zp[J-1])/(J-1); );
xn = xc + sum(J=1, order, xp[J+1]*dt^J);
yn = yc + sum(J=1, order, yp[J+1]*dt^J);
zn = zc + sum(J=1, order, zp[J+1]*dt^J) ;
xc = xn;
yc = yn;
zc = zn; );
print(Q, ” “, precision(xc, 20)))
}

 

Results for x(100), x(200), x(300) and x(400), which agree with
the Kehlett and Logg reference solution for those values:

 

? Lorenz(1.0, 0.0, 0.0)

100 12.2860066770189848088523959400428665893
200 -0.428878362621396885476845988868367367420
300 -7.9465362714960512478195581280017205595
400 5.9432455860803396010549930121329814024

 

Advancing the numerical solution by one time unit,
for example from t = 100.0 to t = 101.0, takes approximately
50 seconds. In the inner loop “for L = 1,250”,
one can see that there is no factorial function and
there are no binomial coefficients. That’s why I consider
this script an improvement over the earlier one.

I believe there is a trade-off that can be made, for the
same precision, between a smaller time-step and a smaller
value of the order of the Taylor series.

So, to minimize the total time, one would look at
pairs of time-step and Taylor series order giving the
same precision , e.g. at t = 1000, or even t = 250,
to find the pair which runs in the least amount of time.

Personal note:
the lorenzy4.gp file is in the directory :
/home/david/graphs/TABU_H_homebrew/CHECK/KEEP6/JULY24
on my PC.

Written by meditationatae

August 11, 2017 at 3:53 pm

Posted in History

Update on Parallel Rope Team Coloring

leave a comment »

At the GECCO 2017 conference in Berlin, Moalic and Gondran gave a presentation of a novel algorithm for graph coloring.

The title of their presentation is:

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

I made a best effort attempt to implement this in the C programming language. I was able to find a 48-coloring for the 500-vertex graph from the DIMACS challenge, “DSJC500.5”.

I haven’t succeeded in finding a proper or valid 47-coloring for this graph. Below, the output refers to DSJC500.5 and 47-colorings, whether valid or not. The variable name “clg” means : conflicts-low, global. The program has various teams of 4 improper colorings evolve in a complex way as described in Moalic and Gondran’s presentation. CLG is the minimum number of conflicted vertices for a team, up to the current time. A conflicted vertex is any vertex for which some edge in the graph connects it to some other vertex which happens to be of the same color. A valid coloring is the same thing as a coloring with zero conflicted vertices.

The output line:

“clg = 2 at 3221 generations for team number 49” indicates

that for the 49th team of four colorings, after 3221 generations (please see Moalic and Gondran paper, the part on evolutionary algorithms and the GPX crossover method), there were two conflicted vertices.

One conflicted vertex by itself is impossible. “clg = 0” would mean a valid 47-coloring. A 47-coloring was discovered around 2012 using another algorithm. The authors report that their implementaion of PrtCol found valid 47-colorings, among other graph colorings. I’m willing to share the program and data needed. PrtCol is a sophisticated algorithm, so there’s 4000 lines of code, with some blocks of code appearing several times with minor differences.

 

clg = 12 at 466 generations for team number 2
clg = 11 at 473 generations for team number 2
clg = 10 at 688 generations for team number 2
clg = 9 at 688 generations for team number 2
clg = 8 at 689 generations for team number 2
clg = 7 at 690 generations for team number 2
clg = 6 at 1701 generations for team number 2
clg = 4 at 3389 generations for team number 2
clg = 12 at 485 generations for team number 3
clg = 11 at 485 generations for team number 3
clg = 12 at 299 generations for team number 4
clg = 11 at 299 generations for team number 4
clg = 10 at 308 generations for team number 4
clg = 8 at 570 generations for team number 4
clg = 7 at 626 generations for team number 4
clg = 6 at 629 generations for team number 4
clg = 12 at 103 generations for team number 5
clg = 11 at 146 generations for team number 5
clg = 10 at 166 generations for team number 5
clg = 9 at 167 generations for team number 5
clg = 8 at 168 generations for team number 5
clg = 7 at 1333 generations for team number 5
clg = 6 at 2049 generations for team number 5
clg = 5 at 2051 generations for team number 5
clg = 12 at 175 generations for team number 6
clg = 11 at 202 generations for team number 6
clg = 10 at 202 generations for team number 6
clg = 9 at 296 generations for team number 6
clg = 8 at 296 generations for team number 6
clg = 7 at 1261 generations for team number 6
clg = 6 at 3052 generations for team number 6
clg = 5 at 4220 generations for team number 6
clg = 4 at 4230 generations for team number 6
clg = 12 at 350 generations for team number 7
clg = 10 at 350 generations for team number 7
clg = 9 at 552 generations for team number 7
clg = 8 at 763 generations for team number 7
clg = 6 at 1147 generations for team number 7
clg = 5 at 1536 generations for team number 7
clg = 11 at 286 generations for team number 8
clg = 10 at 340 generations for team number 8
clg = 9 at 350 generations for team number 8
clg = 8 at 359 generations for team number 8
clg = 7 at 590 generations for team number 8
clg = 6 at 590 generations for team number 8
clg = 5 at 1115 generations for team number 8
clg = 12 at 428 generations for team number 10
clg = 11 at 759 generations for team number 10
clg = 10 at 759 generations for team number 10
clg = 8 at 759 generations for team number 10
clg = 7 at 2287 generations for team number 10
clg = 6 at 2305 generations for team number 10
clg = 5 at 2745 generations for team number 10
clg = 12 at 273 generations for team number 12
clg = 11 at 283 generations for team number 12
clg = 10 at 283 generations for team number 12
clg = 9 at 371 generations for team number 12
clg = 8 at 371 generations for team number 12
clg = 7 at 878 generations for team number 12
clg = 6 at 1149 generations for team number 12
clg = 12 at 208 generations for team number 13
clg = 11 at 208 generations for team number 13
clg = 10 at 232 generations for team number 13
clg = 9 at 412 generations for team number 13
clg = 8 at 476 generations for team number 13
clg = 7 at 588 generations for team number 13
clg = 6 at 590 generations for team number 13
clg = 5 at 757 generations for team number 13
clg = 4 at 4953 generations for team number 13
clg = 3 at 4958 generations for team number 13
clg = 12 at 432 generations for team number 14
clg = 12 at 408 generations for team number 15
clg = 11 at 441 generations for team number 15
clg = 10 at 441 generations for team number 15
clg = 9 at 1029 generations for team number 15
clg = 8 at 1033 generations for team number 15
clg = 7 at 1767 generations for team number 15
clg = 6 at 2154 generations for team number 15
clg = 5 at 2430 generations for team number 15
clg = 12 at 148 generations for team number 16
clg = 11 at 264 generations for team number 16
clg = 10 at 264 generations for team number 16
clg = 9 at 264 generations for team number 16
clg = 8 at 344 generations for team number 16
clg = 7 at 367 generations for team number 16
clg = 12 at 134 generations for team number 17
clg = 11 at 134 generations for team number 17
clg = 10 at 180 generations for team number 17
clg = 8 at 180 generations for team number 17
clg = 7 at 183 generations for team number 17
clg = 6 at 188 generations for team number 17
clg = 5 at 188 generations for team number 17
clg = 4 at 343 generations for team number 17
clg = 12 at 186 generations for team number 18
clg = 11 at 245 generations for team number 18
clg = 10 at 256 generations for team number 18
clg = 9 at 261 generations for team number 18
clg = 8 at 469 generations for team number 18
clg = 12 at 260 generations for team number 19
clg = 11 at 260 generations for team number 19
clg = 10 at 262 generations for team number 19
clg = 9 at 280 generations for team number 19
clg = 8 at 911 generations for team number 19
clg = 7 at 1260 generations for team number 19
clg = 6 at 1301 generations for team number 19
clg = 12 at 402 generations for team number 20
clg = 11 at 403 generations for team number 20
clg = 9 at 465 generations for team number 20
clg = 8 at 473 generations for team number 20
clg = 7 at 473 generations for team number 20
clg = 12 at 89 generations for team number 21
clg = 11 at 96 generations for team number 21
clg = 10 at 542 generations for team number 21
clg = 9 at 1352 generations for team number 21
clg = 8 at 1354 generations for team number 21
clg = 7 at 1359 generations for team number 21
clg = 6 at 1362 generations for team number 21
clg = 5 at 2226 generations for team number 21
clg = 4 at 2758 generations for team number 21
clg = 12 at 169 generations for team number 22
clg = 11 at 201 generations for team number 22
clg = 10 at 530 generations for team number 22
clg = 8 at 1014 generations for team number 22
clg = 7 at 1163 generations for team number 22
clg = 6 at 1529 generations for team number 22
clg = 11 at 64 generations for team number 23
clg = 10 at 64 generations for team number 23
clg = 9 at 67 generations for team number 23
clg = 8 at 1167 generations for team number 23
clg = 7 at 1869 generations for team number 23
clg = 6 at 2552 generations for team number 23
clg = 12 at 426 generations for team number 24
clg = 11 at 427 generations for team number 24
clg = 10 at 427 generations for team number 24
clg = 9 at 431 generations for team number 24
clg = 12 at 496 generations for team number 25
clg = 11 at 501 generations for team number 25
clg = 12 at 149 generations for team number 26
clg = 11 at 472 generations for team number 26
clg = 10 at 472 generations for team number 26
clg = 12 at 381 generations for team number 27
clg = 11 at 383 generations for team number 27
clg = 10 at 384 generations for team number 27
clg = 9 at 387 generations for team number 27
clg = 8 at 390 generations for team number 27
clg = 7 at 538 generations for team number 27
clg = 6 at 538 generations for team number 27
clg = 5 at 2051 generations for team number 27
clg = 12 at 395 generations for team number 28
clg = 11 at 623 generations for team number 28
clg = 10 at 677 generations for team number 28
clg = 9 at 677 generations for team number 28
clg = 8 at 679 generations for team number 28
clg = 7 at 2509 generations for team number 28
clg = 6 at 2518 generations for team number 28
clg = 5 at 2528 generations for team number 28
clg = 12 at 229 generations for team number 29
clg = 11 at 229 generations for team number 29
clg = 10 at 229 generations for team number 29
clg = 9 at 375 generations for team number 29
clg = 8 at 495 generations for team number 29
clg = 7 at 957 generations for team number 29
clg = 6 at 963 generations for team number 29
clg = 12 at 367 generations for team number 30
clg = 10 at 368 generations for team number 30
clg = 9 at 368 generations for team number 30
clg = 8 at 774 generations for team number 30
clg = 6 at 929 generations for team number 30
clg = 12 at 391 generations for team number 31
clg = 11 at 391 generations for team number 31
clg = 10 at 391 generations for team number 31
clg = 9 at 391 generations for team number 31
clg = 8 at 396 generations for team number 31
clg = 7 at 399 generations for team number 31
clg = 6 at 492 generations for team number 31
clg = 5 at 1933 generations for team number 31
clg = 4 at 1956 generations for team number 31
clg = 3 at 2130 generations for team number 31
clg = 12 at 247 generations for team number 32
clg = 11 at 247 generations for team number 32
clg = 10 at 458 generations for team number 32
clg = 8 at 458 generations for team number 32
clg = 7 at 523 generations for team number 32
clg = 6 at 553 generations for team number 32
clg = 5 at 693 generations for team number 32
clg = 4 at 30887 generations for team number 32
clg = 12 at 479 generations for team number 33
clg = 11 at 480 generations for team number 33
clg = 10 at 480 generations for team number 33
clg = 9 at 586 generations for team number 33
clg = 8 at 590 generations for team number 33
clg = 7 at 591 generations for team number 33
clg = 6 at 619 generations for team number 33
clg = 5 at 621 generations for team number 33
clg = 4 at 797 generations for team number 33
clg = 12 at 196 generations for team number 34
clg = 11 at 196 generations for team number 34
clg = 10 at 198 generations for team number 34
clg = 9 at 203 generations for team number 34
clg = 8 at 226 generations for team number 34
clg = 6 at 589 generations for team number 34
clg = 12 at 440 generations for team number 35
clg = 11 at 446 generations for team number 35
clg = 10 at 451 generations for team number 35
clg = 9 at 451 generations for team number 35
clg = 12 at 304 generations for team number 36
clg = 11 at 770 generations for team number 36
clg = 10 at 772 generations for team number 36
clg = 9 at 777 generations for team number 36
clg = 8 at 780 generations for team number 36
clg = 7 at 789 generations for team number 36
clg = 6 at 845 generations for team number 36
clg = 12 at 320 generations for team number 37
clg = 10 at 321 generations for team number 37
clg = 12 at 224 generations for team number 39
clg = 11 at 367 generations for team number 39
clg = 10 at 490 generations for team number 39
clg = 9 at 672 generations for team number 39
clg = 8 at 672 generations for team number 39
clg = 7 at 956 generations for team number 39
clg = 6 at 961 generations for team number 39
clg = 5 at 2167 generations for team number 39
clg = 12 at 157 generations for team number 40
clg = 10 at 157 generations for team number 40
clg = 9 at 473 generations for team number 40
clg = 8 at 502 generations for team number 40
clg = 6 at 1438 generations for team number 40
clg = 5 at 2921 generations for team number 40
clg = 4 at 2924 generations for team number 40
clg = 12 at 325 generations for team number 41
clg = 10 at 325 generations for team number 41
clg = 9 at 325 generations for team number 41
clg = 8 at 535 generations for team number 41
clg = 7 at 600 generations for team number 41
clg = 5 at 600 generations for team number 41
clg = 12 at 172 generations for team number 42
clg = 11 at 202 generations for team number 42
clg = 10 at 202 generations for team number 42
clg = 9 at 659 generations for team number 42
clg = 8 at 735 generations for team number 42
clg = 12 at 456 generations for team number 44
clg = 10 at 499 generations for team number 44
clg = 8 at 561 generations for team number 44
clg = 7 at 679 generations for team number 44
clg = 6 at 695 generations for team number 44
clg = 5 at 908 generations for team number 44
clg = 12 at 175 generations for team number 45
clg = 11 at 175 generations for team number 45
clg = 10 at 192 generations for team number 45
clg = 9 at 362 generations for team number 45
clg = 8 at 362 generations for team number 45
clg = 6 at 397 generations for team number 45
clg = 5 at 510 generations for team number 45
clg = 12 at 225 generations for team number 46
clg = 11 at 330 generations for team number 46
clg = 10 at 341 generations for team number 46
clg = 9 at 343 generations for team number 46
clg = 8 at 344 generations for team number 46
clg = 6 at 465 generations for team number 46
clg = 12 at 424 generations for team number 47
clg = 11 at 426 generations for team number 47
clg = 10 at 731 generations for team number 47
clg = 9 at 740 generations for team number 47
clg = 8 at 788 generations for team number 47
clg = 7 at 801 generations for team number 47
clg = 6 at 801 generations for team number 47
clg = 12 at 178 generations for team number 48
clg = 11 at 180 generations for team number 48
clg = 10 at 224 generations for team number 48
clg = 9 at 225 generations for team number 48
clg = 8 at 268 generations for team number 48
clg = 7 at 456 generations for team number 48
clg = 6 at 507 generations for team number 48
clg = 5 at 766 generations for team number 48
clg = 12 at 235 generations for team number 49
clg = 11 at 246 generations for team number 49
clg = 10 at 747 generations for team number 49
clg = 9 at 752 generations for team number 49
clg = 8 at 946 generations for team number 49
clg = 7 at 1264 generations for team number 49
clg = 6 at 1524 generations for team number 49
clg = 5 at 1526 generations for team number 49
clg = 4 at 1526 generations for team number 49
clg = 2 at 3221 generations for team number 49
clg = 12 at 137 generations for team number 51
clg = 11 at 142 generations for team number 51
clg = 10 at 151 generations for team number 51
clg = 9 at 1277 generations for team number 51
clg = 8 at 1292 generations for team number 51
clg = 7 at 1294 generations for team number 51
clg = 6 at 1294 generations for team number 51
clg = 5 at 4009 generations for team number 51
clg = 4 at 4586 generations for team number 51

Written by meditationatae

August 10, 2017 at 12:23 pm

Posted in History

Blog accepting comments

with one comment

That’s my intention, you can ask questions, answer questions, etc. once I have this figured out.

David Bernier

 

Written by meditationatae

August 10, 2017 at 11:41 am

Posted in History

PARI/gp script for Lorenz system

The Lorenz system of differential equations is challenging to solve over extended periods of of time ‘t’, the independent variable.

In “Long-Time Computability of the Lorenz System”, the authors Kehlet and Logg from Norway give a numerical solution for x(t), y(t), z(t) for t in [0, 1000] and with

initial values x(0) = 1, y(0) =0, z(0) = 0.

Their paper is downloadable from:

https://www.simula.no/publications/long-time-computability-lorenz-system

I’ve tried to reproduce their computations using the PARI/gp calculator environment.

I put it all into a script, lorenz.gp, copied below:

Lorenz(X0, Y0, Z0) =
{
order = 300;
fa=vector(order);
xp=vector(order+1);
yp=vector(order+1);
zp=vector(order+1);
dt = 1.0/200 ;
for(J=1,order, fa[J] = factorial(J));
x0 = X0; y0 = Y0; z0 = Z0;
xc=x0;
yc = y0;
zc = z0;
sig = 10.0;
rho = 28.0;
beta = 8.0/3 ;
for(Q = 1,1000,
for(L = 1, 200,
xp[1]=xc;
yp[1] = yc;
zp[1] = zc;
for(J=2, order+1,
xp[J] = sig*(yp[J-1]-xp[J-1]) ;
yp[J] = rho*xp[J-1] – sum(K=0,J-2, binomial(J-2,K)*xp[K+1]*zp[J-1-K]) -yp[J-1];
zp[J] = sum(K=0,J-2, binomial(J-2,K)*xp[K+1]*yp[J-1-K]) – beta*zp[J-1]);
xn = xc + sum(J=1, order, xp[J+1]*dt^J/fa[J]);
yn = yc + sum(J=1, order, yp[J+1]*dt^J/fa[J]);
zn = zc + sum(J=1, order, zp[J+1]*dt^J/fa[J]) ;
xc = xn;
yc = yn;
zc = zn; );
print(Q, ” “, precision(xc, 20)))
}

===

 

In PARI/gp, the script can be loaded with:

\r lorenz.gp

I set numerical precision to 500 digits like this:

? \p 500
realprecision = 500 significant digits

To start at (1, 0, 0), I type:

Lorenz(1.0, 0.0, 0.0)

The discrete time-step is 0.005, so 200 iterations are needed to go forward by one time unit. The program computes the Taylor series of order 300 for x(t), y(t), z(t) at each time-step: 0.000, 0.005, 0.010 , … 1000.000 .

It takes about 1-2 minutes to advance by one time unit, so it is very slow. As far as I know, only instesive computations can give reasonnably accurate solutions for t from 0 to 1000…

 

===========

Added August 4 2017:

The computation to t = 1000 has finished. I get about 12+ decimals agreement with Kehlet and Logg:

t = 950 (K&L) x(t) = 3.491185243251774 (15 D agreement)
t = 1000 (K&L) x(t) = 12.537229584422063 (12 D agreement)

The table produced by the script:

? Lorenz(1.0, 0.0, 0.0)
====================================================
t: x(t) :
1 -9.4084505670560362053926647410812279910
2 -7.8760825499916576112247558704662995375
3 -8.1439992454340691645934026619087207704
4 -9.4535420101890103223043414853426323883
5 -6.9745704726848179542532974436339082574
6 -9.6818923336166851655646181650890655290
7 -7.8579608665045609128091899527880714120
8 -7.4185991201173199261691101065285675762
9 -10.1532414372932554813701941184685103712
10 -5.8576853824240900202224239159218626923
11 -11.0024967583383758783345802542313611845
12 -5.8730774961019154811654406330301689106
13 -9.4785435897747250563487525717397056854
14 -5.6105140005154145123915396942665469159
15 -10.3070357820504313286787404675298389219
16 -1.18335729105615816320955439922561472664
17 6.3804821158387297849140855485401268279
18 3.93733413894145756683967365620966436374
19 -6.8035678727745526216128784447519103193
20 -8.0211436133174370677125557006619132421
21 -6.0591776679778013133618330547395817304
22 -2.07528223645912353643948709335715566354
23 9.6929728969203854734790669597447531637
24 -8.0059404747358815423143137254796828688
25 -0.96099551633119955849939675909115813132
26 0.424822337829463810386069434219908663338
27 -10.8642106671141747848418670066937446154
28 -4.1621586103568089803258694339114413386
29 -10.9979813009408050226260266572906629193
30 -3.89263733737948547590641988473456118005
31 1.99572807651514218576528453612368319761
32 1.43325307733124367973393310774045812866
33 -11.8565343720266406426694488486170260642
34 -3.41733655479537595456164976097517363240
35 -13.1600336713077062104187375739604320679
36 -12.3174686282022453527364703473167418902
37 2.60771036538164215384084403502968653758
38 4.7205823591627551535608179285539520220
39 -8.5096464125969575357984242640555563082
40 -0.194731422418736965684697218013746750900
41 0.78253204689812728857482698134949747734
42 -10.5198363503292713007868429323362211943
43 -5.2052511757046957644579889821246774643
44 -11.9705198390506667362725349890239138656
45 -4.2098788806682299631678460872650987119
46 -13.2875927913923117998535301065481228038
47 -1.83924277901879257674583204144476729134
48 2.53904825837818892753540097837564333473
49 -14.4938562867421812564678873876490465340
50 16.2462755445693913895185717175175159133
51 -4.3787046311007356317616425774453591101
52 -12.9823788919287098966865458218653821033
53 -2.32075418851248025965707972947870950767
54 -1.84191521884607952879913382763884367088
55 13.2109889354104032496495161351214355527
56 1.40474565147779813032558988076339886443
57 -4.0751696381791201943143345024725282769
58 -5.7561931361828156559263319818937970307
59 5.8662943662512189962900755413119377074
60 4.4354983284223783463498039344583797555
61 12.9747849957870764702196308709512354251
62 -2.89696331966853283118009660839295812808
63 2.39412777761705947895055461433580565342
64 1.77465821322866476545538254922380111030
65 -10.9733621887016633094077125413798098396
66 -3.78838658921602361525289961118766681356
67 -14.2393867085304663047772669820713339088
68 -6.1916575563545819766345308881992632543
69 2.08319447731166645517128541428364077174
70 -7.3048586455218831593134931073497341285
71 7.7251332780086867300114509909131315672
72 0.243628692237215513200711513695979663681
73 -8.0974204108995711246846414135198851485
74 -8.7291417733543468593396394637282425301
75 0.56830713772608435233733412730036661532
76 -9.9471072747257624101076075736366907256
77 -7.4869383142352940404475856820602855298
78 -7.7450640422037108197130497875520360935
79 -9.7781486463545977474497341584262376081
80 -5.7286418376201573987574537308427619399
81 -11.4908792298392806343859475154724073266
82 -5.0531170390861554403428966592291907275
83 -11.5566209684216705186645047331385457406
84 -3.73398128872225880293203713815463420179
85 -14.0091151606937901751251329145291395928
86 -3.73593688353745542735926363581608462042
87 -0.0120404426969351492358464879369103972626
88 5.2498381906489796969138317207053532565
89 9.8563428429920781478184858283095168403
90 5.5920294940027971653879104358674201893
91 10.1844559223738327795605961851866195807
92 1.69396000652493598503636333696888591944
93 -4.6752624674154353014765646074924860150
94 11.7475709024034502121156684556368111131
95 2.62573361972966940045297314018980285148
96 -5.7124201308880073275827772010230063324
97 -14.6697550135289980696528499026827300611
98 1.41701538878385101026952159329277254340
99 -1.13262456181043119266072806208626085365
100 12.2860066770189848088523959400428665893
101 3.23451236716400783523883264566162534354
102 -0.65831121329213781889117045019543925497
103 -10.7575100490922587240216129459619377589
104 -3.72765230890553511115969098163552728184
105 -2.84130559191910455838549296735926318238
106 14.2338343803417345101546897415122485749
107 -5.7032632494640590644138364898013783020
108 0.83357855674259823102317457320635333311
109 -8.9535604654819576521333468403360632042
110 -7.4471446363450498593910995976494484795
111 16.6051739132483750968163355930873198021
112 -6.2729992278060068362804460604079073255
113 -8.5278442110421843904952237649957319570
114 -5.8579148829813261015265731477154717213
115 -10.1063212721277134675951932538957340109
116 -0.450960661104642411631697171808038389764
117 4.7286071981246348942531827094372937018
118 11.1767665972372745811111018080708156887
119 2.82803976886733759775080046789796427650
120 8.4130021659307024776217776421858025620
121 -8.2298705388098722430466931348042172207
122 -0.489948958607854389886816622225492868212
123 -7.0123459515165588156028908885274837756
124 -15.9183207002199908967405026396641255944
125 2.17919838407232421224233459191819054993
126 -0.67439613856024778464348027248194249964
127 11.7829390733989479597476021009978410685
128 3.24616912402863858567069750601103327029
129 5.1150347293269535800994657290738097768
130 -14.0460712267382217275402592129371604226
131 2.58717666284859102963628252266665213741
132 -0.96896307879064242723239785567265269856
133 12.1974848733212035000152238791042343151
134 2.91780939946848818364124239135494327468
135 -2.43252642622591986077770606239276594130
136 -3.55798155497668487223225816686449691745
137 8.9653151486934470143657781304497117940
138 2.01784027053316786179237243662854386875
139 -4.1271982458518324887361785421208345385
140 9.6144031541821452367437182124360882151
141 0.187599535772080823665000109385210116164
142 4.3645126250163374224855716291559022469
143 11.5710302844926563027531831650950468749
144 3.52985180995277984427953204627401587358
145 13.6381708262915008071603436866750677097
146 10.2224164771498747492375028457851235250
147 -2.50614326569454369442452898733521793473
148 -1.60114842867405927425760831881404442934
149 11.3407270180043146792326304017758167378
150 3.71416385015751357190934495114717190190
151 14.0670891551059243749339816445225688773
152 5.3459244400731802499333517088756411424
153 -1.31324797423382136697181240123146872860
154 9.9066611216311311639601257823750863938
155 16.7212541116126541745914556077269653832
156 -2.62202279698366177090829647645280980116
157 -5.9335956332601882689364730444566830619
158 12.6564768338378186424813239074746531123
159 -0.52325665132419839266874951140388524394
160 2.84479310553286312333354179159402087668
161 -14.5535622519889570433517981144912791188
162 7.6228897405529552885788520653126843265
163 -2.28737644428516727410504743772415385430
164 3.91681092716689965263861027326286172802
165 -8.8595195130692743880244499959831481720
166 -1.31608732128764557202013880838968123584
167 7.4390043321443325510267881460782098815
168 -10.8320168966541829296532091245218010649
169 3.95931082204698894015549082699340917336
170 8.7102584413110378004772360998972158243
171 9.7314825788709871941142394027385084099
172 0.64353323454844789626485686169143662042
173 1.92521904940060273039290942872058953321
174 -13.6933887114167417842353696499445407124
175 -1.22526784560756540541259708592224003261
176 -17.1229069025451145253799845955407245196
177 7.2859872527861142410309900271072922581
178 7.3911970715447350436649452386163746105
179 9.3366581877401504163382968014189274753
180 5.0920623196060706996789793326423328808
181 10.3871607970048086754943791399921499099
182 3.96136505248067601734403649083084268975
183 1.74368571697085294544489839682450143050
184 -13.2649915047012925029161085734975266964
185 -8.5219231817345665315694561551884117667
186 1.66336868463203489615913511106355647440
187 -6.9532885699796529456847203284471640945
188 12.0018597127022408918273739912733894562
189 0.165174818410459016055372520932306013821
190 -0.60897588003936435233102198207855020737
191 11.3969748776788983261494448102250558042
192 3.43477599600727684940492910791012917693
193 4.9656754744488707450260179224109651884
194 -11.8969456208996139979306692909121221468
195 3.28855385468983772829374735507539395414
196 1.63518554785829850973770128825687983165
197 -13.6229576687744224432001273150464451093
198 -2.79858145609318097846516170783158652459
199 -2.02145165850451906552134099133871743175
200 -0.428878362621396885476845988868367367420
201 11.1937921710566021219409615638879142356
202 4.6204978102869323872277330572731022695
203 12.6206792121194362025514135325914577905
204 2.98128671494130783932851030005595385499
205 8.3732653754941920451251869535809128321
206 -10.7769345012129254624987576772330441246
207 4.0999896278295234006097588117957082773
208 9.9563770469990980097063711561433212955
209 5.6420605287943715347215743365382876736
210 0.123581489367140830250613251778137322476
211 -9.3848246459618447391239116437391525138
212 -5.0806420436454001652797989712023284845
213 0.79813370303837995902114329861068899596
214 -8.7020292880572307127224465549763512739
215 -12.1253407513409274225089267009041526250
216 0.092660609871206443824852480299096539899
217 4.8685943590310446756919002987450213635
218 14.0909905110020959219649571947342277410
219 13.7127734015114481288710249883957682603
220 -4.9680265718883784244924779904033717738
221 -11.9919083654743267661694977525505203566
222 -0.90243832123607110845568414458318411033
223 5.1523938399247959979720611205786479372
224 13.6774469054595672330135069231735144515
225 12.6356498407568150429565350300276193221
226 -5.1767458291252308919676553402208495799
227 -11.4951177484114412376696741095069964462
228 -0.85430669855982689699511270351136627110
229 5.4564085672088908476507459273235156433
230 13.1828616502861831323083816176994152946
231 12.0559690046746111321483141614088075629
232 -5.3916778787263505077708705703115134312
233 -10.8983423585246713101341395035943552351
234 -0.99646319353607004270807205865798417807
235 6.0444779225144527396534350126154063209
236 15.7487030425083321605417236226404331217
237 -1.13626531150228622454372226704943883914
238 -2.51904967765890485728178995342037666526
239 -12.3929795258801521245994637003524778691
240 -3.07736832527789296231341916833216569856
241 -7.4490992155787268035588851002216661677
242 6.6667672146134526700299725772851025915
243 -5.2524870150795208294685716525389218457
244 -9.2212459867532544763099348001435380846
245 -5.1018695493551347103902323061873071113
246 0.216569803746645428431726505377010582785
247 -7.2827228437517069793331805526616321782
248 -6.8292993779220940229506881744175918932
249 -2.78732204527592700380658867776919568609
250 2.50281409887961591659736807419620512942
251 -9.5674421229385719899839365321311553065
252 -3.98208114512482689022380350578184559039
253 -14.6352896063011888867244613610354391791
254 -7.7180056580717938617907750396961912028
255 5.4795722728666455119377728879298208264
256 11.6977013598378079607833903332378109969
257 4.0995876175596630681003743169791759384
258 12.8090874950140136127697895104850152875
259 2.39810035073764314163995003171130838121
260 -1.66173519111978459487476899801671546142
261 13.1411687987795790939323374485044300906
262 8.7529251041380600198457912052051105260
263 -1.63070867480242793857386593952797391587
264 6.9025520706228743716032838958102423059
265 -12.5451053834594045819352220609194493473
266 -0.0585396962979735416440633353716832628634
267 2.09442459004395505305359234737665927300
268 -14.1565332032682958623622719871271569770
269 -8.3561401810894651325287744429044559306
270 2.62648037981417975340714394045313817629
271 0.76666468403463570689417668037863199974
272 -11.7834498559920824209690001959616331030
273 -4.5437819801792611221364083507048799478
274 -12.6920587906790980576314757324012792167
275 -2.30412063582573951680509583235385353116
276 -2.62665527738636951268698059200362375081
277 12.3146235557311193217395720934626824119
278 0.77035026473388945399712110254359687071
279 -4.3953795261901500905063475718096064889
280 -12.4746981057052492745149848873354100968
281 -1.24228777124753166519946147887195213310
282 4.7889688449972833492272958589301976845
283 6.5706950050946013611869863310152538111
284 -5.2918237316536583171505482478516086653
285 -5.5300120890203933111120545408777952053
286 -15.6024957291601590947758915495088566596
287 1.25803484757054239412431433821209881431
288 3.05619618508495987095718069814462136189
289 11.1399855153894832041261628568371108492
290 -5.6401282171263429052070577552522946259
291 -1.55624434194844043910056929184518794766
292 -6.0502474815893160464371699703499439592
293 13.9485516731306574731194186226358189575
294 -0.327126976886965235968598288308664393026
295 -2.24230890513698213213721751138444330086
296 13.2951464252084024021647036636255457605
297 -12.8646696909985750079564483917279622704
298 2.67764259313386985256243652607671028352
299 5.9511599555257547334488618458591691208
300 -7.9465362714960512478195581280017205595
301 0.86522448574056869541667281561686649766
302 -2.98471015384822860760602897049256291682
303 13.8156511285020763109281647567046585000
304 1.64086134778722428652019899526950978939
305 -1.41285615760941017250692110648527287239
306 12.7156659390672588714730348461791437275
307 4.5611412774630670440711397595476954939
308 1.29047680272272476334405600882880954421
309 -4.9812800383246784459630733775294298195
310 12.0426686856379710994887806839377299777
311 17.8576531845920720630981459491547124993
312 -5.3409683059626506826603730308696780310
313 -10.7635016683689205529356597887873478495
314 -4.3310963516597586345859902418865178042
315 -13.7083934900619879880917549850452036913
316 -0.94745526069631949766312624810686024442
317 -3.35200170632395013808856375011038387537
318 -12.9340893042661211367579496619397844001
319 5.6120053477899146524790516996602201687
320 0.58473750365388298526947135950180532282
321 -7.5767157036309780159386428228521796384
322 -12.2173038576332445766256239218303978111
323 -0.115097392477354785400061675540138915324
324 0.76644759059154788717179407149797860748
325 -11.9906246404858511477796181314164894592
326 -2.99784985448340829615342334422672784010
327 -1.93410057558929119230974101646521370799
328 14.0502400972886454986914947802919904718
329 2.33717232244879522521909519273058704945
330 1.53690354923440765647308476684264581208
331 -8.8049066044872350964294381584590752914
332 13.2397323718623882936597420241220118621
333 -0.72005631638258194931083904883149692030
334 5.0264075827108867603421246616538372679
335 11.8869423368646162944240692977207492347
336 0.349576318368692200870833133607019388783
337 4.3860281972588053726826693569141147953
338 12.8215039884131287387463234396724213889
339 0.85211356925467543104116758587872551189
340 -3.98832014316338925519883942089377586319
341 -12.8107240683800360156223173588396640584
342 -1.77832894724610568824439867744523520940
343 2.28158256136801393541776821384787715240
344 -13.7622578290016992083697350146742356143
345 -0.99605754306736329785137748123896191663
346 -3.24289021984252389867840668828647715035
347 -11.6412562064815891747189297926250951597
348 4.8674962452476516976089288294802180178
349 1.71649542348296392778265987851889189890
350 9.1128236292473042157897058578376699199
351 14.6136411891030044506418737478351118927
352 -3.36135823163262034937965264598328170780
353 -9.5167359400726399522097146382433458935
354 -13.7721696435321049680289634233546689458
355 1.09597222952351160246032378166146486974
356 -5.4824673497806203881772435286531631018
357 -14.6722058256940939448640847099375880268
358 2.31806673173622409337320129851657983521
359 -2.12622532835385902909390055835696181321
360 12.2139781259246293593852452611705870555
361 -10.0166563131655809880327981368055541536
362 1.24416332180889984328792320553207283424
363 -7.0821938303011966662464710892958898779
364 2.79458060809219245213969336806689103755
365 -7.7925813206615255038458642609803690234
366 -8.0023762655212736378337022646048487837
367 -5.9399626943870138893063626228571550334
368 -5.4873248837450638320212317778195015894
369 -14.7944775011050379575460631181247962335
370 1.93732727134830130782748189180792814196
371 -1.76245698867790025354764596314966157611
372 12.9125908030082967801355607405006635110
373 14.2864645450036972435811949184642135828
374 -2.85855827207303456805870104284586289380
375 -8.7531161503677388810083278133724969089
376 8.3041447945781696030609785522135898803
377 0.88475892059462029294756677797227832186
378 4.8538059792801331225309506581314505614
379 -15.6140899906188988683358423183838642033
380 1.21719246622805790800510570832812877932
381 3.15792289678386798076155953818148643503
382 12.5765692334439504549697439046567773892
383 -7.3826499235604635773299801753763075550
384 0.306164094147385976259208700093963226680
385 -5.3786633444546692908904624745831397668
386 -9.7781501885336915033492426221686778698
387 -3.76921991504422064616162327974508082339
388 -14.3089114355662769897157517200419187337
389 17.0110363402255525802536698730850503832
390 -3.92713359950626639911025771201715889680
391 -13.8527026564416095432794689238270153636
392 -1.65276156232501878781274014444856500964
393 -2.98185379659132659285836714225003647072
394 -13.4832182848382549344964872263798179070
395 -2.84838328089396281498819542594610381198
396 -2.18556860812486504373867681973449354977
397 -4.8979656272780799452982795637367961968
398 8.7968815914786192562708400005080267235
399 -0.277658764574771456799257449515402527157
400 5.9432455860803396010549930121329814024
401 14.0743008314345751498458678376718692762
402 -1.43973458987994998822793004236413110677
403 2.46845092667597192641854221994610451959
404 -13.5049739327546409015412733296237771359
405 8.9132729047642291333784052128382141388
406 -1.72452734672673927365202298430562394012
407 6.3855082713706036873368698269480306023
408 -10.9612455974029102390226636879060182136
409 1.51229840883405079949428562285120263823
410 -6.1194051066145535361100077854205178240
411 -14.8377605876395165480169810617903520098
412 0.74675629162613564166815723592785743241
413 1.91220396140306241088498201774338909198
414 -12.4347587544571501710847439768526705198
415 17.0883687613040325483839455352146328454
416 -3.42789178710209818781715501458142168006
417 -12.7219002109411251690841031405473681256
418 -6.6212691173290922128498306480230653810
419 0.239547905097166195336884861510018876358
420 -5.0077411003945275019169969755588130687
421 -10.3462994442068110021069607388795414223
422 -4.5805712866559041538999423588156741803
423 -13.2334963127620193525582482116057844030
424 -0.67780476267208650107510246495183006910
425 -3.82991101776392338077431949902060503127
426 -14.4716718100643584569195113719258683007
427 -5.6062353987200554536940584618534863805
428 2.71298043726360062775752181011423056347
429 -3.17067029947111704944532680080639409015
430 8.8460462976321147846503812503844598139
431 3.32085788914491786763968420097783157273
432 10.6126982031775381347625641581627059299
433 -4.9524615420103352740666446790778577513
434 -2.31875325549274800694914981540826789692
435 7.8594121170165154020969344176052298003
436 9.7517392297453697243262369415553142009
437 6.0223179739238475917936774810430058159
438 11.0362154252736437242179390134283186027
439 5.8830424478133832422578323850014842378
440 9.6258083301261916989941687664698613069
441 6.0446670195684785239060615188479687669
442 9.0206476027826558449027272869741693117
443 2.65485169909339988087830909247518042297
444 2.76565134711522670025059782138919108827
445 -9.7206534739510152898921160730773092902
446 -2.94588212517733856183706408601092094358
447 -7.9403297282593878174118998218419876180
448 6.3973818998206757459492880885363780978
449 -1.43524312085001091507658047431427324586
450 -6.1807219299817278478645579801260499560
451 15.3192876206193852814515059566352318470
452 -0.82207607360240844419542321548057115680
453 -3.24027868132132122502876987915362925107
454 -12.8311770975549088270581710354428925578
455 -2.62313876371609371699390429609826771555
456 -4.9188344040616819282307963206088896617
457 13.6316148282928720561318399988332311280
458 -2.69863606200374657916706462655703225715
459 4.3556314303381251798139102947658625953
460 9.5145401656899187684830197211311639387
461 -4.0881906545008589982649704271776806142
462 -1.37394305115356149089317114492739791165
463 12.5627682484362270599109456739944667306
464 4.6530306769438989657957312138974492377
465 1.36612365045241968570594849018897899929
466 -3.71442729346352516790413232340275473600
467 11.5166385631163222355866937965507191105
468 -0.0571635880835742122610000271412107941107
469 3.23023948937294332681098464163952186029
470 -12.4307229333164951251110140860886483018
471 3.41053878417898512756135101570089452389
472 -1.95422682043998651494444952021417908337
473 -11.6804662295032180766622470080602555481
474 -3.48106884733414055002900246605046511150
475 2.36696755584227729257573223289749934794
476 10.2001102868424673899153470685665138699
477 -15.9162721712019970971909070866028384438
478 2.20924736455353894987518515698809138991
479 1.74068859414248310714193424452107475234
480 -12.4629976226074045277225317357711045890
481 -2.12005271873189719898647997934516856269
482 -0.78407673525303965336956226703262464206
483 12.2696871375558070546270922136503791779
484 3.46032501882941154757706361860478502502
485 11.4718728047265763527589196867127330864
486 6.6015246664535137075532978792393664374
487 0.87744521502057209525002350688581567499
488 -5.2421019248058305624787370830526146217
489 15.8186150227245293719719884966795520421
490 -1.32318255217215294246321770834140158821
491 -1.89209825574101619303826281378327574775
492 10.0800223766666350664761618478446376722
493 4.6988089097987388783105744570022283182
494 11.2138662853195467076227339420019580331
495 3.42853565938401421991780785546937555989
496 1.33064050965018259559514873371164383656
497 -13.0117749906655187906716356304958940263
498 -2.74894492283522837032465528617895181848
499 -1.06413393140852964142426583856616845708
500 -11.1187728908923629076013413164668196357
501 -3.51235049928308642052072596829003822537
502 -2.79103186925723127353159533057692302896
503 14.5532482902878814267737778957123883855
504 -9.2012347458206320292718459320384021048
505 2.80480918280965002700943216709662608757
506 4.1952599699306104573394689163547001236
507 -8.1262731538548841574488335306508235028
508 -1.80648697469440640060135791578303192335
509 6.8316883764124092235726526156934564358
510 -10.0000843970970847438493791747030168517
511 2.03265082702729602580565178608726454568
512 -6.8776603220257960521636413646533841238
513 -10.4367054872651975025074873016456586624
514 -4.4389546595823114354597287813042906508
515 6.6519945251938717173435371355605134513
516 9.1154556082565994114074392486983168988
517 -0.445208784697968794832392834054571664846
518 4.9706497355314746549587978024897822026
519 -1.64856896550739384219545434553484031408
520 9.6686219132313203626070064806311383614
521 6.4248801465771188138901759173168002969
522 8.1693962271961386417627616571737694716
523 4.2148517538542420249743537577876856371
524 14.9257326377780595261841671211313404481
525 -6.7399065023302789854774426094995716634
526 2.59534485360747397797181595041917064525
527 -2.20812124545886260275169021916353325543
528 10.2003700048648899748003916369881534258
529 3.76216604160811478524506337068457649625
530 14.3168759514560905025995036275333938581
531 10.1290990022161059740093549520346522994
532 -4.9988960106497879608234836982725853733
533 -12.1622261556359404391711620119171956130
534 -3.55895920977609685080935634474817749633
535 -11.6898230861291660770967555960349706621
536 -5.0944922060483530525211439556688611756
537 -1.66515021212086763556451433867770631731
538 -5.1551953550689280158814875506993300277
539 11.6759249777343936431111671961750748663
540 17.0453803337429381370160170913041105293
541 -5.5599406127090870342162590790868546540
542 -10.0329160846002155892742033898335743155
543 -3.76804149394077741118146352831503351635
544 -14.3269416005994068169555998684371296460
545 8.3201622764301418955668456038148446799
546 -5.2930216835248430430917919522680300718
547 -11.8243310788621748617645586749053253910
548 -3.85018471754524675588162804083178717896
549 -12.2556195319749170695466588326381148366
550 -3.03550011389703766582954088470615994988
551 2.55400811776724353081511721936392301858
552 11.9799606587056593001348229719901798766
553 16.4813865255171791808211419490101028505
554 -2.98225968169481677715811951261995067364
555 -10.2510306888167256095150090088496557815
556 16.2171464117957967526169913633042096645
557 -2.35163724021998238361324809510968304425
558 -3.33015498760414608107601611261820218515
559 11.5238305798613468231142068437968500761
560 0.237383315594651268589238753084536502160
561 4.6376648539995671867511044858106539962
562 13.1171599348180260707331394461351445181
563 0.50236237903330376399835207764393153225
564 2.51726207059739503542867569044848283469
565 -11.1532571806408171460254246573010685770
566 5.0881584592174667134481720585340810613
567 1.39949742222308654556869198238989312468
568 9.7883934910432417410471592431412482354
569 8.4306238500543370293322486394758002906
570 0.88088366709580042253291795556986180722
571 -0.64841809576799289546559485541563503175
572 11.8937057251388503622892155849282475670
573 3.45903078127580961705641717600047692791
574 9.3130514008676699283920397757699301749
575 12.7132296668283986409553440354085151847
576 -0.60206332548088091587285996427720301674
577 4.7254536459018522082648035111792265275
578 11.6014033410090294738848643348340897153
579 1.65559397165831034111499832684913979903
580 -3.60192444726829617112646353153427882370
581 13.1567158444639565108032429922347894535
582 1.71555932914602592520593468508638737174
583 -3.32970052743790224977127171042430570626
584 10.1272664844344635029942935008090379263
585 -4.0738081239849849247685569991626125467
586 1.25332894420100790353908888391490805719
587 -9.1587833709950721486255857681728816495
588 7.9810135137680327825445715610202483608
589 -4.9021943732383810704010286413616072953
590 -10.4981177754200608531741383604824318167
591 -3.90185896660882360161115041047207700476
592 -0.82671435631144140544180768954692893518
593 11.1912562222256438571567149941991648767
594 3.58328186962528994493310702703994920906
595 -1.65353705231751358795270109005861350795
596 7.8182332965237629255845360027995718776
597 -10.0178113365530061729557423368607564978
598 -0.55890634820632211723553227456554968622
599 -2.27445858946053699538573306097171954192
600 13.9825857807133023531037316993808203469
601 1.28292741415002088429158944862817156298
602 2.34221812867922897424972692912528249420
603 -5.5571939864071304466249038992712572934
604 7.2097679902076917915485958486049245580
605 0.310729295836628937092438355294252769718
606 -5.7733172079348851179837161937337653483
607 -9.0749753486830957461027695770179082411
608 -3.62363407398343925318798857747662002878
609 -13.3835791661059703139540471181398880468
610 5.7310851848762918110407478224431546909
611 0.088133236476397562674169009255496545958
612 -6.1167731033274669505960603575775769587
613 -8.5490828819976698552789109345068128496
614 -3.07561319802543004056063931346429890775
615 -7.0799044528184729203998044469668494531
616 6.0527333825980590391682734495905064839
617 -0.52904293812149869542123480456368643512
618 7.8304241429946496870859526243622148711
619 9.5241412112876395675937962573078567605
620 -6.1183079452170564194585637306294459824
621 6.9006216571144303311530770888414906061
622 7.8003166541472711592047171487967104885
623 1.09562493335582747673625927400794199733
624 -8.4977886348400780182891245404498769471
625 -15.3220947289020221942893048594101183946
626 1.30471078587304167318215302300824952495
627 -4.5733764246978818389446185790451446659
628 -0.300516676622846840346322602576089607781
629 10.6025973812727403101948909721750751583
630 5.6107583233087088323667971944982743060
631 11.0789440402880528192949380515451035408
632 5.5148052023679691814556130735772678793
633 10.1653753312784103062570858558183079717
634 3.97552347007960154651878761986384262659
635 14.5047055268754041600080400999325705042
636 8.8488895484994470887249624079708654730
637 -3.39175334420257848948103096841815084373
638 -10.9108986129008638535788942381110536601
639 4.7016750143928068475834714609829961093
640 14.5812578703697694417410549958797534935
641 -5.9460776113619248368382184608485200231
642 -10.2881081654704194258455394034380027344
643 -6.5381390474233178420515638101724440277
644 -8.0619439533540194269455248042795696871
645 -6.5030545162865546027073923998462983548
646 -8.5235409545164097369728609651278390159
647 -1.01094550196653965008204179472544590618
648 7.8215515869949493717561319865003591049
649 14.6016544317277807991725530013242991695
650 -0.73143216679139762874879412053772560616
651 3.44301892623364594686283152131130889730
652 12.5116992793825283107996666797329637837
653 3.13377029315324207797948647821412841435
654 10.7443835993277738491706052403007618793
655 16.1522119761302359723671586368618420061
656 -3.37368342705240663223792636560721136341
657 -11.3249313647895774654173344038352181169
658 -8.5178949270656835872029482126877219834
659 0.065987403737350929503980696657198715124
660 5.0632571825227662171538052696382546142
661 10.4798510775657498634170284319200319883
662 3.12907097151326612750548606532916376935
663 10.9139784506262799442918528160466934113
664 -7.5595537493353757466352900521135461090
665 -0.66240698531866774206669714619722521589
666 5.6006679217038935481749583638554780527
667 -6.8585299569950630135682909853685285802
668 5.1204788992015798189385363252746024377
669 7.1582009119762752606830810765640393052
670 10.4610326307197375531535329853297317491
671 -15.6069824548498137811924599025428457038
672 5.4683255567993014336858807717279335600
673 10.9522622046727276322375373885513076927
674 5.2026129339574135717640138619334799265
675 10.9814233070897602037569966098958341983
676 2.41385934121556209958041150736796998224
677 3.16964766235628002737351957237355377335
678 -10.2473534738989813703369645291634208155
679 -1.30726142490879852578618698833861564221
680 6.2028652685463537100810499809392950098
681 -13.5820400697446967569089666250320818417
682 2.99826065375748068231372442747809691869
683 3.33888643541688868752393121285252919691
684 -15.0006437008264355127974295274386748421
685 8.9411023769667337147445305803660405798
686 -3.85841391814737307142172923670469354633
687 -14.2240111712823208451282295849817664784
688 5.6622774217560703826121742717604170402
689 -0.79052357331300407077771719125354313282
690 8.8439808199080235978211349809598270935
691 7.1144962475135669240231510594748615010
692 1.46697373920082363403984017481078939694
693 -8.3692547790646640210124104238676359730
694 -6.1963279501694199138141773830790945127
695 0.50998015219411131535674084412981415594
696 -7.7092426144414390433063245131909847306
697 -9.6646215972103418951443099457865818080
698 8.4583411204137359609527465302673671719
699 -6.6525459777853041927353963803775922003
700 -7.9746698395534945016645917053618286411
701 -2.17138323006079050047204991646359660986
702 4.8658435742401166646945503206105370306
703 -8.4518179953180620206057982192623545086
704 -0.0218955802958966813706164618171491217935
705 -5.3728965543966848170773013112984067661
706 -10.0824469374112945544522705120931488804
707 -2.29103242396065063665402253006784806154
708 -0.425943791717419935207041751888786044522
709 11.1763153998373238157181612460362997822
710 4.6035059503676660661624330336712464163
711 12.6274244887851284977348877547543727827
712 2.95161841135071340722027363503320437131
713 7.8587368929730574465017256688391527170
714 -14.1354397631071516944885218718298184470
715 3.22259558679266000693739131366447307516
716 7.4156341854686499474562145531880740532
717 4.9575621184466875336475991408522745711
718 -6.0759596467795444156344156231840899389
719 -8.9066487459922244819447277402705154421
720 -5.1274358106126240003616812453401788422
721 -2.19312044044507410804439226590005229377
722 11.5114399575217307437358144377733121748
723 -8.3116298284380327914515426728889566934
724 0.077259338179300105061474738394171168539
725 4.9299558986297505842260826193333190994
726 10.6419572372386070871127987255745536321
727 3.55194482076323364450567838618933229589
728 13.7593641433627441217196281396940848035
729 -11.0226662784175455146647959057240521202
730 4.7641491461492276165978397294691555378
731 12.3257599302029507699296310078502934423
732 3.19583302087004273072432193305529504105
733 8.6928125682225047294732814631081573527
734 15.0627827532044248568069768708103479460
735 -3.13897057528932232503256155084300648021
736 -8.0715209277230516477796590705932748409
737 -5.8820606311886393337113334960826699144
738 5.6085882549573751867213618167704536952
739 9.4910525069180798343917869244727338081
740 4.6310409846601717548148783627640414870
741 1.89850837480164030674115653589667805158
742 -12.5605859945851637452800309206792074373
743 6.9863277003652309167604214967300886498
744 -5.4323051406363374523782192845127319324
745 -11.2940580172098675588449745597593677581
746 -3.79806808811653653984659303068708858831
747 -9.7163909379033277528282628791790901154
748 -7.6176956128224568384151290543362418588
749 -1.04753585204360996859848774199083459683
750 -5.4839568513074891565029924251963610055
751 15.8856601397134703707811816434035973805
752 -1.35133910432015408791195005652947900578
753 3.37633769204750395912173166270125577960
754 13.3964821065483468532667788070264015887
755 1.75478618937919150119959436884471069173
756 -3.18950215567097867892155185373877897896
757 7.7336935424752301367395231153317502914
758 -5.0886755238407121413644566119063440443
759 -0.71123302433621931367539376865236293056
760 9.7327773068881214876062327154210222078
761 4.9282219942668289943278992116237977317
762 -1.40783548486576505476015021280310778180
763 4.8507632675483221488853471311029823113
764 -11.1298436967401924532902854290426129354
765 -0.93070486122218652488951012941113047526
766 5.3037017243289458839934338750330340982
767 11.3788590486706607038511747580414297132
768 -3.45915484034319032925555627516524712467
769 -2.39605157364607850051742177260138728928
770 14.3574373019429907998684710457182077218
771 14.6741345293617394430374493978361087909
772 -4.5110229589363654796638816085266146562
773 -12.7718141348736084393821200912576373890
774 -2.72886049567670686004029546369886483053
775 -6.0754331257894188399354282161091145947
776 14.7141114105701352387219267776712713701
777 -0.54576138555037113510856125492091490201
778 -3.70190794978431863483040296163464088166
779 -13.1432406313851779692855109928133969714
780 3.63877438199410420106632336636168909812
781 2.12003735924323356361753500207248265059
782 10.3914935728729137111002773786220348069
783 16.0076689273035251998484372140689140452
784 -3.32039714552680956244239269843472755361
785 -10.8330906089720696357986775598642713519
786 -10.9217457299017154073913387528089073657
787 0.76127194030289357934727511168631131191
788 -6.3333143515458886266654198379205006119
789 -11.3129389482522162063682420371268462570
790 -3.93696564233930805083249740546165397462
791 6.2136646812271772528520496664149006094
792 11.0916641286023460036103795997205590071
793 0.391573453996868536944367194818571666544
794 -4.4529705639642122193396006451499137865
795 9.6008967105419402546795307401441407558
796 -4.0297568473473015472507931206206727099
797 -2.61313900024474607675349914317261940657
798 13.6423838175999604217378749512778635298
799 -6.8156523030666281202419837873400828460
800 0.88258757488453133082684549597345300722
801 -8.5115227368504432225343214367896284095
802 -9.3597879824297881479564697379220164329
803 -0.407285229219436291285760812556164307944
804 -5.4521360451776260054378066836000227923
805 9.4711470965324512532788834058994838327
806 -4.1189850173015016431521166728661917803
807 -5.4971301433615857663937969451425305861
808 -9.7239057261205581941328146621656163486
809 4.0206163500944738936406070758501229269
810 4.8483846103498790027962771064726158209
811 -1.43597724154271190770469378981304713402
812 10.0506188993481436941969542667591088305
813 6.2417449412389559282450570403697947274
814 8.5111322830433385268853687789790455102
815 4.4154847689042114781896018685104845379
816 14.7691352114156195819880920313878918544
817 2.23451033616393676606361321453419581325
818 -7.9901914321884520009959969588407279405
819 -9.3380878618176625702597277284612069358
820 -5.6021446827423254695862006336225548839
821 -11.5689657696386894425744730079753099429
822 -4.1887828320580849989494506892709520082
823 -12.7721409405375716154032254339363996711
824 -2.45268086927433340745252460598712252880
825 0.65269282972102608424143737336220904732
826 -11.4020848199215008300283413375329962181
827 -3.34045091673078512823901575371729368886
828 -2.59639311830620851953640867183254662223
829 14.5781661363080727245165491387760727192
830 -7.3924572297940914374322601496006934382
831 5.5293942569402371646841453769542379863
832 11.6219392088029421479164904155520331445
833 4.1045250904740488522839696750286155022
834 12.6911185870052442670220613403341434882
835 2.48101918800403560055025138185099580460
836 -1.60579124204669865320686915940170321663
837 12.9359341534172412907485417533318739540
838 9.0553337115939230317603388364444845921
839 -1.55786659119420799642854998502450169684
840 6.9437986710073858119666283464551144114
841 -13.9772542344513113757367874038555287645
842 0.383099910087822721576482314925624112558
843 4.2532841331745656119318488870131063711
844 14.4930736154052121550002924575925198624
845 7.9206359947744240444577583746955459536
846 -4.0576248034183466181691025648985977621
847 -14.6469492819117914666870133258206409565
848 4.9722593158825097620084498778516535453
849 -0.89735047378762518522684482447942830389
850 9.5225949333749564353073889955626423701
851 7.0372101242450584938869402685995221135
852 -0.68086718306009245209872007745043362616
853 8.4935104930147765860246871926403643532
854 6.5714985815063694873476970282015660030
855 -1.26255444483422066723275531934172340276
856 0.59547643303818028796473393886075791730
857 -11.7857501884293701658457899906544402993
858 -3.80188242929944365636803840379418393193
859 -11.9063845462548795263140825176847498250
860 -3.52229779449338036540819035275598932747
861 1.70749085147299481716300349360868894315
862 11.4122336315805081811450570491967102665
863 3.47585872663625477680824508220547250923
864 -1.95667261892455393164706215300772974147
865 3.49744144570826714612267760696125609296
866 -9.5866040174996190047314521367776189938
867 -1.32512693297537729668409610731392364121
868 6.7389672360122141826889272760127307333
869 -14.1445676130912592412013571119353747125
870 2.95494701383541175825424384311806785647
871 4.1846988525266976675579273924433843090
872 -15.3858669469318507728715510318726090152
873 1.80960511892181128450224981036492891949
874 0.91059723094793000004147958053936411422
875 -10.8764469860005670209758408157634546570
876 -5.1624857864977408315313014909797941395
877 0.239838390750923116277356283348264896765
878 -9.5140848286966951955996869029644926606
879 -4.7880347679671713643201071960280943171
880 0.092274092991121874238419340255141533723
881 -6.2907450706447353549986270772743827076
882 -8.0856683463086059489344328854282660526
883 -5.2983267507571135331475529094309644735
884 -12.4980980050275219846749240429393503328
885 -0.360975983495790547696631666874826515025
886 0.476590636592787607277277255339752468569
887 -10.2853841818218264754146663540363021854
888 -4.0911405462239070775382706665995689394
889 -5.8557182850629013599952672057608598091
890 -13.1518641466092368020500534271034806224
891 2.98627828754302496568995357112162090074
892 1.80059586023466748846852290355645979911
893 -13.9129182542889004743176633100236537795
894 -2.09608588957332445028746054503038034061
895 -2.39167065944552582494764314281343549612
896 -3.98251847825324239279829925014043930660
897 8.7085750570392399272769268083795399518
898 1.38007964088576453236837958661532231553
899 -7.4805217616239752495012812482495390593
900 15.4502766014799645213782156665492677498
901 -2.71641028828345054045021308532275257987
902 -4.0394710641360633341307219339589374055
903 14.4898705680235156337081024405394478854
904 -7.2320133974919151412757710630155867322
905 4.6005143236044416390401191604966428353
906 14.8367837858385733748739183945449214744
907 -15.8697801121044591300822534350423860830
908 4.5752936822165594096088166700219615540
909 12.8604263146558711824635141040942060070
910 1.09400761818161145267655664656155122049
911 -4.6140980201383747157442350682982889598
912 -15.0027916836356203747662038629682591699
913 6.8372520534032773875492883143436147757
914 -3.70603612756262969162763061525863631283
915 -11.8934819463920328808770627455856877107
916 3.80799449363753058356965478156705676991
917 -0.82636255060593537267156755532017926970
918 -10.6585975681745817870264003948746954173
919 -3.80214534709492491444545004713893729466
920 -0.405646531887483071864204724116305636158
921 8.9511725745332638375347824989379803393
922 5.0037438212178759593371972474836422377
923 4.2375737287868235095757552308612032806
924 4.3893236200598517150514557939412525618
925 -6.7726367819027995725884197811316300076
926 -5.5313445483895443338992397020856620381
927 -13.2788063168272504179263490365206899717
928 -16.7961378609370660782119195841802816332
929 5.2286540540353435176756549702308285927
930 10.8914032313034264025370374016634777730
931 2.69845066612951850671769112660147356708
932 6.5962933566380368033508134229270432934
933 -7.9870396889119030453265561284135530780
934 0.96610717159193524198111066211613330177
935 5.2676682643847414995789698412475434608
936 -15.8274545473260121949870487812665384779
937 1.33993196085705930129479732799736605972
938 -1.37136457863689030132169636021679695694
939 -11.5325177390223786380199818761183530700
940 -3.75624555966752493850258479373965450921
941 -10.5121331267438774864906708070686591120
942 -5.9295194817210597489890126340819935868
943 -1.02298040550408447158034538992340869803
944 -9.1291894937184027916982245886295472080
945 -9.2118816072020759421219466164158296841
946 -0.76800907059991769983917237636621973931
947 -0.99929010937747915747100640699623230503
948 12.7547686067287584870946688898739331766
949 2.64519112558713345125883823464658705265
950 3.49118524325177420090424764253732090001
951 -14.0945873709729828712740141466169731502
952 -10.4617012883672102615509276977510503041
953 4.8855229907351850031052118664570564798
954 12.9811964356650400629805689604564424494
955 0.435285568180140806902163569396512679971
956 2.35670468452678538141400958366762332996
957 -12.4916584990103690242278338257772375897
958 6.9703873700727309799280101182400300518
959 -0.0045556759140565319182975718971194195754
960 -5.4000540548937291075902242496974732319
961 -9.7692777525528944760070447399094534645
962 -3.55314701482722253988323619812811790519
963 -13.4754706374725094909255444976769380095
964 8.9915308680092000013890044785027424084
965 -1.72943224208300392659238878603630066771
966 6.3007145319579834905051818660404523071
967 -10.8959880689906326276162879708478723265
968 2.44135504064399431177725918852255482535
969 -6.4070060149674293230338560018334743843
970 -11.9297963987027901207005439773771932685
971 17.2986122256606558665837777025346416304
972 -5.3311923954805232636040180171777434982
973 -10.9316175123749120158329083863031737121
974 -4.5771680482155844072828008468534811051
975 -12.9275410108388706317007101116648141694
976 -0.96783264611411512549155924867572017674
977 4.3219458773082799848807045642093548606
978 13.3787759161748773596980879925674736147
979 0.69569983503832286692849849293300802503
980 3.55276939461921335054647775330810920085
981 13.0080208275885835527343458944614031771
982 -4.1665351625696300543655503203658283551
983 -1.81573048104354973155613289859932023493
984 -3.63796015435851534783716081460373031416
985 10.6192191573621058408243401730728737126
986 0.252797118535904115296470232649700973788
987 4.3683389966436506364326300153165995628
988 11.8366349901071336885801437002137603189
989 2.69001376346150117661049801228690714428
990 7.2489877589912760320119612981894002106
991 -9.5494304355530903973175950707449545478
992 0.87508146774275456521195805166794266666
993 -6.9274479996997769735736466652754668376
994 -12.5913605070333097614038992658570049902
995 0.412590970186684684479867468487476221456
996 -2.58183090854335322495331977740972051770
997 14.5405595988585082118531760034586755436
998 -13.0652499170432781686080075036227861938
999 4.6993694822379784872482517857938728425
1000 12.5372295844221074221658968648287647438
====================================================
~= 12+ decimals agreement with Kehlet and Logg:

950 3.491185243251774 (15)
1000 12.537229584422063 (12)

Written by meditationatae

August 3, 2017 at 11:19 pm

Posted in History

Graph coloring program report 1 vertex conflict

Previously, I thought there could be zero conflicts, two or more conflicts, but not exactly one vertex conflict; I’m not sure what’s going on.

For 500-vertex graph DSJC500.5.col , program reports 1 vertex conflict (??):

 

Added July 31: It’s one edge conflict, or two vertices connected by an edge, and who share the same color.

I’m testing a new version of my  program now.

=====

Added August 4:

Producing a valid 48-coloring of the 500-vertex graph DSJC500.5.col  is much easier than producing a valid 47-coloring.

For 47-colorings, I’ve managed to produce improper 47-colorings with just two problem vertices, i.e. two vertices connected by an edge and that share the same color.

Getting it down from two vertices with conflicts to zero has proved elusive, and seems quite a bit harder.

=====

 

 

54 87 62 23
num_generation = 1069
num_conflicts = 1

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

Written by meditationatae

July 30, 2017 at 2:48 pm

Posted in History

Moalic and Gondran Heuristic rope team : a parallel algorithm for graph coloring (for DSJC500.5 graph)

I’ve got C code that seems to work quite well for their new algorithm, comparatively speaking, meaning compared to what I had before. I’m regularly getting improper 47-colorings of DSJC500.5 with just two conflicting vertices, which means precisely one edge with a conflict. It’s as close as it gets without having no conflicts, unless I’m mistaken. But Gondran/Moalic, for teams of climbers, had a succes rate of 7 times in 10.000 teams. I’d expect to have to try 1000 teams, which could take perhaps 10 days. Anyway, it is what is is.

from directory:

/home/david/graphs/TABU_H_homebrew/CHECK/KEEP6/JULY24/POST_JULY_29

file named:

the_powzoomuzzjo97a.c

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

Based on the algorithm “Heuristic rope team”

of Laurent Moalic and Alexandre Gondran,

Proceedings of GECCO 2017 in Berlin.

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

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

#define MAX_VERTEX 600
#define MAX_COLORS 60

unsigned char adj_mat[MAX_VERTEX][MAX_VERTEX];

int Gamma[MAX_VERTEX][MAX_COLORS];

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

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

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

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

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

 

one = (unsigned char) 1;

zero = (unsigned char) 0;

 

select = 2;

 

is_round_one = 1;

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

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

 

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

 

seed = 18374146278035435545ULL;
seed = 18017113809711968460ULL;
seed = 15087295764204510305ULL;
seed = 8393253763552363970ULL;
seed = 13212404616562293088ULL;
seed = 12562118502008912440ULL;
seed = 17524873809730415988ULL;

 

 

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

 

720772264
478636068
845660406
202090843
925136236
130618921
153748842
638787314
821188033
461020874
907259338
829906907
564747973
194044730
172205770
285938306
562679646
247467988
920729955
454915297
234284638
977396665
238049968
110397175
477497259
688921537
634478212
173573369
638627017
284989426
845795507
883103385
584828833
745406241
412338480
176697335
780145554
289855037
721359412
567318570
257340590
287888101
823343102
938235393
446443300
561106469
252417334
268543602
958868042
300913759
277994571
214143933
83873157
539252373
76719160
58971518
666550009
370241607
614073362
337494019
899061844
806541210
179640567
848579625
121565510
172926945
763779052
139784718
732857271
645346002
823049404
957688945
111813839
686016633
17282484
957873472
590042577
528748941
39116597
339712862
523311736
315024009
78289156
931947692
715275499
92213457
533613737
215147465
805945112
209899310
236348243
659427049
633494249
286938486
630091568
2275155
613503457
728376602
211319789

 

 

 

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

 

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< 89 ; 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)/89;
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&mask);
j1 = ru/b_sol;

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

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

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

 

 

 

 

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

 

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

 

 

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

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

printf(“continuer?\n”);
// scanf(“%d”, &reponse);

if( (num_generation == 100)&&( clg < 7) || (num_generation > 150) )
{
reponse = 1;
}
else
{
reponse = 0;
}

 

 

if(reponse == 0)
{
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;

 

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

 

 

index_maxcolor = 0;

 

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

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

 

}

 

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

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

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

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

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

 

 

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

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

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

 

maxcount = 0;

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

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

 

 

total_maxcount = 0;

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

 

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

 

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

 

index_maxcolor = 0;

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

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

}

 

 

 

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

 

 

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

 

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

 

 

 

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

 

 

 

 

 

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

 

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

 

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

 

/*** child2 below … ***/

 

 

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

 

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

 

 

 

 

 

 

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

 

 

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

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

 

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

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

 

maxcount = 0;

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

 

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

 

 

total_maxcount = 0;

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

 

 

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

 

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

 

 

index_maxcolor = 0;

 

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

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

 

}

 

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

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

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

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

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

 

 

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

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

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

 

maxcount = 0;

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

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

 

 

total_maxcount = 0;

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

 

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

 

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

 

index_maxcolor = 0;

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

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

}

 

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

 

 

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

 

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

 

 

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

 

 

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

 

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

 

 

 

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

 

 

/*** child 3 ***/

 

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

 

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

 

 

 

 

 

 

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

 

 

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

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

 

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

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

 

maxcount = 0;

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

 

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

 

 

total_maxcount = 0;

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

 

 

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

 

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

 

 

index_maxcolor = 0;

 

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

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

 

}

 

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

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

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

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

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

 

 

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

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

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

 

maxcount = 0;

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

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

 

 

total_maxcount = 0;

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

 

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

 

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

 

index_maxcolor = 0;

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

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

}

 

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

 

 

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

 

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

 

 

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

 

 

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

 

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

 

 

 

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

/*** child 3 done ***/

 

 

/*** child 4 ***/

 

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

 

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

 

 

 

 

 

 

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

 

 

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

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

 

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

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

 

maxcount = 0;

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

 

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

 

 

total_maxcount = 0;

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

 

 

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

 

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

 

 

index_maxcolor = 0;

 

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

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

 

}

 

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

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

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

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

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

 

 

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

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

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

 

maxcount = 0;

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

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

 

 

total_maxcount = 0;

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

 

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

 

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

 

index_maxcolor = 0;

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

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

}

 

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

 

 

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

 

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

 

 

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

 

 

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

 

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

 

 

 

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

/*** child 4 done ***/

 

 

 

 

num_colors = 47;

max_iter = 128000 ;

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

 

 

 

if( min_conflicts >= 20)
{
iter_Tcol = 8000;
}

 

if ( (min_conflicts < 20) && ( min_conflicts >= 10) )
{
iter_Tcol = 8000;
}

 

if( ( min_conflicts < 10) && ( min_conflicts >= 8) )
{
iter_Tcol = 8000;
}

if( ( min_conflicts < 8) && ( min_conflicts >= 6) )
{
iter_Tcol = 16000;
}

if( (min_conflicts <6) && (min_conflicts >=4) )
{
iter_Tcol = 64000;
}

if( min_conflicts == 3)
{
iter_Tcol = 1000000;
}

if( min_conflicts == 2)
{
iter_Tcol = 1000000;
}

 

 

 

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

 

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

num_conflicts = num_conflicts/2;
}

 

if( num_conflicts < min_conflicts )
{

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

 

min_conflicts = num_conflicts;

 

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

 

 

if(num_conflicts <= 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”);

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

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

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

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));
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
tabu_rand = ru/b_tabu_rnd;
tl = tl + tabu_rand;

 

 

 

color_tabu = init_coloring[best_vertex];

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

init_coloring[best_vertex] = best_color;

 

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

 

 

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

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

 

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

 

 

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

 

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

 

if( problem_solved == 0 )
{

num_colors = 47;

max_iter = 128000 ;

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

 

 

 

 

if( clg >= 20)
{
iter_Tcol = 2000;
}

 

if ( (clg < 20) && ( clg >= 10) )
{
iter_Tcol = 4000;
}

 

if( ( clg < 10) && ( clg >= 5) )
{
iter_Tcol = 4000;
}

if( clg == 4)
{
iter_Tcol = 16000;
}

if( clg == 3)
{
iter_Tcol = 32000;
}

if( clg == 2)
{
iter_Tcol = 64000;
}

 

 

 

 

 

 

 

if( clg >= 20)
{
iter_Tcol = 2000;
}

 

if ( (clg < 20) && ( clg >= 10) )
{
iter_Tcol = 4000;
}

 

if( ( clg < 10) && ( clg >= 8) )
{
iter_Tcol = 8000;
}

if( ( clg < 8) && ( clg >= 6) )
{
iter_Tcol = 16000;
}

 

 

if( (clg<6) && (clg >=4) )
{
iter_Tcol = 32000;
}

if( clg == 3)
{
iter_Tcol = 64000;
}

if( clg == 2)
{
iter_Tcol = 128000;
}

 

 

 

if( clg >= 20)
{
iter_Tcol = 8000;
}

 

if ( (clg < 20) && ( clg >= 10) )
{
iter_Tcol = 8000;
}

 

if( ( clg < 10) && ( clg >= 8) )
{
iter_Tcol = 8000;
}

if( ( clg < 8) && ( clg >= 6) )
{
iter_Tcol = 16000;
}

 

 

if( (clg<6) && (clg >=4) )
{
iter_Tcol = 32000;
}

if( clg == 3)
{
iter_Tcol = 64000;
}

if( clg == 2)
{
iter_Tcol = 128000;
}

 

 

 

 

if( min_conflicts >= 20)
{
iter_Tcol = 8000;
}

 

if ( (min_conflicts < 20) && ( min_conflicts >= 10) )
{
iter_Tcol = 8000;
}

 

if( ( min_conflicts < 10) && ( min_conflicts >= 8) )
{
iter_Tcol = 8000;
}

if( ( min_conflicts < 8) && ( min_conflicts >= 6) )
{
iter_Tcol = 16000;
}

if( (min_conflicts <6) && (min_conflicts >=4) )
{
iter_Tcol = 64000;
}

if( min_conflicts == 3)
{
iter_Tcol = 1000000;
}

if( min_conflicts == 2)
{
iter_Tcol = 1000000;
}

 

 

 

 

 

 

 

 

 

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

 

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

num_conflicts = num_conflicts/2;
}

 

 

if( num_conflicts < min_conflicts )
{

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

 

min_conflicts = num_conflicts;

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

 

 

if(num_conflicts <= 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”);

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

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

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

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&mask);
can_number = ru/b_candidate;

candidate_count = 0;

 

 

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

 

 

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

}
}

 

 

num_conflicts+= best_delta;

cnodes = 0;

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

 

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

 

 

color_tabu = init_coloring[best_vertex];

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

init_coloring[best_vertex] = best_color;

 

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

 

 

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

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

 

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

 

 

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

 

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

 

if( problem_solved == 0)
{

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

num_colors = 47;

max_iter = 128000 ;

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

 

 

 

if( clg >= 20)
{
iter_Tcol = 2000;
}

 

if ( (clg < 20) && ( clg >= 10) )
{
iter_Tcol = 4000;
}

 

if( ( clg < 10) && ( clg >= 5) )
{
iter_Tcol = 4000;
}

if( clg == 4)
{
iter_Tcol = 16000;
}

if( clg == 3)
{
iter_Tcol = 64000;
}

if( clg == 2)
{
iter_Tcol = 64000;
}

 

 

 

 

if( clg >= 20)
{
iter_Tcol = 2000;
}

 

if ( (clg < 20) && ( clg >= 10) )
{
iter_Tcol = 4000;
}

 

if( ( clg < 10) && ( clg >= 8) )
{
iter_Tcol = 8000;
}

if( ( clg < 8) && ( clg >= 6) )
{
iter_Tcol = 16000;
}

 

 

if( (clg<6) && (clg >=4) )
{
iter_Tcol = 32000;
}

if( clg == 3)
{
iter_Tcol = 64000;
}

if( clg == 2)
{
iter_Tcol = 128000;
}

 

 

 

 

if( clg >= 20)
{
iter_Tcol = 8000;
}

 

if ( (clg < 20) && ( clg >= 10) )
{
iter_Tcol = 8000;
}

 

if( ( clg < 10) && ( clg >= 8) )
{
iter_Tcol = 8000;
}

if( ( clg < 8) && ( clg >= 6) )
{
iter_Tcol = 16000;
}

 

 

if( (clg<6) && (clg >=4) )
{
iter_Tcol = 32000;
}

if( clg == 3)
{
iter_Tcol = 64000;
}

if( clg == 2)
{
iter_Tcol = 128000;
}

 

 

 

 

 

 

 

if( min_conflicts >= 20)
{
iter_Tcol = 8000;
}

 

if ( (min_conflicts < 20) && ( min_conflicts >= 10) )
{
iter_Tcol = 8000;
}

 

if( ( min_conflicts < 10) && ( min_conflicts >= 8) )
{
iter_Tcol = 8000;
}

if( ( min_conflicts < 8) && ( min_conflicts >= 6) )
{
iter_Tcol = 16000;
}

if( (min_conflicts <6) && (min_conflicts >=4) )
{
iter_Tcol = 64000;
}

if( min_conflicts == 3)
{
iter_Tcol = 1000000;
}

if( min_conflicts == 2)
{
iter_Tcol = 1000000;
}

 

 

 

 

 

 

 

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

 

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

num_conflicts = num_conflicts/2;
}

 

 

if( num_conflicts < min_conflicts )
{

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

 

min_conflicts = num_conflicts;

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

 

 

if(num_conflicts <= 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”);

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

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

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

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&mask);
can_number = ru/b_candidate;

candidate_count = 0;

 

 

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

 

 

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

}
}

 

 

num_conflicts+= best_delta;

cnodes = 0;

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

 

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

 

 

color_tabu = init_coloring[best_vertex];

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

init_coloring[best_vertex] = best_color;

 

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

 

 

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

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

 

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

 

 

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

 

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

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

 

 

 

 

if( problem_solved == 0 )
{

 

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

num_colors = 47;

max_iter = 128000 ;

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

 

 

if( clg >= 20)
{
iter_Tcol = 2000;
}

 

if ( (clg < 20) && ( clg >= 10) )
{
iter_Tcol = 4000;
}

 

if( ( clg < 10) && ( clg >= 5) )
{
iter_Tcol = 4000;
}

if( clg == 4)
{
iter_Tcol = 16000;
}

if( clg == 3)
{
iter_Tcol = 32000;
}

if( clg == 2)
{
iter_Tcol = 64000;
}

 

 

 

 

if( clg >= 20)
{
iter_Tcol = 4000;
}

 

if ( (clg < 20) && ( clg >= 10) )
{
iter_Tcol = 8000;
}

 

if( ( clg < 10) && ( clg >= 8) )
{
iter_Tcol = 8000;
}

if( ( clg < 8) && ( clg >= 6) )
{
iter_Tcol = 32000;
}

 

 

if( (clg<6) && (clg >=4) )
{
iter_Tcol = 32000;
}

if( clg == 3)
{
iter_Tcol = 64000;
}

if( clg == 2)
{
iter_Tcol = 128000;
}

 

 

 

 

 

 

 

 

 

if( clg >= 20)
{
iter_Tcol = 8000;
}

 

if ( (clg < 20) && ( clg >= 10) )
{
iter_Tcol = 8000;
}

 

if( ( clg < 10) && ( clg >= 8) )
{
iter_Tcol = 8000;
}

if( ( clg < 8) && ( clg >= 6) )
{
iter_Tcol = 16000;
}

 

 

if( (clg<6) && (clg >=4) )
{
iter_Tcol = 32000;
}

if( clg == 3)
{
iter_Tcol = 64000;
}

if( clg == 2)
{
iter_Tcol = 128000;
}

 

 

 

 

 

if( min_conflicts >= 20)
{
iter_Tcol = 8000;
}

 

if ( (min_conflicts < 20) && ( min_conflicts >= 10) )
{
iter_Tcol = 8000;
}

 

if( ( min_conflicts < 10) && ( min_conflicts >= 8) )
{
iter_Tcol = 8000;
}

if( ( min_conflicts < 8) && ( min_conflicts >= 6) )
{
iter_Tcol = 16000;
}

if( (min_conflicts <6) && (min_conflicts >=4) )
{
iter_Tcol = 64000;
}

if( min_conflicts == 3)
{
iter_Tcol = 1000000;
}

if( min_conflicts == 2)
{
iter_Tcol = 1000000;
}

 

 

 

 

 

 

 

 

 

 

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

 

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

num_conflicts = num_conflicts/2;
}

 

 

if( num_conflicts < min_conflicts )
{

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

 

min_conflicts = num_conflicts;

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

 

 

if(num_conflicts <= 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”);

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

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

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

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&mask);
can_number = ru/b_candidate;

candidate_count = 0;

 

 

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

 

 

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

}
}

 

 

num_conflicts = num_conflicts + best_delta;

cnodes = 0;

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

 

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

 

 

color_tabu = init_coloring[best_vertex];

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

init_coloring[best_vertex] = best_color;

 

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

 

 

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

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

 

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

 

 

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

 

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

 

 

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

if( problem_solved == 0 )
{

 

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

 

 

 

 

 

 

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

end loop …

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

 

 

 

 

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

if( problem_solved == 0 )
{

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

 

 

 

 

 

 

 

 

 

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

 

int fall_archives_size[47];

 

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

 

 

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

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

 

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

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

 

 

 

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

 

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

 

 

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

 

 

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

 

 

diff = 0;

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

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

 

if( diff == 0 )
{

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

 

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

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

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

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

tmatch = 0;

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

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

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

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

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

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

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

arkdup = 0;

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

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

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

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

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

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

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

tmatchark = 0;

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

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

 

 

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

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

 

 

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

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

 

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

 

 

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

 

 

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

 

 

diff = 0;

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

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

 

if( diff == 0 )
{

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

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

 

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

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

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

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

tmatch = 0;

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

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

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

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

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

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

arkdup = 0;

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

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

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

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

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

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

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

tmatchark = 0;

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

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

 

 

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

if(tmatch == 47)
{

 

 

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

 

 

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

 

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

 

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

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

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

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

tmatch = 0;

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

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

 

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

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

}

 

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

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

 

/**** insert ***/

arkdup = 0;

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

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

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

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

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

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

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

tmatchark = 0;

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

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

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

 

 

 

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

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

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

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

 

printf(“\n”);

if( problem_solved == 1)
{
break;
}

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

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

end of loop …

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

 

 

}

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

 

 

}

 

fclose(out);

 
return 0;

}

Written by meditationatae

July 29, 2017 at 6:58 am

Posted in History