book_components.w

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

current vertex doesn't change.

Finally there will come a time when the current vertex~|v| has no
untagged arcs. At this point, the
algorithm might decide that |v| and all its descendants
form a bicomponent, together with |v->parent|.
 Indeed, this condition turns out to be true if and only if
|v->min==v->parent|; a proof appears below. If so, |v| and all its descendants
become settled, and they leave the tree. If not, the tree arc from
|v|'s parent~|u| to~|v| becomes mature, so the value of |v->min| is
used to update the value of |u->min|. In both cases, |v| becomes mature
and the new current vertex will be the parent of~|v|. Notice that only the
value of |u->min| needs to be updated, when the arc from |u| to~|v|
matures; all other values |w->min| stay the same, because a newly
mature arc has no mature predecessors.

The cave analogy helps to clarify the situation: Suppose we enter
room~|v| from room~|u|. If there's no way out of the subcave starting
at~|v| unless we come back through~|u|, and if we can get to~|u| from
all of |v|'s descendants without passing through~|v|, then room~|v|
and its descendants will become a bicomponent together with~|u|.  Once
such a bicomponent is identified, we close it off and don't explore
that subcave any further.

If |v| is the root of the tree, it always has |v->min==dummy|, so it
will always define a new bicomponent at the moment it matures.  Then
the depth-first search will terminate, since |v|~has no real parent.
But the Hopcroft-Tarjan algorithm will press on, trying to find a
vertex~|u| that is still unseen. If such a vertex exists, a
new depth-first search will begin with |u| as the root. This process
keeps on going until at last all vertices are happily settled.

The beauty of this algorithm is that it all works very efficiently
when we organize it as follows:

@<Perform the Hopcroft-Tarjan algorithm on |g|@>=
@<Make all vertices unseen and all arcs untagged@>;
for (vv=g->vertices; vv<g->vertices+g->n; vv++)
  if (vv->rank==0) /* |vv| is still unseen */
    @<Perform a depth-first search with |vv| as the root, finding the
      bicomponents of all unseen vertices reachable from~|vv|@>;

@ @<Glob...@>=
Vertex *vv; /* sweeps over all vertices, making sure none is left unseen */

@ It's easy to get the data structures started, according to the
conventions stipulated above.

@<Make all vertices unseen...@>=
for (v=g->vertices; v<g->vertices+g->n; v++) {
  v->rank=0;
  v->untagged=v->arcs;
}
nn=0;
active_stack=NULL;
dummy.rank=0;

@ The task of starting a depth-first search isn't too bad either. Throughout
this part of the algorithm, variable~|v| will point to the current vertex.

@<Perform a depth-first search with |vv| as the root...@>=
{
  v=vv;
  v->parent=&dummy;
  @<Make vertex |v| active@>;
  do @<Explore one step from the current vertex~|v|, possibly moving
        to another current vertex and calling~it~|v|@>@;
  while (v!=&dummy);
}

@ @<Make vertex |v| active@>=
v->rank=++nn;
v->link=active_stack;
active_stack=v;
v->min=v->parent;

@ Now things get interesting. But we're just doing what any well-organized
spelunker would do when calmly exploring a cave.
There are three main cases,
depending on whether the current vertex stays where it is, moves
to a new child, or backtracks to a parent.

