meditationatae

Just another WordPress.com site

Archive for the ‘History’ Category

newtabuzf99a.c for DIMACS DSJC500.5.col

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

“Hybrid Evolutionary Algorithms for Graph Coloring”.

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

Filename:   newtabuzf99a.c

 

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

#define MAX_VERTEX 1000
#define MAX_COLORS 500

int adj_mat[MAX_VERTEX][MAX_VERTEX];

int Gamma[MAX_VERTEX][MAX_COLORS];

int Fast_Gamma[MAX_VERTEX][MAX_COLORS];

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

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

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

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

int main(int argc, char *argv[] )
{
FILE *in;
unsigned long long im,cng=123456789987654321ULL, xs=362436069362436069ULL;
unsigned long long mask = 2147483647ULL;
unsigned long long kiss1, kiss2, seed;
int num_colors;
int num_vertex;
int num_edges;
int num_conflicts;
int k;
int i;
int j;
int sum_adj_mat;
int ru;
int b;
int color;
int init_coloring[MAX_VERTEX];
int old_init_coloring[MAX_VERTEX];
int conflict_count;
int sum_Gamma;
int best_delta;
int delta;
int best_vertex;
int best_color;
int iter_counter;
int A;
float alpha;
int tl;
int b_tabu_rnd;
int tabu_rand;
int color_tabu;
int min_conflicts;
int job_done;
int differences;
FILE *out;
int is_round_one;
int problem_solved;
// FILE *in2;
int cnodes;
int select;
int temp;
int max_iter;
int candidate_count;
int b_candidate;
int can_number;

select = 2;

 

is_round_one = 1;

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

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

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

seed = 10000845109132110031ULL;

 

num_colors = atoi(argv[2]);
printf(“num_colors = %d\n” , num_colors);

in = fopen(argv[1], “r”);

fscanf(in, “%d %d”, &num_vertex, &num_edges);

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

for(i = 0 ; i < MAX_VERTEX; i++)
{
for(j = 0 ; j < MAX_VERTEX; j++)
{
adj_mat[i][j] = 0;
}
}

 

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

if(i == j)
{
printf(“warning: edge %d is = %d %d\n”, k+1, i, j);
}
}

fclose(in);

sum_adj_mat = 0;

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

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

printf(“\n”);

 

 

while( job_done == 0)
{

 

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

min_conflicts = 1000000;

 

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

 

printf(“\n”);

 

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

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

 

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

 

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

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

 

 

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

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

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

 

}
}

 

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

}

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

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

 

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

problem_solved = 0;

 

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

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

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

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

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

 

cnodes = 0;

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

 

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

 

 

 

best_delta = 1000000;

 

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

 

 

 

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

matches_best_delta[i][j] = 0;

if(j != init_coloring[i])
{
delta = Fast_Gamma[i][j] – Fast_Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
best_delta = delta;
}
}
}
}
}

candidate_count = 0;

for(i = 0; i < num_vertex; i++)
{
for(j = 0; j < num_colors; j++)
{
if(j != init_coloring[i])
{
delta = Fast_Gamma[i][j] – Fast_Gamma[i][init_coloring[i]];

if( delta == best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
matches_best_delta[i][j] = 1;
candidate_count++;
}
}
}
}
}

b_candidate = ((int) mask)/candidate_count;
b_candidate = b_candidate + 1;
ru = (int) (KISS&mask);
can_number = ru/b_candidate;

candidate_count = 0;

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

 

 

num_conflicts = num_conflicts + best_delta;

 

color_tabu = init_coloring[best_vertex];

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

init_coloring[best_vertex] = best_color;

 

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == 1)
{
Fast_Gamma[i][color_tabu] = Fast_Gamma[i][color_tabu]-1;
Fast_Gamma[i][best_color] = Fast_Gamma[i][best_color]+1;
}
}

 

 

}

 

if( problem_solved == 1)
{

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

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

fprintf(out, “\n”);

fflush(out);

num_colors = num_colors – 1;

is_round_one = 0;

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

 

 

 

}

 

 

fclose(out);

 
return 0;

}

Written by meditationatae

June 22, 2017 at 11:37 am

Posted in History

This guy has my vote: libreadline cleanup

[root@localhost ~]# cd /usr/local/lib

I had built and installed a non-system readline library as root in /usr/local/lib .

As far as I can tell, the system readline library is in

the file:

/lib64/libreadline.so.6.0

Running

# ldd -d -r /lib64/libreadline.so.6.0

linux-vdso.so.1 =>  (0x00007ffd0139b000)
libtinfo.so.5 => /lib64/libtinfo.so.5 (0x0000003e73200000)
libc.so.6 => /lib64/libc.so.6 (0x0000003752000000)
/lib64/ld-linux-x86-64.so.2 (0x0000003751c00000)

