;
@#
main(int argc) {
register int j,k,l,p,q,s;
int rfl,rot;
for (p=3;p<=maxp;p++) {
pp=p+p;
ptot=pltot=0;
for (j=2;j;
@;
}
printf("%d (%d labeled) with perimeter %d; ",ptot,pltot,pp);
printf("%d (%d labeled) with %d vertices; ",vtot[pp],vltot[pp],pp);
printf("%d (%d labeled) with %d vertices; ",vtot[pp+1],vltot[pp+1],pp+1);
printf("%d (%d labeled) with %d squares.\n",stot[p-1],sltot[p-1],p-1);
}
}
@* Generating the deltas.
The delta sequence is stored in array |del|, and another array |occ|
records the cells of the implicit restricted growth string that are
currently known (``occupied''). If the first occurrence of $j$
in the growth string is in cell $i_j$, we set $|back|[i_j]=i_{j-1}$
for $0=
int del[4*maxp];
int occ[3*maxp+1];
int back[2*maxp];
@ @=
del[0]=j, del[j]=pp-j;
occ[0]=occ[j]=1;
k=1, s=0;
@ This program is one of those backtrack jobs
where I still like to use |goto| statements,
forty years after the ``structured programming revolution.''
The value of |s| points to the most recent entry that we've entered
into the |del| table. It's essentially a stack pointer.
@=
advance:@+while (occ[k]) k++;
if (k==pp)
@;
occ[k]=1, back[k]=s;
l=k+j; /* the first conceivable way to place the mate of cell |k| */
nextslot:@+while (occ[l]) l++;
if (l>=pp) goto backtrack; /* no more places to match cell |k| */
if (abcabc(k,l)) {
l++;@+goto nextslot;
}
del[k]=l-k, del[l]=pp-l+k, occ[l]=1;
s=k++;
goto advance;
next: occ[s+del[s]]=0;
k=s;
backtrack: occ[k]=0;
k=back[k];
if (k) {
l=k+del[k], occ[l]=0, l++;
goto nextslot;
}
occ[j]=0;
@ @=
int abcabc(int k,int l) {
register int i,j;
for (j=back[k];j;j=back[j]) {
if (l=
{
@;
@;
@;
@;
@;
goto next;
}
@ @=
for (k=0;k;
@ The reflected sequence is unchanged by a $k$-shift if and only if the
unreflected sequence is.
@d rdel(x) pp-del[pp+pp-x]
@=
rfl=0;
for (k=1;k<=pp;k++) { /* try cyclic shifting by |k| */
for (q=k; q2p$;
it represents a segment of the chord that runs between points |e[j].from|
and |e[j].to|. It also has a ``mate,'' $e[j\pm1]$, which runs the
other way on the same chord segment and belongs to an adjacent region.
After the whole graph has been constructed we will mark each edge
with the number of the region to which it belongs.
@ @=
struct {
int succ; /* index of the next edge in this region */
int from, to; /* points that define the chord, if internal */
int reg; /* region number */
} e[2*maxp*maxp];
int eptr; /* address of first unused entry in |e| */
@ New edges are allocated in mated pairs.
The |e| array, with |2*maxp*maxp| entries, should have plenty of
room for all the edges we need. But we check it, just to be sure.
@=
int newedge(int s,int t) {
e[eptr].from=e[eptr+1].to=s;
e[eptr].to=e[eptr+1].from=t;
e[eptr].reg=e[eptr+1].reg=0;
eptr+=2;
if (eptr>=2*maxp*maxp) {
fprint(stderr,"Memory overflow!\n");
exit(-2);
}
return eptr-2;
}
@ For convenience we assume that |eptr| is always even, so that the mate
of edge~$k$ is obtained by simply complementing the units bit of~$k$.
@d mate(k) ((k)^1)
@ We could have made the region lists doubly linked, but they tend to
be short. Therefore it probably doesn't hurt to search sequentially
for the predecessor of an edge.
@=
int pred(int k) {
register int j;
for (j=k;e[j].succ!=k;j=e[j].succ) ;
return j;
}
@ The task of building the graph consists of starting with just the
enclosing circle, then inserting the chords one by one.
@=
@;
for (k=s;;k=back[k]) {
newchord(k,(k+del[k])%pp);
if (k==0) break;
}
@ @=
for (k=1;k=
void finishchord(int q,int s,int t) {
register int m=newedge(s,t);
e[m].succ=e[t+1].succ, e[m+1].succ=e[q].succ;
e[t+1].succ=m+1, e[q].succ=m;
}
@ A more complex operation is needed when we split a region by introducing
an interior vertex. Then we need to create two new pairs of mated edges.
One of these, from |t| to~|s|, becomes the successor of some
{\it interior\/} edge~|p|, which is being cut into two edges; its mate,
from |s| to~|t|, becomes the successor of a given edge~|q|, which
doesn't need to be cut. The second mated pair of new edges becomes
the other half of edge~|p| (and its mate) after cutting.
The following subroutine returns the index of the internal edge that
can be used to continue chord insertion on the next region to be
encountered between |s| and~|t|.
@=
int internalchord(int p,int q,int s,int t) {
register int m=newedge(s,t), mm=newedge(e[p].from,e[p].to);
register int pp=mate(p), ppp=pred(pp);
e[m].succ=mm, e[m+1].succ=e[q].succ;
e[mm].succ=e[p].succ, e[mm+1].succ=pp;
e[p].succ=m+1, e[q].succ=m, e[ppp].succ=mm+1;
return mm+1;
}
@ Now we're ready to insert a new chord in its entirety.
We use the fact that points $(a,b,c)$ are ``cyclically ordered'' if and
only if $(b-a)\bmod|pp|<(c-a)\bmod|pp|$.
@=
void newchord(int s,int t) {
register int p,q;
for (q=s+1;;) {
p=e[q].succ; /* the edge following |q| will never be cut */
for (p=e[p].succ;;p=e[p].succ) {
if (p==q) {
fprintf(stderr,"This can't happen (newchord loop)!\n");
exit(-1);
}
if (p<=pp) { /* exterior edge */
if (p==t+1) break;
}@+else { /* interior edge */
if (((t-e[p].from+pp)%pp)<((e[p].to-e[p].from+pp)%pp)) break;
}
}
if (p<=pp) break;
q=internalchord(p,q,s,t); /* see the discussion below */
}
finishchord(q,s,t);
}
@ The situation that arises when the |internalchord| routine is
called in the loop above needs some justification and further explanation.
Edge |p| is an internal edge that goes from $s'$ to $t'$, say. We also
know that the points $(s,s',t,t')$ appear in that order as we traverse the
outer circle.
If the predecessor of edge |p| is also an internal edge, say from
$s''$ to $t''$, then the points $(s,s'',s',t'',t')$ are in cyclic order.
In order to be sure that the new chord from $s$ to~$t$ is forced to cut
edge~$p$, we need to know that $(t'',t,t')$ are in cyclic order. The
alternative is the cyclic order $(s,s'',s',t,t'',t')$; if that were true,
the edge to cut would be ambiguous. Fortunately, however, the $abcabc$
condition has ruled out such a possibility.
A similar argument applies if the successor of edge |p| is internal;
again, we conclude that the |newchord| algorithm is justified
in cutting edge~|p|.
A fancier argument would set up an invariant relation on each region
that arises during the construction process, showing that the
endpoints of each internal edge maintain a simple cyclic relationship.
Instead of making formal definitions, an example should suffice here:
Consider a region with edges $(k_1,k_2,\ldots,k_8)$ in cyclic order,
where $k_1$, $k_2$, and $k_5$ are external, while $k_3$ is
internal from $s_3$ to $t_3$, etc. Then $k_2-1=k_1$, $s_3=k_2$, $t_4=k_5-1$,
$s_6=k_5$, and $t_8=k_1-1$; and the points
$$(k_1,k_2,s_4,t_3,k_5-1,k_5,s_7,t_6,s_8,t_7,k_1-1)$$
are in cyclic order. Think about it.
@ Once we've inserted the chords, we can construct the graph by
giving each region an identifying number.
At the same time we can reject cases with articulation points ---
namely, when a region has more than one exterior edge.
When this computation is finished, we will have discovered the total number of
regions, |l|, which is also the total number of vertices in the corresponding
squaregraph.
Note: We execute this code at a time when the local variables |p|, |j|,
and~|s| must not be changed. (They are part of the backtracking mechanism
for delta sequences.) The author apologies for not subroutinizing everything.
@=
for (l=0,k=1;k=
ptot++;
printf("%d:",ptot);
for (k=0;k>1)-1-p,l-pp,(eptr>>2)-p);
/* that's vertices, edges, internal vertices, and squares */
if (verbose) @;
@ @=
for (k=q=1;k<=l;k++) {
register int r;
printf(" %d --",k);
while (e[q].reg!=k) q++;
for (r=e[q].succ;;r=e[r].succ) {
if (r<=pp) break;
printf(" %d",e[mate(r)].reg);
if (r==q) break;
}
printf("\n");
}
@ @=
q=pp/rot;
if (rfl==0) q<<=1; /* now |q| is the number of labeled varieties of |del| */
pltot+=q;
vtot[l]++;
vltot[l]+=q;
stot[(eptr>>2)-p]++;
sltot[(eptr>>2)-p]+=q;
@*Index.