gb_graph.w

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

               @[(t*)@]gb_alloc((long)((n)*@[sizeof@](t)),s)@]
extern void gb_free(); /* deallocate all blocks for an area */

@ Here we try to allocate 10 million bytes of memory. If we succeed,
fine; if not, we verify that the error was properly reported.

(An early draft of this program attempted to allocate memory until all
space was exhausted. That tactic provided a more thorough test, but it
was a bad idea because it brought certain large systems to their
knees; it was terribly unfriendly to other users who were innocently
trying to do their own work on the same machine.)

@<Test some intentional errors@>=
if (gb_alloc(0L,s)!=NULL || gb_trouble_code!=2) {
  fprintf(stderr,"Allocation error 2 wasn't reported properly!\n");@+return -2;
}
for (;g->vv.I<100;g->vv.I++)@+ if (gb_alloc(100000L,s)) {
  g->uu.I++;
  printf(".");
  fflush(stdout);
}
if (g->uu.I<100 && gb_trouble_code!=3) {
  fprintf(stderr,"Allocation error 1 wasn't reported properly!\n");@+return -1;
}
if (g->uu.I==0) {
  fprintf(stderr,"I couldn't allocate any memory!\n");@+return -3;
}
gb_free(s); /* we've exhausted memory, let's put some back */
printf("Hey, I allocated %ld00000 bytes successfully. Terrific...\n",g->uu.I);

gb_trouble_code=0;

@ @<Decl...@>=
Area s; /* temporary allocations in the test routine */

@*Growing a graph. Now we're ready to look at the \&{Graph} type. This is
a data structure that can be passed to an algorithm that operates on
graphs---to find minimum spanning trees, or strong components, or whatever.

A \&{Graph} record has seven standard fields and six utility fields. The
standard fields are
$$\vcenter{\halign{#,\ \ \hfil&#\hfil\cr
|vertices|&a pointer to an array of |Vertex| records;\cr
|n|&the total number of vertices;\cr
|m|&the total number of arcs;\cr
|id|&a symbolic identification giving parameters of the GraphBase procedure\cr
\omit& that generated this graph;\cr
|util_types|&a symbolic representation of the data types in utility fields;\cr
|data|&an |Area| used for |Arc| storage and string storage;\cr
|aux_data|&an |Area| used for auxiliary information that some users might\cr
\omit     &want to discard.\cr}}$$
The utility fields are called |uu|, |vv|, |ww|, |xx|, |yy|, and |zz|.

As a consequence of these conventions, we can visit all arcs of a
graph~|g| by using the following program:
$$\vcenter{\halign{#\hfil\cr
|Vertex *v;|\cr
|Arc *a;|\cr
|for (v=g->vertices; v<g->vertices+g->n; v++)|\cr
\quad|for (a=v->arcs; a; a=a->next)|\cr
\qquad\\{visit}|(v,a)|;\cr}}$$

@<Type...@>=
#define ID_FIELD_SIZE 161
typedef struct graph_struct {
  Vertex *vertices; /* beginning of the vertex array */
  long n; /* total number of vertices */
  long m; /* total number of arcs */
  char id[ID_FIELD_SIZE]; /* GraphBase identification */
  char util_types[15]; /* usage of utility fields */
  Area data; /* the main data blocks */
  Area aux_data; /* subsidiary data blocks */
  util uu,vv,ww,xx,yy,zz; /* multipurpose fields */
} Graph;

@ The |util_types| field should always hold a string of length 14, followed
as usual by a null character to terminate that string. The first six
characters of |util_types| specify the usage of utility fields |u|, |v|,
|w|, |x|, |y|, and~|z| in |Vertex| records; the next two characters give the
format of the utility fields in |Arc| records; the last six give the
format of the utility fields in |Graph| records.  Each character
should be either \.I (denoting a |long| integer),
\.S (denoting a pointer to a string),
\.V (denoting a pointer to a |Vertex|), \.A (denoting a pointer to an
|Arc|), \.G (denoting a pointer to a |Graph|), or \.Z (denoting an
unused field that remains zero). The default for |util_types| is
|"ZZZZZZZZZZZZZZ"|, when none of the utility fields is being used.

For example, suppose that a bipartite graph |g| is using field |g->uu.I|
to specify the size of its first part. Suppose further that |g| has a
string in utility field |a| of each |Arc| and uses
utility field |w| of |Vertex| records to point to an |Arc|. If |g|
leaves all other utility fields untouched, its |util_types| should be
|"ZZAZZZSZIZZZZZ"|.

The |util_types| string is presently examined only by the |save_graph| and
|restore_graph| routines, which convert GraphBase graphs from internal
data structures to symbolic external files and vice versa. Therefore
users need not update the |util_types| when they write algorithms to
manipulate graphs, unless they are going to use |save_graph| to output
a graph in symbolic form, or unless they are using some other
GraphBase-related software that might rely on the conventions of
|util_types|.  (Such software is not part of the ``official'' Stanford
GraphBase, but it might conceivably exist some~day.)

