@*Intro. Here's an easy way to calculate the number of graceful labelings that
have $m$ edges and $n$ nonisolated vertices, for $0\le n\le m+1$,
given~$m>1$. I subdivide into connected and nonconnected graphs.
The idea is to run through all $m$-tuples $(x_1,\ldots,x_m)$ with
$0\le x_j\le m-j$; edge $j$ will go from the vertex labeled $x_j$
to the vertex labeled $x_j+j$.
I consider only the labelings in which $x_{m-1}=1$; in other words,
I assume that edge $m-1$ runs from 1~to~$m$.
(These are in one-to-one correspondence with the labelings for which that
edge runs from 0~to~$m{-}1$.) But I multiply all the answers by~2;
hence the total over all $n$ is exactly~$m!$.
I could go through those $m$-tuples in some sort of Gray code order,
with only one $x_j$ changing at a time. But I'm not trying to
be tricky or extremely efficient. So I simply use reverse colexicographic order.
That is, for each choice of $(x_{j+1},\ldots,x_m)$, I run through the
possibilities for~$x_j$ from $m-j$ to~0, in decreasing order.
@d maxm 20 /* this is plenty big, because $20!$ is a 61-bit number */
@ I do, however, want to have some fun with data structures.
Every vertex is represented by its label. Vertex~$v$, for $0\le v\le m$,
is isolated if and only if label~$v$ has not been used in any of
the edges. (In particular, vertices 0, 1, and~$m$ are never isolated,
because of the assumption above.)
It's easy to maintain, for each vertex, a linked list of all
its neighbors.
These lists are stacks, since they change in first-in-last-out fashion.
It's also easy to maintain a dynamic union-find structure, because
of the first-in-last-out behavior of this algorithm.
@ OK, let's get going.
@c
#include
#include
int mm; /* command-line parameter */
@;
main(int argc,char*argv[]) {
register j,k,l,m;
@;
@;
while (1) {
@;
@;
}
done:@+@;
}
@ @=
if (argc!=2 || sscanf(argv[1],"%d",
&mm)!=1) {
fprintf(stderr,"Usage: %s m\n",
argv[0]);
exit(-1);
}
m=mm;
if (m<2 || m>maxm) {
fprintf(stderr,"Sorry, m must be between 2 and %d!\n",
maxm);
exit(-2);
}
@ @=
for (j=1;x[j]==0;j++) {
@;
}
if (j==m-1) goto done;
@;
x[j]--;
@;
for (j--;j;j--) {
x[j]=m-j;
@;
}
@*Graceful structures.
An unusual --- indeed, somewhat amazing --- data structure works well
with graceful graphs.
Suppose $v$ has neighbors $w_1$, \dots, $w_t$. Let $f_v(w)=w-v$,
if $w>v$; $f_v(w)=m+v-w$, if $w=
@;
for (j=m;j;j--) {
x[j]=m-j;
@;
}
@ @=
{
register int p,u,v,uu,vv;
u=x[j];
v=u+j;
@;
p=arcs[u];
if (!p) active++;
link[j]=p, arcs[u]=j;
p=arcs[v];
if (!p) active++;
link[m+j]=p, arcs[v]=m+j;
}
@ @=
{
register int p,u,v,uu,vv;
u=x[j];
v=u+j;
p=link[m+j]; /* at this point |arcs[v]=m+j| */
arcs[v]=p;
if (!p) active--;
p=link[j]; /* at this point |arcs[u]=j| */
arcs[u]=p;
if (!p) active--;
@;
}
@ Two vertices are equivalent if they belong to the same component.
We use a classic union-find data structure to keep of equivalences:
The invariant relations state that
|parent[v]<0| and |size[v]=c| if |v| is the root of an
equivalence class of size~|c|; otherwise |parent[v]| points to
an equivalent vertex that is nearer the root. These trees have
at most $\lg m$ levels, because we never merge a tree of size~|c|
into a tree of size |=
for (j=0;j<=m;j++) parent[j]=-1,size[j]=1; /* and |l=0| */
l=0;
@ @=
for (uu=u;parent[uu]>=0;uu=parent[uu]) ;
for (vv=v;parent[vv]>=0;vv=parent[vv]) ;
if (uu==vv) move[l]=-1;
else if (size[uu]<=size[vv])
parent[uu]=vv, move[l]=uu, size[vv]+=size[uu];
else parent[vv]=uu, move[l]=vv, size[uu]+=size[vv];
l++;
@ Dynamic union-find is ridiculously easy because, as observed above,
the operations are strictly last-in-first-out.
And we didn't clobber the |size| information when merging two classes.
@ @=
l--;
uu=move[l];
if (uu>=0) {
vv=parent[uu]; /* we have |parent[vv]<0| */
size[vv]-=size[uu];
parent[uu]=-1;
}
@ @=
int active; /* this many vertices are currently labeled (not isolated) */
int parent[maxm+1], size[maxm+1], move[maxm]; /* the union-find structures */
int arcs[maxm+1]; /* the first neighbor of |v| */
int link[2*maxm+1]; /* the next element in a list of neighbors */
int x[maxm+1]; /* the governing sequence of edge choices */
@*Doing it.
Now we're ready to harvest the routines we've built up.
[A puzzle for the reader: Is |parent[m]| always negative at this point?
Answer: Not if, say, $m=7$ and $(x_1,\ldots,x_m)=(5,4,3,2,0,1,0)$.]
@=
for (k=parent[m];parent[k]>=0;k=parent[k]) ;
if (size[k]==active) connected[active]++;
else disconnected[active]++;
@ @=
printf("Counts for %d edges:\n",
m);
for (k=2;k<=m+1;k++) if (connected[k]+disconnected[k]) {
printf("on %5d vertices, %lld are connected, %lld not\n",
k,2*connected[k],2*disconnected[k]);
totconnected+=2*connected[k],totdisconnected+=2*disconnected[k];
}
printf("Altogether %lld connected and %lld not.\n",
totconnected,totdisconnected);
@ @=
unsigned long long connected[maxm+2],disconnected[maxm+2];
unsigned long long totconnected,totdisconnected;
@*Index.