meditationatae

Just another WordPress.com site

Unit distance graph searcher for 14 vertices in C

I wrote a modified searcher for 14-vertex, non 3-colorable, unit distance graphs, embeddable in the plane R^2 with edges of length 1 between vertices, at least numerically.

The searcher has a randomozing seed constant for the PRNG (pseudo-random number generator): it is the unisgned long long constant:

14502779422240352273ULL

present in the array initiaizer code:

for(i=0;i<2097152;i++)
{
Q[i]=CNG+XS;
Q[i] = Q[i]&14502779422240352273ULL;

// seed above = 14502779422240352273ULL
}

Any value from 0 to 2^64 – 1 will work, if as with my system a 64-bit compilation is done by default. For 32-bits by default, something must be told to the compiler, or maybe the source code modified.

The stages of the search will probably be described in another post.

So far, the new searcher has found some (probable) 14-vertex UDGs, with at least 25 edges, and which are not 3-colorable:

 

$ cat udgraph14_solver019a.txt | grep count_4_colorings | sort
count_4_colorings = 2143 num_4_colorings_mod_24 = 0
count_4_colorings = 2496 num_4_colorings_mod_24 = 0
count_4_colorings = 3130 num_4_colorings_mod_24 = 0
count_4_colorings = 3644 num_4_colorings_mod_24 = 0
count_4_colorings = 3908 num_4_colorings_mod_24 = 0
count_4_colorings = 4419 num_4_colorings_mod_24 = 0
count_4_colorings = 4446 num_4_colorings_mod_24 = 0
count_4_colorings = 896 num_4_colorings_mod_24 = 0

The smallest number of four-colorings found for one of these is 896 (where colour permutations count as the same 4-colouring). This compares to 811 (a prime) distinct 4-colourings in the 24-hour run of the searcher with another seed value.

[david@localhost golomb19]$ cat udgraph14_solver019a.c

(C cource code follows).
#include <stdio.h>
#include <math.h>
#define NUMSTEPS 2500
#define MAXDIFFAT100 ((long double) 18)/((long double) 1)
#define MAXDIFFAT50 ((long double) 18)/((long double) 1)
#define MAXDIFFAT25 ((long double) 40)/((long double) 1)
#define MAXDIFFAT1 ((long double) 40)/((long double) 1)
#define MAXDIFFAT200 ((long double) 96)/((long double) 10)
#define MAXDIFFAT400 ((long double) 67)/((long double) 1000)
#define MAXDIFFAT800 ((long double) 79)/((long double) 100000000)
#define MAXDIFFAT1200 ((long double) 84)/((long double)1000000000000)
#define VERBOSE
#define VERTEX 14

/**********************************************
rec_diff1 = 28.852841 40.0
rec_diff25 = 39.668785 40.0
rec_diff50 = 17.967935 18.0
rec_diff100 = 17.856958 18.0
rec_diff200 = 9.573263 9.6
rec_diff400 = 0.066982 6.7e-2
rec_diff800 = 0.0000007832212564 7.9e-7
rec_diff1200 = 0.0000000000839841 8.4e-11
************************************************/

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

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

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

10-point non-singular solutions to the unit
graph problem are found numerically at a rate of
57.9 solutions per second on a dual core Athlon
5000+ processor.

The solutions are expected to be isometric as a
10-point metric space to the soltion depicted in
the graph in my blog post :

Sketch of 10-vertex unit distance graph, 2013
at URL =

meditationatae.wordpress.com/2017/02/06/sketch-of-10-vertex-unit-distance-graph-2013
The sci dot math posts:

mathforum.org/kb/message.jspa?messageID=10081388

and earlier:

mathforum.org/kb/message.jspa?messageID=10074716

This solver for a particular graph has been optimized
to run in as little time as possible for the given graph,
decribed by the 10×10 adjacency matrix.

To compile, I type:

$ gcc -lm -O3 -o udgraph_solver201a.out udgraph_solver201a.c

at the shell command line in Linux.

