\datethis
@i gb_types.w
@*Intro. This is an experimental program to find ``rooted''
graceful labelings of a given graph. (Some of the vertex labels may be
prespecified. Every edge has a vertex in common with a longer edge, or
has at least one prespecified vertex, except possibly for edge |m| itself.)
I hacked this code from {\mc BACK-GRACEFUL-ROOTED}, which considered the
special case where vertex~0 (only) was prespecified, and which looked
exhaustively for {\it all\/} solutions. By contrast, this program
is intended for large graphs, where we feel lucky to find even a single
solution and we can't hope to find them all. Therefore we'll use
randomization with frequent restarts.
(Thanks to Tom Rokicki for many of the ideas used here.)
@d maxn 64 /* at most this many vertices */
@d maxm 128 /* at most this many edges */
@d interval 100 /* print `\..' to show progress, every so often */
@c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "gb_graph.h"
#include "gb_save.h"
#include "gb_flip.h"
@<global variables@>;
main (int argc,char*argv[]) {
 register int i,j,k,l,m,n,p,q,r,t,bad,vv,ll;
 Graph *g;
 Vertex *v,*w;
 Arc *a;
 @<process the command line, and set &#124;prespec&#124; to the prespecified labelings@>;
 @<set up the fixed data structures@>;
 while (1) {
 rounds++;
 if ((rounds%interval)==0) fprintf(stderr,".");
 @<set the cutoff for a new trial@>;
 @<backtrack for at most &#124;T&#124; steps@>;
 }
}
@ The command line names a graph in SGB format, followed by a minimum cutoff
time $T_{\rm min}$ (measured in search tree nodes examined before restarting).
Then comes a random seed, so that results of this run can be replicated
if necessary.
Then come zero or more prespecifications, in the form `\.{VERTNAME=label}'.
@<process the command line...@>=
if (argc<4 &#124;&#124; sscanf(argv[2],"%lld", &Tmin)!=1 &#124;&#124; sscanf(argv[3],"%d", &seed)!=1) { fprintf(stderr,"Usage: %s foo.gb Tmin seed [VERTEX=label...]\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); } m=g->m/2,n=g->n;
if (m>maxm) {
 fprintf(stderr,"Sorry, at present I require m<=%d!\n",maxm); exit(-3); } if (n>maxn) {
 fprintf(stderr,"Sorry, at present I require n<=%d!\n",maxn); exit(-4); } for (k=4;argv[k];k++) { for (i=1;argv[k][i];i++) if (argv[k][i]=='=') break; if (!argv[k][i] &#124;&#124; sscanf(&argv[k][i+1],"%d", &label)!=1 &#124;&#124; label<0 &#124;&#124; label>m) {
 fprintf(stderr,"spec `%s' doesn't have the form `VERTEX=label'!\n",
 argv[k]);
 exit(-3);
 }
 argv[k][i]=0;
 for (j=0;j<n;j++) if (strcmp((g->vertices+j)->name,argv[k])==0) break;
 if (j==n) {
 fprintf(stderr,"There's no vertex named `%s'!\n",
 argv[k]);
 exit(-5);
 }
 if (verttoprespec[j]) {
 fprintf(stderr,"Vertex %s was already specified!\n",
 (g->vertices+j)->name);
 exit(-6);
 }
 verttoprespec[j]=1;
 if (!xprespec && (label==0 &#124;&#124; label==m)) xprespec=1,prespec[0]=(j<<8)+label; else prespec[prespecptr++]=(j<<8)+label; } gb_init_rand(seed); fprintf(stderr,"OK, I've got a graph with %d vertices, %d edges.\n", n,m); @ @<set up the fixed data structures@>=
for (k=0;k<n;k++) { v=g->vertices+k;
 for (a=v->arcs;a;a=a->next) {
 w=a->tip;
 edges[k][deg[k]++]=w-g->vertices;
 }
}
for (k=0;k<prespecptr;k++) moves[k]=1,move[k][0]=prespec[k]; @ Las Vegas algorithms like this one are best controlled by multiples of the ``reluctant doubling'' sequence defined by Luby, Sinclair, and Zuckerman (see equation 7.2.2.2--(131) in {\sl TAOCP\/}), unless we already know a pretty good cutoff value. @<set the cutoff for a new trial@>=
T=Tmin*reluctant_v;
if ((reluctant_u & -reluctant_u)!=reluctant_v) reluctant_v<<=1; else reluctant_u++,reluctant_v=1; @ @<glob...@>=
int vbose=0; /* set this nonzero to watch me work */
int rounds; /* how many random trials have we started? */
long long nodes; /* how many nodes have we started on this round? */
long long reluctant_u=1, reluctant_v=1; /* restart parameters */
long long T; /* cutoff time for the current random trial */
long long Tmin; /* minimum cutoff time (from the command line) */
int seed; /* seed for &#124;gb_init_rand&#124; */
int label; /* a label value read from &#124;argv[k]&#124; */
int prespec[maxn]; /* prespecified labels */
int verttoprespec[maxn]; /* has this vertex been prespecified? */
int prespecptr=1; /* how many are prespecified? */
int xprespec; /* did any of them specify label 0 or label &#124;m&#124;? */
@*Data structures.
The vertices are internally numbered from 0 to &#124;n-1&#124;.
Vertex &#124;v&#124; has &#124;deg[v]&#124; neighbors, and they appear in the first
&#124;deg[v]&#124; slots of &#124;edges[v]&#124;. Its label is &#124;verttolab[v]&#124;; but &#124;verttolab[v]=-1&#124;
if &#124;v&#124; hasn't yet been labeled.
Labels potentially range from 0 to~&#124;m&#124;.
If label &#124;l&#124; hasn't yet been used, &#124;labunlab[l]&#124; is negative,
and &#124;labtovert[l]&#124; is undefined.
Otherwise &#124;labtovert[l]&#124; is the vertex labeled~&#124;l&#124;, and
&#124;labunlab[l]&#124; is the number of unlabeled neighbors of that vertex.
For each &#124;q&#124; between 1 and~&#124;m&#124;, &#124;edgecount[q]&#124; is the number of
edges labeled~&#124;q&#124;. (This number might momentarily exceed~1, although
it will be exactly equal to~1 when the labeling is graceful.)
@<glob...@>=
int deg[maxn]; /* how many neighbors of &#124;v&#124;? */
int edges[maxn][maxm]; /* their identities */
int verttolab[maxn]; /* what is &#124;v&#124;'s label? */
int labtovert[maxm+1]; /* what vertex &#124;v[l]&#124; is labeled &#124;l&#124;? */
int labunlab[maxm+1]; /* how many unlabeled neighbors does &#124;v[l]&#124; have? */
int edgecount[maxm+1]; /* how many edges are labeled &#124;q&#124;? */
@ We begin by converting from Stanford GraphBase format to the data
structures used here.
@<initialize the data structures@>=
for (k=0;k<n;k++) { verttolab[k]=-1; } for (q=0;q<=m;q++) labunlab[q]=-1,edgecount[q]=0; @*Backtracking. The main computation is based on Walker's backtrack method, Algorithm~7.2.2W. It's an implicit recursion, spelled out so that the costs of updating and downdating are made explicit. @<backtrack for at most &#124;T&#124; steps@>=
w1:@+@<initialize the data structures@>;
 l=0,nodes=0;
 if (!xprespec) {
 while (1) {
 vv=(n*(unsigned long long)gb_next_rand())>>31;
 if (!verttoprespec[vv]) break;
 }
 move[0][0]=vv<<8; } w2:@+if (++nodes>T) goto done;
 if (l<prespecptr) { r=1; goto w3; } q=target[l-1]; for (q=(q?q-1:m);edgecount[q];q--) ; if (q==0) @<visit a solution and &#124;goto done&#124;@>;
 target[l]=q;
 @<determine the &#124;r&#124; potential moves that might create edge &#124;q&#124;@>;
 @<shuffle those moves@>;
 moves[l]=r;
w3:@+if (r>0) {
 t=move[l][--r];
 vv=t>>8,ll=t&0xff;
 if (vbose) @<show this potential move@>;
 @<update the edge counts that would result from &#124;verttolab[vv]=ll&#124;, setting &#124;bad&#124; nonzero if any of them would exceed~1, also setting &#124;p&#124; to the number of unlabeled neighbors of &#124;vv&#124;@>;
 if (bad) goto w4a;
 @<give label &#124;ll&#124; to vertex &#124;vv&#124;@>;
 x[l++]=r;
 goto w2;
}
w4:@+if (--l>=0) {
 r=x[l],t=move[l][r],vv=t>>8,ll=t&0xff;
 @<take label &#124;ll&#124; from vertex &#124;vv&#124;@>;
w4a:@+@<downdate the edge counts that would result from &#124;verttolab[vv]=ll&#124;@>;
 goto w3;
 }
done:
@ @<show this potential move@>=
if (target[l]) fprintf(stderr,"L%d: %s=%d (%d of %d for edge %d)\n",
 l,(g->vertices+vv)->name,ll,moves[l]-r,moves[l],target[l]);
else fprintf(stderr,"L%d: %s=%d (prespecified)\n",
 l,(g->vertices+vv)->name,ll);
@ @<visit a solution and &#124;goto done&#124;@>=
{
 count++;
 fprintf(stderr,"\n");
 for (k=0;k<=m;k++) if (labunlab[k]>=0) {
 if (labunlab[k]>0)
 fprintf(stderr,"This can't happen!\n");
 vv=labtovert[k];
 printf("%s=%d ",
 (g->vertices+vv)->name,k);
 }
 printf("#%d (round %d, step %lld\n",
 count,rounds,nodes);
 fflush(stdout);
 goto done;
}
@ By giving an arbitrary permutation to the list of possible moves,
we're providing the maximum randomization over the entire search tree for
all rooted labelings that meet the prespecifications.
I don't think this will add a significant amount to the running time.
But if it does, we could back off by doing only a partial shuffle
(for example, only on certain levels, or a maximum of 10 swaps, or \dots).
@<shuffle those moves@>=
for (q=r-1;q>0;q--) {
 p=((q+1)*((unsigned long long)gb_next_rand()))>>31;
 t=move[l][p];
 move[l][p]=move[l][q];
 move[l][q]=t;
}
@ I think this is the inner loop.
@<determine the &#124;r&#124; potential moves that might create edge &#124;q&#124;@>=
for (r=j=0,k=q;k<=m;j++,k++) { if (labunlab[j]>0 && labunlab[k]<0) { for (vv=labtovert[j],i=deg[vv]-1;i>=0;i--) {
 t=verttolab[edges[vv][i]];
 if (t<0) move[l][r++]=(edges[vv][i]<<8)+k; } }@+else if (labunlab[j]<0 && labunlab[k]>0) {
 for (vv=labtovert[k],i=deg[vv]-1;i>=0;i--) {
 t=verttolab[edges[vv][i]];
 if (t<0) move[l][r++]=(edges[vv][i]<<8)+j; } } } @ And this loop too is pretty much ``inner.'' @<update the edge counts that would result from &#124;verttolab[vv]=ll&#124;...@>=
for (p=deg[vv],i=p-1,bad=0;i>=0;i--) {
 t=verttolab[edges[vv][i]];
 if (t>=0) {
 p--;
 q=abs(t-ll);
 t=edgecount[q], bad&#124;=t;
 edgecount[q]=t+1;
 }
}
@ Maybe the last line here will go faster if rewritten
`&#124;edgecount[abs(t-ll)]-=(t>=0)&#124;', because of branch prediction?
If so, are modern compilers smart enough to see this?
@<downdate the edge counts that would result from &#124;verttolab[vv]=ll&#124;@>=
for (i=deg[vv]-1;i>=0;i--) {
 t=verttolab[edges[vv][i]];
 if (t>=0) edgecount[abs(t-ll)]--;
}
@ The value of &#124;p&#124; has been set up for us nicely at this point.
We need to perform another loop, but this one isn't needed quite so often.
@<give label &#124;ll&#124; to vertex &#124;vv&#124;@>=
verttolab[vv]=ll,labtovert[ll]=vv,labunlab[ll]=p;
for (i=deg[vv]-1;i>=0;i--) {
 t=verttolab[edges[vv][i]];
 if (t>=0) labunlab[t]--;
}
@ @<take label &#124;ll&#124; from vertex &#124;vv&#124;@>=
for (i=deg[vv]-1;i>=0;i--) {
 t=verttolab[edges[vv][i]];
 if (t>=0) labunlab[t]++;
}
verttolab[vv]=labunlab[ll]=-1;
@ @<glob...@>=
int count; /* this many solutions found so far */
int target[maxn]; /* the edge we try to set, on each level */
int move[maxn][maxm]; /* the things we want to try, on each level */
int x[maxn]; /* the moves currently being tried, on each level */
int moves[maxn]; /* used in verbose tracing only */
@*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-graceful-rooted-randomrestarts.w">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="https://cs.stanford.edu/~knuth/programs/back-graceful-rooted-randomrestarts.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>