@*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); } @; } } @ @= if (argc!=2 || sscanf(argv[1],"%d", &seed)!=1) { fprintf(stderr,"Usage: %s seed < graphs\n", argv[0]); exit(-1); } gb_init_rand(seed); for (k=0;k= for (i=0;i; for (h=i=0;i>1; /* each |hash[i]| is odd */ printf("%08x\n", h); @ We start by creating the breadth-first search tree for vertices reachable from~|i|. Vertices at distance~|j| are tagged with |ran[j]|. @= { for (k=0;k; hash[i]=h; } @ The key nontrivial step is to modify the tag of each vertex~|v| at a given level~|q| in the BFS tree, multiplying it by the product of |ran[j]-tag[w]| over |v|'s neighbors~|w|. (The multiplication is mod $2^{32}$. Those factors are odd, because |ran[j]| is even and |tag[w]| is odd.) @= { for (k=start[q];k=start[q];k--) v=vert[k],tag[v]=ttag[v]; } @ At this point |p=start[j]=start[j+1]| is the size of the component that contains vertex~|i|; we might have \$p= for (h=1,q=j-1;q>=0;q--,j++) @; @*Index.