gb_graph.w

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

  Vertex *u, *v; /* new arcs will go from |u| to |v| and from |v| to |u| */
  long len; /* their length */
{@+register Arc *cur_arc=gb_virgin_arc();
  if (cur_arc!=dummy_arc) next_arc++;
  if (u<v) {
    cur_arc->tip=v; @+cur_arc->next=u->arcs;
    (cur_arc+1)->tip=u; @+(cur_arc+1)->next=v->arcs;
    u->arcs=cur_arc; v->arcs=cur_arc+1;
  }@+else {
    (cur_arc+1)->tip=v; @+(cur_arc+1)->next=u->arcs;
    u->arcs=cur_arc+1; /* do this now in case |u==v| */
    cur_arc->tip=u; @+cur_arc->next=v->arcs;
    v->arcs=cur_arc;
  }
  cur_arc->len=(cur_arc+1)->len=len;
  cur_graph->m+=2;
}

@ Sometimes (let us hope rarely) we might need to use a dirty trick
hinted at in the previous discussion. On most computers, the mate to
arc~|a| will be |a-1| if and only if |edge_trick&(siz_t)a|
is nonzero.
@^system dependencies@>
@^pointer hacks@>

@<External d...@>=
siz_t edge_trick=sizeof(Arc)-(sizeof(Arc)&(sizeof(Arc)-1));