@<Explore one step from the current vertex~|v|, possibly moving
        to another current vertex and calling~it~|v|@>=
{@+register Vertex *u; /* a vertex adjacent to |v| */
  register Arc *a=v->untagged; /* |v|'s first remaining untagged arc, if any */
  if (a) {
    u=a->tip;
    v->untagged = a->next; /* tag the arc from |v| to |u| */
    if (u->rank) { /* we've seen |u| already */
      if (u->rank < v->min->rank)
        v->min=u; /* non-tree arc, just update |v->min| */
    }@+else { /* |u| is presently unseen */
      u->parent = v; /* the arc from |v| to |u| is a new tree arc */
      v = u; /* |u| will now be the current vertex */
      @<Make vertex |v| active@>;
    }
  }@+else { /* all arcs from |v| are tagged, so |v| matures */
    u=v->parent; /* prepare to backtrack in the tree */
    if (v->min==u) @<Remove |v| and all its successors on the active stack
         from the tree, and report them as a bicomponent of the graph
         together with~|u|@>@;
    else  /* the arc from |u| to |v| has just matured,
             making |v->min| visible from |u| */@,
      if (v->min->rank < u->min->rank)
        u->min=v->min;
    v=u; /* the former parent of |v| is the new current vertex |v| */
  }
}

@ The elements of the active stack are always in order by rank, and
all children of a vertex~|v| in the tree have rank higher than~|v|.
The Hopcroft-Tarjan algorithm relies on a converse property:
{\sl All active nodes whose rank exceeds that of the current vertex~|v|
are descendants of~|v|.} (This property holds because the algorithm has
constructed the tree by assigning ranks in preorder, ``the order of
succession to the throne.'' First come |v|'s firstborn and descendants,
then the nextborn, and so on.) Therefore the descendants of the
current vertex always appear consecutively at the top of the stack.

Suppose |v| is a mature, active vertex with |v->min==v->parent|, and
let |u=v->parent|. We want to prove that |v| and its descendants,
together with~|u| and all edges between these vertices, form a
biconnected graph.  Call this subgraph~$H$. The parent links
define a subtree of~$H$, rooted at~|u|, and |v| is the only vertex
having |u| as a parent (because all other vertices are descendants
of~|v|). Let |x| be any vertex of~$H$ different from |u| and |v|.
Then there is a path from |x| to |x->min| that does not touch~|x->parent|,
and |x->min| is a proper ancestor of |x->parent|. This property
is sufficient to establish the biconnectedness of~$H$. (A proof appears
at the conclusion of this program.) Moreover, we cannot add any
more vertices to~$H$ without losing biconnectivity. If |w|~is another
vertex, either |w| has been output already as a non-articulation point
of a previous biconnected component, or we can prove that
there is no path from |w| to~|v| that avoids the vertex~|u|.

@ Therefore we are justified in settling |v| and its active descendants now.
Removing them from the tree of active vertices does not remove any
vertex from which there is a path to a vertex of rank less than |u->rank|.
Hence their removal does not affect the validity of the |w->min| value
for any vertex~|w| that remains active.

A slight technicality arises with respect to whether or not
the parent of~|v|, vertex~|u|, is part of the present bicomponent.
When |u| is the dummy vertex, we have already printed the final bicomponent
of a connected component of the original graph, unless |v| was
an isolated vertex. Otherwise |u| is an
articulation point that will occur in subsequent bicomponents,
unless the new bicomponent is the final bicomponent of a connected component.
(This aspect of the algorithm is probably its most subtle point;
consideration of an example or two should clarify everything.)

We print out enough information for a reader to verify the
biconnectedness of the claimed component easily.

@<Remove |v| and all its successors on the active stack...@>=
if (u==&dummy) { /* |active_stack| contains just |v| */
  if (artic_pt)
    printf(" and %s (this ends a connected component of the graph)\n",
              vertex_name(artic_pt,0));
  else printf("Isolated vertex %s\n",vertex_name(v,0));
  active_stack=artic_pt=NULL;
}@+else {@+register Vertex *t; /* runs through the vertices of the
                        new bicomponent */
  if (artic_pt)
    printf(" and articulation point %s\n",vertex_name(artic_pt,0));
  t=active_stack;
  active_stack=v->link;
  printf("Bicomponent %s", vertex_name(v,0));
  if (t==v) putchar('\n'); /* single vertex */
  else {
    printf(" also includes:\n");
    while (t!=v) {
      printf(" %s (from %s; ..to %s)\n",
        vertex_name(t,0), vertex_name(t->parent,1),vertex_name(t->min,2));
      t=t->link;
    }
  }
  artic_pt=u; /* the printout will be finished later */
}