The executable is then udgraph_solver201a.out .
In C pre-processor terms, if VERBOSE is defined by
a pre-processor directive,
Number-Sign define VERBOSE
say on line 7 above after the other
Number-sign defines,
then the solution count and the 10×10 matrix of vertex to vertex
distances for a solution will be printed.

As above VERBOSE is not defined, the program will run with
minimal output until it finishes after about 9 minutes
with my system.

This README is based on file
Slash home slash david slash graphs slash golomb6
slash udgraph_solver201a dot c,

will serve to write the local file:

Slash home slash david slash graphs slash golomb6
slash udgraph_solver301a dot c ,

and will go by the Moniker or alias
“unit distance graph solver draft 101”

a hexadecimal dump will be posted to my blog

meditationatae.wordpress.com
David Bernier

********************* README END *************************/

int main(void)
{
unsigned long long i,cng=123456789987654321LL, xs=362436069362436069LL;
unsigned long long randx;
unsigned long long mask = 2147483647LL;
int B;
int j;
int k;
int quit;
int is_singular;
int graph_found;
int total_edges;
int degree_test_passed;
int l, m;
int n, p;
int has_k4;
int is_3colorable;
int count;
int total_finds;
int probable_unit_lengths;
int solution_found;
int coloring_found;
char alphabet[VERTEX];
unsigned long long maxi_ull;
long double xcoord[VERTEX];
long double diff;
long double diff25;
long double diff50;
long double diff100;
long double diff200;
long double diff400;
long double diff800;
long double diff1200;
long double diff1;
long double rec_diff25;
long double rec_diff50;
long double rec_diff100;
long double rec_diff200;
long double rec_diff400;
long double rec_diff800;
long double rec_diff1200;
long double rec_diff1;
int ru1;
int ru2;
long double epsilon;
int co1;
int co2;
int colors[VERTEX];
int num_4_colorings;
int num_4_colorings_mod_24;
int count_4_colorings;
int n_colors;
int degrees[VERTEX];
int v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13;
int has_failed;
int numedges;
long double diff_record;
long double maxdiffat400;
long double one;
long double ycoord[VERTEX];
long double forces[VERTEX][2];
long double C;
long double vector[2];
long double xgood[VERTEX];
long double ygood[VERTEX];
int four_colouring_failed;
int has_converged_flag;
int has_converged_step;
int max_has_converged_step;
long double scaling;
long double dmatrix[VERTEX][VERTEX];
int adjmat[VERTEX][VERTEX];
int post_adjmat[VERTEX][VERTEX];
/************************************************************************

udgraph_solver3401a.c : user 22m50.198s w/
MAXDIFFAT100 ((long double) 38)/((long double) 1)

newtestz746a.out 345 : 8m 34.631s for 30k solns. , using -O3
newtestz745a.out 340 : 8m 35s for 30000 solutions, with -O3
newtestz585a.c: 8m 51s for 30000 solutions, using -O3 optimization
newtest83a.c: 9m 57s for 30000 solutions, using -O3 optimization option
newtest81a.c: 9m 57s for 30000 solutions, using -O3 optimization option
newtest73a.c: 8m 49s for 30000 solutions, using -O3 optimization option
newtest66a.c: 10m 25s for 30000 solutions, using -O3 optimization option
newtest65a.c: 11m 30s for 30000 solutions
newtest64a.c: 11m 30s for 30000 solutions
newtest63a.c: 11m 33s for 30000 solutions
newtest62a.c: 11m 33s for 30000 solutions
newtest61a.c: 3m 51s for 10000 solutions
newtest57a.c: 6m 27s for 10000 solutions
newtest56a.c: 6m 37s for 10000 solutions
newtest55a.c: 6m 43s for 10000 solutions
newtest54a.c: 6m 48s for 10000 solutions
newtest53a.c: 6m 46s for 10000 solutions
newtest48a.c: 62 seconds for 1600 solutions
newtest47a.c: 14 seconds for 400 solutions
newtest46a.c: 66 seconds for 400 solutions
newtest39a.c: 67 seconds for 400 solutions
newtest37a.c: 70 seconds for 400 solutions
newtest35a.c: 79 seconds for 400 solutions
newtest34a.c: 72 seconds for 400 solutions
newtest33a.c: 91 seconds for 400 solutions
newtest30a.c: 16 seconds for 100 solutions
newtest29a.c: 18 seconds for 100 solutions
newtest28a.c: 25 seconds for 100 solutions
newtest27a.c: 50 seconds for 100 solutions
newtest26a.c: 99 seconds for 100 solutions
newtest25a.c: 3000 solutions per hour
for 100 solutions, 2 minutes …
808 solutions per minute for 4-point diamond shape.
gtest230a.c :
2600 solutions per minute for 7-point 4-colour
graph
gtest980a.c :
98000 solutions per minute for 7-point 4-colour
graph, Mosers’ spindle.
en.wikipedia.org slash wiki slash Moser_spindle
*************************************************/
B = 340;
total_edges = 25 ;

total_finds = 0;

maxi_ull = ((unsigned long long)6700417)*((unsigned long
long)2753074036095);
scaling = ((long double) 37)/((long double) 10);
one = (long double) 1;
diff_record = ((long double) 4100)/((long double) 100);

diff_record = MAXDIFFAT1;
maxdiffat400 = ((long double)1)/((long double)100000);
maxdiffat400 = (((long double)1)/((long double)100000))*maxdiffat400;
maxdiffat400 = (((long double)1)/((long double)100000))*maxdiffat400;

epsilon = ((long double)1)/((long double)10000000);

rec_diff25 = (long double) 0;
rec_diff50 = (long double) 0;
rec_diff100 = (long double) 0;
rec_diff1 = (long double) 0;
rec_diff200 = (long double) 0;
rec_diff400 = (long double) 0;
rec_diff800 = (long double) 0;
rec_diff1200 = (long double) 0;
alphabet[0] = ‘A’;
alphabet[1] = ‘B’;
alphabet[2] = ‘C’;
alphabet[3] = ‘D’;
alphabet[4] = ‘E’;
alphabet[5] = ‘F’;
alphabet[6] = ‘G’;
alphabet[7] = ‘H’;
alphabet[8] = ‘I’;
alphabet[9] = ‘J’;
alphabet[10] = ‘K’;
alphabet[11] = ‘L’;
alphabet[12] = ‘M’;
alphabet[13] = ‘N’;
/* First seed Q[] with CNG+XS: */
for(i=0;i<2097152;i++)
{
Q[i]=CNG+XS;
Q[i] = Q[i]&14502779422240352273ULL;
}

for(l=0; l< VERTEX ; l++)
{
dmatrix[l][l] = (long double) 0;
}

while( total_finds < 5000000000 )
{

graph_found = 0;

while( graph_found == 0)
{

numedges = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
adjmat[l][m] = 0;
}
}

while(numedges < total_edges )
{
ru1 = (int) (KISS&mask);
co1 = ru1/153391690;
ru2 = (int) (KISS&mask);
co2 = ru2/153391690;
if( (co1 != co2) && (adjmat[co1][co2] == 0) )
{
adjmat[co1][co2] = 1;
adjmat[co2][co1] = 1;
numedges++;
}
}

/*** compute degrees[] ***/
/*** each 3 or more ***/

degree_test_passed = 1;

for(l=0; l< VERTEX ; l++)
{
degrees[l] = 0;

for(m=0; m < VERTEX; m++)
{
degrees[l] = degrees[l] + adjmat[l][m];
}

if( degrees[l] < 3 )
{
degree_test_passed = 0;
break;
}
}

if(degree_test_passed == 1)
{
graph_found = 1;
}

}
count = 0;
max_has_converged_step = 0;
while( count < 20 )
{
solution_found = 0;

while( 0 == solution_found )
{
for( j=0; j< VERTEX ; j++)
{
randx = KISS;
xcoord[j] = ((long double) randx)/((long double) maxi_ull);
xcoord[j] = scaling*xcoord[j];
randx = KISS;
ycoord[j] = ((long double) randx)/((long double) maxi_ull);
ycoord[j] = scaling*ycoord[j];
}
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l ; m++)
{
dmatrix[l][m] = (xcoord[l]-xcoord[m])*(xcoord[l]-xcoord[m]);
dmatrix[l][m] = dmatrix[l][m] +
(ycoord[l]-ycoord[m])*(ycoord[l]-ycoord[m]);
dmatrix[l][m] = sqrtl(dmatrix[l][m]);
}
for(m= l+1 ; m< VERTEX ; m++)
{
dmatrix[l][m] = dmatrix[m][l];
}
}
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff1 = diff;

