gb_books.w

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

if (gb_close()!=0)
  panic(late_data_fault);
    /* checksum or other failure in data file; see |io_errors| */

@ @<Read the character codes...@>=
for (k=0;k<MAX_CODE;k++) xnode[k]=NULL;
{@+register long c; /* current code entering the system */
  p=node_block; /* current node entering the system */
  while ((c=gb_number(36))!=0) { /* note that \.{00} is not a legal code */
    if (c>=MAX_CODE || gb_char()!=' ') panic(syntax_error);
                                     /* unreadable line in data file */
    if (p>=&node_block[MAX_CHARS])
      panic(syntax_error+1); /* data has too many characters */
    p->link=(p==node_block?NULL:p-1);
    p->code=c;
    xnode[c]=p;
    p->in=p->out=p->chap=0;
    p->vert=NULL;
    p++;
    gb_newline();
  }
  characters=p-node_block;
  gb_newline(); /* bypass the blank line that terminates the character data */
}

@ Later we will read through this part of the file again, extracting
additional information if it turns out to be relevant. The
\<description> string is provided to users in a |desc| field,
in case anybody cares to look at it. The |in| and |out| statistics
are also made available in utility fields called |in_count| and |out_count|.
The code value is placed in the |short_code| field.

@d desc z.S /* utility field |z| points to the \<description> string */
@d in_count y.I /* utility field |y| counts appearances in selected chapters */
@d out_count x.I /* utility field |x| counts appearances in other chapters */
@d short_code u.I /* utility field |u| contains a radix-36 number */

@<Read the data about characters again, noting vertex names and the
  associated descriptions@>=
{@+register long c; /* current code entering the system a second time */
  while ((c=gb_number(36))!=0) {@+register Vertex *v=xnode[c]->vert;
    if (v) {
      if (gb_char()!=' ') panic(impossible); /* can't happen */
      gb_string(str_buf,','); /* scan the \<name> part */
      v->name=gb_save_string(str_buf);
      if (gb_char()!=',')
        panic(syntax_error+2); /* missing comma after \<name> */
      if (gb_char()!=' ')
        panic(syntax_error+3); /* missing space after comma */
      gb_string(str_buf,'\n'); /* scan the \<description> part */
      v->desc=gb_save_string(str_buf);
      v->in_count=xnode[c]->in;
      v->out_count=xnode[c]->out;
      v->short_code=c;
    }
    gb_newline();
  }
  gb_newline(); /* bypass the blank line that terminates the character data */
}  

