gb_basic.w

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

if we use infix notation and name the leaves $(a,b,c,d)$ from left to right.
Here each tree is related to its two neighbors by associativity. The
first and last trees are also related in the same way.

If |max_height=0|, it is changed to |n|, which means there is no
restriction on the height of a leaf. In this case the graph will have
exactly ${2n+1\choose n}/ (2n+1)$ vertices; furthermore, each vertex
will have exactly $n-1$ neighbors, because a rotation will be possible
just above every internal node except the root.  The graph in this
case can also be interpreted geometrically: The vertices are in
one-to-one correspondence with the triangulations of a regular
$(n+2)$-gon; two triangulations are adjacent if and only if one is obtained
from the other by replacing the pair of adjacent triangles $ABC,DCB$
by the pair $ADC,BDA$.

The partial ordering corresponding to the directed graph on
${2n+1\choose n}/(2n+1)$ vertices created by |all_trees(n,1)|
is a lattice with interesting properties. See Huang and Tamari,
@^Huang, Samuel Shung@>
@^Tamari, Dov@>
{\sl Journal of Combinatorial Theory\/ \bf A13} (1972), 7--13.

@(gb_basic.h@>=
#define all_trees(n,directed) @[binary((long)(n),0L,(long)(directed))@]

@ The program for |binary| is very similar in structure to the program
for |parts| already considered. But the details are more exciting.

@<Basic subroutines@>=
Graph *binary(n,max_height,directed)
  unsigned long n; /* the number of internal nodes */
  unsigned long max_height; /* maximum height of a leaf */
  long directed; /* should the graph be directed? */
{@+@<Vanilla local variables@>@;@#
  if (2*n+2>BUF_SIZE) panic(bad_specs); /* |n| is too huge for us */
  if (max_height==0 || max_height>n) max_height=n;
  if (max_height>30) panic(very_bad_specs); /* more than a billion vertices */
  @<Create a graph with one vertex for each binary tree@>;
  @<Name the trees and create the arcs or edges@>;
  if (gb_trouble_code) {
    gb_recycle(new_graph);
    panic(alloc_fault); /* uff da, we ran out of memory somewhere back there */
  }
  return new_graph;
}

@ The number of vertices is the coefficient of $z^n$
in the power series $G_h$, where $h=|max_height|$ and $G_h$ satisfies
the recurrence
$$G_0=1,\qquad G_{h+1}=1+z G_h^2.$$

The coefficients of $G_5$ are $\le55308$, but the
coefficients of $G_6$ are much larger; they exceed one billion when
$28\le n\le49$, and they exceed one million when $17\le n\le 56$.
In order to avoid overflow during this calculation, we use a
special method when $h\ge6$ and $n\ge20$: In such cases, graphs
of reasonable size arise only if $n\ge 2^h-7$, and we look at the
coefficient of $z^{-(2^h-1-n)}$ in $R_h=G_h/z^{2^h-1}$, which is a
power series in $z^{-1}$ defined by the recurrence
$$R_0=1,\qquad R_{h+1}=R_h^2+z^{1-2^{h+1}}.$$

@<Create a graph with one vertex for each binary tree@>=
{@+long nverts; /* the number of vertices */
  if (n>=20 && max_height>=6) @<Compute |nverts| using the $R$ series@>@;
  else {
    nn[0]=nn[1]=1;
    for (k=2;k<=n;k++) nn[k]=0;
    for (j=2;j<=max_height;j++)
      for (k=n-1;k;k--) {
        for (s=0,i=k;i>=0;i--) s+=nn[i]*nn[k-i]; /* overflow impossible */
        nn[k+1]=s;
      }
    nverts=nn[n];
  }
  new_graph=gb_new_graph(nverts);
  if (new_graph==NULL)
    panic(no_room); /* out of memory before we're even started */
  sprintf(new_graph->id,"binary(%lu,%lu,%d)",
    n,max_height,directed?1:0);
  strcpy(new_graph->util_types,"VVZZZZZZZZZZZZ"); /* hash table will be used */
}

@ The smallest nontrivial graph that is unilaterally disallowed by
this procedure on the grounds of size limitations occurs when |max_height=6|
and |n=20|; it has 14,162,220 vertices.

@<Compute |nverts| using the $R$ series@>=
{@+register float ss;
  d=(1L<<max_height)-1-n;
  if (d>8) panic(bad_specs+1); /* too many vertices */
  if (d<0) nverts=0;
  else {
    nn[0]=nn[1]=1;
    for (k=2;k<=d;k++) nn[k]=0;
    for (j=2;j<=max_height;j++) {
      for (k=d;k;k--) {
        for (ss=0.0,i=k;i>=0;i--) ss+=((float)nn[i])*((float)nn[k-i]);
        if (ss>MAX_NNN) panic(very_bad_specs+1); /* way too big */
        for (s=0,i=k;i>=0;i--) s+=nn[i]*nn[k-i]; /* overflow impossible */
        nn[k]=s;
      }
      i=(1L<<j)-1;
      if (i<=d) nn[i]++; /* add $z^{1-2^j}$ */
    }
    nverts=nn[d];
  }
}

@ We generate the trees in lexicographic order of their Polish prefix
notation, encoded in binary notation as $x_0x_1\ldots x_{2n}$, using `1'
for an internal node and `0' for a leaf. For example, the five
trees when $n=3$ are
$$1010100,\quad 1011000,\quad 1100100,\quad 1101000,\quad 1110000,$$
in lexicographic order. The algorithm for lexicographic generation maintains
three auxiliary arrays $l_j$, $y_j$, and $\sigma_j$, where
$$\sigma_j\;=\;n-j+\sum_{i=0}^{j-1}x_i\;=\;-1+\sum_{i=j}^{2n}(1-x_i)$$
is one less than the number of 0's (leaves) in $(x_j,\ldots,x_{2n})$.
The values of $l_j$ and $y_j$ are harder
to describe formally; $l_j$ is $2^{h-l}$ when $h=|max_height|$ and when
$x_j$ represents a node at level~$l$ of the tree, based on the values
of $(x_0,\ldots,x_{j-1})$. The value of $y_j$ is a binary encoding of
tree levels in which an internal node has not yet received a right child;
$y_j$ is also the maximum number of future leaves that can be produced by
previously specified internal nodes without exceeding the maximum height.
The number of 1-bits in $y_j$ is the minimum number of future leaves,
based on previous specifications.

Therefore if $\sigma_j>y_j$, $x_j$ is forced to be~1. If $l_j=1$,
$x_j$ is forced to be~0. If the number of 1-bits of $y_j$ is equal
to $\sigma_j$, $x_j$ is forced to be~0. Otherwise $x_j$ can be
either 0 or~1, and it will be possible to complete the partial
solution $x_0\ldots x_j$ to a full Polish prefix code $x_0\ldots x_{2n}$.

For example, here are the arrays for one of the binary trees
that is generated when $n=h=3$:
$$\vcenter{\halign{$\hfil#$\quad=&&\quad#\cr
j       &0&1&2&3&4&5&6\cr
l_j     &8&4&2&2&1&1&4\cr
y_j     &0&4&6&4&5&4&0\cr
\sigma_j&3&3&3&2&2&1&0\cr
x_j     &1&1&0&1&0&0&0\cr}}$$
If $x_j=1$ and $j<2n$, we have $l_{j+1}=l_j/2$, $y_{j+1}=y_j+l_{j+1}$,
and $\sigma_{j+1}=\sigma_j$. If $x_j=0$ and $j<2n$, we have $l_{j+1}=
2^t$, $y_{j+1}=y_j-2^t$, and $\sigma_{j+1}=\sigma_j-1$, where $2^t$ is the
least power of~2 in the binary representation of~$y_j$. It is not difficult to
prove by induction that $\sigma_j<y_j+l_j$, assuming that $n<2^h$.

@<Name the trees and create the arcs or edges@>=
{@+register long *xtab,*ytab,*ltab,*stab;
  @<Initialize |xtab|, |ytab|, |ltab|, and |stab|; also set |d=2n|@>;
  v=new_graph->vertices;
  if (ltab[0]>n) {
    k=0;@+xtab[0]=n?1:0;
    while (1) {
      @<Complete the partial tree $x_0\ldots x_k$@>;
      @<Assign a Polish prefix code name to vertex~|v|@>;
      @<Create arcs or edges from |v| to previous trees@>;
      v++;
      @<Advance to the next partial tree $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 */
gb_free(working_storage);

@ @<Initialize |xtab|, |ytab|, |ltab|, and |stab|...@>=
xtab=gb_typed_alloc(8*n+4,long,working_storage);
if (gb_trouble_code) { /* no room for |xtab| */
  gb_recycle(new_graph);@+panic(no_room+2);@+}
d=n+n;
ytab=xtab+(d+1);
ltab=ytab+(d+1);
stab=ltab+(d+1);
ltab[0]=1L<<max_height;
stab[0]=n; /* |ytab[0]=0| */

@ @<Complete the partial tree...@>=
for (j=k+1;j<=d;j++) {
  if (xtab[j-1]) {
    ltab[j]=ltab[j-1]>>1;
    ytab[j]=ytab[j-1]+ltab[j];
    stab[j]=stab[j-1];
  }@+else {
    ytab[j]=ytab[j-1]&(ytab[j-1]-1); /* remove least significant 1-bit */
    ltab[j]=ytab[j-1]-ytab[j];
    stab[j]=stab[j-1]-1;
  }
  if (stab[j]<=ytab[j]) xtab[j]=0;
  else xtab[j]=1;  /* this is the lexicographically smallest completion */
}

@ As in previous routines, 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 tree...@>=
for (k=d-1;;k--) {
  if (k<=0) goto last; /* this happens only when |n<=1| */
  if (xtab[k]) break; /* find rightmost 1 */
}
for (k--;;k--) {
  if (xtab[k]==0 && ltab[k]>1) break;
  if (k==0) goto last;
}
xtab[k]++;

@ In the |name| field, we encode internal nodes of the binary tree by
`\..' and leaves by `\.x'. Thus the five trees shown above in binary
code will be named
$$\.{.x.x.xx},\quad \.{.x..xxx},\quad \.{..xx.xx},\quad \.{..x.xxx},\quad
\.{...xxxx},$$
respectively.

@<Assign a Polish prefix...@>=
{@+register char *p=buffer; /* string pointer */
  for (k=0;k<=d;k++,p++) *p=(xtab[k]? '.': 'x');
  v->name=gb_save_string(buffer);
  hash_in(v); /* enter |v->name| into the hash table
                  (via utility fields |u,v|) */
}

@ Since we are generating the trees in lexicographic order of their
Polish prefix notation, it is relatively easy to find all pairs of trees that
are adjacent via one application of the associative law: We simply
replace a substring of the form $\..\..\alpha\beta$ by
$\..\alpha\..\beta$, when $\alpha$ and $\beta$ are Polish prefix
strings. The result comes earlier in lexicographic order, so it will
be an existing vertex unless it violates the |max_height| restriction.

@<Create arcs or edges from |v| to previous trees@>=
for (j=0;j<d;j++)
  if (xtab[j]==1 && xtab[j+1]==1) {
    for (i=j+1,s=0;s>=0;s+=(xtab[i+1]<<1)-1,i++) xtab[i]=xtab[i+1];
    xtab[i]=1;
    {@+register char *p=buffer; /* string pointer */
      register Vertex *u;
      for (k=0;k<=d;k++,p++) *p=(xtab[k]? '.': 'x');
      u=hash_out(buffer);
      if (u) {
        if (directed) gb_new_arc(v,u,1L);
        else gb_new_edge(v,u,1L);
      }
    }
    for (i--;i>j;i--) xtab[i+1]=xtab[i]; /* restore |xtab| */
    xtab[i+1]=1;
  }

@* Complementing and copying. We have seen how to create a wide
variety of basic graphs with the |board|, |simplex|, |subsets|,
|perms|, |parts|, and |binary| procedures. The remaining routines
of {\sc GB\_\,BASIC} are somewhat different. They transform existing
graphs into new ones, thereby presenting us with an almost
mind-boggling array of further possibilities.

The first of these transformations is perhaps the simplest. It
complements a given graph, making vertices adjacent if and only if
they were previously nonadjacent. More precisely, the subroutine call
|complement(g,copy,self,directed)| returns a graph with the
same vertices as |g|, but with complemented arcs.
If |self!=0|, the new graph will have a self-loop from a vertex |v| to itself
when the original graph did not; if |self=0|, the new graph will
have no self-loops. If |directed!=0|, the new graph will have
an arc from |u| to |v| when the original graph did not; if |directed=0|,
the new graph will be undirected, and it will have an edge between |u|
and~|v| when the original graph did not. In the latter case, the original
graph should also be undirected (that is, its arcs should come in pairs,
as described in the |gb_new_edge| routine of {\sc GB\_\,GRAPH}).

If |copy!=0|, a double complement will actually be done. This means that
the new graph will essentially be a copy of the old, except that
duplicate arcs (and possibly self-loops) will be removed. Regardless of
the value of |copy|, information that might have been present in the utility
fields will not be copied, and arc lengths will all be set to~1.

One possibly useful feature of the graphs returned by |complement| is
worth noting. The vertices adjacent to~|v|, namely the list
$$\hbox{|v->arcs->tip|,\quad |v->arcs->next->tip|,\quad
 |v->arcs->next->next->tip|,\quad \dots\thinspace,}$$
will be in strictly decreasing order (except in the case of an
undirected self-loop, when |v| itself will appear twice in succession).

@ @<Basic subroutines@>=
Graph *complement(g,copy,self,directed)
  Graph *g; /* graph to be complemented */
  long copy; /* should we double-complement? */
  long self; /* should we produce self-loops? */
  long directed; /* should the graph be directed? */
{@+@<Vanilla local variables@>@;@+@q{@>@t}\6{@>@q}@>
  register long n;
  register Vertex *u;
  register siz_t delta; /* difference in memory addresses */
  if (g==NULL) panic(missing_operand); /* where's |g|? */
  @<Set up a graph with the vertices of |g|@>;
  sprintf(buffer,",%d,%d,%d)",copy?1:0,self?1:0,directed?1:0);
  make_compound_id(new_graph,"complement(",g,buffer);
  @<Insert complementary arcs or edges@>;
  if (gb_trouble_code) {
    gb_recycle(new_graph);
    panic(alloc_fault);
     /* worse luck, we ran out of memory somewhere back there */
  }
  return new_graph;
}

@ In several of the following routines, it is efficient to circumvent
\CEE/'s normal rules for pointer arithmetic, and to use the
fact that the vertices of a graph being copied are a constant distance away
in memory from the vertices of its clone.

@d vert_offset(v,delta) ((Vertex*)(((siz_t)v)+delta))
@^pointer hacks@>

@<Set up a graph with t