if(diff < diff_record)
{
solution_found = 1;

for( j =0; j< VERTEX ; j++)
{
xgood[j] = xcoord[j];
ygood[j] = ycoord[j];
}
}
}

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

have solution …

*****************************************************************/
has_converged_flag = 0;
quit = 0;
count = count + 1;
/*************** BEGIN ITERATIONS TO CONVERGE **************/
for( k = 0; k < NUMSTEPS ; k++)
{
if( quit == 1)
{
break;
}

if( (k+1) < 100)
{
C = ((long double) 345)/((long double) 1000);
}
else
{
C = ((long double) B )/((long double) 1000);
}

for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l ; m++)
{
dmatrix[l][m] = (xgood[l]-xgood[m])*(xgood[l]-xgood[m]);
dmatrix[l][m] = dmatrix[l][m] +
(ygood[l]-ygood[m])*(ygood[l]-ygood[m]);
dmatrix[l][m] = sqrtl(dmatrix[l][m]);
}
for(m= l+1 ; m< VERTEX ; m++)
{
dmatrix[l][m] = dmatrix[m][l];
}
}
if( (k+1) == 25 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff25 = diff;

if( diff > MAXDIFFAT25 )
{
quit = 1;
}
}
if( (k+1) == 50 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff50 = diff;

if( diff > MAXDIFFAT50 )
{
quit = 1;
}
}
if( (k+1) == 100 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff100 = diff;

if( diff > MAXDIFFAT100 )
{
quit = 1;
}
}

