meditationatae

Just another WordPress.com site

My first test-drive using exiftool on Windows

I had read that EXIF metadata in files that are images, whether .jpg or other file formats, have embbedded data, sometimes inluding geotags (coordinates).

Below is the copy/paste of my first test running exiftool.exe on Windows 10:

C:\Users\abcde\Downloads> C:\Users\abcde\Downloads\exiftool -All Louvre_Museum_Wikimedia_Commons.jpg

ExifTool Version Number : 10.45
File Name : Louvre_Museum_Wikimedia_Commons.jpg
Directory : .
File Size : 53 kB
File Modification Date/Time : 2017:03:08 07:18:37-05:00
File Access Date/Time : 2017:03:08 07:18:37-05:00
File Creation Date/Time : 2017:03:08 07:18:36-05:00
File Permissions : rw-rw-rw-
File Type : JPEG
File Type Extension : jpg
MIME Type : image/jpeg
JFIF Version : 1.01
Resolution Unit : inches
X Resolution : 240
Y Resolution : 240
Comment : File source: https://commons.wikimedia.org/wiki/File:Louvre_Museum_Wikimedia_Commons.jpg
Profile CMM Type : lcms
Profile Version : 2.1.0
Profile Class : Display Device Profile
Color Space Data : RGB
Profile Connection Space : XYZ
Profile Date Time : 2012:01:25 03:41:57
Profile File Signature : acsp
Primary Platform : Apple Computer Inc.
CMM Flags : Not Embedded, Independent
Device Manufacturer :
Device Model :
Device Attributes : Reflective, Glossy, Positive, Color
Rendering Intent : Perceptual
Connection Space Illuminant : 0.9642 1 0.82491
Profile Creator : lcms
Profile ID : 0
Profile Description : c2
Profile Copyright : FB
Media White Point : 0.9642 1 0.82491
Media Black Point : 0.01205 0.0125 0.01031
Red Matrix Column : 0.43607 0.22249 0.01392
Green Matrix Column : 0.38515 0.71687 0.09708
Blue Matrix Column : 0.14307 0.06061 0.7141
Red Tone Reproduction Curve : (Binary data 64 bytes, use -b option to extract)
Green Tone Reproduction Curve : (Binary data 64 bytes, use -b option to extract)
Blue Tone Reproduction Curve : (Binary data 64 bytes, use -b option to extract)
Image Width : 800
Image Height : 336
Encoding Process : Baseline DCT, Huffman coding
Bits Per Sample : 8
Color Components : 3
Y Cb Cr Sub Sampling : YCbCr4:2:0 (2 2)
Image Size : 800×336
Megapixels : 0.269

Written by meditationatae

March 8, 2017 at 12:41 pm

Posted in History

A 12-vertex, 26-edge, probable unit distance graph

okmarch4scan

The 12-vertex, 26-edge graph shown above is not 3-colorable, and is 4-colorable in 178 ways, up to permutation of the four colors. Numerical evidence suggests that it is a unit distance graph, i.e. embeddable in the plane with all edges of unit length.

My unit distance graph solver found no 12-vertex, non 3-colorable, 4-colorable udg with less than 178 different colorings, counting permutations of the four colors as equivalent. The search was not exahaustive and lasted a day.

Below, I copy the adjacency matrix for the graph above. The rows and columns are not labeled, but it is easy to guess: A for row 1, B for row 2, C for row 3, …. L for row 12; similarly for the labeling of the columns.

I don’t know how to do a fixed-width, or monospace font, in WordPress, so I omit the labels to avoid misalignment.

Adjacency matrix, 12 by 12:

0 1 0 0 0 1 1 1 1 0 0 0
1 0 0 0 0 0 0 0 1 0 1 1
0 0 0 1 0 1 1 0 0 1 0 1
0 0 1 0 1 1 0 0 1 0 0 0
0 0 0 1 0 0 0 1 1 1 1 0
1 0 1 1 0 0 0 1 0 0 0 0
1 0 1 0 0 0 0 0 1 1 0 0
1 0 0 0 1 1 0 0 0 1 1 0
1 1 0 1 1 0 1 0 0 0 0 0
0 0 1 0 1 0 1 1 0 0 0 1
0 1 0 0 1 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 1 0 0

 

Written by meditationatae

March 4, 2017 at 8:28 pm

Posted in History

Unit distance graph solver for 15 vertices

