@i gb_types.w
\def\given{\!\mid\!}
@*Intro. Given a graph $G$ on the vertex set $V,ドル and a vertex $s\in V,ドル
this program finds all possible simple paths from $s$ that could be
traversed by Warnsdorf's (nondeterministic) rule.
It reports their lengths and their final vertices.
Warndorf's rule is simply this: At a given stage, we have covered
a set of vertices~$U,ドル with a path from $s$ to some $v\in U$.
If $v$ has no neighbors $\notin U,ドル stop. Otherwise
cover a neighbor $u\notin U$ whose degree in $G\given(V-U)$ is minimum,
and set $v\gets u,ドル and repeat.
An optional extension to that rule is also implemented: One or more
vertices can be mentioned as preferred candidates for the end of the path.
(For example, we might want to mention a neighbor of $s,ドル because
that would imply a Hamiltonian cycle.)
This implementation has an interesting artifact: If the same vertex is
mentioned more than once as a target, it essentially disappears from the
graph. Therefore we could, say, try for a Hamiltonian path that
ends with $a,ドル $b,ドル $c$ by listing $a,ドル $b,ドル $b,ドル $c,ドル $c$ on the
command line.
@d maxn 1000
@c
#include <stdio.h>
#include <stdlib.h>
#include "gb_graph.h"
#include "gb_save.h"
unsigned long long nodes,lnodes[maxn];
unsigned long long count,hcount,lcount[maxn],vcount[maxn];
double pr[maxn],vpr[maxn],lpr[maxn],totalpr;
Vertex *start,*vstack[maxn];
int sptr,bestl;
int mv[maxn],ht[maxn];
@<subroutines@>@;
main(int argc, char*argv[]) {
 register int d,k,l,x;
 register Arc *a;
 register Graph *g;
 register Vertex *u,*v;
 register double p;
 @<process the command line@>;
 @<backtrack through the Warnsdorf tree@>;
 @<output the results@>;
}
@ @<process the command line@>=
if (argc<3) { fprintf(stderr,"Usage: %s foo.gb start [dest]*\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 --- I can't deal with more than %d vertices!\n",
 maxn-1);
 exit(-6);
}
start=findvert(g,argv[2]);
@ @<sub...@>=
Vertex *findvert(Graph *g, char*str) {
 register Vertex *v;
 for (v=g->vertices;v<g->vertices+g->n;v++)
 if (strcmp(v->name,str)==0) break;
 if (v<g->vertices+g->n) return v;
 fprintf(stderr,"Vertex %s isn't in the graph!\n",
 str);
 exit(-3);
}
@ Again I follow ye olde structure of Algorithm 7.2.2B.
@d deg u.I
@d covered v.I
@<backtrack through the Warnsdorf tree@>=
b1:@+for (v=g->vertices;v<g->vertices+g->n;v++) {
 for (d=0,a=v->arcs;a;a=a->next) d++;
 v->deg=d,v->covered=0;
 }
 for (k=3;argv[k];k++)
 findvert(g,argv[k])->deg+=g->n; /* make this vertex undesirable */
 l=0,v=start,ht[0]=0;
 vstack[0]=v,sptr=1,x=0;
 p=1.0;
b2: nodes++, lnodes[l]++; /* at this point &#124;v=vstack[x]&#124; */
 mv[l]=x, x=ht[++l]=sptr;
 p=p/(double)(ht[l]-ht[l-1]);
 pr[l]=p; /* the probability that a random tree walk would get here */
 v->covered=1;
 for (d=g->n+g->n,a=v->arcs;a;a=a->next) {
 u=a->tip;
 if (u->covered) continue;
 k=u->deg-1, u->deg=k;
 if (k>d) continue;
 if (k<d) d=k,sptr=x; vstack[sptr++]=u; } if (x==sptr) @<report end of path and &#124;goto b5&#124;@>;
b3: v=vstack[x];
 goto b2;
b4:@+if (++x<sptr) goto b3; b5:@+if (--l) { x=mv[l],p=pr[l],v=vstack[x],sptr=ht[l+1]; v->covered=0;
 for (a=v->arcs;a;a=a->next) {
 u=a->tip;
 if (u->covered) continue;
 u->deg++;
 }
 goto b4;
 }
@ @<report end of path and &#124;goto b5&#124;@>=
{
 count++, lcount[l]++, lpr[l]+=p, totalpr+=p;
 nodes++, lnodes[l]++; /* count the solution nodes with the branch nodes */
 if (l>=bestl) {
 bestl=l;
 @<publish the current path@>;
 if (l==g->n) hcount++,vcount[v-g->vertices]++,vpr[v-g->vertices]+=p;
 }
 goto b5; 
}
@ @<publish the current path@>=
{
 for (k=0;k<l;k++) printf("%s ", vstack[mv[k]]->name);
 printf("(%d,%g) #%llu, %g\n",
 l,p,count,totalpr); @q)@>;
}
@ @<output the results@>=
fprintf(stderr,"Altogether %llu nodes, %llu paths, %llu hpaths.\n",
 nodes,count,hcount);
for (l=0;l<=bestl;l++) { fprintf(stderr," Level %d: %12llu node%s", l,lnodes[l],lnodes[l]==1?"":"s"); if (lcount[l]) fprintf(stderr,", %llu paths (%g)", lcount[l],lpr[l]/totalpr); fprintf(stderr,"\n"); } for (k=0;k<g->n;k++) if (vcount[k])
 fprintf(stderr," hamiltonian to %s: %12llu, %g\n",
 (g->vertices+k)->name,vcount[k],vpr[k]/totalpr);
@ Here's a routine that I might use while debugging.
@<sub...@>=
void print_vert(Vertex *v) {
 fprintf(stderr," %s %s%ld%s\n",
 v->name,v->covered?"(":"",v->deg,v->covered?")":"");
}
@ And another, to display the state of {\it all\/} the vertices.
@<sub...@>=
void print_state(Graph *g) {
 register int k;
 for (k=0;k<g->n;k++) print_vert(g->vertices+k);
}
@ Yet another, to show the neighbors of a given vertex and their
current degrees.
@<sub...@>=
void print_arcs(Vertex *v) {
 register Arc *a;
 register Vertex *u;
 fprintf(stderr,"%s ->",
 v->name);
 for (a=v->arcs;a;a=a->next) {
 u=a->tip;
 if (u->covered) fprintf(stderr," (%s)",
 u->name)@q)@>;
 else fprintf(stderr," %s(%ld)",
 u->name,u->deg);
 }
 fprintf(stderr,"\n");
}
@*Index.
</div><div class="naked_ctrl">
<form action="/index.cgi/speech" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="https://cs.stanford.edu/~knuth/programs/back-warnsdorf.w">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="https://cs.stanford.edu/~knuth/programs/back-warnsdorf.w" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech" selected="selected">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>