book_components.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!
@i gb_types.w

\def\title{BOOK\_\kern.05emCOMPONENTS}
\def\<#1>{$\langle${\rm#1}$\rangle$}

\prerequisite{GB\_\,BOOKS}
@* Bicomponents. This demonstration program computes the
biconnected components of GraphBase graphs derived from world literature,
using a variant of Hopcroft and Tarjan's algorithm [R. E. Tarjan, ``Depth-first
@^Hopcroft, John Edward@>
@^Tarjan, Robert Endre@>
search and linear graph algorithms,'' {\sl SIAM Journal on Computing\/
\bf1} (1972), 146--160]. Articulation points and ordinary (connected)
components are also obtained as byproducts of the computation.

Two edges belong to the same  biconnected component---or ``bicomponent''
for short---if and only if they are identical or both belong to a
simple cycle. This defines an equivalence relation on edges.
The bicomponents of a connected graph form a
free tree, if we say that two bicomponents are adjacent when they have
a common vertex (i.e., when there is a vertex belonging to at least one edge
in each of the bicomponents). Such a vertex is called an {\sl articulation
point\/}; there is a unique articulation point between any two adjacent
bicomponents. If we choose one bicomponent to be the ``root'' of the
free tree, the other bicomponents can be represented conveniently as
lists of vertices, with the articulation point that leads toward the root
listed last. This program displays the bicomponents in exactly that way.

@ We permit command-line options in typical \UNIX/ style so that a variety of
graphs can be studied: The user can say `\.{-t}\<title>',
`\.{-n}\<number>', `\.{-x}\<number>', `\.{-f}\<number>',
`\.{-l}\<number>', `\.{-i}\<number>', `\.{-o}\<number>', and/or
`\.{-s}\<number>' to change the default values of the parameters in
the graph generated by |book(t,n,x,f,l,i,o,s)|.

When the bicomponents are listed, each character in the book is identified by
a two-letter code, as found in the associated data file.
An explanation of these codes will appear first if the \.{-v} or \.{-V} option
is specified. The \.{-V} option prints a fuller explanation than~\.{-v}; it
also shows each character's weighted number of appearances.

The special command-line option \.{-g}$\langle\,$filename$\,\rangle$
overrides all others. It substitutes an external graph previously saved by
|save_graph| for the graphs produced by |book|. 

@^UNIX dependencies@>

@p
#include "gb_graph.h" /* the GraphBase data structures */
#include "gb_books.h" /* the |book| routine */
#include "gb_io.h" /* the |imap_chr| routine */
#include "gb_save.h" /* |restore_graph| */
@h@#
@<Global variables@>@;
@<Subroutines@>@;
main(argc,argv)
  int argc; /* the number of command-line arguments */
  char *argv[]; /* an array of strings containing those arguments */
{@+Graph *g; /* the graph we will work on */
  register Vertex *v; /* the current vertex of interest */
  char *t="anna"; /* the book to use */
  unsigned long n=0; /* the desired number of vertices (0 means infinity) */
  unsigned long x=0; /* the number of major characters to exclude */
  unsigned long f=0; /* the first chapter to include */
  unsigned long l=0; /* the last chapter to include (0 means infinity) */
  long i=1; /* the weight for appearances in selected chapters */
  long o=1; /* the weight for appearances in unselected chapters */
  long s=0; /* the random number seed */
  @<Scan the command-line options@>;
  if (filename) g=restore_graph(filename);
  else g=book(t,n,x,f,l,i,o,s);
  if (g==NULL) {
    fprintf(stderr,"Sorry, can't create the graph! (error code %ld)\n",
             panic_code);
    return -1;
  }
  printf("Biconnectivity analysis of %s\n\n",g->id);
  if (verbose) @<Print the cast of selected characters@>;
  @<Perform the Hopcroft-Tarjan algorithm on |g|@>;
  return 0; /* normal exit */
}

@ @<Scan the command-line options@>=
while (--argc) {
@^UNIX dependencies@>
  if (strncmp(argv[argc],"-t",2)==0) t=argv[argc]+2;
  else if (sscanf(argv[argc],"-n%lu",&n)==1) ;
  else if (sscanf(argv[argc],"-x%lu",&x)==1) ;
  else if (sscanf(argv[argc],"-f%lu",&f)==1) ;
  else if (sscanf(argv[argc],"-l%lu",&l)==1) ;
  else if (sscanf(argv[argc],"-i%ld",&i)==1) ;
  else if (sscanf(argv[argc],"-o%ld",&o)==1) ;
  else if (sscanf(argv[argc],"-s%ld",&s)==1) ;
  else if (strcmp(argv[argc],"-v")==0) verbose=1;
  else if (strcmp(argv[argc],"-V")==0) verbose=2;
  else if (strncmp(argv[argc],"-g",2)==0) filename=argv[argc]+2;
  else {
    fprintf(stderr,
         "Usage: %s [-ttitle][-nN][-xN][-fN][-lN][-iN][-oN][-sN][-v][-gfoo]\n",
         argv[0]);
    return -2;
  }
}
if (filename) verbose=0;

@ @<Subroutines@>=
char *filename=NULL; /* external graph to be restored */
char code_name[3][3];
char *vertex_name(v,i) /* return (as a string) the name of vertex |v| */
  Vertex *v;
  char i; /* |i| should be 0, 1, or 2 to avoid clash in |code_name| array */
{
  if (filename) return v->name; /* not a |book| graph */
  code_name[i][0]=imap_chr(v->short_code/36);
  code_name[i][1]=imap_chr(v->short_code%36);
  return code_name[i];
}