@ Like all global variables, |artic_pt| is initially zero (|NULL|).

@<Glob...@>=
Vertex *artic_pt; /* articulation point to be printed if the current
  bicomponent isn't the last in its connected component */

@*Proofs.
The program is done, but we still should prove that it works.
First we want to clarify the informal definition by verifying that
the cycle relation between edges, as stated in the introduction, is indeed an
equivalence relation.

\def\dash{\mathrel-\joinrel\joinrel\mathrel-}
Suppose $u\dash v$ and $w\dash x$ are edges of a simple cycle~$C$, while
$w\dash x$ and $y\dash z$ are edges of a simple cycle~$D$. We want to show
that there is a simple cycle containing the edges $u\dash v$ and $y\dash z$.
There are vertices $a,b\in C$ such that $a\dash^\ast y\dash z\dash^\ast b$
is a subpath of~$D$ containing no other vertices of $C$ besides $a$ and~$b$.
Join this subpath to the subpath in $C$ that runs from $b$ to~$a$ through
the edge $u\dash v$.

Therefore the stated relation between edges is transitive, and it is
an equivalence relation.
A graph is biconnected if it contains a single vertex, or if each of
its vertices is adjacent to at least one other vertex and any two edges are
equivalent.

@ Next we prove the well-known fact that a graph is biconnected if and
only if it is connected and, for any three distinct vertices $x$,
$y$,~$z$, it contains a path from $x$ to~$y$ that does not touch~$z$.
Call the latter condition property~P.

Suppose $G$ is biconnected, and let $x,y$ be distinct vertices of~$G$.
Then there exist edges $u\dash x$ and $v\dash y$, which are either
identical (hence $x$ and~$y$ are adjacent) or part of a simple cycle
(hence there are two paths from $x$ to~$y$, having no other vertices in
common). Thus $G$ has property~P.

Suppose, conversely, that $G$ has property~P, and let $u\dash v,
w\dash x$ be distinct edges of~$G$. We want to show that these edges
belong to some simple cycle. The proof is by induction on
$k=\min\bigl(d(u,w),d(u,x),\allowbreak d(v,w),d(v,x)\bigr)$, where $d$~denotes
distance. If $k=0$, property~P gives the result directly. If $k>0$,
we can assume by symmetry that $k=d(u,w)$; so there's a vertex $y$
with $u\dash y$ and $d(y,w)=k-1$. And we have $u\dash v$ equivalent to
$u\dash y$ by property~P, $u\dash y$ equivalent to $w\dash x$ by induction,
hence $u\dash v$ is equivalent to $w\dash x$ by transitivity.

@ Finally, we prove that $G$ satisfies property~P if it has the
following properties: (1)~There are two distinguished vertices $u$
and~$v$.  (2)~Some of the edges of~$G$ form a subtree rooted at~$u$,
and $v$ is the only vertex whose parent in this tree is~$u$.
(3)~Every vertex~$x$ other than $u$ or $v$ has a path to its
grandparent that does not go through its parent.

If property P doesn't hold, there are distinct vertices $x,y,z$ such
that every path from $x$ to~$y$ goes through~$z$. In particular, $z$ must be
between $x$ and~$y$ in the unique path~$\pi$ that joins them in the subtree.
It follows that $z\ne u$ is the parent of some node $z'$ in that path; hence
$z'\ne u$ and $z'\ne v$. But we can
avoid $z$ by going from $z'$ to the grandparent of $z'$, which is
also part of path~$\pi$ unless $z$ is also the parent of another node
$z''$ in~$\pi$. In the latter case, however,
we can avoid $z$ by going from $z'$ to the grandparent of $z'$ and from there
to $z''$, since $z'$ and $z''$ have the same grandparent.

@* Index. We close with a list that shows where the identifiers of this
program are defined and used.