miles_span.w

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

@<Find and remove...@>=    
mm=m&(m-1);
o,q=h->qsib;
k=m-mm;
if (mm) { /* there's more than one tree */
  p=q;@+qq=h;
  o,key=q->len;
  do@+{@+long t=mm&(mm-1);
    pp=p;@+o,p=p->qsib;
    if (o,p->len<=key) {
      q=p;@+qq=pp;@+k=mm-t;@+key=p->len;
    }
    mm=t;
  }@+while (mm);
  if (k+k<=m) oo,qq->qsib=q->qsib; /* remove the tree rooted at |q| */
}

@ To complete our implementation, here is an algorithm that traverses
a binomial queue, ``visiting'' each node exactly once, destroying the
queue as it goes. The total number of mems required is about |1.75m|.

@<Prio...@>=
qtraverse(h,visit)
  Arc *h; /* head of binomial queue to be unraveled */
  void @[@] (*visit)(); /* procedure to be invoked on each node */
{@+register long m; /* the number of nodes remaining */
  register Arc *p,*q,*r; /* current position and neighboring positions */
  o,m=h->qcount;
  p=h;
  while (m) {
    o,p=p->qsib;
    (*visit)(p);
    if (m&1) m--;
    else {
      o,q=p->qchild;
      if (m&2) (*visit)(q);
      else {
        o,r=q->qsib;
        if (m&(m-1)) oo,q->qsib=p->qsib;
        (*visit)(r);
        p=r;
      }
      m-=2;
    }
  }
}

@* Cheriton, Tarjan, and Karp's algorithm.
\def\lsqrtn{\hbox{$\lfloor\sqrt n\,\rfloor$}}%
\def\usqrtn{\hbox{$\lfloor\sqrt{n+1}+{1\over2}\rfloor$}}%
The final algorithm we shall consider takes yet another approach to
spanning tree minimization. It operates in two distinct stages: Stage~1
creates small fragments of the minimum tree, working locally with the
edges that lead out of each fragment instead of dealing with the
full set of edges at once as in Kruskal's method. As soon as the
number of component fragments has been reduced from $n$ to \lsqrtn,
stage~2 begins. Stage~2 runs through the remaining edges and builds a
$\lsqrtn\times\lsqrtn$ matrix, which represents the problem of
finding a minimum spanning tree on the remaining \lsqrtn\ components.
A simple $O(\sqrt n\,)^2=O(n)$ algorithm then completes the job.

The philosophy underlying stage~1 is that an edge leading out of a
vertex in a small component is likely to lead to a vertex in another
component, rather than in the same one. Thus each delete-min operation
tends to be productive. Karp and Tarjan proved [{\sl Journal of Algorithms\/
@^Karp, Richard Manning@>
@^Tarjan, Robert Endre@>
\bf1} (1980), 374--393] that the average running time on a random graph with
$n$ vertices and $m$ edges will be $O(m)$.

The philosophy underlying stage~2 is that the problem
on an initially sparse graph eventually reduces to a problem on a smaller
but dense graph that is best solved by a different method.

@<Sub...@>=
unsigned long cher_tar_kar(g)
  Graph *g;
{@+@<Local variables for |cher_tar_kar|@>@;@#
  mems=0;
  @<Do stage 1 of |cher_tar_kar|@>;
  if (verbose) printf("    [Stage 1 has used %ld mems]\n",mems);
  @<Do stage 2 of |cher_tar_kar|@>;
  return tot_len;
}

@ We say that a fragment is {\sl large} if it contains \usqrtn\ or more
vertices. As soon as a fragment becomes large, stage~1 stops trying
to extend it. There cannot be more than \lsqrtn\ large fragments,
because $(\lsqrtn+1)\usqrtn>n$. The other fragments are called {\sl small}.

Stage~1 keeps a list of all the small fragments. Initially this list
contains $n$ fragments consisting of one vertex each. The algorithm
repeatedly looks at the first fragment on its list, and finds the
smallest edge leading to another fragment. These two fragments are
removed from the list and combined. The resulting fragment is put at
the end of the list if it is still small, or put onto another list if
it is large.

@<Local variables for |ch...@>=
register Vertex *s,*t; /* beginning and end of the small list */
Vertex *large_list; /* beginning of the list of large fragments */
long frags; /* current number of fragments, large and small */
unsigned long tot_len=0; /* total length of all edges in fragments */
register Vertex *u,*v; /* registers for list manipulation */
register Arc *a; /* and another */
register long j,k; /* index registers for stage 2 */

@ We need to make |lo_sqrt| global so that the |note_edge| procedure
below can access it.