@ @<Print the cast of selected characters@>=
{
  for (v=g->vertices;v<g->vertices+g->n;v++) {
    if (verbose==1) printf("%s=%s\n",vertex_name(v,0),v->name);
    else printf("%s=%s, %s [weight %ld]\n",vertex_name(v,0),v->name,v->desc,@|
     i*v->in_count+o*v->out_count);
  }
  printf("\n");
}

@*The algorithm.
The Hopcroft-Tarjan algorithm is inherently recursive. We will
implement the recursion explicitly via linked lists, instead of using
\CEE/'s runtime stack, because some computer systems bog down in the
presence of deeply nested recursion.

Each vertex goes through three stages during the algorithm. First it is
``unseen''; then it is ``active''; finally it becomes ``settled,'' when it
has been assigned to a bicomponent.

The data structures that represent the current state of the algorithm
are implemented by using five of the utility fields in each vertex:
|rank|, |parent|, |untagged|, |link|, and |min|. We will consider each of
these in turn.

@ First is the integer |rank| field, which is zero when a vertex is unseen.
As soon as the vertex is first examined, it becomes active and its |rank|
becomes and remains nonzero. Indeed, the $k$th vertex to become active
will receive rank~$k$.

It's convenient to think of the Hopcroft-Tarjan algorithm as a simple adventure
game in which we want to explore all the rooms of a cave. Passageways between
the rooms allow two-way travel. When we come
into a room for the first time, we assign a new number to that room;
this is its rank. Later on we might happen to come into the same room
again, and we will notice that it has nonzero rank. Then we'll be able
to make a quick exit, saying ``we've already been here.'' (The extra
complexities of computer games, like dragons that might need to be
vanquished, do not arise.)

@d rank z.I /* the |rank| of a vertex is stored in utility field |z| */

@<Glob...@>=
long nn; /* the number of vertices that have been seen */

@ The active vertices will always form an oriented tree, whose arcs are
a subset of the arcs in the original graph. A tree arc from |u| to~|v|
will be represented by |v->parent==u|. Every active vertex has a
parent, which is usually another active vertex; the only exception is
the root of the tree, whose |parent| is a dummy vertex called |dummy|.
The dummy vertex has rank zero.

In the cave analogy, the ``parent'' of room |v| is the room we were in
immediately before entering |v| the first time. By following parent
pointers, we will be able to leave the cave whenever we want.

@d parent y.V /* the |parent| of a vertex is stored in utility field |y| */

@<Glob...@>=
Vertex dummy; /* imaginary parent of the root vertex */

@ All edges in the original undirected graph are explored systematically during
a depth-first search. Whenever we look at an edge, we tag it so that
we won't need to explore it again. In a cave, for example, we might
mark each passageway between rooms once we've tried to go through~it.

In a GraphBase graph, undirected edges are represented as a pair of directed
arcs. Each of these arcs will be examined and eventually tagged.

The algorithm doesn't actually place a tag on its |Arc| records; instead,
each vertex |v| has a pointer |v->untagged| that leads to all
hitherto-unexplored arcs from~|v|. The arcs of the list that appear
between |v->arcs| and |v->untagged| are the ones already examined.

@d untagged x.A
 /* the |untagged| field points to an |Arc| record, or |NULL| */ 

@ The algorithm maintains a special stack, the |active_stack|, which contains
all the currently active vertices. Each vertex has a |link| field that points
to the vertex that is next lower on its stack, or to |NULL| if the vertex is
at the bottom. The vertices on |active_stack| always appear in increasing
order of rank from bottom to top.

@d link w.V /* the |link| field of a vertex occupies utility field |w| */

@<Glob...@>=
Vertex * active_stack; /* the top of the stack of active vertices */

@ Finally there's a |min| field, which is the tricky part that makes
everything work. If vertex~|v| is unseen or settled, its |min| field is
irrelevant. Otherwise |v->min| points to the active vertex~|u|
of smallest rank having the following property:
There is a directed path from |v| to |u| consisting of
zero or more mature tree arcs followed by a single non-tree arc.

What is a tree arc, you ask. And what is a mature arc? Good questions. At the
moment when arcs of the graph are tagged, we classify them either as tree
arcs (if they correspond to a new |parent| link in the tree of active
nodes) or non-tree arcs (otherwise). The tree arcs therefore correspond to
passageways that have led us to new territory. A tree arc becomes mature
when it is no longer on the path from the root to the current vertex being
explored. We also say that a vertex becomes mature when it is
no longer on that path. All arcs from a mature vertex have been tagged.

We said before that every vertex is initially unseen, then active, and
finally settled. With our new definitions, we see further that every arc starts
out untagged, then it becomes either a non-tree arc or a tree arc. In the
latter case, the arc begins as an immature tree arc and eventually matures.

The dummy vertex is considered to be active, and we assume that
there is a non-tree arc from the root vertex back to |dummy|. Thus
there is a non-tree arc from |v| to |v->parent| for all~|v|, and |v->min|
will always point to a vertex whose rank is less than or equal to
|v->parent->rank|. It will turn out that |v->min| is always an ancestor
of~|v|.

Just believe these definitions, for now. All will become clear soon.

@d min v.V /* the |min| field of a vertex occupies utility field |v| */

@ Depth-first search explores a graph by systematically visiting all
vertices and seeing what they can lead to. In the Hopcroft-Tarjan algorithm, as
we have said, the active vertices form an oriented tree. One of these
vertices is called the current vertex.

If the current vertex still has an arc that hasn't been tagged, we
tag one such arc and there are two cases: Either the arc leads to
an unseen vertex, or it doesn't. If it does, the arc becomes a tree
arc; the previously unseen vertex becomes active, and it becomes the
new current vertex.  On the other hand if the arc leads to a vertex
that has already been seen, the arc becomes a non-tree arc and the