@ @(gb_graph.h@>=
extern siz_t edge_trick; /* least significant 1 bit in |sizeof(Arc)| */

@ The type |siz_t| just mentioned should be the type returned by \CEE/'s
|sizeof| operation; it's the basic unsigned type for machine
addresses in pointers. ANSI standard \CEE/ calls this type \&{size\_t},
but we cannot safely use \&{size\_t} in all the GraphBase programs
because some older \CEE/
systems mistakenly define \&{size\_t} to be a signed type.
@^system dependencies@>

@f siz_t int

@<Type d...@>=
typedef unsigned long @[siz_t@];
  /* basic machine address, as signless integer */

@ Vertices generally have a symbolic name, and we need a place to put
such names. The |gb_save_string| function is a convenient utility
for this purpose:
Given a null-terminated string of any length, |gb_save_string| stashes
it away in a safe place and returns a pointer to that place. Memory is
conserved by combining strings from the current graph into largish blocks
of a convenient size.

Note that |gb_save_string| should be used only after |gb_new_graph|
has provided suitable initialization, because the private variable
|cur_graph| must point to the graph for which storage is currently
being allocated, and because the private variables |next_string| and
|bad_string| must also have suitable values.

@d string_block_size 1016 /* $1024-8$ is usually efficient */

@<External f...@>=
char *gb_save_string(s)
  register char *s; /* the string to be copied */
{@+register char *p=s;
  register long len;
       /* length of the string and the following null character */
  while (*p++) ; /* advance to the end of the string */
  len=p-s;
  p=next_string;
  if (p+len>bad_string) { /* not enough room in the current block */
    long size=string_block_size;
    if (len>size)
      size=len;
    p=gb_alloc(size,cur_graph->data);
    if (p==NULL)
      return null_string; /* return a pointer to |""| if memory ran out */
    bad_string=p+size;
  }
  while (*s) *p++=*s++; /* copy the non-null bytes of the string */
  *p++='\0'; /* and append a null character */
  next_string=p;
  return p-len;
}

@ The test routine illustrates some of these basic maneuvers.

@<Create a small graph@>=
g=gb_new_graph(2L);
if (g==NULL) {
  fprintf(stderr,"Oops, I couldn't even create a trivial graph!\n");
  return -4;
}
u=g->vertices;@+ v=u+1;
u->name=gb_save_string("vertex 0");
v->name=gb_save_string("vertex 1");

@ @<Decl...@>=
Graph *g;
Vertex *u,*v;

@ If the ``edge trick'' fails, the standard GraphBase routines are
unaffected except for the demonstration program {\sc MILES\_\,SPAN}. (And
that program uses |edge_trick| only when printing verbose comments.)
@^edge trick failure@>

@<Check that the small graph is still there@>=
if (strncmp(u->name,v->name,7)) {
  fprintf(stderr,"Something is fouled up in the string storage machinery!\n");
  return -5;
}
gb_new_edge(v,u,-1L);
gb_new_edge(u,u,1L);
gb_new_arc(v,u,-1L);
if ((edge_trick&(siz_t)(u->arcs))||
    (edge_trick&(siz_t)(u->arcs->next->next))||
    !(edge_trick&(siz_t)(v->arcs->next)))
  printf("Warning: The \"edge trick\" failed!\n");
if (v->name[7]+g->n!=v->arcs->next->tip->name[7]+g->m-2) {
     /* |'1'+2!='0'+5-2| */
  fprintf(stderr,"Sorry, the graph data structures aren't working yet.\n");
  return -6;
}

@ Some applications might need to add arcs to several graphs at a time,
violating the assumptions stated above about |cur_graph| and the other
private variables. The |switch_to_graph| function gets around that
restriction, by using the utility slots |ww|, |xx|, |yy|, and
|zz| of |Graph| records to save and restore the private variables.

Just say |switch_to_graph(g)| in order to make |cur_graph| be~|g| and
to restore the other private variables that are needed by
|gb_new_arc|, |gb_virgin_arc|, |gb_new_edge|, and |gb_save_string|.
Restriction: The graph |g| being switched to must have previously been
switched from; that is, it must have been |cur_graph| when |switch_to_graph|
was called previously. Otherwise its private allocation variables will
not have been saved. To meet this restriction, you should say
|switch_to_graph(NULL)| just before calling |gb_new_graph|, if you
intend to switch back to the current graph later.

(The swap-in-swap-out nature of these conventions may seem inelegant, but
convenience and efficiency are more important than elegance when most
applications do not need the ability to switch between graphs.)

@<External f...@>=
void switch_to_graph(g)
  Graph *g;
{
  cur_graph->ww.A=next_arc; @+cur_graph->xx.A=bad_arc;
  cur_graph->yy.S=next_string; @+cur_graph->zz.S=bad_string;
  cur_graph=(g? g: &dummy_graph);
  next_arc=cur_graph->ww.A; @+bad_arc=cur_graph->xx.A;
  next_string=cur_graph->yy.S; @+bad_string=cur_graph->zz.S;
  cur_graph->ww.A=NULL;
  cur_graph->xx.A=NULL;
  cur_graph->yy.S=NULL;
  cur_graph->zz.S=NULL;
}

@ Finally,
here's a routine that obliterates an entire graph when it is no longer needed:

@<External fun...@>=
void gb_recycle(g)
  Graph *g;
{
  if (g) {
    gb_free(g->data);
    gb_free(g->aux_data);
    free((char*)g); /* the user must not refer to |g| again */
  }
}

@ @(gb_graph.h@>=
#define gb_new_graph gb_nugraph /* abbreviations for external linkage */
#define gb_new_arc gb_nuarc
#define gb_new_edge gb_nuedge
extern Graph*gb_new_graph(); /* create a new graph structure */
extern void gb_new_arc(); /* append an arc to the current graph */
extern Arc*gb_virgin_arc(); /* allocate a new |Arc| record */
extern void gb_new_edge(); /* append an edge (two arcs) to the current graph */
extern char*gb_save_string(); /* store a string in the current graph */
extern void switch_to_graph(); /* save allocation variables, swap in others */
extern void gb_recycle(); /* delete a graph structure */

@* Searching for vertices. We sometimes want to be able to find a vertex, given
its name, and it is nice to do this in a standard way. The following simple
subroutines can be used:

{\narrower
\smallskip|hash_in(v)| puts the name of vertex |v| into the hash table;
\smallskip|hash_out(s)| finds a vertex named |s|, if present in the hash table;
\smallskip|hash_setup(g)| prepares a hash table for all vertices of graph~|g|;
\smallskip|hash_lookup(s,g)| looks up the name |s| in the hash table of |g|.
\smallskip}

\noindent Routines |hash_in| and |hash_out| apply to the current graph being
created, while |hash_setup| and |hash_lookup| apply to arbitrary graphs.

Important: Utility fields |u| and |v| of each vertex are reserved for use by
the search routine when hashing is active. You can crash the system
if you try to fool around with these values yourself, or if you use any
subroutines that change those fields. The first two characters in the
current graph's |util_types| field should be \.{VV} if the hash table
information is to be saved by {\sc GB\_\,SAVE}.

Warning: Users of this hash scheme must preserve the number of
vertices |g->n| in the current graph~|g|. If |g->n| is changed,
the hash table will be worthless, unless |hash_setup| is used to
rehash everything.

@<gb_graph.h@>=
extern void hash_in(); /* input a name to the hash table of current graph */
extern Vertex* hash_out(); /* find a name in hash table of current graph */
extern void hash_setup(); /* create a hash table for a given graph */
extern Vertex* hash_lookup(); /* find a name in a given graph */

@ The lookup scheme is quite simple. We compute a more-or-less random
value |h| based on the vertex name, where |0<=h<n|, assuming that
the graph has |n|~vertices. There is a list of all vertices whose hash
address is~|h|, starting at |(g->vertices+h)->hash_head| and linked
together in the |hash_link| fields, where |hash_head| and |hash_link| are
utility fields |u.V| and |v.V|.

@d hash_link u.V
@d hash_head v.V

@ @<External fun...@>=
void hash_in(v)
  Vertex *v;
{@+  register char *t=v->name;
  register Vertex *u;
  @<Find vertex |u|, whose location is the hash code for string |t|@>;
  v->hash_link=u->hash_head;
  u->hash_head=v;
}

@ The hash code for a string $c_1c_2\ldots c_l$ of length $l$ is a
nonlinear function of the characters; this function appears to produce
reasonably random results between 0 and the number of vertices in the
current graph.  Simpler approaches were noticeably poorer in the
author's tests.

Caution: This hash coding scheme is system-dependent, because it
uses the system's character codes. If you create a graph on a
machine with ASCII code and save it with {\sc GB\_\,SAVE}, and if you
subsequently ship the
resulting text file to some friend whose machine does not use ASCII code,
your friend will have to rebuild the hash structure with |hash_setup|
before being able to use |hash_lookup| successfully.
@^character-set dependencies@>

@d HASH_MULT 314159 /* random multiplier */
@d HASH_PRIME 516595003 /* the 27182818th prime; it's less than $2^{29}$ */

@<Find vertex |u|...@>=
{@+register long h;
  for (h=0;*t;t++) {
    h+=(h^(h>>1))+HASH_MULT*(unsigned char)*t;
    while (h>=HASH_PRIME) h-=HASH_PRIME;
  }
  u=cur_graph->vertices+(h % cur_graph->n);
}

@ If the hash function were truly random, the average number of
string comparisons made would be less than $(e^2+7)/8\approx 1.80$ on
a successful search, and less than $(e^2+1)/4\approx2.10$ on an
unsuccessful search [{\sl Sorting and Searching}, Section 6.4,
Eqs.~(15) and~(16)].

@<External fun...@>=
Vertex* hash_out(s)
  char* s;
{@+register char *t=s;
  register Vertex *u;
  @<Find vertex |u|...@>;
  for (u=u->hash_head;u;u=u->hash_link)
    if (strcmp(s,u->name)==0) return u;
  return NULL; /* not found */
}

@ @<External fun...@>=
void hash_setup(g)
  Graph *g;
{@+Graph *save_cur_graph;
  if (g && g->n>0) {@+register Vertex *v;
    save_cur_graph=cur_graph;
    cur_graph=g;
    for (v=g->vertices;v<g->vertices+g->n;v++) v->hash_head=NULL;
    for (v=g->vertices;v<g->vertices+g->n;v++) hash_in(v);
    g->util_types[0]=g->util_types[1]='V';
         /* indicate usage of |hash_head| and |hash_link| */
    cur_graph=save_cur_graph;
  }
}

@ @<External fun...@>=
Vertex* hash_lookup(s,g)
  char *s;
  Graph *g;
{@+Graph *save_cur_graph;
  if (g && g->n>0) {@+register Vertex *v;
    save_cur_graph=cur_graph;
    cur_graph=g;
    v=hash_out(s);
    cur_graph=save_cur_graph;
    return v;
  }
  else return NULL;
}

@* Index. Here is a list that shows where the identifiers of this program are
defined and used.