gives no unresolved symbols etc.

vkarthickeyan solution to mis-installed librealines libraries in /usr/local/lib/

is contained in his post:

https://vkarthickeyan.wordpress.com/2012/02/16/mysql-symbol-lookup-error-usrlocalliblibreadline-so-6-undefined-symbol-up/

So within /usr/local/lib/ I created a new directory temp via:

# mkdir temp

then I moved all the files starting with librealine from /usr/local/lib/ into the subdirectory temp/ :

# mv libreadline* temp

Then the directory listings look like this:
[root@localhost lib]# ls -l
total 9320
-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
drwxr-xr-x. 2 root root 4096 Feb 23 11:55 pari
drwxr-xr-x. 2 root root 4096 Apr 29 05:20 temp

and this:

[root@localhost lib]# ls -l temp/
total 4428
-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 18 Apr 19 23:04 libreadline.so.6 -> libreadline.so.6.3
-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

More importantly, the Configure script for the program I want to install completes without a hitch (screen copy follows):

$ ./Configure
Configuring pari-2.9.2 (STABLE)
Checking echo to see how to suppress newlines…
…using -n.
Looking for some tools first …
…gzip is /bin/gzip
…cc is /usr/bin/cc
…gcc is /usr/bin/gcc
…ld is /usr/bin/ld
…perl is /usr/bin/perl
…zcat is /bin/zcat
Choosing C compiler …
GNU compatible compiler: gcc version 4.4.7 20120313 (Red Hat 4.4.7-18) (GCC)
Using mt engine single
Given the previous choices, sizeof(long) is 8 chars.
The internal word representation of a double is not needed (64bit).
==========================================================================
Building for: amd64 running linux (x86-64/GMP kernel) 64-bit version
==========================================================================
C compiler is /usr/bin/gcc -O3 -Wall -fno-strict-aliasing -fomit-frame-pointer -fPIC
Executable linker is /usr/bin/gcc -O3 -Wall -fno-strict-aliasing -fomit-frame-pointer -Wl,–export-dynamic
Dynamic Lib linker is /usr/bin/gcc -shared $(CFLAGS) $(DLCFLAGS) -Wl,-shared,-soname=$(LIBPARI_SONAME)
Looking in C lib for some symbols…
…Found exp2.
…Found log2.
…Found strftime.
…Found getrusage.
…Found gettimeofday.
…Found sigaction.
…Found TIOCGWINSZ.
…Found getrlimit.
…Found stat.
…Found vsnprintf.
…Found mmap.
…Found waitpid.
…Found setsid.
…Found getenv.
…Found isatty.
…Found alarm.
…Found system.
…I did not find dlopen.
Try again, with -ldl this time…
…Found dlopen.
Checking for optional libraries and headers…
Using GNU MP, version 6.1.2
…Found X11 header files in /usr/include/X11
…X11 libraries: -lX11
Hi-Res Graphics: X11
Using GNU readline, version 6.0
Installation prefix ? [/usr/local]
…for architecture-independent files (share-prefix) ? [/usr/local/share]
Installation directories for:
…executables (gp, gphelp) ? [/usr/local/bin]
…libraries (libpari) ? [/usr/local/lib]
…include files ? [/usr/local/include]
…manual pages ? [/usr/local/share/man/man1]
…other system-dependent data ? [/usr/local/lib/pari]
…other system-independent data ? [/usr/local/share/pari]
Default is dynamic executable and shared library
==========================================================================
Extracting examples/Makefile.linux-x86_64
Extracting Olinux-x86_64/Makefile
Extracting Olinux-x86_64/paricfg.h
Extracting Makefile
Extracting scripts and macros
…in doc
…in misc
==========================================================================
Shall we try to build pari 2.9.2 (released) now (y/n)? [n]
Ok. Type “make install” when you are ready
Bye !

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

Added April 29 at 6:25 am

The building and installation of Pari 2.9.2 went successfully:

[david@localhost ~]$ clear

[david@localhost ~]$ gp
GP/PARI CALCULATOR Version 2.9.2 (released)
amd64 running linux (x86-64/GMP-6.1.2 kernel) 64-bit version
compiled: Apr 29 2017, gcc version 4.4.7 20120313 (Red Hat 4.4.7-18) (GCC)
threading engine: single
(readline v6.0 enabled, extended help enabled)

Copyright (C) 2000-2017 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
?

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

 

 

 

Written by meditationatae

April 29, 2017 at 9:53 am

Posted in History

Data on possible/probable 15-vertex, 37-edge unit distance graph

Note: copied from the output of a computer program.