This program is a variation on the solver for 14 vertices. The solver for 15 vertices has the added ingredient that it forces the first seven vertices and the edges that join some of these 7 vertices to each other to form as a subgraph a Moser spindle: a particular 7-vertex, 11-edge graph decribed at Wikipedia:

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

The first find of the 15-vertex solver is a probable 28-edge unit distance graph (with 15 vertices) that is 4-colorable, but is not 3-colorable:
adjacency matrix:
0 0 1 1 0 0 1 1 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 1 0 0 0 0 1 0 0 0
1 1 0 0 0 1 0 0 0 0 0 0 1 0 0
0 1 1 0 0 1 1 0 0 0 0 0 0 0 1
0 1 0 1 1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 0 1 0 0 0 0 0 0 1
1 0 0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 1 0 1
0 0 0 0 0 0 0 1 0 0 0 1 1 0 0
0 0 1 0 0 0 0 0 1 0 1 0 0 1 0
0 0 0 1 0 0 0 0 0 1 1 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 1 1 0 0
0 0 0 0 1 0 1 0 0 1 0 0 0 0 0

post adjacency matrix:
0 0 1 1 0 0 1 1 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 1 0 0 0 0 1 0 0 0
1 1 0 0 0 1 0 0 0 0 0 0 1 0 0
0 1 1 0 0 1 1 0 0 0 0 0 0 0 1
0 1 0 1 1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 0 1 0 0 0 0 0 0 1
1 0 0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 1 0 1 0 1 1 0 0
0 0 1 0 0 0 0 0 1 0 1 0 0 1 0
0 0 0 1 0 0 0 0 0 1 1 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 1 1 0 0
0 0 0 0 1 0 1 0 0 1 0 0 0 0 0
total_finds = 1
Tests count = 11 has_converged_step = 1417 max_has_converged_step = 1417
rec_diff1 = 33.276408
rec_diff25 = 8.437412
rec_diff50 = 2.569091
rec_diff100 = 0.578599
rec_diff200 = 0.132061
rec_diff400 = 0.000661
rec_diff800 = 0.0000000147489021
rec_diff1200 = 0.0000000000003289
probable_unit_lengths = 28
graph is 3-colorable:no.
count_4_colorings = 5122 num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M N O
A 0.00 0.74 1.00 1.00 1.73 1.57 1.00 1.00 1.46 2.46 1.47 0.47 2.00 1.21 2.00
B 0.74 0.00 0.58 1.00 1.00 1.00 0.46 1.19 1.16 2.04 1.06 0.49 1.90 1.47 1.37
C 1.00 0.58 0.00 1.57 1.00 1.46 1.00 1.73 1.72 2.54 1.59 1.00 2.47 2.00 1.73
D 1.00 1.00 1.57 0.00 1.73 1.00 0.74 0.29 0.58 1.56 0.72 0.62 1.00 0.54 1.44
E 1.73 1.00 1.00 1.73 0.00 1.00 1.00 2.00 1.53 1.98 1.31 1.45 2.31 2.27 1.00
F 1.57 1.00 1.46 1.00 1.00 0.00 0.58 1.29 0.58 1.09 0.35 1.11 1.32 1.51 0.46
G 1.00 0.46 1.00 0.74 1.00 0.58 0.00 1.00 0.72 1.59 0.60 0.56 1.49 1.27 1.00
H 1.00 1.19 1.73 0.29 2.00 1.29 1.00 0.00 0.84 1.76 1.00 0.73 1.05 0.28 1.73
I 1.46 1.16 1.72 0.58 1.53 0.58 0.72 0.84 0.00 1.00 0.23 1.00 0.79 1.00 0.95
J 2.46 2.04 2.54 1.56 1.98 1.09 1.59 1.76 1.00 0.00 1.00 1.99 1.00 1.84 1.00
K 1.47 1.06 1.59 0.72 1.31 0.35 0.60 1.00 0.23 1.00 0.00 1.00 1.00 1.20 0.74
L 0.47 0.49 1.00 0.62 1.45 1.11 0.56 0.73 1.00 1.99 1.00 0.00 1.60 1.00 1.55
M 2.00 1.90 2.47 1.00 2.31 1.32 1.49 1.05 0.79 1.00 1.00 1.60 0.00 1.00 1.57
N 1.21 1.47 2.00 0.54 2.27 1.51 1.27 0.28 1.00 1.84 1.20 1.00 1.00 0.00 1.94
O 2.00 1.37 1.73 1.44 1.00 0.46 1.00 1.73 0.95 1.00 0.74 1.55 1.57 1.94 0.00

 

