1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625

% 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{FOOTBALL}
\prerequisite{GB\_\,GAMES}
@* Introduction. This demonstration program uses graphs
constructed by the {\sc GB\_\,GAMES} module to produce
an interactive program called \.{football}, which finds preposterously
long chains of scores to ``prove'' that one given team might outrank another
by a huge margin.
\def\<#1>{$\langle${\rm#1}$\rangle$}
The program prompts you for a starting team. If you simply type \<return>,
it exits; otherwise you should enter a team name (e.g., `\.{Stanford}')
before typing \<return>.
Then the program prompts you for another team. If you simply type
\<return> at this point, it will go back and ask for a new starting team;
otherwise you should specify another name (e.g., `\.{Harvard}').
Then the program finds and displays a chain from the starting team
to the other one. For example, you might see the following:
$$\vbox{\halign{\tt#\hfil\cr
Oct 06: Stanford Cardinal 36, Notre Dame Fighting Irish 31 (+5)\cr
Oct 20: Notre Dame Fighting Irish 29, Miami Hurricanes 20 (+14)\cr
Jan 01: Miami Hurricanes 46, Texas Longhorns 3 (+57)\cr
Nov 03: Texas Longhorns 41, Texas Tech Red Raiders 22 (+76)\cr
Nov 17: Texas Tech Red Raiders 62, Southern Methodist Mustangs 7 (+131)\cr
Sep 08: Southern Methodist Mustangs 44, Vanderbilt Commodores 7 (+168)\cr
\omit\qquad\vdots\cr
Nov 10: Cornell Big Red 41, Columbia Lions 0 (+2188)\cr
Sep 15: Columbia Lions 6, Harvard Crimson 9 (+2185)\cr}}$$
The chain isn't necessarily optimal; it's just this particular
program's best guess. Another chain, which establishes a victory margin
of $+2279$ points, can in fact be produced by modifying this
program to search back from Harvard instead of forward from Stanford.
Algorithms that find even better chains should be fun to invent.
Actually this program has two variants. If you invoke it by saying simply
`\.{football}', you get chains found by a simple ``greedy algorithm.''
But if you invoke it by saying `\.{football} \<number>', assuming \UNIX/
commandline conventions, the program works harder. Higher values of
\<number> do more calculation and tend to find better chains. For
example, the simple greedy algorithm favors Stanford over Harvard by
only 781; \.{football}~\.{10} raises this to 1895; the
example above corresponds to \.{football}~\.{4000}.
@ Here is the general program layout, as seen by the \CEE/ compiler:
@^UNIX dependencies@>
@p
#include "gb_graph.h" /* the standard GraphBase data structures */
#include "gb_games.h" /* the routine that sets up the graph of scores */
#include "gb_flip.h" /* random number generator */
@h@#
@<Type declarations@>@;
@<Global variables@>@;
@<Subroutines@>@;
main(argc,argv)
int argc; /* the number of commandline arguments */
char *argv[]; /* an array of strings containing those arguments */
{
@<Scan the commandline options@>;
@<Set up the graph@>;
while(1) {
@<Prompt for starting team and goal team; break if none given@>;
@<Find a chain from start to goal, and print it@>;
}
return 0; /* normal exit */
}
@ Let's deal with \UNIX/dependent stuff first. The rest of this program
should work without change on any operating system.
@^UNIX dependencies@>
@<Scan the commandline options@>=
if (argc==3 && strcmp(argv[2],"v")==0) verbose=argc=2; /* secret option */
if (argc==1) width=0;
else if (argc==2 && sscanf(argv[1],"%ld",&width)==1) {
if (width<0) width=width; /* a \UNIX/ user might have used a hyphen */
}@+else {
fprintf(stderr,"Usage: %s [searchwidth]\n",argv[0]);
return 2;
}
@ @<Glob...@>=
long width; /* number of cases examined per stratum */
Graph *g; /* the graph containing score information */
Vertex *u,*v; /* vertices of current interest */
Arc *a; /* arc of current interest */
Vertex *start,*goal; /* teams specified by the user */
long mm; /* counter used only in verbose mode */
@ An arc from u to v in the graph generated by games has a len field
equal to the number of points scored by u against v.
For our purposes we want also a del field, which gives the difference
between the number of points scored by u and the number of points
scored by~v in that game.
@d del a.I /* del info appears in utility field a of an Arc record */
@<Set up the graph@>=
g=games(0L,0L,0L,0L,0L,0L,0L,0L);
/* this default graph has the data for the entire 1990 season */
if (g==NULL) {
fprintf(stderr,"Sorry, can't create the graph! (error code %ld)\n",
panic_code);
return 1;
}
for (v=g>vertices;v<g>vertices+g>n;v++)
for (a=v>arcs;a;a=a>next)
if (a>tip>v) { /* arc a+1 is the mate of arc a iff a>tip>v */
a>del=a>len(a+1)>len;
(a+1)>del=a>del;
}
@* Terminal interaction. While we're getting trivialities out of the way,
we might as well take care of the simple dialog that transpires
between this program and the user.
@<Prompt for...@>=
putchar('\n'); /* make a blank line for visual punctuation */
restart: /* if we avoid this label, the break command will be broken */
if ((start=prompt_for_team("Starting"))==NULL) break;
if ((goal=prompt_for_team(" Other"))==NULL) goto restart;
if (start==goal) {
printf(" (Um, please give me the names of two DISTINCT teams.)\n");
goto restart;
}
@ The user must spell team names exactly as they appear in the file
\.{games.dat}. Thus, for example, `\.{Berkeley}' and `\.{Cal}' don't
work; it has to be `\.{California}'. Similarly, a person must type
`\.{Pennsylvania}' instead of `\.{Penn}', `\.{NevadaLas} \.{Vegas}'
instead of `\.{UNLV}'. A backslash is necessary in `\.{Texas} \.{A\\\&M}'.
@<Sub...@>=
Vertex *prompt_for_team(s)
char *s; /* string used in prompt message */
{@+register char *q; /* current position in buffer */
register Vertex *v; /* current vertex being examined in sequential search */
char buffer[30]; /* a line of input */
while (1) {
printf("%s team: ",s);
fflush(stdout); /* make sure the user sees the prompt */
fgets(buffer,30,stdin);
if (buffer[0]=='\n') return NULL; /* the user just hit \<return> */
buffer[29]='\n';
for (q=buffer;*q!='\n';q++) ; /* scan to end of input */
*q='\0';
for (v=g>vertices;v<g>vertices+g>n;v++)
if (strcmp(buffer,v>name)==0) return v; /* aha, we found it */
printf(" (Sorry, I don't know any team by that name.)\n");
printf(" (One team I do know is %s...)\n",
(g>vertices+gb_unif_rand(g>n))>name);
}
}
@*Greed. This program's primary task is to find the longest possible
simple path from start to goal, using del as the length of each
arc in the path. This is an NPcomplete problem, and the number of
possibilities is pretty huge, so the present program is content to
use heuristics that are reasonably easy to compute. (Researchers are hereby
challenged to come up with better heuristics. Does simulated annealing
give good results? How about genetic algorithms?)
Perhaps the first approach that comes to mind is a simple ``greedy'' approach
in which each step takes the largest possible del that doesn't prevent
us from eventually getting to goal. So that's the method we will
implement first.
@ @<Find a chain from start to goal, and print it@>=
@<Initialize the allocation of auxiliary memory@>;
if (width==0) @<Use a simpleminded
greedy algorithm to find a chain from start to goal@>@;
else @<Use a stratified heuristic to find a chain from start to goal@>;
@<Print the solution corresponding to cur_node@>;
@<Recycle the auxiliary memory used@>;
@ We might as well use data structures that are more general than we need,
in anticipation of a more complex heuristic that will be implemented later.
The set of all possible solutions can be viewed as a backtrack tree
in which the branches from each node are the games that can possibly
follow that node. We will examine a small part of that gigantic tree.
@<Type declarations@>=
typedef struct node_struct {
Arc *game; /* game from the current team to the next team */
long tot_len; /* accumulated length from start to here */
struct node_struct *prev; /* node that gave us the current team */
struct node_struct *next;
/* list pointer to node in same stratum (see below) */
} node;
@ @<Glob...@>=
Area node_storage; /* working storage for heuristic calculations */
node *next_node; /* where the next node is slated to go */
node *bad_node; /* end of current allocation block */
node *cur_node; /* current node of particular interest */
@ @<Initialize the allocation of auxiliary memory@>=
next_node=bad_node=NULL;
@ @<Subroutines@>=
node *new_node(x,d)
node *x; /* an old node that the new node will call prev */
long d; /* incremental change to tot_len */
{
if (next_node==bad_node) {
next_node=gb_typed_alloc(1000,node,node_storage);
if (next_node==NULL) return NULL; /* we're out of space */
bad_node=next_node+1000;
}
next_node>prev=x;
next_node>tot_len=(x?x>tot_len:0)+d;
return next_node++;
}
@ @<Recycle the auxiliary memory used@>=
gb_free(node_storage);
@ When we're done, cur_node>game>tip will be the goal vertex, and
we can get back to the start vertex by following prev links
from cur_node. It looks better to print the answers from start to
goal, so maybe we should have changed our algorithm to go the
other way.
But let's not worry over trifles. It's easy to change
the order of a linked list. The secret is simply to think of the list
as a stack, from which we pop all the elements off to another stack;
the new stack has the elements in reverse order.
@<Print the solution corresponding to cur_node@>=
next_node=NULL; /* now we'll use next_node as top of temporary stack */
do@+{@+register node*t;
t=cur_node;
cur_node=t>prev; /* pop */
t>prev=next_node;
next_node=t; /* push */
}@+while (cur_node);
for (v=start;v!=goal;v=u,next_node=next_node>prev) {
a=next_node>game;
u=a>tip;
@<Print the score of game a between v and u@>;
printf(" (%+ld)\n",next_node>tot_len);
}
@ @<Print the score of game a between v and u@>=
{@+register long d=a>date; /* date of the game, 0 means Aug 26 */
if (d<=5) printf(" Aug %02ld",d+26);
else if (d<=35) printf(" Sep %02ld",d5);
else if (d<=66) printf(" Oct %02ld",d35);
else if (d<=96) printf(" Nov %02ld",d66);
else if (d<=127) printf(" Dec %02ld",d96);
else printf(" Jan 01"); /* d=128 */
printf(": %s %s %ld, %s %s %ld",v>name,v>nickname,a>len,
u>name,u>nickname,a>lena>del);
}
@ We can't just move from v to any adjacent vertex; we can go only
to a vertex from which goal can be reached without touching v
or any other vertex already used on the path from start.
Furthermore, if the locally best move from v is directly to goal,
we don't want to make that move unless it's our last chance; we can
probably do better by making the chain longer. Otherwise, for example,
a chain between a team and its worst opponent would consist of
only a single game.
To keep track of untouchable vertices, we use a utility field
called blocked in each vertex record. Another utility field,
valid, will be set to a validation code in each vertex that
still leads to the goal.
@d blocked u.I
@d valid v.V
@<Use a simpleminded greedy algorithm to find a chain...@>=
{
for (v=g>vertices;v<g>vertices+g>n;v++) v>blocked=0,v>valid=NULL;
cur_node=NULL;
for (v=start;v!=goal;v=cur_node>game>tip) {@+register long d=10000;
register Arc *best_arc; /* arc that achieves del=d */
register Arc *last_arc; /* arc that goes directly to goal */
v>blocked=1;
cur_node=new_node(cur_node,0L);
if (cur_node==NULL) {
fprintf(stderr,"Oops, there isn't enough memory!\n");@+return 2;
}
@<Set u>valid=v for all u to which v might now move@>;
for (a=v>arcs;a;a=a>next)
if (a>del>d && a>tip>valid==v)
if (a>tip==goal) last_arc=a;
else best_arc=a,d=a>del;
cur_node>game=(d==10000?last_arc:best_arc);
/* use last_arc as a last resort */
cur_node>tot_len+=cur_node>game>del;
}
}
@ A standard marking algorithm supplies the final missing link in
our algorithm.
@d link w.V
@<Set u>valid=v for all u to which v might now move@>=
u=goal; /* u will be the top of a stack of nodes to be explored */
u>link=NULL;
u>valid=v;
do@+{
for (a=u>arcs,u=u>link;a;a=a>next)
if (a>tip>blocked==0 && a>tip>valid!=v) {
a>tip>valid=v; /* mark a>tip reachable from goal */
a>tip>link=u;
u=a>tip; /* push it on the stack, so that its successors
will be marked too */
}
}@+while (u);
@*Stratified greed. One approach to better chains is the following
algorithm, motivated by similar ideas of Pang Chen [Ph.D. thesis,
Stanford University, 1989]: @^Chen, PangChieh@> Suppose the nodes of
a (possibly huge) backtrack tree are classified into a (fairly small)
number of strata, by a function $h$ with the property that $h({\rm
child})<h({\rm parent})$ and $h({\rm goal})=0$. Suppose further that
we want to find a node $x$ that maximizes a given function~$f(x)$,
where it is reasonable to believe that $f$(child) will be relatively
large among nodes in a child's stratum only if $f$(parent) is
relatively large in the parent's stratum. Then it makes sense to
restrict backtracking to, say, the top $w$ nodes of each stratum,
ranked by their $f$ values.
The greedy algorithm already described is a special case of this general
approach, with $w=1$ and with $h(x)=($length of chain leading to~$x)$.
The refined algorithm we are about to describe uses a general value of $w$
and a somewhat more relevant stratification function: Given a node~$x$
of the backtrack tree for longest paths, corresponding to a path from
start to a certain vertex~$u=u(x)$, we will let $h(x)$ be the number of
vertices that lie between u and goal (in the sense that the simple
path from start to~u can be extended until it passes through such
a vertex and then all the way to~goal).
Here is the top level of the stratified greedy algorithm. We maintain
a linked list of nodes for each stratum, that is, for each possible value
of~$h$. The number of nodes required is bounded by $w$ times the
number of strata.
@<Use a strat...@>=
{
@<Make list[0] through list[n1] empty@>;
cur_node=NULL; /* NULL represents the root of the backtrack tree */
m=g>n1; /* the highest stratum not yet fully explored */
do@+{
@<Place each child~x of cur_node into list[h(x)], retaining
at most width nodes of maximum tot_len on each list@>;
while (list[m]==NULL)
@<Decrease m and get ready to explore another list@>;
cur_node=list[m];
list[m]=cur_node>next; /* remove a node from highest remaining stratum */
if (verbose) @<Print ``verbose'' info about cur_node@>;
}@+while (m>0); /* exactly one node should be in list[0] (see below) */
}
@ The calculation of $h(x)$ is somewhat delicate, and we will defer it
for a moment. But the list manipulation is easy, so we can finish it
quickly while it's fresh in our minds.
@d MAX_N 120 /* the number of teams in \.{games.dat} */
@<Glob...@>=
node *list[MAX_N]; /* the best nodes known in given strata */
long size[MAX_N]; /* the number of elements in a given list */
long m,h; /* current lists of interest */
node *x; /* a child of cur_node */
@ @<Make list[0]...@>=
for (m=0;m<g>n;m++) list[m]=NULL,size[m]=0;
@ The lists are maintained in order by tot_len, with the largest
tot_len value at the end so that we can easily delete the smallest.
When h=0, we retain only one node instead of~width different nodes,
because we are interested in only one solution.
@<Place node~x into list[h], retaining
at most width nodes of maximum tot_len@>=
if ((h>0 && size[h]==width)  (h==0 && size[0]>0)) {
if (x>tot_len<=list[h]>tot_len) goto done; /* drop node x */
list[h]=list[h]>next; /* drop one node from list[h] */
}@+else size[h]++;
{@+register node *p,*q; /* node in list and its predecessor */
for (p=list[h],q=NULL; p; q=p,p=p>next)@+
if (x>tot_len<=p>tot_len) break;
x>next=p;
if (q) q>next=x;@+ else list[h]=x;
}
done:;
@ We reverse the list so that large entries will tend to go in first.
@<Decrease m and get ready to explore another list@>=
{@+register node *r=NULL, *s=list[m], *t;
while (s) t=s>next, s>next=r, r=s, s=t;
list[m]=r;
mm=0; /* mm is an index for ``verbose'' printing */
}
@ @<Print ``verbose'' info...@>=
{
cur_node>next=(node*)((++mm<<8)+m); /* pack an ID for this node */
printf("[%lu,%lu]=[%lu,%lu]&%s (%+ld)\n",m,mm,@
cur_node>prev?((unsigned long)cur_node>prev>next)&0xff:0L,@
cur_node>prev?((unsigned long)cur_node>prev>next)>>8:0L,@
cur_node>game>tip>name, cur_node>tot_len);
}
@ Incidentally, it is plausible to conjecture that the stratified algorithm
always beats the simple greedy algorithm, but that conjecture is false.
For example, the greedy algorithm is able to rank Harvard over Stanford
by 1529, while the stratified algorithm achieves only 1527 when
width=1. On the other hand, the greedy algorithm often fails
miserably; when comparing two Ivy League teams, it doesn't find a
way to break out of the Ivy and Patriot Leagues.
@*Bicomponents revisited.
How difficult is it to compute the function $h$? Given a connected graph~$G$
with two distinguished vertices $u$ and~$v$, we want to count the number
of vertices that might appear on a simple path from $u$ to~$v$.
(This is {\sl not\/} the same as the number of vertices reachable from both
$u$ and~$v$. For example, consider a ``claw'' graph with four vertices
$\{u,v,w,x\}$ and with edges only from $x$ to the other three vertices;
in this graph $w$ is reachable from $u$ and~$v$, but it is not on any simple
path between them.)
The best way to solve this problem is probably to compute the bicomponents
of~$G$, or least to compute some of them. Another demo program,
{\sc BOOK\_\kern.05emCOMPONENTS}, explains the relevant theory in some
detail, and we will assume familiarity with that algorithm in the present
discussion.
Let us imagine extending $G$ to a slightly larger graph $G^+$ by
adding a dummy vertex~$o$ that is adjacent only to $v$. Suppose we determine
the bicomponents of $G^+$ by depthfirst search starting at~$o$.
These bicomponents form a tree rooted at the bicomponent that contains
just $o$ and~$v$. The number of vertices on paths between $u$ and~$v$,
not counting $v$ itself, is then the number of vertices in the bicomponent
containing~$u$ and in any other bicomponents between that one and the root.
Strictly speaking, each articulation point belongs
to two or more bicomponents. But we will assign each articulation point
to its bicomponent that is nearest the root of the tree; then the vertices
of each bicomponent are precisely the vertices output in bursts by the
depthfirst procedure. The bicomponents we want to enumerate are $B_1$, $B_2$,
\dots,~$B_k$, where $B_1$ is the bicomponent containing~$u$ and
$B_{j+1}$ is the bicomponent containing the articulation point associated
with~$B_j$; we stop at~$B_k$ when its associated articulation point is~$v$.
(Often $k=1$.)
The ``children'' of a given graph~$G$ are obtained by removing vertex~$u$
and by considering paths from $u'$ to~$v$, where $u'$ is a vertex
formerly adjacent to~$u$; thus $u'$ is either in~$B_1$ or it is $B_1$'s
associated articulation point. Removing $u$ will, in general, split
$B_1$ into a tree of smaller bicomponents, but $B_2,\ldots,B_k$ will be
unaffected. The implementation below does not take full advantage of this
observation, because the amount of memory required to avoid recomputation
would probably be prohibitive.
@ The following program is copied almost verbatim from
{\sc BOOK\_\kern.05emCOMPONENTS}.
Instead of repeating the commentary that appears there, we will mention
only the significant differences. One difference is that we start
the depthfirst search at a definite place, the goal.
@<Place each child~x of cur_node into list[h(x)], retaining
at most width nodes of maximum tot_len on each list@>=
@<Make all vertices unseen and all arcs untagged, except for vertices
that have already been used in steps leading up to cur_node@>;
@<Perform a depthfirst search with goal as the root, finding
bicomponents and determining the number of vertices accessible
between any given vertex and goal@>;
for (a=(cur_node? cur_node>game>tip: start)>arcs; a; a=a>next)
if ((u=a>tip)>untagged==NULL) { /* goal is reachable from u */
x=new_node(cur_node,a>del);
if (x==NULL) {
fprintf(stderr,"Oops, there isn't enough memory!\n");@+return 3;
}
x>game=a;
@<Set h to the number of vertices on paths between u and goal@>;
@<Place node...@>;
}
@ Setting the rank field of a vertex to infinity before beginning
a depthfirst search is tantamount to removing that vertex from
the graph, because it tells the algorithm not to look further at
such a vertex.
@d rank z.I /* when was this vertex first seen? */
@d parent u.V /* who told me about this vertex? */
@d untagged x.A /* what is its first untagged arc? */
@d min v.V /* how low in the tree can we jump from its mature descendants? */
@<Make all vertices unseen and all arcs untagged, except for vertices
that have already been used in steps leading up to cur_node@>=
for (v=g>vertices; v<g>vertices+g>n; v++) {
v>rank=0;
v>untagged=v>arcs;
}
for (x=cur_node;x;x=x>prev)
x>game>tip>rank=g>n; /* ``infinite'' rank (or close enough) */
start>rank=g>n;
nn=0;
active_stack=settled_stack=NULL;
@ @<Glob...@>=
Vertex * active_stack; /* the top of the stack of active vertices */
Vertex *settled_stack; /* the top of the stack of bicomponents found */
long nn; /* the number of vertices that have been seen */
Vertex dummy; /* imaginary parent of goal; its rank is zero */
@ The settled_stack will contain a list of all bicomponents in
the opposite order from which they are discovered. This is the order
we'll need later for computing the h function in each bicomponent.
@<Perform a depthfirst search...@>=
{
v=goal;
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);
@<Use settled_stack to put the mutual reachability count for
each vertex u in u>parent>rank@>;
}
@ @<Make vertex v active@>=
v>rank=++nn;
v>link=active_stack;
active_stack=v;
v>min=v>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; /* nontree 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 */
}
}
@ When a bicomponent is found, we reset the parent field of each vertex
so that, afterwards, two vertices will belong to the same bicomponent
if and only if they have the same parent. (This trick was not used in
{\sc BOOK\_\kern.05emCOMPONENTS}, but it does appear in the similar algorithm
of {\sc ROGET\_\,COMPONENTS}.) The new parent, v, will represent that
bicomponent in subsequent computation; we put it onto settled_stack.
We also reset v>rank to be the bicomponent's size, plus a constant
large enough to keep the algorithm from getting confused. (Vertex~u
might still have untagged arcs leading into this bicomponent; we need to
keep the ranks at least as big as the rank of u>min.) Notice that
v>min is u, the articulation point associated with this bicomponent.
Later the rank field will
contain the sum of all counts between here and the root.
We don't have to do anything when v==goal; the trivial root bicomponent
always comes out last.
@<Remove v and all its successors on the active stack...@>=
{@+if (v!=goal) {@+register Vertex *t; /* runs through the vertices of the
new bicomponent */
long c=0; /* the number of vertices removed */
t=active_stack;
while (t!=v) {
c++;
t>parent=v;
t=t>link;
}
active_stack=v>link;
v>parent=v;
v>rank=c+g>n; /* the true component size is c+1 */
v>link=settled_stack;
settled_stack=v;
}
}
@ So here's how we sum the ranks. When we get to this step, the \\{settled}
stack contains all bicomponent representatives except goal itself.
@<Use settled_stack to put the mutual reachability count for
each vertex u in u>parent>rank@>=
while (settled_stack) {
v=settled_stack;
settled_stack=v>link;
v>rank+=v>min>parent>rank+1g>n;
} /* note that goal>parent>rank=0 */
@ And here's the last piece of the puzzle.
@<Set h to the number of vertices on paths between u and goal@>=
h=u>parent>rank;
@* Index. Finally, here's a list that shows where the identifiers of this
program are defined and used.
