roget_components.w

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

|v->min==v|; 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: If there's no way out
of the subcave starting at~|v| unless we come back through |v| itself,
and if we can get back to |v| from all its descendants, then
room~|v| and its descendants will become a strong component. Once
such a strong component 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==v|,
so it will always define a new strong component at the moment it matures.
Then the depth-first search will terminate, since |v|~has no parent.
But Tarjan's 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 Tarjan's 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
      strong components of all unseen vertices reachable from~|vv|@>;
@<Print out one representative of each arc that runs
    between strong components@>;

@ @<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+g->n-1; v>=g->vertices; v--) {
  v->rank=0;
  v->untagged=v->arcs;
}
nn=0;
active_stack=settled_stack=NULL;

@ 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=NULL;
  @<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!=NULL);
}

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

@ 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==v) @<Remove |v| and all its successors on the active stack
         from the tree, and mark them as a strong component of the graph@>@;
    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|. Tarjan's 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.

Another fundamental property of Tarjan's algorithm is more subtle:
{\sl There is always a way to get from any active vertex to the
current vertex.} This follows from the fact that all mature active vertices~|u|
have |u->min->rank<u->rank|.  If some active vertex does not lead to the
current vertex~|v|,
let |u| be the counterexample with smallest rank. Then |u| isn't an
ancestor of~|v|, hence |u| must be mature; hence it leads to the
active vertex |u->min|, from which there {\sl is\/} a path to~|v|,
contradicting our assumption.

Therefore |v| and its active descendants are all reachable from each
other, and they must belong to the same strong component. Moreover, if
|v->min=v|, this component can't be made any larger. For there is no
arc from any of these vertices to an unseen vertex; all arcs from |v|
and its descendants have already been tagged. And there is no arc from
any of these vertices to an active vertex that is below |v| on the
stack; otherwise |v->min| would have smaller rank than~|v|. Hence all
arcs, if any, that lead from these vertices to some other vertex must
lead to settled vertices. And we know from previous steps of the
computation that the settled vertices all belong to other strong
components.

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 |v->rank|.
Hence their removal does not affect the validity of the |u->min| value
for any vertex~|u| that remains active.

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

@d infinity g->n /* infinite rank (or close enough) */

@<Remove |v| and all its successors on the active stack
         from the tree, and mark them as a strong component of the graph@>=
{@+register Vertex *t; /* runs through the vertices of the
                        new strong component */
  t=active_stack;
  active_stack=v->link;
  v->link=settled_stack;
  settled_stack=t;  /* we've moved the top of one stack to the other */
  printf("Strong component `%ld %s'", specs(v));
  if (t==v) putchar('\n'); /* single vertex */
  else {
    printf(" also includes:\n");
    while (t!=v) {
      printf(" %ld %s (from %ld %s; ..to %ld %s)\n",
              specs(t), specs(t->parent), specs(t->min));
      t->rank=infinity; /* now |t| is settled */
      t->parent=v; /* and |v| represents the new strong component */
      t=t->link;
    }
  }
  v->rank=infinity; /* |v| too is settled */
  v->parent=v; /* and represents its own strong component */
}

@ After all the strong components have been found, we can also compute the
relations between them, without mentioning any cross-connection more than
once. In fact, we built the |settled_stack| precisely so that this task
could be done easily without sorting or searching. If only the strong
components themselves were of interest, this part of the algorithm wouldn't
be necessary.

For this step we use the name |arc_from| for the field we previously
called |untagged|. The trick here relies on the fact that all vertices of the
same strong component appear together in |settled_stack|.

@d arc_from x.V /* utility field |x| will now point to a vertex */

@<Print out one representative of each arc that runs between...@>=
printf("\nLinks between components:\n");
for (v=settled_stack; v; v=v->link) {@+register Vertex *u=v->parent;
  register Arc *a;
  u->arc_from=u;
  for (a=v->arcs; a; a=a->next) {@+register Vertex *w=a->tip->parent;
    if (w->arc_from!=u) {
      w->arc_from=u;
      printf("%ld %s -> %ld %s (e.g., %ld %s -> %ld %s)\n",
              specs(u),specs(w),specs(v),specs(a->tip));
    }
  }
}

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