gb_basic.w

来自「模拟器提供了一个简单易用的平台」· W 代码 · 共 1,575 行 · 第 1/5 页

to the $\delta$'s, but we always leave $\delta_k$ positive if $\delta_1=
\cdots=\delta_{k-1}=0$. For every such vector~$\delta$, we generate moves
from |v| to $v+\delta$ for every vertex |v|. When |directed=0|,
we use |gb_new_edge| instead of |gb_new_arc|, so that the reverse arc
from $v+\delta$ to~|v| is also generated.

@<Insert arcs or edges for all legal moves@>=
@<Initialize the |wr|, |sig|, and |del| tables@>;
p=piece;
if (p<0) p=-p;
while (1) {
  @<Advance to the next nonnegative |del| vector, or |break| if done@>;
  while (1) {
    @<Generate moves for the current |del| vector@>;
    @<Advance to the next signed |del| vector, or restore |del|
          to nonnegative values and |break|@>;
  }
}

@ The \CEE/ language does not define |>>| unambiguously. If |w| is negative,
the assignment `|w>>=1|' here should keep |w| negative.
(However, this technicality doesn't matter except in highly unusual cases
when there are more than 32 dimensions.)
@^system dependencies@>

@<Initialize the |wr|, |sig|, and |del| tables@>=
{@+register long w=wrap;
  for (k=1;k<=d;k++,w>>=1) {
    wr[k]=w&1;
    del[k]=sig[k]=0;
  }
  sig[0]=del[0]=sig[d+1]=0;
}

@ The |sig| array makes it easy to backtrack through all partitions
of |p| into an ordered sum of squares.

@<Advance to the next nonnegative |del|...@>=
for (k=d;sig[k]+(del[k]+1)*(del[k]+1)>p;k--) del[k]=0;
if (k==0) break;
del[k]++;
sig[k+1]=sig[k]+del[k]*del[k];
for (k++;k<=d;k++) sig[k+1]=sig[k];
if (sig[d+1]<p) continue;

@ @<Advance to the next signed |del| vector, or restore |del|
          to nonnegative values and |break|@>=
for (k=d;del[k]<=0;k--) del[k]=-del[k];
if (sig[k]==0) break; /* all but |del[k]| were negative or zero */
del[k]=-del[k]; /* some entry preceding |del[k]| is positive */

@ We use the mixed-radix addition technique again when generating moves.

@<Generate moves for the current |del| vector@>=
for (k=1;k<=d;k++) xx[k]=0;
for (v=new_graph->vertices;;v++) {
  @<Generate moves from |v| corresponding to |del|@>;
  for (k=d;xx[k]+1==nn[k];k--) xx[k]=0;
  if (k==0) break; /* a ``carry'' has occurred all the way to the left */
  xx[k]++; /* increase coordinate |k| */
}

@ The legal moves when |piece| is negative are derived as follows, in
the presence of possible wraparound: Starting at $(x_1,\ldots,x_d)$, we
move to $(x_1+\delta_1,\ldots,x_d+\delta_d)$, $(x_1+2\delta_1,\ldots,
x_d+2\delta_d)$,~\dots, until either coming to a position with a nonwrapped
coordinate out of range or coming back to the original point.

A subtle technicality should be noted: When coordinates are wrapped and
|piece>0|, self-loops are possible---for example, in |board(1,0,0,0,1,1,1)|.
But self-loops never arise when |piece<0|.

@<Generate moves from |v|...@>=
for (k=1;k<=d;k++) yy[k]=xx[k]+del[k];
for (l=1;;l++) {
  @<Correct for wraparound, or |goto no_more| if off the board@>;
  if (piece<0) @<Go to |no_more| if |yy=xx|@>;
  @<Record a legal move from |xx| to |yy|@>;
  if (piece>0) goto no_more;
  for (k=1;k<=d;k++) yy[k]+=del[k];
}
no_more:@;

@ @<Go to |no_more|...@>=
{
  for (k=1;k<=d;k++) if (yy[k]!=xx[k]) goto unequal;
  goto no_more;
  unequal:;
}

@ @<Correct for wraparound, or |goto no_more| if off the board@>=
for (k=1;k<=d;k++) {
  if (yy[k]<0) {
    if (!wr[k]) goto no_more;
    do yy[k]+=nn[k];@+ while (yy[k]<0);
  }@+else if (yy[k]>=nn[k]) {
    if (!wr[k]) goto no_more;
    do yy[k]-=nn[k];@+ while (yy[k]>=nn[k]);
  }
}

@ @<Record a legal move from |xx| to |yy|@>=
for (k=2,j=yy[1];k<=d;k++) j=nn[k]*j+yy[k];
if (directed) gb_new_arc(v,new_graph->vertices+j,l);
else gb_new_edge(v,new_graph->vertices+j,l);

@* Generalized triangular boards. The subroutine call
|simplex(n,n0,n1,n2,n3,n4,directed)| creates a graph based on
generalized triangular or tetrahedral configurations. Such graphs are
similar in spirit to the game boards created by |board|, but they
pertain to nonrectangular grids like those in Chinese checkers. As
with |board| in the case |piece=1|, the vertices represent board positions
and the arcs run from board positions to their nearest neighbors. Each arc has
length~1.{\tolerance=1000\par}

More formally, the vertices can be defined as sequences of nonnegative
integers $(x_0,x_1,\ldots,x_d)$ whose sum is~|n|, where two sequences
are considered adjacent if and only if they differ by $\pm1$ in exactly
two components---equivalently, if the Euclidean distance between them
is~$\sqrt2$. When $d=2$, for example, the vertices can be visualized
as a triangular array
$$\vcenter{\halign{&\hbox to 2em{\hss$#$\hss}\cr
&&&(0,0,3)\cr
&&(0,1,2)&&(1,0,2)\cr
&(0,2,1)&&(1,1,1)&&(2,0,1)\cr
(0,3,0)&&(1,2,0)&&(2,1,0)&&(3,0,0)\cr}}$$
containing $(n+1)(n+2)/2$ elements, illustrated here when $n=3$; each vertex of
the array has up to 6 neighbors. When $d=3$ the vertices form a tetrahedral
array, a stack of triangular layers, and they can have as many as 12
neighbors. In general, a vertex in a $d$-simplicial array will have up to
$d(d+1)$ neighbors.

If the |directed| parameter is nonzero, arcs run only from vertices to
neighbors that are lexicographically greater---for example, downward
or to the right in the triangular array shown. The directed graph is
therefore acyclic, and a vertex of a $d$-simplicial array has
out-degree at most $d(d+1)/2$.

@ The first parameter, |n|, specifies the sum of the coordinates
$(x_0,x_1,\ldots,x_d)$. The following parameters |n0| through |n4|
specify upper bounds on those coordinates, and they also specify the
dimensionality~|d|.

If, for example, |n0|, |n1|, and |n2| are positive while |n3=0|, the
value of~|d| will be~2 and the coordinates will be constrained to
satisfy $0\le x_0\le|n0|$, $0\le x_1\le|n1|$, $0\le x_2\le|n2|$. These
upper bounds essentially lop off the corners of the triangular array.
We obtain a hexagonal board with $6m$ boundary cells by asking for
|simplex(3m,2m,2m,2m,0,0,0)|. We obtain the diamond-shaped board used
in the game of Hex [Martin Gardner, {\sl The Scientific American
@^Gardner, Martin@>
Book of Mathematical Puzzles {\char`\&} Diversions\/} (Simon {\char`\&}
Schuster, 1959), Chapter~8] by calling |simplex(20,10,20,10,0,0,0)|.

In general, |simplex| determines |d| and upper bounds $(n_0,n_1,\ldots,n_d)$
in the following way: Let the first nonpositive entry of the sequence
|(n0,n1,n2,n3,n4,0)|$\null=(n_0,n_1,n_2,n_3,n_4,0)$ be~$n_k$. If $k>0$
and $n_k=0$, the value of~$d$ will be $k-1$ and the coordinates will be
bounded by the given numbers $(n_0,\ldots,n_d)$. If $k>0$ and $n_k<0$,
the value of~$d$ will be $\vert n_k\vert$ and the coordinates will be
bounded by the first $d+1$ elements of the infinite periodic sequence
$(n_0,\ldots,n_{k-1},n_0,\ldots,n_{k-1},n_0,\ldots\,)$. If $k=0$ and
$n_0<0$, the value of~$d$ will be $\vert n_0\vert$ and the coordinates
will be unbounded; equivalently, we may set $n_0=\cdots=n_d=n$. In
this case the number of vertices will be $n+d\choose d$. Finally,
if $k=0$ and $n_0=0$, we have the default case of a triangular array
with $3n$ boundary cells, exactly as if $n_0=-2$.

For example, the specification |n0=3|, |n1=-5| will produce all vertices
$(x_0,x_1,\ldots,x_5)$ such that $x_0+x_1+\cdots+x_5=n$ and $0\le x_j\le3$.
The specification |n0=1|, |n1=-d| will essentially produce all $n$-element
subsets of the $(d+1)$-element set $\{0,1,\ldots,d\}$, because we can
regard an element~$k$ as being present in the set if $x_k=1$ and absent
if $x_k=0$. In that case two subsets are adjacent if and only if
they have exactly $n-1$ elements in common. 

@ @<Basic subroutines@>=
Graph *simplex(n,n0,n1,n2,n3,n4,directed)
  unsigned long n; /* the constant sum of all coordinates */
  long n0,n1,n2,n3,n4; /* constraints on coordinates */
  long directed; /* should the graph be directed? */
{@+@<Vanilla local variables@>@;@#
  @<Normalize the simplex parameters@>;
  @<Create a graph with one vertex for each point@>;
  @<Name the points and create the arcs or edges@>;
  if (gb_trouble_code) {
    gb_recycle(new_graph);
    panic(alloc_fault); /* darn, we ran out of memory somewhere back there */
  }
  return new_graph;
}

@ @<Normalize the simplex parameters@>=
if (n0==0) n0=-2;
if (n0<0) {@+k=2;@+nn[0]=n;@+d=-n0;@+n1=n2=n3=n4=0;@+}
else {
  if (n0>n) n0=n;
  nn[0]=n0;
  if (n1<=0) {@+k=2;@+d=-n1;@+n2=n3=n4=0;@+}
  else {
    if (n1>n) n1=n;
    nn[1]=n1;
    if (n2<=0) {@+k=3;@+d=-n2;@+n3=n4=0;@+}
    else {
      if (n2>n) n2=n;
      nn[2]=n2;
      if (n3<=0) {@+k=4;@+d=-n3;@+n4=0;@+}
      else {
        if (n3>n) n3=n;
        nn[3]=n3;
        if (n4<=0) {@+k=5;@+d=-n4;@+}
        else {@+if (n4>n) n4=n;
          nn[4]=n4;@+d=4;@+goto done;@+}
      }
    }
  }
}
if (d==0) {@+d=k-2;@+goto done;@+}
nn[k-1]=nn[0];
@<Compute component sizes periodically...@>;
done: /* now |nn[0]| through |nn[d]| are set up */

@ @<Create a graph with one vertex for each point@>=
@<Determine the number of feasible $(x_0,\ldots,x_d)$,
  and allocate the graph@>;
sprintf(new_graph->id,"simplex(%lu,%ld,%ld,%ld,%ld,%ld,%d)",
    n,n0,n1,n2,n3,n4,directed?1:0);
strcpy(new_graph->util_types,"VVZIIIZZZZZZZZ"); /* hash table will be used */

@ We determine the number of vertices by determining the coefficient of~$z^n$
in the power series
$$(1+z+\cdots+z^{n_0})(1+z+\cdots+z^{n_1})\ldots(1+z+\cdots+z^{n_d}).$$

@<Determine the number of feasible $(x_0,\ldots,x_d)$...@>=
{@+long nverts; /* the number of vertices */
  register long *coef=gb_typed_alloc(n+1,long,working_storage);
  if (gb_trouble_code) panic(no_room+1); /* can't allocate |coef| array */
  for (k=0;k<=nn[0];k++) coef[k]=1;
   /* now |coef| represents the coefficients of $1+z+\cdots+z^{n_0}$ */
  for (j=1;j<=d;j++)
    @<Multiply the power series coefficients by $1+z+\cdots+z^{n_j}$@>;
  nverts=coef[n];
  gb_free(working_storage); /* recycle the |coef| array */
  new_graph=gb_new_graph(nverts);
  if (new_graph==NULL)
    panic(no_room); /* out of memory before we're even started */
}

@ There's a neat way to multiply by $1+z+\cdots+z^{n_j}$: We multiply
first by $1-z^{n_j+1}$, then sum the coefficients.

We want to detect impossibly large specifications without risking
integer overflow. It is easy to do this because multiplication is being
done via addition.

@<Multiply the power series coefficients by $1+z+\cdots+z^{n_j}$@>=
{
  for (k=n,i=n-nn[j]-1;i>=0;k--,i--) coef[k]-=coef[i];
  s=1;
  for (k=1;k<=n;k++) {
    s+=coef[k];
    if (s>1000000000) panic(very_bad_specs); /* way too big */
    coef[k]=s;
  }
}

@ As we generate the vertices, it proves convenient to precompute an
array containing the numbers $y_j=n_j+\cdots+n_d$, which represent the
largest possible sums $x_j+\cdots+x_d$. We also want to maintain
the numbers $\sigma_j=n-(x_0+\cdots+x_{j-1})=x_j+\cdots+x_d$. The
conditions
$$0\le x_j\le n_j, \qquad \sigma_j-y_{j+1}\le x_j\le \sigma_j$$
are necessary and sufficient, in the sense that we can find at least
one way to complete a partial solution $(x_0,\ldots,x_k)$ to a full
solution $(x_0,\ldots,x_d)$ if and only if the conditions hold for
all $j\le k$.

There is at least one solution if and only if $n\le y_0$.

We enter the name string into a hash table, using the |hash_in|
routine of {\sc GB\_\,GRAPH}, because there is no simple way to compute the
location of a vertex from its coordinates.

@<Name the points and create the arcs or edges@>=
v=new_graph->vertices;
yy[d+1]=0;@+sig[0]=n;
for (k=d;k>=0;k--) yy[k]=yy[k+1]+nn[k];
if (yy[0]>=n) {
  k=0;@+xx[0]=(yy[1]>=n? 0: n-yy[1]);
  while (1) {
    @<Complete the partial solution $(x_0,\ldots,x_k)$@>;
    @<Assign a symbolic name for $(x_0,\ldots,x_d)$ to vertex~|v|@>;
    hash_in(v); /* enter |v->name| into the hash table
                  (via utility fields |u,v|) */
    @<Create arcs or edges from previous points to~|v|@>;
    v++;
    @<Advance to the next partial solution $(x_0,\ldots,x_k)$, where |k| is
       as large as possible; |goto last| if there are no more solutions@>;
  }
}
last:@+if (v!=new_graph->vertices+new_graph->n)
  panic(impossible); /* can't happen */

@ @<Complete the partial solution $(x_0,\ldots,x_k)$@>=
for (s=sig[k]-xx[k],k++;k<=d;s-=xx[k],k++) {
  sig[k]=s;
  if (s<=yy[k+1]) xx[k]=0;
  else xx[k]=s-yy[k+1];
}
if (s!=0) panic(impossible+1) /* can't happen */

@ Here we seek the largest $k$ such that $x_k$ can be increased without
violating the necessary and sufficient conditions stated earlier.

@<Advance to the next partial solution $(x_0,\ldots,x_k)$...@>=