@ @(gb_books.h@>=
#define desc @t\quad@> z.S /* utility field definitions for the header file */
#define in_count @t\quad@> y.I
#define out_count @t\quad@> x.I
#define short_code @t\quad@> u.I

@*Edges.
The second part of the data file has a line for each chapter, containing
``cliques of encounters.'' For example, the line
$$\hbox{\tt3.22:AA,BB,CC,DD;CC,DD,EE;AA,FF}$$
means that, in chapter 22 of book 3, there were encounters between the pairs
$$\def\\{{\rm,} }
\hbox{\tt AA-BB\\AA-CC\\AA-DD\\BB-CC\\BB-DD\\CC-DD\\CC-EE\\DD-EE\\{\rm and }%
AA-FF\rm.}$$
(The encounter \.{CC-DD} is specified twice, once in the clique
\.{AA,BB,CC,DD} and once in \.{CC,DD,EE}; this does not imply anything about
the actual number of encounters between \.{CC} and \.{DD} in the chapter.)

A clique might involve one character only, when that character is featured
in sort of a soliloquy.

A chapter might contain no references to characters at all. In such a case
the `\.:' following the chapter number is omitted.

There might be more encounters than will fit on a single line. In such cases,
continuation lines begin with `\.{\&:}'. This convention turns out to be
needed only in \.{homer.dat}; chapters in {\sl The Iliad\/} are
substantially more complex than the chapters in other GraphBase books.

On our first pass over the data, we simply want to compute statistics about
who appears in what chapters, so we ignore the distinction between
commas and semicolons.

@<Skim the chapter information, counting the number of chapters in
  which each character appears@>=
for (k=1; k<MAX_CHAPS && !gb_eof(); k++) {
  gb_string(str_buf,':'); /* read past the chapter number */
  if (str_buf[0]=='&') k--; /* continuation of previous chapter */
  while (gb_char()!='\n') {@+register long c=gb_number(36);
    if (c>=MAX_CODE)
      panic(syntax_error+4); /* missing punctuation between characters */
    p=xnode[c];
    if (p==NULL) panic(syntax_error+5); /* unknown character */
    if (p->chap!=k) {
      p->chap=k;
      if (k>=first_chapter && k<=last_chapter) p->in++;
      else p->out++;
    }
  }
  gb_newline();
}
if (k==MAX_CHAPS) panic(syntax_error+6); /* too many chapters */
chapters=k-1;

@ Our second pass over the data is very similar to the first, if we
are simply computing a bipartite graph. In that case we add an edge
to the graph between each selected chapter and each selected character
in that chapter. Local variable |chap_base| will point to a
vertex such that |chap_base+k| is the vertex corresponding to chapter~|k|.

The |in_count| of a chapter vertex is the degree of that vertex, i.e., the
number of selected characters that appear in the corresponding chapter.
The |out_count| is the number of characters that appear in the
chapter but were omitted from the graph. Thus the |in_count| and
|out_count| for chapters are analogous to the |in_count| and |out_count|
for characters.

@<Read the chapter information a second time and create the
  appropriate bipartite edges@>=
{
  for (p=node_block;p<node_block+characters;p++) p->chap=0;
  for (k=1; !gb_eof(); k++) {
    gb_string(str_buf,':'); /* read the chapter number */
    if (str_buf[0]=='&') k--;
    else chap_name[k]=gb_save_string(str_buf);
    if (k>=first_chapter && k<=last_chapter) {@+register Vertex *u=chap_base+k;
      if (str_buf[0]!='&') {
        u->name=chap_name[k];
        u->desc=null_string;
        u->in_count=u->out_count=0;
      }
      while (gb_char()!='\n') {@+register long c=gb_number(36);
        p=xnode[c];
        if (p->chap!=k) {@+register Vertex *v=p->vert;
          p->chap=k;
          if (v) {@+
            gb_new_edge(v,u,1L);
            u->in_count++;
          }@+else u->out_count++;
        }
      }
    }
    gb_newline();
  }
}

@ @<Local variables@>=
Vertex *chap_base;
  /* the bipartite vertex for chapter~|k| is |chap_base+k| */

@ The second pass has to work a little harder when we are recording
encounters from cliques, but the logic isn't difficult really.
We insert a reference to the first chapter that generated each edge, in
utility field |chap_no| of the corresponding |Arc| record.

@d chap_no a.I /* utility field |a| holds a chapter number */

@<Read the chapter information a second time and create the
  appropriate edges for encounters@>=
for (k=1; !gb_eof(); k++) {@+char *s;
  s=gb_string(str_buf,':'); /* read the chapter number */
  if (str_buf[0]=='&') k--;
  else {@+if (*(s-2)=='\n') *(s-2)='\0';
    chap_name[k]=gb_save_string(str_buf);
  }
  if (k>=first_chapter && k<=last_chapter) {@+register long c=gb_char();
    while (c!='\n') {@+register Vertex **pp=clique_table;
      register Vertex **qq,**rr; /* pointers within the clique table */
      do@+{@+
        c=gb_number(36); /* set |c| to code for next character of clique */
        if (xnode[c]->vert) /* is that character a selected vertex? */
          *pp++=xnode[c]->vert;
            /* if so, that vertex joins the current clique */
        c=gb_char();
      }@+while (c==','); /* repeat until end of the clique */
      for (qq=clique_table;qq+1<pp;qq++)
        for (rr=qq+1;rr<pp;rr++)
          @<Make the vertices |*qq| and |*rr| adjacent,
              if they aren't already@>;
    }
  }
  gb_newline();
}

@ @(gb_books.h@>=
#define chap_no @[a.I@] /* utility field definition in the header file */

@ @<Priv...@>=
static Vertex *clique_table[30];
 /* pointers to vertices in the current clique */

@ @<Make the vertices |*qq| and |*rr| adjacent...@>=
{@+register Vertex *u=*qq, *v=*rr;
  register Arc *a;
  for (a=u->arcs; a; a=a->next)
    if (a->tip==v) goto found;
  gb_new_edge(u,v,1L); /* not found, so they weren't already adjacent */
  if (u<v) a=u->arcs;
  else a=v->arcs; /* the new edge consists of arcs |a| and |a+1| */
  a->chap_no=(a+1)->chap_no=k;
found:;
}

@*Administration.
The program is now complete except for a few missing organizational details.
I will add these after lunch.
@^out to lunch@>

@ OK, I'm back; what needs to be done? The main thing is to create
the graph itself.

@<Choose the vertices and put them into an empty graph@>=
if (n>characters) n=characters;
if (x>n) x=n;
if (last_chapter>chapters) last_chapter=chapters;
if (first_chapter>last_chapter) first_chapter=last_chapter+1;
new_graph=gb_new_graph(n-x+(bipartite?last_chapter-first_chapter+1:0));
if (new_graph==NULL) panic(no_room); /* out of memory already */
strcpy(new_graph->util_types,"IZZIISIZZZZZZZ");
              /* declare the types of utility fields */
sprintf(new_graph->id,"%sbook(\"%s\",%lu,%lu,%lu,%lu,%ld,%ld,%ld)",
  bipartite?"bi_":"",title,n,x,first_chapter,last_chapter,
  in_weight,out_weight,seed);
if (bipartite) {
  mark_bipartite(new_graph,n-x);
  chap_base=new_graph->vertices+(new_graph->n_1-first_chapter);
}
@<Compute the weights and assign vertices to chosen nodes@>;

@ @<Compute the weights and assign vertices to chosen nodes@>=
for (p=node_block; p<node_block+characters; p++)
  p->key=in_weight*(p->in)+out_weight*(p->out)+0x40000000;
gb_linksort(node_block+characters-1);
k=n; /* we will look at this many nodes */
{@+register Vertex *v=new_graph->vertices; /* the next vertex to define */
  for (j=127; j>=0; j--)
    for (p=(node*)gb_sorted[j]; p; p=p->link) {
      if (x>0) x--; /* ignore this node */
      else p->vert=v++; /* choose this node */
      if (--k==0) goto done;
    }
}
done:;

@ Once the graph is there, we're ready to fill it in.

@<Read the data file more carefully and fill the graph as instructed@>=
if (gb_open(file_name)!=0)
  panic(impossible+1);
    /* this can't happen, because we were successful before */
@<Read the data about characters again, noting vertex names and the
  associated descriptions@>;
if (bipartite)
  @<Read the chapter information a second time and create the
    appropriate bipartite edges@>@;
else @<Read the chapter information a second time and create the
  appropriate edges for encounters@>;
if (gb_close()!=0)
  panic(impossible+2); /* again, can hardly happen the second time around */

@* Index. As usual, we close with an index that
shows where the identifiers of \\{gb\_books} are defined and used.