@*Intro. This program is an experiment.
I'm trying to find a function $h(G)$, defined for any (simple)
graph on~$n$ vertices, that has the following properties:
\smallskip
\itemitem{0)} $h(G)$ can be computed rapidly, with a fairly short program.
\itemitem{1)} $0\le h(G)<2^{32}$.
\itemitem{2)} $h(G)=h(G')$ whenever $G$ is isomorphic to $G'$.
\itemitem{3)} $h(G)\ne h(G')$ whenever $G$ is {\it not\/} isomorphic to $G'$.
\smallskip\noindent
I'm thinking of $n<10$, say; there are 274668 simple graphs with 9 vertices.
Of course there are oodles of functions $h(G)$ that satisfy (0), (1), and~(2).
But in order to satisfy property~(3), I can't think of any plausible method
that needs only $O(n)$ steps. My best idea so far takes time $O(n^2)$,
and consists of $n$ linear-time hashes on the $n$ graphs obtained by
giving a special mark to each of the vertices in turn.
(When the graph has $m$ edges, I could try instead for $m$ linear-time
hashes on the graphs obtained by marking each of the {\it edges\/} in turn.
My goal, however, is to perform approximately $cn^2$ operations
where $c$ is as small as possible. Hence I'm experimenting first with the
simplest methods that seem plausible, before resorting to anything fancier.)
The method adopted here is based on a multivariate polynomial that is an
invariant of any graph. By evaluating this polynomial at a ``random'' point,
mod~$2^{32}$, I'm hoping to have a suitable hash.
Input to this program on |stdin| is a list of simple graphs, one per line,
in the format defined by {\mc G6-TO-EZ}.
(Different graphs in the input need not actually have the same number of
vertices.) The output is the
sequence of (hexadecimal) hash codes, again one per line, in the same order.
{\it Note, 07 December 2020:\/}\enspace Success --- almost! I tried
seeds 1000--1999, and found two cases with only one collision:
1286 and 1654. So I used the seed 1286 to make the files in \.{/home/lib/graphs};
see the file \.{/home/lib/graphs/collision} for details.
There's no real ambiguity, because one graph has 18 edges,
the other has 28 edges. (Both have 9 vertices.)
@ The command line contains a random seed. If the polynomials defined
here are truly distinct for non-isomorphic graphs --- and I really don't
understand the situation well enough to be sure of that! ---
I'm hoping to find a seed that distinguishes all of them.
@d maxn 11 /* beware: there are more than a billion 11-vertex graphs */
@d maxrn 50 /* only this many ``random'' numbers are generated */
@d bufsize 120 /* 112 is enough to handle $n=11$ */
@c
#include
#include
#include "gb_flip.h"
char buf[bufsize];
int seed; /* command-line parameter */
unsigned int ran[maxrn]; /* the ``random'' numbers used --- all even */
unsigned int hash[maxn]; /* individual hashes for different marked vertices */
unsigned int tag[maxn],ttag[maxn]; /* intermediate hash values on vertices */
int deg[maxn]; /* degree of each vertex */
int nbr[maxn][maxn]; /* edges at each vertex */
int vert[maxn]; /* vertices found breadth-first */
int start[maxn+2]={0,1}; /* boundaries between levels in |vert| */
main(int argc,char*argv[]) {
register int i,j,k,l,n,p,q,v,w,vvv;
register unsigned int h,t;
@;
while (1) {
if (!fgets(buf,bufsize,stdin)) break;
for (n=k=0;;k+=2) {
if (buf[k]=='0') continue; /* isolated vertex is ignored */
i=buf[k]-'a',j=buf[k+1]-'a';
if (i<0 || j<0 || i>maxn || j>maxn) break;
while (i>=n) deg[n++]=0;
while (j>=n) deg[n++]=0;
nbr[i][deg[i]++]=j;
nbr[j][deg[j]++]=i;
}
if (buf[k]!='\n') {
fprintf(stderr,"bad format: %s",
buf);
exit(-2);
}
@