gb_basic.w

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

% This file is part of the Stanford GraphBase (c) Stanford University 1993
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
@i gb_types.w

\def\title{GB\_\,BASIC}

\prerequisite{GB\_\,GRAPH}
@* Introduction. This GraphBase module contains six subroutines that generate
standard graphs of various types, together with six routines that combine or
transform existing graphs.

Simple examples of the use of these routines can be found in the
demonstration programs {\sc QUEEN} and {\sc QUEEN\_WRAP}.

@<gb_basic.h@>=
extern Graph *board(); /* moves on generalized chessboards */
extern Graph *simplex(); /* generalized triangular configurations */
extern Graph *subsets(); /* patterns of subset intersection */
extern Graph *perms(); /* permutations of a multiset */
extern Graph *parts(); /* partitions of an integer */
extern Graph *binary(); /* binary trees */
@#
extern Graph *complement(); /* the complement of a graph */
extern Graph *gunion(); /* the union of two graphs */
extern Graph *intersection(); /* the intersection of two graphs */
extern Graph *lines(); /* the line graph of a graph */
extern Graph *product(); /* the product of two graphs */
extern Graph *induced(); /* a graph induced from another */

@ The \CEE/ file \.{gb\_basic.c} has the following overall shape:

@p
#include "gb_graph.h" /* we use the {\sc GB\_\,GRAPH} data structures */
@h@#
@<Private variables@>@;
@<Basic subroutines@>@;
@<Applications of basic subroutines@>@;

@ Several of the programs below allocate arrays that will be freed again
before the routine is finished.

@<Private variables@>=
static Area working_storage;

@ If a graph-generating subroutine encounters a problem, it returns |NULL|
(that is, \.{NULL}), after putting a code number into the external variable
|panic_code|. This code number identifies the type of failure.
Otherwise the routine returns a pointer to the newly created graph, which
will be represented with the data structures explained in {\sc GB\_\,GRAPH}.
(The external variable |panic_code| is itself defined in {\sc GB\_\,GRAPH}.)

@d panic(c) 
  {@+panic_code=c;
    gb_free(working_storage);
    gb_trouble_code=0;
    return NULL;
  }

@ The names of vertices are sometimes formed from the names of other
vertices, or from potentially long sequences of numbers. We assemble
them in the |buffer| array, which is sufficiently long that the
vast majority of applications will be unconstrained by size limitations.
The programs assume that |BUF_SIZE| is rather large, but in cases of
doubt they ensure that |BUF_SIZE| will never be exceeded.

@d BUF_SIZE 4096

@<Private v...@>=
static char buffer[BUF_SIZE];

@*Grids and game boards. The subroutine call
|board(n1,n2,n3,n4,piece,wrap,directed)|
constructs a graph based on the moves of generalized chesspieces on a
generalized rectangular board. Each vertex of the graph corresponds to a
position on the board. Each arc of the graph corresponds to a move from
one position to another.

The first parameters, |n1| through |n4|, specify the size of the board.
If, for example, a two-dimensional board with $n_1$ rows and $n_2$ columns
is desired, you set $|n1|=n_1$, $|n2|=n_2$, and $|n3|=0$; the resulting
graph will have $n_1n_2$ vertices. If you want a three-dimensional
board with $n_3$ layers, set $|n3|=n_3$ and $n_4=0$. If you want
a 4-{\mc D} board, put the number of 4th coordinates in~|n4|.
If you want a $d$-dimensional board with $2^d$ positions, set |n1=2|
and |n2=-d|.

In general, the |board| subroutine determines the dimensions by scanning the
sequence |(n1,n2,n3,n4,0)=@t$(n_1,n_2,n_3,n_4,0)$@>| from left to right
until coming to the first nonpositive parameter $n_{k+1}$. If $k=0$
(i.e., if |n1<=0|), the default size $8\times8$ will be used; this is
an ordinary chessboard with 8~rows and 8~columns. Otherwise if $n_{k+1}=0$,
the board will have $k$~dimensions $n_1$, \dots,~$n_k$. Otherwise
we must have $n_{k+1}<0$; in this case, the board will have $d=\vert n_{k+1}
\vert$ dimensions, chosen as the first $d$ elements of the infinite
periodic sequence $(n_1,\ldots,n_k,n_1,\ldots,n_k,n_1,\ldots\,)$.
For example, the specification |(n1,n2,n3,n4)=(2,3,5,-7)| is about as
tricky as you can get. It produces a seven-dimensional board with
dimensions $(n_1,\ldots,n_7)=(2,3,5,2,3,5,2)$, hence a graph with
$2\cdot3\cdot5\cdot2\cdot3\cdot5\cdot2=1800$ vertices.

