\def\adj{\mathrel{\!\mathrel-\mkern-8mu\mathrel-\mkern-8mu\mathrel-\!}} @i gb_types.w @*Intro. OK, you've heard about {\mc SIGGRAPH}; what's this? {\mc GRAPH-SIG} is an experimental program to find potential equivalence classes in automorphism testing. Given a graph $G$ and a vertex $v_0$, we compute signatures'' of all vertices such that, if there's an automorphism that fixes $v_0$ and takes $v$ to $v'$, then $v$ and $v'$ will have the same signature. I plan to generalize the idea, but in this test case I just proceed as follows: First I compute level~0 signatures, which are just the distances from $v_0$. Then, given level~$k$ signatures~$\sigma_k$, I compute signatures $\sigma_{k+1}(v)=\prod_{u\adj v}(x-\sigma_k(u))$, where $x$ is a random integer and the multiplication is done mod~$2^{64}$. We keep going until reaching a round where no class is further refined. My tentative name for these signatures is lookahead invariants.'' (Notes for the future: If there's an automorphism that takes $v_0$ into $v_0'$, then the multiset of signatures computed with respect to $v_0$ will be the same as the multiset computed with respect to $v_0'$, after each round. Also we can generalize to automorphisms that fix $k$ vertices, by defining level~0 signatures as the ordered sequence of distances from $v_0$, \dots,~$v_{k-1}$. Universal hashing schemes conveniently map such an ordered sequence into a single number.) @d maxn 100 /* upper bound on vertices in the graph */ @c #include #include #include #include "gb_graph.h" #include "gb_save.h" #include "gb_flip.h" long sg[maxn]; /* new signatures found in current class */ Vertex *hd[maxn],*tl[maxn]; /* subdivisions of current class */ main(int argc,char*argv[]) { register int i,j,k,r,change; register Graph *g; register Vertex *u,*v; register Arc *a,*b; register long x,s; Vertex *v0,*prev,*head; @; @; for (change=1,r=1;change;r++) { change=0; @; } } @ @= if (argc!=3) { fprintf(stderr,"Usage: %s foo.gb v0\n", argv[0]); exit(-1); } g=restore_graph(argv[1]); if (!g) { fprintf(stderr,"I couldn't reconstruct graph %s!\n", argv[1]); exit(-2); } if (g->n>maxn) { fprintf(stderr,"Recompile me: g->n=%ld, maxn=%d!\n", g->n,maxn); exit(-3); } gb_init_rand(0); /* the seed doesn't matter much */ for (v=g->vertices;vvertices+g->n;v++) if (strcmp(v->name,argv[2])==0) break; if (v==g->vertices+g->n) { fprintf(stderr,"I can't find a vertex named `%s'!\n", argv[2]); exit(-9); } v0=v; @ Vertices with the same signature are linked cyclically. As mentioned above, we start by simply computing distances from~$v_0$. @d sig w.I /* signature of a vertex */ @d link u.V /* link field in a circular list */ @d tag v.I /* to what extent have we processed the vertex? */ @= printf("Initial round:\n"); for (v=g->vertices;vvertices+g->n;v++) v->sig=-1,v->tag=0; v0->sig=0,v0->link=v0,k=1,v=v0; while (v) { prev=head=NULL; while (1) { printf(" %s dist %ld\n", v->name,v->sig); @; v->tag=k; v=v->link; if (v->tag) break; } if (prev==NULL) break; /* all vertices reachable from $v_0$ have been seen */ head->link=prev; /* close the cycle */ v=prev,k++; } @ @= for (a=v->arcs;a;a=a->next) { u=a->tip; if (u->sig<0) { u->sig=k; if (prev==NULL) head=u; else u->link=prev; prev=u; } } @ Now comes the fun part. As we pass from $\sigma_{r-1}$ to $\sigma_r$, each equivalence class becomes one or more classes. @d oldsig z.I @= printf("Round %d:\n", r); for (v=g->vertices;vvertices+g->n;v++) v->oldsig=v->sig; k++; /* |k| is a unique stamp to identify this round */ x=(gb_next_rand()<<1)+1; /* pseudorandom number used for new signatures */ for (v=g->vertices;vvertices+g->n;v++) if (v->tag>0) { if (v->tag==k) continue; if (v->link==v) { printf(" %s is fixed\n", v->name); /* class of size 1 */ v->tag=-k; /* we needn't pursue it further */ continue; } for (j=0;v->tag!=k;v=u) { u=v->link; @; printf(" %s %lx\n", v->name,s); v->sig=s; for (i=0,sg[j]=s;sg[i]!=s;i++); if (i==j) hd[j]=tl[j]=v,j++; /* a new cyclic list begins */ else v->link=tl[i],tl[i]=v; /* continue building an existing list */ v->tag=k; } for (i=0;ilink=tl[i]; /* complete the cycles */ if (j>1) change=1; } @ @= for (s=1,a=v->arcs;a;a=a->next) s*=x-a->tip->oldsig; @*Index.