@ Some applications of bipartite graphs require all vertices of the first
part to appear at the beginning of the |vertices| array. In such cases,
utility field |uu.I| is traditionally given the symbolic name |n_1|, and
it is set equal to the size of that first part. The size of the other
part is then |g->n - g->n_1|.
@^bipartite graph@>

@d n_1 uu.I /* utility field |uu| may denote size of bipartite first part */

@(gb_graph.h@>=
#define n_1 @t\quad@> uu.I
#define mark_bipartite(g,n1) @[g->n_1=n1,g->util_types[8]='I'@]

@ A new graph is created by calling |gb_new_graph(n)|, which returns a
pointer to a |Graph| record for a graph with |n| vertices and no arcs.
This function also initializes several private variables that are used
by the |gb_new_arc|, |gb_new_edge|, |gb_virgin_arc|, and |gb_save_string|
procedures below.

We actually reserve space for |n+extra_n| vertices, although claiming only~$n$,
because several graph manipulation algorithms like to add a special vertex
or two to the graphs they deal with. 

@<External f...@>=
Graph *gb_new_graph(n)
  long n; /* desired number of vertices */
{
  cur_graph=(Graph*)calloc(1,sizeof(Graph));
  if (cur_graph) {
    cur_graph->vertices=gb_typed_alloc(n+extra_n,Vertex,cur_graph->data);
    if (cur_graph->vertices) {Vertex *p;
      cur_graph->n=n;
      for (p=cur_graph->vertices+n+extra_n-1; p>=cur_graph->vertices; p--)
        p->name=null_string;
      sprintf(cur_graph->id,"gb_new_graph(%ld)",n);
      strcpy(cur_graph->util_types,"ZZZZZZZZZZZZZZ");
    }@+else {
      free((char*)cur_graph);
      cur_graph=NULL;
    }
  }
  next_arc=bad_arc=NULL;
  next_string=bad_string=NULL;
  gb_trouble_code=0;
  return cur_graph;
}

@ The value of |extra_n| is ordinarily~4, and it should probably always be at
least~4.

@<External d...@>=
long extra_n=4; /* the number of shadow vertices allocated by |gb_new_graph| */
char null_string[1]; /* a null string constant */

@ @(gb_graph.h@>=
extern long extra_n;
  /* the number of shadow vertices allocated by |gb_new_graph| */
extern char null_string[]; /* a null string constant */
extern void make_compound_id();
  /* routine to set one |id| field from another */
extern void make_double_compound_id(); /* ditto, but from two others */

@ The |id| field of a graph is sometimes manufactured from the |id| field
of another graph. The following routines do this without allowing the
string to get too long after repeated copying.

@<External f...@>=
void make_compound_id(g,s1,gg,s2) /* |sprintf(g->id,"%s%s%s",s1,gg->id,s2)| */
  Graph *g; /* graph whose |id| is to be set */
  char *s1; /* string for the beginning of the new |id| */
  Graph *gg; /* graph whose |id| is to be copied */
  char *s2; /* string for the end of the new |id| */
{@+int avail=ID_FIELD_SIZE-strlen(s1)-strlen(s2);
  char tmp[ID_FIELD_SIZE];
  strcpy(tmp,gg->id);
  if (strlen(tmp)<avail) sprintf(g->id,"%s%s%s",s1,tmp,s2);
  else sprintf(g->id,"%s%.*s...)%s",s1,avail-5,tmp,s2);
}

@ @<External f...@>=
void make_double_compound_id(g,s1,gg,s2,ggg,s3)
              /* |sprintf(g->id,"%s%s%s%s%s",s1,gg->id,s2,ggg->id,s3)| */
  Graph *g; /* graph whose |id| is to be set */
  char *s1; /* string for the beginning of the new |id| */
  Graph *gg; /* first graph whose |id| is to be copied */
  char *s2; /* string for the middle of the new |id| */
  Graph *ggg; /* second graph whose |id| is to be copied */
  char *s3; /* string for the end of the new |id| */
{@+int avail=ID_FIELD_SIZE-strlen(s1)-strlen(s2)-strlen(s3);
  if (strlen(gg->id)+strlen(ggg->id)<avail)
    sprintf(g->id,"%s%s%s%s%s",s1,gg->id,s2,ggg->id,s3);
  else sprintf(g->id,"%s%.*s...)%s%.*s...)%s",s1,avail/2-5,gg->id,
             s2,(avail-9)/2,ggg->id,s3);
}

@ But how do the arcs get there? That's where the private variables in
|gb_new_graph| come in. If |next_arc| is unequal to |bad_arc|, it points to
an unused |Arc| record in a previously allocated block of |Arc| records.
Similarly, |next_string| and |bad_string| are addresses used to
place strings into a block of memory allocated for that purpose.

@<Private...@>=
static Arc *next_arc; /* the next |Arc| available for allocation */
static Arc *bad_arc; /* but if |next_arc=bad_arc|, that |Arc| isn't there */
static char *next_string; /* the next byte available for storing a string */
static char *bad_string; /* but if |next_string=bad_string|, don't byte */
static Arc dummy_arc[2]; /* an |Arc| record to point to in an emergency */
static Graph dummy_graph; /* a |Graph| record that's normally unused */
static Graph *cur_graph=&dummy_graph; /* the |Graph| most recently created */

@ All new |Arc| records that are created by the automatic |next_arc|/|bad_arc|
scheme originate in a procedure called |gb_virgin_arc|, which returns the
address of a new record having type |Arc|.

When a new block of |Arc| records is needed, we create 102 of them at once.
This strategy causes exactly 2048 bytes to be allocated on most
computer systems---a nice round number. The routine will still work, however,
if 102 is replaced by any positive even number. The new block goes into
the |data| area of |cur_graph|.

Graph-building programs do not usually call |gb_virgin_arc| directly;
they generally invoke one of the higher-level routines |gb_new_arc|
or |gb_new_edge| described below.

If memory space has been exhausted, |gb_virgin_arc| will return a
pointer to |dummy_arc|, so that the calling procedure can safely
refer to fields of the result even though |gb_trouble_code| is nonzero.

@d arcs_per_block 102

@<External f...@>=
Arc *gb_virgin_arc()
{@+register Arc *cur_arc=next_arc;
  if (cur_arc==bad_arc) {
    cur_arc=gb_typed_alloc(arcs_per_block,Arc,cur_graph->data);
    if (cur_arc==NULL)
      cur_arc=dummy_arc;
    else {
      next_arc = cur_arc+1;
      bad_arc = cur_arc+arcs_per_block;
    }
  }
  else next_arc++;
  return cur_arc;
}

@ The routine |gb_new_arc(u,v,len)| creates a new arc of length |len|
from vertex~|u| to vertex~|v|. The arc becomes part of the graph that
was most recently created by |gb_new_graph|---the graph
pointed to by the private variable |cur_graph|. This routine assumes
that |u| and |v| are both vertices in |cur_graph|.

The new arc will be pointed to by |u->arcs|, immediately after
|gb_new_arc(u,v,len)| has acted. If there is no room for the new arc,
|gb_trouble_code| is set nonzero, but |u->arcs| will point to the non-|NULL|
record |dummy_arc|
so that additional information can safely be stored in its utility fields
without risking system crashes before |gb_trouble_code| is tested.
However, the linking structure of arcs is apt to be fouled up in such
cases; programs should make sure that |gb_trouble_code==0| before doing any
extensive computation on a graph.

@<External f...@>=
void gb_new_arc(u,v,len)
  Vertex *u, *v; /* a newly created arc will go from |u| to |v| */
  long len; /* its length */
{@+register Arc *cur_arc=gb_virgin_arc();
  cur_arc->tip=v; @+cur_arc->next=u->arcs; @+cur_arc->len=len;
  u->arcs=cur_arc;
  cur_graph->m++;
}

@ An undirected graph has ``edges'' instead of arcs. We represent an edge
by two arcs, one going each way.
@^undirected graph@>

The fact that |arcs_per_block| is even means that the |gb_new_edge|
routine needs to call |gb_virgin_arc| only once instead of twice.

Caveats: This routine, like |gb_new_arc|, should be used only after
|gb_new_graph| has caused the private variable |cur_graph| to point to
the graph containing the new edge. The routine |gb_new_edge| must
not be used together with |gb_new_arc| or |gb_virgin_arc| when
building a graph, unless |gb_new_arc| and |gb_virgin_arc| have been
called an even number of times before |gb_new_edge| is invoked.

The new edge will be pointed to by |u->arcs| and by |v->arcs| immediately
after |gb_new_edge| has created it, assuming that |u!=v|. The two arcs
appear next to each other in memory; indeed, |gb_new_edge| rigs things so
that |v->arcs| is |u->arcs+1| when |u<v|.

On many computers it turns out that the first |Arc| record of every such
pair of arcs will have an address that is a multiple of~8, and the
second |Arc| record will have an address that is not a multiple of~8 (because
the first |Arc| will be 20 bytes long, and because |calloc| always returns
a multiple of~8). However, it is not safe to assume this when writing
portable code. Algorithms for undirected graphs can still make good use of
the fact that arcs for edges are paired, without needing any mod~8 assumptions,
if all edges have been created and linked into the graph by |gb_new_edge|:
The inverse of an arc~|a| from |u| to~|v| will be arc |a+1| if and only if
|u<v| or |a->next=a+1|; it will be arc |a-1| if and only if |u>=v| and
|a->next!=a+1|. The condition |a->next=a+1| can hold only if |u=v|.

@d gb_new_graph gb_nugraph /* abbreviations for Procrustean linkers */
@d gb_new_arc gb_nuarc
@d gb_new_edge gb_nuedge

@<External f...@>=
void gb_new_edge(u,v,len)