\datethis @i gb_types.w @*Symmetric Hamiltonian cycles. This program finds all Hamiltonian cycles of an undirected graph in which the mapping $v\mapsto N-1-v$ is an automorphism, such that the same automorphism also applies to the cycle. We use a utility field to record the vertex degrees. @d deg u.I @d mm 8 /* should be even */ @d nn 9 @c #include "gb_graph.h" /* the GraphBase data structures */ #include "gb_basic.h" /* standard graphs */ main() { Graph *g=board(mm,nn,0,0,5,0,0); /* knight moves on rectangular chessboard */ Vertex *x, *z, *tmax; register Vertex *t,*u,*v; register Arc *a,*aa, *yy; register int d; Arc *b,*bb; int count=0,dcount=0; int dmin; @; @; for (v=g->vertices;vvertices+g->n;v++) printf(" %d",v->deg); printf("\n"); /* TEMPORARY CHECK */ if (x->deg<2) { printf("The minimum degree is %d (vertex %s)!\n",x->deg,x->name); return -1; } for (b=x->arcs;b->next;b=b->next) for (bb=b->next;bb;bb=bb->next) { a=b; z=bb->tip; @n-2| from |a->tip| to |z|, avoiding |x|@>; } printf("Altogether %d solutions and %d wannabees.\n",count,dcount); for (v=g->vertices;vvertices+g->n;v++) printf(" %d",v->deg); printf("\n"); /* TEMPORARY CHECK, SHOULD AGREE WITH FORMER VALUES */ } @ We identify each vertex with its symmetric mate, and set the length of an arc to 1 if the arc crosses to the mate instead of staying in the same class. Multiple arcs and self-loops can be introduced in this step. @d mate(v) (Vertex*)(((unsigned long)g->vertices)+ ((unsigned long)(g->vertices+g->n-1))- ((unsigned long)v)) @= for (v=g->vertices;mate(v)>v;v++) for (a=v->arcs;a;a=a->next) { u=mate(a->tip); if (u>a->tip) a->len=0; else { a->len=1; a->tip=u; } } g->n/=2; @ Self-loops caused a subtle bug (my test for |v->deg==1| below failed), and they are of no interest in Hamiltonian circuits. So I'm now getting rid of them. @= for (v=g->vertices;vvertices+g->n;v++) for (a=v->arcs,aa=NULL;a;a=a->next) if (a->tip==v) { if (aa) aa->next=a->next; else v->arcs=a->next; } else aa=a; @ Vertices that have already appeared in the path are taken,'' and their |taken| field is nonzero. Initially we make all those fields zero. @d taken v.I @= @; dmin=g->n; for (v=g->vertices;vvertices+g->n;v++) { v->taken=0; d=0; for (a=v->arcs;a;a=a->next) d++; v->deg=d; if (dark| when |t| is the |k|th vertex of the graph. This program is a typical backtrack program. I am more comfortable doing it with labels and goto statements than with while loops, but some day I may learn my lesson. @d ark x.A @n-2|...@>= v=a->tip; t=g->vertices;@+tmax=t+g->n-1; x->taken=1; a->len+=4; /* the first move is forced'' */ advance: @; try: @; restore: @; backtrack: @; done: @ @= t->ark=a; t++; v=a->tip; v->taken=1; if (v==z) { if (t==tmax && v->deg==1) @; goto backtrack; } yy=NULL; /* |yy| is a forced arc, if any exist */ for (aa=v->arcs;aa;aa=aa->next) { u=aa->tip; d=u->deg-1; if (d==1 && u->taken==0) { if (yy) goto restore; /* restoration will stop at |aa| */ yy=aa; } u->deg=d; } if (yy) { a=yy; a->len+=4; goto advance; } a=v->arcs; @ @= for (a=(t-1)->ark->tip->arcs;a!=aa;a=a->next) a->tip->deg++; @ @= while (a) { if (a->tip->taken==0) { a->len+=2; /* oops, this is unnecessary residue of {\sc SHAMR} */ goto advance; } a=a->next; } restore_all: aa=NULL; /* all moves tried; we fall through to |restore| */ @ Here we come to a subtle point. When a forced move is a duplicated arc, we want to continue with the duplicate arc; we don't want to backtrack! But that isn't the most subtle part. It turns out that we want to consider the duplicate arc {\it previous\/} to the one that worked. (That one should really have been considered forced; if on the other hand the first of two duplicate arcs is selected, the second one will decrease the degree to zero and cannot lead to a complete tour, so we don't want to reconsider it.) Get it? The present logic works only when there are at most two duplicate arcs. @= t--; a=t->ark; a->tip->taken=0; d=a->len; a->len &=1; if (d<4) { a=a->next; goto try; } if (t==g->vertices) goto done; for (aa=(t-1)->ark->tip->arcs;aa!=a;aa=aa->next) if (aa->tip==a->tip) { aa->len+=4; a=aa; goto advance; } goto restore_all; /* the move was forced */ @ @= { int s=0; for (u=g->vertices;uark->len&1; if (s) { count++; if (count%100000==0) { /* use 100000 for the $8\times8$ */ printf("%d: %s",count,x->name); for (u=g->vertices;uark->len&1? "*":" ",u->ark->tip->name); printf("\n"); } } else { dcount++; if (dcount%100000==0) { /* use 1 for small cases */ printf(">%d: %s",dcount,x->name); for (u=g->vertices;uark->len&1? "*":" ",u->ark->tip->name); printf("\n"); } } } @*Index.