@<Glob...@>=
long lo_sqrt,hi_sqrt; /* \lsqrtn\ and \usqrtn\ */

@ There is a nonobvious way to compute \usqrtn\ and \lsqrtn. Since
$\sqrt n$ is small and arithmetic is mem-free, the author
couldn't resist writing the |for| loop shown here.
Of course, different ground rules for counting mems would be
appropriate if this sort of computing were a critical factor in
the running time.
@^discussion of \\{mems}@>

@<Do stage 1 of |cher_tar_kar|@>=
o,frags=g->n;
for (hi_sqrt=1;hi_sqrt*(hi_sqrt+1)<=frags;hi_sqrt++) ;
if (hi_sqrt*hi_sqrt<=frags) lo_sqrt=hi_sqrt;
else lo_sqrt=hi_sqrt-1;
large_list=NULL;
@<Create the small list@>;
while (frags>lo_sqrt) {
  @<Combine the first fragment on the small list with its nearest neighbor@>;
  frags--;
}

@ To represent fragments, we will use several utility fields already
defined above. The |lsib| and |rsib| pointers are used between fragments
in the small list, which is doubly linked; |s|~points to the first small
fragment, |s->rsib| to the next, \dots, |t->lsib| to the second-from-last,
and |t| to the last. The pointer fields |s->lsib| and |t->rsib| are
undefined. The |large_list| is singly linked via |rsib| pointers,
terminating with |NULL|.

The |csize| field of each fragment tells how many vertices it contains.

The |comp| field of each vertex is |NULL| if this vertex represents a
fragment (i.e., if this vertex is in the small list or |large_list|);
otherwise it points to another vertex that is closer to the fragment
representative.

Finally, the |pq| pointer of each fragment points to the header node of
its priority queue, which is a binomial queue containing all
unlooked-at arcs that originate from vertices in the fragment.
This pointer is identical to the |newarc| pointer already set up.
In a production implementation, we wouldn't need |pq| as a
separate field; it would be part of a vertex record. So we do not
pay any mems for referring to it.
@^discussion of \\{mems}@>

@d pq newarc

@<Create the small...@>=
o,s=g->vertices;
for (v=s;v<s+frags;v++) {
  if (v>s) {
    o,v->lsib=v-1;@+o,(v-1)->rsib=v;
  }
  o,v->comp=NULL;
  o,v->csize=1;
  o,v->pq->qcount=0; /* the binomial queue is initially empty */
  for (o,a=v->arcs;a;o,a=a->next) qenque(v->pq,a);
}
t=v-1;

@ @<Combine the first fragment...@>=
v=s;
o,s=s->rsib; /* remove |v| from small list */
do@+{a=qdel_min(v->pq);
  if (a==NULL) return INFINITY; /* the graph isn't connected */
  o,u=a->tip;
  while (o,u->comp) u=u->comp; /* find the fragment pointed to */
}@+while (u==v); /* repeat until a new fragment is found */
if (verbose) @<Report the new edge verbosely@>;
o,tot_len+=a->len;
o,v->comp=u;
qmerge(u->pq,v->pq);
o,old_size=u->csize;
o,new_size=old_size+v->csize;
o,u->csize=new_size;
@<Move |u| to the proper list position@>;

@ @<Local variables for |cher...@>=
long old_size,new_size; /* size of fragment |u|, before and after */

@ Here is a fussy part of the program. We have just merged the small
fragment |v| into another fragment~|u|. If |u| was already large,
there's nothing to do (except to check if the small list has just
become empty). Otherwise we need to move |u| to the end of the small
list, or we need to put it onto the large list.
All these cases are special, if we
want to avoid unnecessary memory references; so let's hope we get them right.

@<Move |u|...@>=
if (old_size>=hi_sqrt) { /* |u| was large */
  if (t==v) s=NULL; /* small list just became empty */
}@+else if (new_size<hi_sqrt) { /* |u| was and still is small */
  if (u==t) goto fin; /* |u| is already where we want it */
  if (u==s) o,s=u->rsib; /* remove |u| from front */
  else {
    ooo,u->rsib->lsib=u->lsib; /* detach |u| from middle */
    o,u->lsib->rsib=u->rsib; /* do you follow the mem-counting here? */
@^discussion of \\{mems}@>
  }
  o,t->rsib=u; /* insert |u| at the end */
  o,u->lsib=t;
  t=u;
}@+else { /* |u| has just become large */
  if (u==t) {
    if (u==s) goto fin; /* well, keep it small, we're done anyway */
    o,t=u->lsib; /* remove |u| from end */
  }@+else if (u==s)
    o,s=u->rsib; /* remove |u| from front */
  else {
    ooo,u->rsib->lsib=u->lsib; /* detach |u| from middle */
    o,u->lsib->rsib=u->rsib;
  }
  o,u->rsib=large_list;@+large_list=u; /* make |u| large */
}
fin:;

