\datethis @s try x @i gb_types.w @*Hamiltonian cycles. This program finds all Hamiltonian cycles of an undirected graph. [It's a slight revision of the program published in my paper Mini-indexes for literate programs,'' {\sl Software---Concepts and Tools\/ \bf15} (1994), 2--11.] The input graph should be in Stanford GraphBase format, and should be named on the command line as, for example, \.{foo.gb}. An optional second command-line parameter is a modulus |m|, which causes every $m$th solution to be printed. We use a utility field to record the vertex degrees. @d deg u.I @c #include "gb_graph.h" /* the GraphBase data structures */ #include "gb_save.h" /* |restore_graph| */ main(int argc,char *argv[]) { Graph *g; Vertex *x,*y,*z, *tmax; register Vertex *t,*u,*v; register Arc *a,*aa; register int d; Arc *b,*bb; int count=0; int dmin,modulus; @; @; 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) { v=b->tip; z=bb->tip; @n-2| from |v| to |z|, avoiding |x|@>; } printf("Altogether %d solutions.\n",count); for (v=g->vertices;vvertices+g->n;v++) printf(" %d",v->deg); printf("\n"); /* TEMPORARY CHECK, SHOULD AGREE WITH FORMER VALUES */ } @ @= if (argc>1) g=restore_graph(argv[1]);@+ else g=NULL; if (argc<3 || sscanf(argv[2],"%d",&modulus)!=1) modulus=1000000000; if (!g || modulus<=0) { fprintf(stderr,"Usage: %s foo.gb [modulus]\n",argv[0]); exit(-1); } @ 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 (dvert| when |t| is the |k|th vertex of the graph. If the move was not forced, |t->ark| will point to the Arc record representing the edge from |t->vert| to |(t+1)->vert|; otherwise |t->ark| will be |NULL|. 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 vert w.V @d ark x.A @n-2|...@>= t=g->vertices;@+tmax=t+g->n-1; x->taken=1;@+t->vert=x; t->ark=NULL; advance: @; try: @; restore: @; backtrack: @; done: @ @= t++; t->vert=v; v->taken=1; if (v==z) { if (t==tmax) @; goto backtrack; } for (aa=v->arcs,y=NULL;aa;aa=aa->next) { u=aa->tip; d=u->deg-1; if (d==1 && u->taken==0) { if (y) goto restore; /* restoration will stop at |aa| */ y=u; } u->deg=d; } if (y) { t->ark=NULL; v=y; goto advance; } a=v->arcs; @ @= for (a=t->vert->arcs;a!=aa;a=a->next) a->tip->deg++; @ @= while (a) { v=a->tip; if (v->taken==0) { t->ark=a; goto advance; } a=a->next; } restore_all: aa=NULL; /* all moves tried; we fall through to |restore| */ @ @= t->vert->taken=0; t--; if (t->ark) { a=t->ark->next; goto try; } if (t==g->vertices) goto done; goto restore_all; /* the move was forced */ @ @= { count++; if (count%modulus==0) { printf("%d: ",count); for (u=g->vertices;u<=tmax;u++) printf("%s ",u->vert->name); printf("\n"); } } @*Index.