===

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 0
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 0
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 0 1 0 0 0 1 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 = 43
Tests count = 15 has_converged_step = 2616 max_has_converged_step = 2616
rec_diff1 = 39.857967
rec_diff25 = 5.935028
rec_diff50 = 2.601235
rec_diff100 = 0.381244
rec_diff200 = 0.069902
rec_diff400 = 0.005289
rec_diff800 = 0.0000311393226121
rec_diff1200 = 0.0000001835105382
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 1.57 0.58 1.95 1.73 1.00 1.00 1.00 1.95 2.73 1.46 1.91 1.00 2.43 1.46
B 1.57 0.00 1.00 1.57 1.00 1.00 0.58 1.46 0.46 1.73 0.58 0.74 0.74 1.00 1.00
C 0.58 1.00 0.00 1.73 1.37 0.74 0.46 1.00 1.37 2.35 1.00 1.44 0.46 1.91 1.00
D 1.95 1.57 1.73 0.00 0.58 1.00 1.46 1.00 1.95 1.00 1.00 1.00 1.91 1.46 2.43
E 1.73 1.00 1.37 0.58 0.00 0.74 1.00 1.00 1.37 1.00 0.46 0.46 1.44 1.00 1.91
F 1.00 1.00 0.74 1.00 0.74 0.00 0.58 0.46 1.46 1.73 0.58 1.00 1.00 1.57 1.57
G 1.00 0.58 0.46 1.46 1.00 0.58 0.00 1.00 1.00 1.95 0.58 1.00 0.46 1.46 1.00
H 1.00 1.46 1.00 1.00 1.00 0.46 1.00 0.00 1.91 1.91 1.00 1.37 1.37 1.95 1.95
I 1.95 0.46 1.37 1.95 1.37 1.46 1.00 1.91 0.00 1.91 1.00 1.00 1.00 1.00 1.00
J 2.73 1.73 2.35 1.00 1.00 1.73 1.95 1.91 1.91 0.00 1.37 1.00 2.35 1.00 2.73
K 1.46 0.58 1.00 1.00 0.46 0.58 0.58 1.00 1.00 1.37 0.00 0.46 1.00 1.00 1.46
L 1.91 0.74 1.44 1.00 0.46 1.00 1.00 1.37 1.00 1.00 0.46 0.00 1.37 0.58 1.73
M 1.00 0.74 0.46 1.91 1.44 1.00 0.46 1.37 1.00 2.35 1.00 1.37 0.00 1.73 0.58
N 2.43 1.00 1.91 1.46 1.00 1.57 1.46 1.95 1.00 1.00 1.00 0.58 1.73 0.00 1.95
O 1.46 1.00 1.00 2.43 1.91 1.57 1.00 1.95 1.00 2.73 1.46 1.73 0.58 1.95 0.00

TBC …

===

Added:  Mon Mar 20 04:02:36 EDT 2017

A reminder:

Thomas Sauvaget who has a blog named

episodic thoughts

found a 16-vertex graph consisting approximately of two

Moser spindles, plus two more points in a special

configuration:

https://thomas1111.wordpress.com/2015/01/03/on-a-certain-4-chromatic-planar-graph/

He writes in part:

As it happens, if we enforce unit distances at 6~14 and 10~14 then the abscissa of vertex #14 is not 0.5 (which would make things work), but instead

-\frac{895702085}{177666094271969928} \sqrt{514527538436665}+ \frac{415413875483399597}{676176985277553384} \approx 0.49999956608   (and same problem with vertex #15).  ”

===

 

So, I’m thinking that I should not be assuming that vertices in an embedded graph are a unit apart, just because they are 1.0 units apart to within 0.0000001  …

Perhaps I can use the MPFR library, or PARI/gp to

calculate distances between points that appear to be 1.0 units apart, to 50 or more decimals or significant figures …

 

 

Written by meditationatae

March 20, 2017 at 8:00 am

Posted in History

Image of a 15-vertex 35-edge possible unit distance graph

Scanudg15a

Written by meditationatae

March 18, 2017 at 10:54 pm

Posted in History

Using the ldd command with the verbose option

With respect to the readline library, some versions have various symbols (UP, etc.) defined, and some do not.

For PARI/gp on my system, it only works when these various symbols are defined.

 

PARI/gp question: how does one get a history of the commands input at the terminal ?

 

 

We are in the directory:  /usr/local/lib .

ls -l gives output:

-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 Mar 10 08:32 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

 

I single out the libreadline text:

lrwxrwxrwx. 1 root root 16 Feb 23 02:55 libreadline.so -> libreadline.so.6
lrwxrwxrwx. 1 root root 25 Mar 10 08:32 libreadline.so.6 -> /lib64/libreadline.so.6.0

 

The ‘l’ signifies a symbolic link, so that

libreadline.so is an alias name for libreadline.so.6, and

libreadline.so.6 is an alias name for /lib64/libreadline.so.6.0 , and

/lib64/libreadline.so.6.0 is a normal file:

$ ls -l /lib64/libreadline.so.6.0
-rwxr-xr-x. 1 root root 272008 Jun 22 2012 /lib64/libreadline.so.6.0    (272 kbytes ).

 

Now, I try:

$ ldd -v libreadline.so  and I get this:

 

linux-vdso.so.1 => (0x00007ffd3c5fc000)
libtinfo.so.5 => /lib64/libtinfo.so.5 (0x0000003b0fa00000)
libc.so.6 => /lib64/libc.so.6 (0x0000003afce00000)
/lib64/ld-linux-x86-64.so.2 (0x0000003afc600000)

Version information:
./libreadline.so:
libc.so.6 (GLIBC_2.4) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.3) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.3.4) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.11) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.2.5) => /lib64/libc.so.6
/lib64/libtinfo.so.5:
libc.so.6 (GLIBC_2.4) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.3) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.3.4) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.2.5) => /lib64/libc.so.6
/lib64/libc.so.6:
ld-linux-x86-64.so.2 (GLIBC_PRIVATE) => /lib64/ld-linux-x86-64.so.2
ld-linux-x86-64.so.2 (GLIBC_2.3) => /lib64/ld-linux-x86-64.so.2

 