The |piece| parameter specifies the legal moves of a generalized chesspiece.
If |piece>0|, a move from position~|u| to position~|v| is considered legal
if and only if the Euclidean distance between points |u| and~|v| is
equal to $\sqrt{\vphantom1\smash{|piece|}}$.
For example, if |piece=1| and if we have a
two-dimensional board, the legal moves from $(x,y)$ are to $(x,y\pm1)$ and
$(x\pm1,y)$; these are the moves of a so-called wazir, the only moves that
a king and a rook can both make. If |piece=2|, the legal moves from $(x,y)$
are to $(x\pm1,y\pm1)$; these are the four moves that a king and a bishop
can both make. (A piece that can make only these moves was called a ``fers''
in ancient Muslim chess.) If |piece=5|, the legal moves are those of a
knight, from $(x,y)$ to $(x\pm1,y\pm2)$ or to $(x\pm2,y\pm1)$. If |piece=3|,
there are no legal moves on a two-dimensional board; but moves from
$(x,y,z)$ to $(x\pm1,y\pm1,z\pm1)$ would be legal in three dimensions.
If |piece=0|, it is changed to the default value |piece=1|.

If the value of |piece| is negative, arbitrary multiples of the basic moves
for $\vert|piece|\vert$ are permitted. For example, |piece=-1| defines the
moves of a rook, from $(x,y)$ to $(x\pm a,y)$ or to $(x,y\pm a)$ for all
$a>0$; |piece=-2| defines the moves of a bishop, from $(x,y)$ to
$(x\pm a,y\pm a)$. The literature of ``fairy chess'' assigns standard names
to the following |piece| values: $\rm wazir=1$, $\rm fers=2$, $\rm dabbaba=4$,
$\rm knight=5$, $\rm alfil=8$, $\rm camel=10$, $\rm zebra=13$, $\rm giraffe
=17$, $\rm fiveleaper=25$, $\hbox{root-50-leaper}=50$, etc.; $\rm rook=-1$,
$\rm bishop=-2$, $\rm unicorn=-3$, $\rm dabbabarider=-4$, $\rm nightrider=-5$,
$\rm alfilrider=-8$, $\rm camelrider=-10$, etc.

To generate a board with the moves of a king, you can use the |gunion|
subroutine below to take the union of boards with |piece=1| and
|piece=2|. Similarly, you can get queen moves by taking the union of
boards with |piece=-1| and |piece=-2|.

If |piece>0|, all arcs of the graph will have length~1. If |piece<0|, the
length of each arc will be the number of multiples of a basic move that
produced the arc.

@ If the |wrap| parameter is nonzero, it specifies a subset of coordinates
in which values are computed modulo the corresponding size.
For example, the coordinates $(x,y)$ for vertices on a two-dimensional
board are restricted to the range $0\le x<n_1$, $0\le y<n_2$; therefore
when |wrap=0|, a move from $(x,y)$ to $(x+\delta_1,y+\delta_2)$ is
legal only if $0\le x+\delta_1<n_1$ and $0\le y+\delta_2<n_2$.
But when |wrap=1|, the $x$~coordinates are allowed to ``wrap around'';
the move would then be made to $((x+\delta_1)\bmod n_1,y+\delta_2)$,
provided that $0\le y+\delta_2<n_2$. Setting |wrap=1| effectively
makes the board into a cylinder instead of a rectangle. Similarly, the
$y$~coordinates are allowed to wrap around when |wrap=2|. Both $x$ and
$y$ coordinates are treated modulo their corresponding sizes when
|wrap=3|; the board is then effectively a torus.  In general,
coordinates $k_1$, $k_2$, \dots~ will wrap around when
$|wrap|=2^{k_1-1}+2^{k_2-1}+\cdots\,$. Setting |wrap=-1| causes all
coordinates to be computed modulo their size.

The graph constructed by |board| will be undirected unless |directed!=0|.
Directed |board| graphs will be acyclic when |wrap=0|, but they may
have cycles when |wrap!=0|. Precise rules defining the directed arcs
are given below.

Several important special cases are worth noting. To get the complete graph
on |n| vertices, you can say |board(n,0,0,0,-1,0,0)|. To get the
transitive tournament on |n| vertices, i.e., the directed graph
with arcs from |u| to |v| when |u<v|, you can say |board(n,0,0,0,-1,0,1)|.
To get the empty graph on |n| vertices, you can say |board(n,0,0,0,2,0,0)|.
To get a circuit (undirected) or a cycle (directed) of length~|n|,
you can say |board(n,0,0,0,1,1,0)| and |board(n,0,0,0,1,1,1)|,
respectively.

@(gb_basic.h@>=
#define complete(n) @[board((long)(n),0L,0L,0L,-1L,0L,0L)@]
#define transitive(n) @[board((long)(n),0L,0L,0L,-1L,0L,1L)@]
#define empty(n) @[board((long)(n),0L,0L,0L,2L,0L,0L)@]
#define circuit(n) @[board((long)(n),0L,0L,0L,1L,1L,0L)@]
#define cycle(n) @[board((long)(n),0L,0L,0L,1L,1L,1L)@]

@ @<Basic subroutines@>=
Graph *board(n1,n2,n3,n4,piece,wrap,directed)
  long n1,n2,n3,n4; /* size of board desired */
  long piece; /* type of moves desired */
  long wrap; /* mask for coordinate positions that wrap around */
  long directed; /* should the graph be directed? */
{@+@<Vanilla local variables@>@;@+@q{@>@t}\6{@>@q}@>
  long n; /* total number of vertices */
  long p; /* $\vert|piece|\vert$ */
  long l; /* length of current arc */
  @<Normalize the board-size parameters@>;
  @<Set up a graph with |n| vertices@>;
  @<Insert arcs or edges for all legal moves@>;
  if (gb_trouble_code) {
    gb_recycle(new_graph);
    panic(alloc_fault); /* alas, we ran out of memory somewhere back there */
  }
  return new_graph;
}

@ Most of the subroutines in {\sc GB\_\,BASIC} use the following local
variables.

@<Vanilla local variables@>=
Graph *new_graph; /* the graph being constructed */
register long i,j,k; /* all-purpose indices */
register long d; /* the number of dimensions */
register Vertex *v; /* the current vertex of interest */
register long s; /* accumulator */

@ Several arrays will facilitate the calculations that |board| needs to make.
The number of distinct values in coordinate position~$k$ will be |nn[k]|;
this coordinate position will wrap around if and only if |wr[k]!=0|.
The current moves under consideration will be from $(x_1,\ldots,x_d)$
to $(x_1+\delta_1,\ldots, x_d+\delta_d)$, where $\delta_k$ is stored
in |del[k]|. An auxiliary array |sig| holds the sums
$\sigma_k=\delta_1^2+\cdots+\delta_{k-1}^2$.  Additional arrays |xx|
and |yy| hold coordinates of vertices before and after a move is made.

Some of these arrays are also used for other purposes by other programs
besides |board|; we will meet those programs later.

We limit the number of dimensions to 91 or less. This is hardly a limitation,
since the number of vertices would be astronomical even if the dimensionality
were only half this big. But some of our later programs will be able
to make good use of 40 or 50 dimensions and perhaps more; the number 91
is an upper limit imposed by the number of standard printable characters
(see the convention for vertex names in the |perms| routine).

@d MAX_D 91

@<Private...@>=
static long nn[MAX_D+1]; /* component sizes */
static long wr[MAX_D+1]; /* does this component wrap around? */
static long del[MAX_D+1]; /* displacements for the current move */
static long sig[MAX_D+2]; /* partial sums of squares of displacements */
static long xx[MAX_D+1], yy[MAX_D+1]; /* coordinate values */

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

@ At this point, |nn[1]| through |nn[k-1]| are the component sizes
that should be replicated periodically. In unusual cases, the number
of dimensions might not be as large as the number of specifications.

@<Compute component sizes periodically...@>=
if (d>MAX_D) panic(bad_specs); /* too many dimensions */
for (j=1; k<=d; j++,k++) nn[k]=nn[j];

@ We want to make the subroutine idiot-proof, so we use floating-point
arithmetic to make sure that boards with more than a billion cells have
not been specified.

@d MAX_NNN 1000000000.0

@<Set up a graph with |n| vertices@>=
{@+float nnn; /* approximate size */
  for (n=1,nnn=1.0,j=1; j<=d; j++) {
    nnn *= (float)nn[j];
    if (nnn>MAX_NNN) panic(very_bad_specs); /* way too big */
    n *= nn[j]; /* this multiplication cannot cause integer overflow */
  }
  new_graph=gb_new_graph(n);
  if (new_graph==NULL)
    panic(no_room); /* out of memory before we're even started */
  sprintf(new_graph->id,"board(%ld,%ld,%ld,%ld,%ld,%ld,%d)",
    n1,n2,n3,n4,piece,wrap,directed?1:0);
  strcpy(new_graph->util_types,"ZZZIIIZZZZZZZZ");
  @<Give names to the vertices@>;
}

@ The symbolic name of a board position like $(3,1)$ will be the string
`\.{3.1}'. The first three coordinates are also stored as integers, in
utility fields |x.I|, |y.I|, and |z.I|, because immediate access to
those values will be helpful in certain applications. (The coordinates can,
of course, always be recovered in a slower fashion from the vertex name,
via |sscanf|.)

The process of assigning coordinate values and names is equivalent to
adding unity in a mixed-radix number system. Vertex $(x_1,\ldots,x_d)$
will be in position $x_1n_2\ldots n_d+\cdots+x_{d-1}n_d+x_d$ relative
to the first vertex of the new graph; therefore it is also possible to
deduce the coordinates of a vertex from its address.

@<Give names...@>=
{@+register char *q; /* string pointer */
  nn[0]=xx[0]=xx[1]=xx[2]=xx[3]=0;
  for (k=4;k<=d;k++) xx[k]=0;
  for (v=new_graph->vertices;;v++) {
    q=buffer;
    for (k=1;k<=d;k++) {
      sprintf(q,".%ld",xx[k]);
      while (*q) q++;
    }
    v->name=gb_save_string(&buffer[1]); /* omit |buffer[0]|, which is |'.'| */
    v->x.I=xx[1];@+v->y.I=xx[2];@+v->z.I=xx[3];
    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| */
  }
}
      
@ Now we come to a slightly tricky part of the routine: the move generator.
Let $p=\vert|piece|\vert$. The outer loop of this procedure runs through all
solutions of the equation $\delta_1^2+\cdots+\delta_d^2=p$, where the
$\delta$'s are nonnegative integers. Within that loop, we attach signs