@ We don't have room in our binomial queues to keep track of both
endpoints of the arcs. But the arcs occur in pairs, and by looking
at the address of |a| we can tell whether the matching arc is
|a+1| or |a-1|. (See the explanation in {\sc GB\_\,GRAPH}.)

@<Report the new edge verbosely@>=
report((edge_trick&(siz_t)a? a-1: a+1)->tip,a->tip,a->len);

@*Cheriton, Tarjan, and Karp's algorithm (continued).
And now for the second part of the algorithm. Here we need to
find room for a $\lsqrtn\times\lsqrtn$ matrix of edge lengths;
we will use random access into the |z| utility fields of vertex records,
since these haven't been used for anything yet by |cher_tar_kar|.
We can also use the |v| utility fields to record the arcs that
are the source of the best lengths, since this was the |lsib|
field (no longer needed). The program doesn't count mems for
updating that field, since it considers its goal to be simply
the calculation of minimum spanning tree length; the actual
edges of the minimum spanning tree are computed only for
|verbose| mode. (We want to see how competitive |cher_tar_kar| is
when we streamline it as much as possible.)
@^discussion of \\{mems}@>

In stage 2, the vertices will be assigned integer index numbers
between 0 and $\lsqrtn-1$. We'll put this into the |csize| field,
which is no longer needed, and call it |findex|.

@d findex csize
@d matx(j,k) (gv+((j)*lo_sqrt+(k)))->z.I
 /* distance between fragments |j| and |k| */
@d matx_arc(j,k) (gv+((j)*lo_sqrt+(k)))->v.A
 /* arc corresponding to |matx(j,k)| */
@d INF 30000 /* upper bound on all edge lengths */

@<Do stage 2 of |cher_tar_kar|@>=
gv=g->vertices; /* the global variable |gv| helps access auxiliary memory */
@<Map all vertices to their index numbers@>;
@<Create the reduced matrix by running through all remaining edges@>;
@<Execute Prim's algorithm on the reduced matrix@>;

@ The vertex-mapping algorithm is $O(n)$ because each non-null |comp| link
is examined at most three times. We set the |comp| field to null
as an indication that |findex| has been set.

@<Map all...@>=
if (s==NULL) s=large_list;
else o,t->rsib=large_list;
for (k=0,v=s;v;o,v=v->rsib,k++) o,v->findex=k;
for (v=g->vertices;v<g->vertices+g->n;v++)
  if (o,v->comp) {
    for (t=v->comp;o,t->comp;t=t->comp) ;
    o,k=t->findex;
    for (t=v;o,u=t->comp;t=u) {
      o,t->comp=NULL;
      o,t->findex=k;
    }
  }

@ @<Create the reduced matrix by running through all remaining edges@>=
for (j=0;j<lo_sqrt;j++) for (k=0;k<lo_sqrt;k++) o,matx(j,k)=INF;
for (kk=0;s;o,s=s->rsib,kk++) qtraverse(s->pq,note_edge);

@ The |note_edge| procedure ``visits'' every edge in the
binomial queues traversed by |qtraverse| in the preceding code.
Global variable |kk|, which would be a global register in a
production version, is the index of the fragment from which
this arc emanates.

@<Procedures to be declared early@>=
void note_edge(a)
  Arc *a;
{@+register long k;
  oo,k=a->tip->findex;
  if (k==kk) return;
  if (oo,a->len<matx(kk,k)) {
    o,matx(kk,k)=a->len;
    o,matx(k,kk)=a->len;
    matx_arc(kk,k)=matx_arc(k,kk)=a;
  }
}

@ As we work on the final subproblem of size $\lsqrtn\times\lsqrtn$,
we'll have a short vector that tells us the distance to each fragment that
hasn't yet been joined up with fragment~0. The vector has |-1| in positions
that already have been joined up. In a production version, we could
keep this in row~0 of |matx|.

@<Glob...@>=
long kk; /* current fragment */
long distance[100]; /* distances to at most \lsqrtn\ unhit fragments */
Arc *dist_arc[100]; /* the corresponding arcs, for |verbose| mode */

@ The last step, as suggested by Prim, repeatedly updates
@^Prim, Robert Clay@>
the distance table against each row of the matrix as it is encountered.
This is the algorithm of choice to find the minimum spanning tree of
a complete graph.

@<Execute