Note: there are no missing symbols.

 

What about libreadline.so.6.3 ? It looks just as good…

 

$ ldd -v libreadline.so.6.3         gives output:

linux-vdso.so.1 => (0x00007ffdd6951000)
libc.so.6 => /lib64/libc.so.6 (0x00007f815ed7e000)
/lib64/ld-linux-x86-64.so.2 (0x0000003afc600000)

Version information:
./libreadline.so.6.3:
libc.so.6 (GLIBC_2.3) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.2.5) => /lib64/libc.so.6
/lib64/libc.so.6:
ld-linux-x86-64.so.2 (GLIBC_PRIVATE) => /lib64/ld-linux-x86-64.so.2
ld-linux-x86-64.so.2 (GLIBC_2.3) => /lib64/ld-linux-x86-64.so.2

===

It looks good too, although  /lib64/libtinfo.so.5 present in first is what defines UP etc.

 

===

Another try, this time with:  libreadline.so.7.0

 

$ ldd -v libreadline.so.7.0
linux-vdso.so.1 => (0x00007fff4e3b2000)
libc.so.6 => /lib64/libc.so.6 (0x00007f301dec9000)
/lib64/ld-linux-x86-64.so.2 (0x0000003afc600000)

Version information:
./libreadline.so.7.0:
libc.so.6 (GLIBC_2.3) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.2.5) => /lib64/libc.so.6
/lib64/libc.so.6:
ld-linux-x86-64.so.2 (GLIBC_PRIVATE) => /lib64/ld-linux-x86-64.so.2
ld-linux-x86-64.so.2 (GLIBC_2.3) => /lib64/ld-linux-x86-64.so.2

 

===

this one also doesn’t have

/lib64/libtinfo.so.5.

===

linux-vdso.so.1 => (0x00007ffe2756a000)
libc.so.6 => /lib64/libc.so.6 (0x0000003afce00000)
/lib64/ld-linux-x86-64.so.2 (0x0000003afc600000)

Version information:
/lib64/libtinfo.so.5:
libc.so.6 (GLIBC_2.4) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.3) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.3.4) => /lib64/libc.so.6
libc.so.6 (GLIBC_2.2.5) => /lib64/libc.so.6
/lib64/libc.so.6:
ld-linux-x86-64.so.2 (GLIBC_PRIVATE) => /lib64/ld-linux-x86-64.so.2
ld-linux-x86-64.so.2 (GLIBC_2.3) => /lib64/ld-linux-x86-64.so.2

===

Written by meditationatae

March 17, 2017 at 6:12 pm

Posted in History

Re: “Best candidate” graph, 14 vertices, udg

The post from a few weeks ago shows a 14-vertex 33-edge probable unit distance graph with 324 4-colorings.

The URL of that blog post =

https://meditationatae.wordpress.com/2017/02/20/best-candidate-graph-14-vertices-udg/

Written by meditationatae

March 14, 2017 at 2:46 pm

Posted in History

Figure of a 13-vertex 28-edge graph

It’s a probable unit distance graph.

It has 356 4-colorings, and is not 3-colorable.

Its adjacency matrix is:

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

 

It also contains as a subgraph the Moser spindle; one of the vertices of the Moser spindle subgraph is the degree 4 (in the Moser spindle) vertex that is uppermost in the figure. Five of the seven vertices in the Moser spindle together with 5 edges amongst these 5 vertices make up a pentagon with bilateral symmetry; by staring enough at the figure, it can be found by me without too much trouble:

Graph13-12ed-Screenshot

Written by meditationatae

March 10, 2017 at 2:58 pm

Posted in History