The source code file, udgraph15_solver14a.c , is copied below.

 

#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 15

/**********************************************
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, v14;
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];
int spindle[7][7] = {{0,0,1,1,0,0,1},{0,0,0,1,1,1,0},{1,0,0,0,1,0,1},{1,1,0,0,0,1,0},{0,1,1,0,0,1,1},{0,1,0,1,1,0,0},{1,0,1,0,1,0,0}};

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

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 = 27 ;

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’;
alphabet[14] = ‘O’;

/* First seed Q[] with CNG+XS: */
for(i=0;i<2097152;i++)
{
Q[i]=CNG+XS;
Q[i] = Q[i]^14502779422240352273ULL;
Q[i] = Q[i]^9440806654508920842ULL;
}

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

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

numedges = 11 ;

while(numedges < total_edges )
{
ru1 = (int) (KISS&mask);
co1 = ru1/143165577 ;
ru2 = (int) (KISS&mask);
co2 = ru2/143165577 ;
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++)
{
for(v14 = 0; v14< n_colors ; v14++)
{

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;
colors[14] = v14;
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 )
{
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++)
{
for(v14 = 0; v14< n_colors ; v14++)
{

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;
colors[14] = v14;
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(“%.2Lf “, 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;
}

Written by meditationatae

February 28, 2017 at 3:33 am

Posted in History

Scan of complicated 14-vertex graph

newscan7

If I’m not mistaken, there are 33 edges.

If we remove the vertex M and the four edges incident on M, this leaves 29 edges. The 13-point configuration has bilateral symmetry across a line through the points J, H, and I. In the 13-point configuration where M is removed, by symmetry, edges have mirror images different from themselves, except for the edge BF, which is its own mirror image across an axis through J, H, and I.

====

Added: Thu Mar 2 21:11:34 EST 2017

The solver for 15 vertices that starts from a 7-vertex Moser spindle isn’t going very far very fast.

$ cat data1232a.txt
adjacency matrix:
0 0 1 1 0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 1 1 0 0 0 0 0 1 0
1 1 0 0 0 1 0 0 0 0 0 0 1 0 0
0 1 1 0 0 1 1 0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 1 0 0 0 0 1 0 0
1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 1 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 1 0 0
0 0 0 1 0 1 0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 1 0 0 0 1 0

post adjacency matrix:
0 0 1 1 0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 0 1 1
1 0 0 0 1 0 1 1 0 0 0 0 0 1 0
1 1 0 0 0 1 0 0 0 1 1 0 1 0 0
0 1 1 0 0 1 1 0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 1 0 0 0 0 1 0 0
1 0 1 0 1 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 1 0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 1 0 0 1 1 1 0 0
0 0 0 1 0 0 0 0 0 0 1 1 0 0 1
0 0 0 1 0 0 0 1 1 1 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 0 0 1 0 0
0 0 0 1 0 1 0 0 1 0 0 1 0 0 0
0 1 1 0 0 0 0 1 0 0 1 0 0 0 1
0 1 0 0 0 0 1 0 0 1 0 0 0 1 0
total_finds = 92
Tests count = 13 has_converged_step = 1600 max_has_converged_step = 1600
rec_diff1 = 39.325534
rec_diff25 = 32.270247
rec_diff50 = 16.837123
rec_diff100 = 13.714747
rec_diff200 = 9.446856
rec_diff400 = 0.019220
rec_diff800 = 0.0000007856360233
rec_diff1200 = 0.0000000000793501
probable_unit_lengths = 33
graph is 3-colorable:no.
count_4_colorings = 1232 num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M N O
A 0.00 0.74 1.00 1.00 1.73 1.57 1.00 0.58 1.29 1.57 0.74 2.29 1.98 0.46 0.58
B 0.74 0.00 0.58 1.00 1.00 1.00 0.46 0.46 1.44 1.91 1.37 2.35 1.73 1.00 1.00
C 1.00 0.58 0.00 1.57 1.00 1.46 1.00 1.00 2.00 2.43 1.73 2.93 2.29 1.00 1.46
D 1.00 1.00 1.57 0.00 1.73 1.00 0.74 0.58 0.46 1.00 1.00 1.37 1.00 1.46 0.58
E 1.73 1.00 1.00 1.73 0.00 1.00 1.00 1.37 2.18 2.73 2.35 2.89 2.00 1.91 1.95
F 1.57 1.00 1.46 1.00 1.00 0.00 0.58 1.00 1.37 1.95 1.91 1.91 1.00 1.95 1.46
G 1.00 0.46 1.00 0.74 1.00 0.58 0.00 0.46 1.19 1.73 1.44 2.00 1.29 1.37 1.00
H 0.58 0.46 1.00 0.58 1.37 1.00 0.46 0.00 1.00 1.46 1.00 1.95 1.46 1.00 0.58
I 1.29 1.44 2.00 0.46 2.18 1.37 1.19 1.00 0.00 0.58 1.00 1.00 1.00 1.73 0.74
J 1.57 1.91 2.43 1.00 2.73 1.95 1.73 1.46 0.58 0.00 1.00 1.00 1.46 1.95 1.00
K 0.74 1.37 1.73 1.00 2.35 1.91 1.44 1.00 1.00 1.00 0.00 1.91 1.95 1.00 0.46
L 2.29 2.35 2.93 1.37 2.89 1.91 2.00 1.95 1.00 1.00 1.91 0.00 1.00 2.73 1.73
M 1.98 1.73 2.29 1.00 2.00 1.00 1.29 1.46 1.00 1.46 1.95 1.00 0.00 2.43 1.57
N 0.46 1.00 1.00 1.46 1.91 1.95 1.37 1.00 1.73 1.95 1.00 2.73 2.43 0.00 1.00
O 0.58 1.00 1.46 0.58 1.95 1.46 1.00 0.58 0.74 1.00 0.46 1.73 1.57 1.00 0.00

The UDG it has found has 33 edges and 1232 4-colorings, up to permutation of the 4 colors (and no 3-colorings).

I’ll check that the 33-edge 14-vertex UDG in the picture does indeed have bilateral symmetry for an axis of symmetry through the points J , H, and I.

Maybe as 15th point I can add the mirror image of point M in the axis of symmetry through J, H, and I.

It’s getting complicated.

=====

Added: Thu Mar 2 22:07:18 EST 2017

Indeed, there is an axis of symmetry through points J, H, and I. 14 points minus 3 points equals 11 points, but point M has no mirror image, so subract one again to get 10 points in 5 pairs of mirror image points:

D and E  ( pair number 1)

L and N ( pair number 2)

B and F (pair number 3)

G and K (pair number 4)

A and C (pair number 5)

image:

scan22

=====

Added:  Thu Mar 2 23:10:13 EST 2017

Please note that the line through points J, H, and I above is only to show the axis of symmetry, and no graph edges are part of this line…

My enumeration of the 33 edges follows. Please contact me at

david250 at videotron dot ca if you find mistakes.

A F
A G
A H
A M
B C
B E
B F
B N
C H
C K
D J
D L
D H
D F
D K
E J
E N
E H
E G
F M
F L
G H
G L
G I
H K
I L
I N
I K
I M
J L
J N
K N
K M

=====

Added: Fri Mar 3 03:56:16 EST 2017

Point “O” is the mirror image of point M, and therefore there are edges BO and CO, mirror images of edges FM and AM.

Result:

adjacency matrix:
0 0 0 0 0 1 1 0 0 0 0 0 1 0 0
0 0 1 0 0 1 0 0 0 0 0 0 0 1 1
0 1 0 0 0 0 0 1 0 0 1 0 0 0 1
0 0 0 0 0 1 0 1 0 1 0 1 0 0 0
0 0 0 0 0 0 1 1 0 1 0 0 0 1 0
1 1 0 1 0 0 0 0 0 0 0 1 0 0 0
1 0 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 1 1 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0
0 0 0 1 1 0 0 0 0 0 0 1 0 1 0
0 0 1 0 0 0 0 0 1 0 0 0 1 1 0
0 0 0 1 0 1 0 0 1 1 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0 1 0 0 0 0
0 1 0 0 1 0 0 0 0 1 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0

post adjacency matrix:
0 0 0 0 0 1 1 1 0 0 0 0 1 0 0
0 0 1 0 1 1 0 0 0 0 0 0 0 1 1
0 1 0 0 0 0 0 1 0 0 1 0 0 0 1
0 0 0 0 0 1 0 1 0 1 1 1 0 0 0
0 1 0 0 0 0 1 1 0 1 0 0 0 1 0
1 1 0 1 0 0 0 0 0 0 0 1 1 0 0
1 0 0 0 1 0 0 1 1 0 0 1 0 0 1
1 0 1 1 1 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0 1 1 1 1 1
0 0 0 1 1 0 0 0 0 0 0 1 0 1 0
0 0 1 1 0 0 0 1 1 0 0 0 1 1 0
0 0 0 1 0 1 1 0 1 1 0 0 0 0 0
1 0 0 0 0 1 0 0 1 0 1 0 0 0 0
0 1 0 0 1 0 0 0 1 1 1 0 0 0 0
0 1 1 0 0 0 1 0 1 0 0 0 0 0 0
total_finds = 4
Tests count = 1 has_converged_step = 2540 max_has_converged_step = 2540
rec_diff1 = 64.481510
rec_diff25 = 1.995834
rec_diff50 = 1.403561
rec_diff100 = 1.203674
rec_diff200 = 0.626094
rec_diff400 = 0.150774
rec_diff800 = 0.0118507527986628
rec_diff1200 = 0.0010902257621921
probable_unit_lengths = 37
graph is 3-colorable:no.
count_4_colorings = 364 num_4_colorings_mod_24 = 0
Matrix of distances vertex to vertex:
A B C D E F G H I J K L M N O
A 0.00 0.74 0.46 1.91 1.73 1.00 1.00 1.00 0.46 2.35 1.37 1.37 1.00 1.44 0.58
B 0.74 0.00 1.00 1.57 1.00 1.00 0.46 0.58 0.58 1.73 1.46 0.74 1.57 1.00 1.00
C 0.46 1.00 0.00 1.73 1.91 0.74 1.37 1.00 0.46 2.35 1.00 1.44 0.58 1.37 1.00
D 1.91 1.57 1.73 0.00 1.46 1.00 1.95 1.00 1.46 1.00 1.00 1.00 1.95 0.58 2.43
E 1.73 1.00 1.91 1.46 0.00 1.57 1.00 1.00 1.46 1.00 1.95 0.58 2.43 1.00 1.95
F 1.00 1.00 0.74 1.00 1.57 0.00 1.46 0.58 0.58 1.73 0.46 1.00 1.00 0.74 1.57
G 1.00 0.46 1.37 1.95 1.00 1.46 0.00 1.00 1.00 1.91 1.91 1.00 1.95 1.37 1.00
H 1.00 0.58 1.00 1.00 1.00 0.58 1.00 0.00 0.58 1.37 1.00 0.46 1.46 0.46 1.46
I 0.46 0.58 0.46 1.46 1.46 0.58 1.00 0.58 0.00 1.95 1.00 1.00 1.00 1.00 1.00
J 2.35 1.73 2.35 1.00 1.00 1.73 1.91 1.37 1.95 0.00 1.91 1.00 2.73 1.00 2.73
K 1.37 1.46 1.00 1.00 1.95 0.46 1.91 1.00 1.00 1.91 0.00 1.37 1.00 1.00 1.95
L 1.37 0.74 1.44 1.00 0.58 1.00 1.00 0.46 1.00 1.00 1.37 0.00 1.91 0.46 1.73
M 1.00 1.57 0.58 1.95 2.43 1.00 1.95 1.46 1.00 2.73 1.00 1.91 0.00 1.73 1.46
N 1.44 1.00 1.37 0.58 1.00 0.74 1.37 0.46 1.00 1.00 1.00 0.46 1.73 0.00 1.91
O 0.58 1.00 1.00 2.43 1.95 1.57 1.00 1.46 1.00 2.73 1.95 1.73 1.46 1.91 0.00

15 vertices, 37 edges, 364 4-colorings.

Source code used = /home/david/graphs/golomb23/udgraph15_solver43a.c

#include <stdio.h>
#include <math.h>
#define NUMSTEPS 10000
#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) 400)/((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 15

/**********************************************
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, v14;
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;
int sum_of_degrees;
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 testmat[VERTEX][VERTEX];
int blog_mat[14][14];
FILE *in;
int post_adjmat[VERTEX][VERTEX];
int spindle[7][7] = {{0,0,1,1,0,0,1},{0,0,0,1,1,1,0},{1,0,0,0,1,0,1},{1,1,0,0,0,1,0},{0,1,1,0,0,1,1},{0,1,0,1,1,0,0},{1,0,1,0,1,0,0}};
int base_mat[8][8];

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

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 = 27 ;

total_finds = 0;

maxi_ull = ((unsigned long long)6700417)*((unsigned long
long)2753074036095);
scaling = ((long double) 57)/((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’;
alphabet[14] = ‘O’;
in=fopen(“/home/david/graphs/golomb23/base_mat_from_blog01a.txt”, “r”);
for(l=0; l< 14 ; l++)
{
for(m=0; m < 14; m++)
{
fscanf(in, “%d”, &blog_mat[l][m]);
}
}

fclose(in);
for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX ; m++)
{
testmat[l][m] = 0;
}
}

for(l=0; l< 14 ; l++)
{
for(m=0; m < 14; m++)
{
testmat[l][m] = blog_mat[l][m];
}
}
/***************************************************

add edges:

BO
CO

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

testmat[1][14] = 1;
testmat[2][14] = 1;
testmat[14][1] = 1;
testmat[14][2] = 1;

sum_of_degrees = 0;

for(l=0; l< VERTEX ; l++)
{
for(m=0; m < VERTEX ; m++)
{
if(testmat[l][m] == 1)
{
sum_of_degrees = sum_of_degrees +1;
}
}
}

printf(“\n sum_of_degrees = %d\n\n”, sum_of_degrees);
/* First seed Q[] with CNG+XS: */
for(i=0;i<2097152;i++)
{
Q[i]=CNG+XS;
Q[i] = Q[i]^14502779422240352273ULL;
Q[i] = Q[i]^9440806654508920842ULL;
Q[i] = Q[i]^11231778222269950461ULL;
}

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

while( total_finds < 5000000000 )
{

graph_found = 0;

while( graph_found == 0)
{

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

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

while(numedges < total_edges )
{
ru1 = (int) (KISS&mask);
co1 = ru1/143165577 ;
ru2 = (int) (KISS&mask);
co2 = ru2/143165577 ;
if( (co1 != co2) && (adjmat[co1][co2] == 0) )
{
if( (co1 > 13) || (co2 > 13) )
{
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 < 1 )
{
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) 200)/((long double) 1000);
}
else
{
C = ((long double) 200 )/((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++)
{
for(v14 = 0; v14< n_colors ; v14++)
{

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;
colors[14] = v14;

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 )
{
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++)
{
for(v14 = 0; v14< n_colors ; v14++)
{
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;
colors[14] = v14;

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(“%.2Lf “, 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;
}

 

 

The file  base_mat_from_blog01a.txt :

0 0 0 0 0 1 1 0 0 0 0 0 1 0
0 0 1 0 0 1 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 1 0 1 0 1 0 1 0 0
0 0 0 0 0 0 1 1 0 1 0 0 0 1
1 1 0 1 0 0 0 0 0 0 0 1 0 0
1 0 0 0 1 0 0 1 0 0 0 0 0 0
0 0 1 1 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 1 1 0 0 0 0 0 0 1 0 1
0 0 1 0 0 0 0 0 1 0 0 0 1 1
0 0 0 1 0 1 0 0 1 1 0 0 0 0
1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 0 0 0 0 1 1 0 0 0

 

Written by meditationatae

February 27, 2017 at 9:30 pm

Posted in History

PostScript “source code”, 14-vertex 33-edge graph

Starts below, with a fixed number of lines (4 it seems) for each of the 33 edges programmed to be drawn. File name should end in .ps :

newpath
73 269 moveto
353 289 lineto
stroke
newpath
73 269 moveto
353 289 lineto
stroke
newpath
73 269 moveto
296 440 lineto
stroke
newpath
73 269 moveto
230 36 lineto
stroke
newpath
136 466 moveto
172 188 lineto
stroke
newpath
136 466 moveto
259 719 lineto
stroke
newpath
136 466 moveto
353 289 lineto
stroke
newpath
136 466 moveto
416 486 lineto
stroke
newpath
172 188 moveto
296 440 lineto
stroke
newpath
172 188 moveto
453 207 lineto
stroke
newpath
576 460 moveto
353 289 lineto
stroke
newpath
576 460 moveto
296 440 lineto
stroke
newpath
576 460 moveto
539 738 lineto
stroke
newpath
576 460 moveto
453 207 lineto
stroke
newpath
576 460 moveto
316 567 lineto
stroke
newpath
259 719 moveto
36 548 lineto
stroke
newpath
259 719 moveto
296 440 lineto
stroke
newpath
259 719 moveto
539 738 lineto
stroke
newpath
259 719 moveto
416 486 lineto
stroke
newpath
353 289 moveto
316 567 lineto
stroke
newpath
353 289 moveto
230 36 lineto
stroke
newpath
36 548 moveto
296 440 lineto
stroke
newpath
36 548 moveto
193 315 lineto
stroke
newpath
36 548 moveto
316 567 lineto
stroke
newpath
296 440 moveto
453 207 lineto
stroke
newpath
193 315 moveto
453 207 lineto
stroke
newpath
193 315 moveto
316 567 lineto
stroke
newpath
193 315 moveto
230 36 lineto
stroke
newpath
193 315 moveto
416 486 lineto
stroke
newpath
539 738 moveto
316 567 lineto
stroke
newpath
539 738 moveto
416 486 lineto
stroke
newpath
453 207 moveto
230 36 lineto
stroke
newpath
453 207 moveto
416 486 lineto
stroke

 

Comment: Bill Casselman at UBC has written a book on using PostScript in mathematical illustrations. Some of the chapters can be downloaded for free in PDF from his web-site.

You can google:

Casselman UBC PostScript

to find this.

Coordinates above are in points, where a point is 1/72 of an inch in PostScript. ps2pdf will convert a *.ps file to a *.pdf file that can be opened with Adobe Reader. Below, I add a screenshot of the screen-displayed PDF file. I still need to label the vertices, so it becomes possible to name triangles, paths and so on in the graph. I’ll do that later by hand, since my knowledge of PostScript is beginner level.

graph33ascreenshot

Written by meditationatae

February 27, 2017 at 4:31 pm

Posted in History

Useful command: rpm -qi

To know details of a Linux package, example:

$ rpm -qi firefox

gives this:

Name : firefox
Relocations: (not relocatable)
Version : 45.7.0
Vendor: CentOS
Release : 2.el6.centos
Build Date: Tue 21 Feb 2017 10:37:31 AM EST
Install Date: Wed 22 Feb 2017 02:00:30 PM EST
Build Host: c1bm.rdu2.centos.org
Group : Applications/Internet
Source RPM: firefox-45.7.0-2.el6.centos.src.rpm
Size : 134348863
License: MPLv1.1 or GPLv2+ or LGPLv2+
Signature : RSA/SHA1, Wed 22 Feb 2017 07:19:45 AM EST, Key ID 0946fca2c105b9de
Packager : CentOS BuildSystem <http://bugs.centos.org&gt;
URL : http://www.mozilla.org/projects/firefox/
Summary : Mozilla Firefox Web browser
Description :
Mozilla Firefox is an open-source web browser, designed for standards
compliance, performance and portability.

Written by meditationatae

February 26, 2017 at 12:17 pm

Posted in History

My “fix” of reaeadline problem in PARI/gp following #yum update

[david@localhost ~]$ /bin/su –
Password:
[root@localhost ~]# cd /usr
[root@localhost usr]# ls
bin etc games include lib lib64 libexec local sbin share src tmp
[root@localhost usr]# cd local
[root@localhost local]# ls
bin etc games include lib lib64 libexec sbin share src
[root@localhost local]# cd lib
[root@localhost lib]# ls
libgmp.a libhistory.so libpari-gmp.so.5 libreadline.so.7
libgmp.la libhistory.so.6 libpari.so libreadline.so.7.0
libgmp.so libhistory.so.6.3 libreadline.a libreadline.so.7.0.old
libgmp.so.10 libhistory.so.7 libreadline.old pari
libgmp.so.10.3.2 libhistory.so.7.0 libreadline.so
libhistory.a libhistory.so.7.0.old libreadline.so.6
libhistory.old libpari-gmp.so.2.9.1 libreadline.so.6.3
[root@localhost lib]# ls -l libreadline.so.6
lrwxrwxrwx. 1 root root 18 Feb 25 02:43 libreadline.so.6 -> libreadline.so.6.3
[root@localhost lib]# rm libreadline.so.6
rm: remove symbolic link `libreadline.so.6′? y
[root@localhost lib]# ls -l /lib64/libreadline.so.6.0
-rwxr-xr-x. 1 root root 272008 Jun 22 2012 /lib64/libreadline.so.6.0
[root@localhost lib]# ldd -d -r /lib64/libreadline.so.6.0
linux-vdso.so.1 => (0x00007fffd437e000)
libtinfo.so.5 => /lib64/libtinfo.so.5 (0x0000003b0fa00000)
libc.so.6 => /lib64/libc.so.6 (0x0000003afce00000)
/lib64/ld-linux-x86-64.so.2 (0x0000003afc600000)
[root@localhost lib]# ln -s /lib64/libreadline.so.6.0 libreadline.so.6
[root@localhost lib]# ls -l
total 13744
-rw-r–r–. 1 root root 1291398 Feb 22 12:51 libgmp.a
-rwxr-xr-x. 1 root root 913 Feb 22 12:51 libgmp.la
lrwxrwxrwx. 1 root root 16 Feb 22 12:51 libgmp.so -> libgmp.so.10.3.2
lrwxrwxrwx. 1 root root 16 Feb 22 12:51 libgmp.so.10 -> libgmp.so.10.3.2
-rwxr-xr-x. 1 root root 523381 Feb 22 12:51 libgmp.so.10.3.2
-rw-r–r–. 1 root root 162874 Feb 23 02:55 libhistory.a
-rw-r–r–. 1 root root 171982 Feb 22 14:11 libhistory.old
lrwxrwxrwx. 1 root root 15 Feb 23 02:55 libhistory.so -> libhistory.so.6
lrwxrwxrwx. 1 root root 17 Feb 23 02:55 libhistory.so.6 -> libhistory.so.6.3
-r-xr-xr-x. 1 root root 99093 Feb 23 02:55 libhistory.so.6.3
lrwxrwxrwx. 1 root root 21 Feb 22 14:11 libhistory.so.7 -> libhistory.so.7.0.old
-r-xr-xr-x. 1 root root 106376 Feb 22 14:11 libhistory.so.7.0
-r-xr-xr-x. 1 root root 106376 Feb 22 12:35 libhistory.so.7.0.old
-rwxr-xr-x. 1 root root 7060519 Feb 23 11:55 libpari-gmp.so.2.9.1
lrwxrwxrwx. 1 root root 20 Feb 23 11:55 libpari-gmp.so.5 -> libpari-gmp.so.2.9.1
lrwxrwxrwx. 1 root root 20 Feb 23 11:55 libpari.so -> libpari-gmp.so.2.9.1
-rw-r–r–. 1 root root 1199592 Feb 23 02:55 libreadline.a
-rw-r–r–. 1 root root 1239926 Feb 22 14:11 libreadline.old
lrwxrwxrwx. 1 root root 16 Feb 23 02:55 libreadline.so -> libreadline.so.6
lrwxrwxrwx. 1 root root 25 Feb 25 05:04 libreadline.so.6 -> /lib64/libreadline.so.6.0
-r-xr-xr-x. 1 root root 680148 Feb 23 02:55 libreadline.so.6.3
lrwxrwxrwx. 1 root root 22 Feb 22 14:11 libreadline.so.7 -> libreadline.so.7.0.old
-r-xr-xr-x. 1 root root 702910 Feb 22 14:11 libreadline.so.7.0
-r-xr-xr-x. 1 root root 702910 Feb 22 12:35 libreadline.so.7.0.old
drwxr-xr-x. 2 root root 4096 Feb 23 11:55 pari
[root@localhost lib]# ldd -d -r libreadline.so.6
linux-vdso.so.1 => (0x00007ffeea7d3000)
libtinfo.so.5 => /lib64/libtinfo.so.5 (0x0000003b0fa00000)
libc.so.6 => /lib64/libc.so.6 (0x0000003afce00000)
/lib64/ld-linux-x86-64.so.2 (0x0000003afc600000)
[root@localhost lib]# exit
logout
[david@localhost ~]$ gp
GP/PARI CALCULATOR Version 2.9.1 (released)
amd64 running linux (x86-64/GMP-6.1.2 kernel) 64-bit version
compiled: Feb 23 2017, gcc version 4.4.7 20120313 (Red Hat 4.4.7-17) (GCC)
threading engine: single
(readline v6.0 enabled, extended help enabled)

Copyright (C) 2000-2016 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT
ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?15 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000
? isprime(2^127 -1)
%1 = 1
? quit
Goodbye!
[david@localhost ~]$
[david@localhost ~]$ date
Sat Feb 25 05:05:49 EST 2017
[david@localhost ~]$

Written by meditationatae

February 25, 2017 at 10:08 am

Posted in History