if( (k+1) == 200 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff200 = diff;

if( diff > MAXDIFFAT200 )
{
quit = 1;
}
}
if( (k+1) == 400 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff400 = diff;

if( diff > MAXDIFFAT400 )
{
quit = 1;
}
}
if( (k+1) == 800 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff800 = diff;

if( diff > MAXDIFFAT800 )
{
quit = 1;
}

}
if( (k+1) == 1200 )
{
diff = (long double) 0;
for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

diff1200 = diff;

if( diff > MAXDIFFAT1200 )
{
quit = 1;
}

}
diff = (long double) 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m< l; m++)
{
if( 1 == adjmat[l][m] )
{
diff = diff + fabsl(one-dmatrix[l][m]);
}
}
}

if( (diff < maxdiffat400) && (has_converged_flag == 0) )
{
has_converged_flag = 1;
has_converged_step = k+1;

if( has_converged_step > max_has_converged_step )
{
max_has_converged_step = has_converged_step;
}

quit = 1;

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

int is_singular;

**********************/
is_singular = 0;

for(l=0; l < VERTEX; l++)
{
for(m = 0; m < l; m++)
{
if( dmatrix[l][m] < epsilon )
{
is_singular = 1;
}
}
}
if( is_singular == 0)
{

total_finds = total_finds + 1;

if( (diff25 > rec_diff25) && (has_converged_step > 25))
{
rec_diff25 = diff25;
}

if( (diff50 > rec_diff50) && (has_converged_step > 50))
{
rec_diff50 = diff50;
}
if( (diff100 > rec_diff100) && (has_converged_step > 100))
{
rec_diff100 = diff100;
}

if( diff1 > rec_diff1)
{
rec_diff1 = diff1;
}

if( (diff200 > rec_diff200) && (has_converged_step > 200) )
{
rec_diff200 = diff200;
}

if( (diff400 > rec_diff400 ) && (has_converged_step > 400))
{
rec_diff400 = diff400;
}
if( (diff800 > rec_diff800) && (has_converged_step > 800))
{
rec_diff800 = diff800;
}
if( (diff1200 > rec_diff1200) && (has_converged_step > 1200))
{
rec_diff1200 = diff1200;
}
#ifdef VERBOSE
for(l = 0; l< VERTEX; l++)
{
for(m=0; m< VERTEX; m++)
{
post_adjmat[l][m] = 0;
}
}
probable_unit_lengths = 0;

for(l = 0; l<VERTEX; l++)
{
for(m = 0; m < l; m++)
{
if( fabsl(dmatrix[l][m]-one) < epsilon )
{
probable_unit_lengths++ ;
post_adjmat[l][m] = 1;
post_adjmat[m][l] = 1;
}
}
}
/**** TEST post_adjmat[][] for 3-coloring BEGIN ****/

n_colors = 3;
coloring_found = 0;
for(v0 = 0; v0< 1 ; v0++)
{
for(v1 = 0; v1< 2 ; v1++)
{
for(v2 = 0; v2< n_colors ; v2++)
{
for(v3 = 0; v3< n_colors ; v3++)
{
for(v4 = 0; v4< n_colors ; v4++)
{
for(v5 = 0; v5< n_colors ; v5++)
{
for(v6 = 0; v6< n_colors ; v6++)
{
for(v7 = 0; v7< n_colors ; v7++)
{
for(v8 = 0; v8< n_colors ; v8++)
{
for(v9 = 0; v9< n_colors ; v9++)
{
for(v10 = 0; v10< n_colors ; v10++)
{
for(v11 = 0; v11< n_colors ; v11++)
{
for(v12 = 0; v12< n_colors ; v12++)
{
for(v13 = 0; v13< n_colors ; v13++)
{
colors[0] = v0;
colors[1] = v1;
colors[2] = v2;
colors[3] = v3;
colors[4] = v4;
colors[5] = v5;
colors[6] = v6;
colors[7] = v7;
colors[8] = v8;
colors[9] = v9;
colors[10] = v10;
colors[11] = v11;
colors[12] = v12;
colors[13] = v13;
has_failed = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < l; m++)
{
if( (post_adjmat[l][m]==1)&& (colors[l]==colors[m]) )
{
has_failed = 1;
}
}
}

if( has_failed == 0 )
{
coloring_found = 1;
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}
if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}

}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}

if( coloring_found == 1 )
{
break;
}
}
if( coloring_found == 1 )
{
is_3colorable = 1;
}
else
{
is_3colorable = 0;
}

/**** TEST post_adjmat[][] for 3-coloring END ****/

printf(“adjacency matrix:\n”);

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
printf(“%d “, adjmat[l][m]) ;
}
printf(“\n”);
}

printf(“\n”);
printf(“post adjacency matrix:\n”);

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX; m++)
{
printf(“%d “, post_adjmat[l][m]) ;
}
printf(“\n”);
}

if( is_3colorable == 0)
{

n_colors = 4;
coloring_found = 0;
num_4_colorings = 0;

for(v0 = 0; v0< n_colors ; v0++)
{
for(v1 = 0; v1< n_colors ; v1++)
{
for(v2 = 0; v2< n_colors ; v2++)
{
for(v3 = 0; v3< n_colors ; v3++)
{
for(v4 = 0; v4< n_colors ; v4++)
{
for(v5 = 0; v5< n_colors ; v5++)
{
for(v6 = 0; v6< n_colors ; v6++)
{
for(v7 = 0; v7< n_colors ; v7++)
{
for(v8 = 0; v8< n_colors ; v8++)
{
for(v9 = 0; v9< n_colors ; v9++)
{
for(v10 = 0; v10< n_colors ; v10++)
{
for(v11 = 0; v11< n_colors ; v11++)
{
for(v12 = 0; v12< n_colors ; v12++)
{
for(v13 = 0; v13< n_colors ; v13++)
{
colors[0] = v0;
colors[1] = v1;
colors[2] = v2;
colors[3] = v3;
colors[4] = v4;
colors[5] = v5;
colors[6] = v6;
colors[7] = v7;
colors[8] = v8;
colors[9] = v9;
colors[10] = v10;
colors[11] = v11;
colors[12] = v12;
colors[13] = v13;
has_failed = 0;
four_colouring_failed = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < l; m++)
{
if( (post_adjmat[l][m]==1)&& (colors[l]==colors[m]) )
{
has_failed = 1;
four_colouring_failed = 1;
}
if( four_colouring_failed == 1)
{
break;
}
}

if( four_colouring_failed == 1)
{
break;
}
}

if( has_failed == 0 )
{
coloring_found = 1;
num_4_colorings++ ;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}

num_4_colorings_mod_24 = num_4_colorings%24 ;

count_4_colorings = num_4_colorings/24;

}
printf(“total_finds = %d\n”, total_finds);
printf(“Tests count = %d “, count);
printf(“has_converged_step = %d “, has_converged_step);
printf(“max_has_converged_step = %d\n”, max_has_converged_step);
printf(“rec_diff1 = %.6Lf\n”, rec_diff1);
printf(“rec_diff25 = %.6Lf\n”, rec_diff25);
printf(“rec_diff50 = %.6Lf\n”, rec_diff50);
printf(“rec_diff100 = %.6Lf\n”, rec_diff100);
printf(“rec_diff200 = %.6Lf\n”, rec_diff200);
printf(“rec_diff400 = %.6Lf\n”, rec_diff400);
printf(“rec_diff800 = %.16Lf\n”, rec_diff800);
printf(“rec_diff1200 = %.16Lf\n”, rec_diff1200);
printf(“probable_unit_lengths = %d\n”, probable_unit_lengths);

printf(“graph is 3-colorable:”);
if(is_3colorable == 1)
{
printf(“yes. \n”);
}
else
{
printf(“no. \n”);
}
if( is_3colorable == 0 )
{
printf(“count_4_colorings = %d “, count_4_colorings);
printf(“num_4_colorings_mod_24 = %d\n”, num_4_colorings_mod_24);
}

printf(“Matrix of distances vertex to vertex:\n”);
printf(” “);
for(m=0; m<VERTEX; m++)
{
printf(” %c “, alphabet[m]);
}
printf(“\n”);
for(l=0; l< VERTEX ; l++)
{
printf(“%c “, alphabet[l]);
for(m=0; m< VERTEX ; m++)
{
printf(“%.3Lf “, dmatrix[l][m]);
}
printf(“\n”);
}

printf(“\n”);
fflush(stdout);
#endif

}
}
for(l=0; l< VERTEX ; l++)
{
forces[l][0] = (long double) 0;
forces[l][1] = (long double) 0;

for(m=0; m< VERTEX ; m++)
{
if( 1 == adjmat[l][m] )
{
vector[0] = xgood[m]-xgood[l];
vector[1] = ygood[m]-ygood[l];
vector[0] = vector[0]/dmatrix[l][m];
vector[1] = vector[1]/dmatrix[l][m];
vector[0] = vector[0]*C;
vector[1] = vector[1]*C;
vector[0] = vector[0]*(dmatrix[l][m]-one);
vector[1] = vector[1]*(dmatrix[l][m]-one);

forces[l][0] = forces[l][0] + vector[0];
forces[l][1] = forces[l][1] + vector[1];
}
}
}

for( j =0; j< VERTEX ; j++)
{
xgood[j] = xgood[j] + forces[j][0];
ygood[j] = ygood[j] + forces[j][1];
}
}
/******************************************************
Below, post-convergence algorithm or heuristic:
******************************************************/
}
/*****************************************
while( count < 1 ) end Block
*****************************************/
}
/********************************************
end of while( 1 == 1 ) Block
********************************************/
return 0;
}

Advertisements

Written by meditationatae

February 21, 2017 at 1:38 pm

Posted in History

%d bloggers like this: