gb_graph.w

模拟器提供了一个简单易用的平台

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

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

@* Introduction. This is {\sc GB\_\,GRAPH}, the data-structure module
used by all GraphBase routines to allocate memory. The basic data
types for graph representation are also defined~here.

Many examples of how to use these conventions appear in other GraphBase
modules. The best introduction to such examples can probably be found
in {\sc GB\_\,BASIC}, which contains subroutines for generating and
transforming various classical graphs.

@ The code below is believed to be system-independent; it should
produce equivalent results on all systems, assuming that the standard
|calloc| and |free| functions of \CEE/ are available.

However, a test program helps build confidence that everything does in fact
work as it should. To make such a test, simply compile and run \.{test\_graph}.
This particular test is fairly rudimentary, but it should be passed before
more elaborate routines are tested.

@(test_graph.c@>=
#include "gb_graph.h"  /* all users of {\sc GB\_\,GRAPH} should do this */
@<Declarations of test variables@>@;
@#
int main()
{
  @<Create a small graph@>;
  @<Test some intentional errors@>;
  @<Check that the small graph is still there@>;
  printf("OK, the gb_graph routines seem to work!\n");
  return 0;
}

@ The \CEE/ code for {\sc GB\_\,GRAPH} doesn't have a main routine;
it's just a bunch of subroutines waiting to be incorporated into
programs at a higher level via the system loading routine. Here is
the general outline of \.{gb\_graph.c}:

@p
#ifdef SYSV
#include <string.h>
#else
#include <strings.h>
#endif
#include <stdio.h>
#include <stdlib.h>
@h@#
@<Type declarations@>@;
@<Private declarations@>@;
@<External declarations@>@;
@<External functions@>

@ The type declarations of {\sc GB\_\,GRAPH} appear also in the header file
\.{gb\_graph.h}. For convenience, that header file also incorporates the
standard system headers for input/output and string manipulation.

Some system header files define an unsafe macro called |min|, which will
interfere with GraphBase use of a useful identifier. We scotch that.

@(gb_graph.h@>=
#include <stdio.h>
#include <stdlib.h>
#ifdef SYSV
#include <string.h>
#else
#include <strings.h>
#endif
#undef min
@<Type declarations@>@;

@ GraphBase programs often have a ``verbose'' option, which needs to
be enabled by the setting of an external variable. They also tend to have
a variable called |panic_code|, which helps identify unusual errors.
We might as well declare those variables here.

@<External d...@>=
long verbose=0; /* nonzero if ``verbose'' output is desired */
long panic_code=0; /* set nonzero if graph generator returns null pointer */

@ Every external variable should be declared twice in this \.{CWEB}
file: once for {\sc GB\_\,GRAPH} itself (the ``real'' declaration for
storage allocation purposes) and once in \.{gb\_graph.h} (for
cross-references by {\sc GB\_\,GRAPH} users).

@(gb_graph.h@>=
extern long verbose; /* nonzero if ``verbose'' output is desired */
extern long panic_code; /* set nonzero if graph generator panics */

@ When |panic_code| is assigned a nonzero value, one of the symbolic
names defined here is used to help pinpoint the problem.
Small values indicate memory limitations; values in the 10s and 20s
indicate input/output anomalies; values in the 30s and 40s indicate
errors in the parameters to a subroutine. Some panic codes
stand for cases the author doesn't think will ever arise, although
the program checks for them just to be extra safe. Multiple instances
of the same type of error within a single subroutine are distinguished
by adding an integer; for example, `|syntax_error+1|' and `|syntax_error+2|'
identify two different kinds of syntax error, as an aid in trouble-shooting.
The |early_data_fault| and |late_data_fault| codes are explained further
by the value of |io_errors|.

@(gb_graph.h@>=
#define alloc_fault (-1) /* a previous memory request failed */
#define no_room 1 /* the current memory request failed */
#define early_data_fault 10 /* error detected at beginning of \.{.dat} file */
#define late_data_fault 11 /* error detected at end of \.{.dat} file */
#define syntax_error 20 /* error detected while reading \.{.dat} file */
#define bad_specs 30 /* parameter out of range or otherwise disallowed */
#define very_bad_specs 40 /* parameter far out of range or otherwise stupid */
#define missing_operand 50 /* graph parameter is |NULL| */
#define invalid_operand 60 /* graph parameter doesn't obey assumptions */
#define impossible 90 /* ``this can't happen'' */

@* Representation of graphs. The GraphBase programs employ a simple
and flexible set of data structures to represent and manipulate graphs
in computer memory.  Vertices appear in a sequential array of
\&{Vertex} records, and the arcs emanating from each vertex appear in
a linked list of \&{Arc} records. There is also a \&{Graph} record, to
provide information about the graph as a whole.

The structure layouts for \&{Vertex}, \&{Arc}, and \&{Graph} records
include a number of utility fields that can be used for any purpose by
algorithms that manipulate the graphs. Each utility field is a union
type that can be either a pointer of various kinds or a (long) integer.

Let's begin the formal definition of these data structures by declaring the
union type \&{util}. The suffixes .|V|, .|A|, .|G|, and .|S| on the name
of a utility variable mean that the variable is a pointer to a vertex, arc,
graph, or string, respectively; the suffix .|I| means that the variable is
an integer. (We use one-character names because such names are easy to type
when debugging.)

@<Type dec...@>=
typedef union {
  struct vertex_struct *V; /* pointer to \&{Vertex} */
  struct arc_struct *A; /* pointer to \&{Arc} */
  struct graph_struct *G; /* pointer to \&{Graph} */
  char *S; /* pointer to string */
  long I; /* integer */
} util;

@ Each \&{Vertex} has two standard fields and six utility fields; hence it
occupies 32 bytes on most systems, not counting the memory needed for
supplementary string data. The standard fields are
$$\vcenter{\halign{#,\ \ \hfil&#\hfil\cr
|arcs|&a pointer to an \&{Arc};\cr
|name|&a pointer to a string of characters.\cr}}$$
If |v| points to a \&{Vertex} and |v->arcs| is |NULL|, there are no arcs
emanating from~|v|. But if |v->arcs| is non-|NULL|, it points to an \&{Arc}
record representing an arc from~|v|, and that record has a |next| field that
points in the same way to the representations of all other arcs from~|v|.

The utility fields are called |u|, |v|, |w|, |x|, |y|, |z|. Macros can
be used to give them syntactic sugar in particular applications. They are
typically used to record such things as the in-degree or out-degree, or
whether a vertex is `marked'. Utility fields might also link the vertex
to other vertices or arcs in one or more lists.

@<Type dec...@>=
typedef struct vertex_struct {
  struct arc_struct *arcs; /* linked list of arcs coming out of this vertex */
  char *name; /* string identifying this vertex symbolically */
  util u,v,w,x,y,z; /* multipurpose fields */
} Vertex;

@ Each \&{Arc} has three standard fields and two utility fields. Thus it
occupies 20~bytes on most computer systems. The standard fields are
$$\vcenter{\halign{#,\ \ \hfil&#\hfil\cr
|tip|&a pointer to a |Vertex|;\cr
|next|&a pointer to an \&{Arc};\cr
|len|&a (long) integer.\cr}}$$
If |a| points to an \&{Arc} in the list of arcs from vertex~|v|, it represents
an arc of length |a->len| from |v| to |a->tip|, and the next arc from |v|
in the list is represented by |a->next|.

The utility fields are called |a| and |b|.

@<Type dec...@>=
typedef struct arc_struct {
  struct vertex_struct *tip; /* the arc points to this vertex */
  struct arc_struct *next; /* another arc pointing from the same vertex */
  long len; /* length of this arc */
  util a,b; /* multipurpose fields */
} Arc;

@* Storage allocation. Memory space must be set aside dynamically for
vertices, arcs, and their attributes. The GraphBase routines provided by
{\sc GB\_\,GRAPH} accomplish this task with reasonable ease and efficiency
by using the concept of memory ``areas.'' The user should first declare an
\&{Area} variable by saying, for example,
$$\hbox{\&{Area} |s|;}$$
and if this variable isn't static or otherwise known to be zero, it must be
cleared initially by saying `|init_area(s)|'. Then any number of subroutine
calls of the form  `|gb_alloc(n,s)|' can be given; |gb_alloc|
will return a pointer to a block of |n| consecutive bytes, all cleared to zero.
Finally, the user can issue the command
$$\hbox{|gb_free(s)|;}$$
this statement will return all memory blocks currently allocated to area~|s|,
making them available for future allocation.

The number of bytes |n| specified to |gb_alloc| must be positive, and
it should usually be 1000 or more, since this will reduce the number
of system calls. Other routines are provided below to allocate smaller
amounts of memory, such as the space needed for a single new \&{Arc}.

If no memory of the requested size is presently available, |gb_alloc|
returns the null pointer |NULL|. In such cases |gb_alloc| also sets
the external variable |gb_trouble_code| to a nonzero value. The user
can therefore discover whether any one of an arbitrarily long series
of allocation requests has failed by making a single test, `|if
(gb_trouble_code)|'. The value of |gb_trouble_code| should be cleared to zero
by every graph generation subroutine; therefore it need not be
initialized to zero.

A special macro |gb_typed_alloc(n,t,s)| makes it convenient to allocate
the space for |n| items of type~|t| in area~|s|.

@d gb_typed_alloc(n,t,s) @[(t*)@]gb_alloc((long)((n)*@[sizeof@](t)),s)

@ The implementation of this scheme is almost ridiculously easy. The
value of~|n| is increased by twice the number of bytes in a pointer,
and the resulting number is rounded upwards if necessary so that it's
a multiple of 256. Then memory is allocated using |calloc|.  The extra
bytes will contain two pointers, one to the beginning of the block and
one to the next block associated with the same area variable.

The \&{Area} type is defined to be an array of length 1. This makes it possible
for users to say just `|s|' instead of `|&s|' when using an area
variable as a parameter.

@<Type...@>=
#define init_area(s) @t\quad@> @[*s=NULL@]
struct area_pointers {
  char *first; /* address of the beginning of this block */
  struct area_pointers *next; /* address of area pointers in the previously
        allocated block */
};

typedef struct area_pointers *Area[1];

@ First we round |n| up, if necessary, so that it's a multiple of the
size of a pointer variable. Then we know we can put |area_pointers| into
memory at a position |n| after any address returned by |calloc|. (This
logic should work whenever the number of bytes in a pointer variable
is a divisor of~256.)

The upper limit on |n| here is governed by old \CEE/ conventions in
which the first parameter to |calloc| must be less than~$2^{16}$.
Users who need graphs with more than half a million vertices might
want to raise this limit on their systems, but they would probably
be better off representing large graphs in a more compact way.

{\sl Important Note:\/}
Programs of the Stanford GraphBase implicitly assume that all
memory allocated by |calloc| comes from a single underlying memory array.
Pointer values are compared to each other in many places, even when
the objects pointed to have been allocated at different times. Strictly
speaking, this liberal use of pointer comparisons fails to conform to
the restrictions of ANSI Standard \CEE/, if the comparison involves
a less-than or greater-than relation. Users whose system supports only
the strict standard will need to make several dozen changes.
@^system dependencies@>

@<External fun...@>=
char *gb_alloc(n,s)
  long n; /* number of consecutive bytes desired */
  Area s; /* storage area that will contain the new block */
{@+long m=sizeof(char *); /* |m| is the size of a pointer variable */
  Area t; /* a temporary pointer */
  char *loc; /* the block address */
  if (n<=0 || n>0xffff00-2*m) {
    gb_trouble_code|=2; /* illegal request */
    return NULL;
  }
  n=((n+m-1)/m)*m; /* round up to multiple of |m| */
  loc=(char*)calloc((unsigned)((n+2*m+255)/256),256);
  if (loc) {
    *t=(struct area_pointers*)(loc+n);
    (*t)->first=loc;
    (*t)->next=*s;
    *s=*t;
  }@+else gb_trouble_code|=1;
  return loc;
}

@ @<External d...@>=
long gb_trouble_code=0; /* did |gb_alloc| return |NULL|? */

@ @(gb_graph.h@>=
extern long gb_trouble_code; /* anomalies noted by |gb_alloc| */

@ Notice that |gb_free(s)| can be called twice in a row, because the list
of blocks is cleared out of the area variable~|s|.

@<External fun...@>=
void gb_free(s)
  Area s;
{@+Area t;
  while (*s) {
    *t=(*s)->next;
    free((*s)->first);
    *s=*t;
  }
}

@ The two external procedures we've defined above should be mentioned in
the header file, so let's do that before we forget.

@(gb_graph.h@>=
extern char *gb_alloc(); /* allocate another block for an area */
#define gb_typed_alloc(n,t,s) @[@t\quad@>\