miles_span.w

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

  j=k>>1; /* |k/2| */
  if (j>0 && (oo,(u=heap_elt(j))->dist>d)) { /* change is needed */
    do@+{
      o,heap_elt(k)=u; /* the hole moves to parent position */
      o,u->heap_index=k;
      k=j;
      j=k>>1; /* |k/2| */
    }@+while (j>0 && (oo,(u=heap_elt(j))->dist>d));
    o,heap_elt(k)=v;
    o,v->heap_index=k;
  }
}

@ Finally, the procedure for removing the vertex with smallest key is
only a bit more difficult. The vertex to be removed is always
|heap_elt(1)|. After we delete it, we ``sift down'' |heap_elt(hsize)|,
until the basic heap inequalities hold once again.

At a crucial point in this process, we have |j->dist<u->dist|. We cannot
then have
|j=hsize+1|, because the previous steps have made |(hsize+1)->dist=u->dist=d|.

@<Prior...@>=
Vertex *del_heap()
{@+Vertex *v; /* vertex to return */
  register Vertex *u; /* vertex being sifted down */
  register unsigned long k; /* hole in the heap */
  register unsigned long j; /* child of that hole */
  register long d; /* |u->dist|, the vertex of the vertex being sifted */
  if (hsize==0) return NULL;
  o,v=heap_elt(1);
  o,u=heap_elt(hsize--);
  o,d=u->dist;
  k=1;
  j=2;
  while (j<=hsize) {
    if (oooo,heap_elt(j)->dist>heap_elt(j+1)->dist) j++;
    if (heap_elt(j)->dist>=d) break;
    o,heap_elt(k)=heap_elt(j); /* NB: we cannot have |j>hsize|, see above */
    o,heap_elt(k)->heap_index=k;
    k=j; /* the hole moves to child position */
    j=k<<1; /* |2k| */
  }
  o,heap_elt(k)=u;
  o,u->heap_index=k;
  return v;
}

@ OK, here's how we plug binary heaps into Jarn{\'\i}k/Prim.

@<Execute |jar_pr(g)| with binary heaps as the priority queue algorithm@>=
init_queue=init_heap;
enqueue=enq_heap;
requeue=req_heap;
del_min=del_heap;
if (sp_length!=jar_pr(g)) {
  printf(" ...oops, I've got a bug, please fix fix fix\n");
  return -4;
}

@*Fibonacci heaps.
The running time of Jarn{\'\i}k/Prim with binary heaps, when the algorithm is
applied to a connected graph with $n$ vertices and $m$ edges, is $O(m\log n)$,
because the total number of operations is $O(m+n)=O(m)$ and each
heap operation takes at most $O(\log n)$ time.

Fibonacci heaps were invented by Fredman and Tarjan in 1984, in order
@^Fibonacci, Leonardo, heaps@>
@^Fredman, Michael Lawrence@>
@^Tarjan, Robert Endre@>
to do better than this. The Jarn{\'\i}k/Prim algorithm does $O(n)$
enqueueing operations, $O(n)$ delete-min operations, and $O(m)$
requeueing operations; so Fredman and Tarjan designed a data structure
that would support requeueing in ``constant amortized time.'' In other
words, Fibonacci heaps allow us to do $m$ requeueing operations with a
total cost of~$O(m)$, even though some of the individual requeueings
might take longer. The resulting asymptotic running time is then
$O(m+n\log n)$. (This turns out to be optimum within a constant
factor, when the same technique is applied to Dijkstra's algorithm for
shortest paths. But for minimum spanning trees the Fibonacci method is
not always optimum; for example, if $m\approx n\sqrt{\mathstrut\log n}$, the
algorithm of Cheriton and Tarjan has slightly better asymptotic
behavior, $O(m\log\log n)$.)

Fibonacci heaps are more complex than binary heaps, so we can expect
that overhead  costs will make them non-competitive unless $m$ and $n$ are
quite large. Furthermore, it is not clear that the running time with simple
binary heaps will behave as $m\log n$ on realistic data, because
$O(m\log n)$ is a worst-case estimate based on rather pessimistic
assumptions. (For example, requeueing might rarely require many
iterations of the siftup loop.) But it will be instructive to
implement Fibonacci heaps as best we can, just to see how good they
look in actual practice.

Let us say that the {\sl rank\/} of a node in a forest is the number
of children it has. A Fibonacci heap is an unordered forest of trees
in which the key of each node is less than or equal to the key of each
child of that node, and in which the following further condition,
called property~F, also holds: The ranks $\{r_1,r_2,\ldots,r_k\}$ of the
children of every node of rank~$k$, when put into nondecreasing
order $r_1\le r_2\le\cdots\le r_k$, satisfy $r_j\ge j-2$ for all~$j$.

As a consequence of property F, we can prove by induction that every
node of rank~$k$ has at least $F_{k+2}$ descendants (including itself).
Therefore, for example, we cannot have a node of rank $\ge30$ unless
the total size of the forest is at least $F_{32}=2{,}178{,}309$. We cannot
have a node of rank $\ge46$ unless the total size of the forest
exceeds~$2^{32}$.

@ We will represent a Fibonacci heap with a rather elaborate data structure,
in order to guarantee the efficiency of all the necessary operations.
Each node will have four pointers: |parent|, the node's parent (or
|NULL| if the node is a root); |child|, one of the node's children
(or undefined if the node has no children); |lsib| and |rsib|, the
node's left and right siblings. The children of each node, and the
roots of the forest, are doubly linked by |lsib| and |rsib| in
circular lists; the nodes in these lists can appear in any convenient
order, and the |child| pointer can point to any child.

Besides the four pointers, there is a \\{rank} field, which tells how
many children exist, and a \\{tag} field, which is either 0 or~1.

Suppose a node has children of ranks $\{r_1,r_2,\ldots,r_k\}$, where
$r_1\le r_2\le\cdots\le r_k$. We know that $r_j\ge j-2$ for all~$j$;
we say that the node has $l$ {\sl critical\/} children if there are
$l$ cases of equality, where $r_j=j-2$. Our implementation will
guarantee that any node with $l$ critical children will have at
least $l$ tagged children of the corresponding ranks. For example,
suppose a node has seven children, of respective ranks $\{1,1,1,2,4,4,6\}$.
Then it has three critical children, because $r_3=1$, $r_4=2$, and
$r_6=4$. In our implementation, at least one of the children of
rank~1 will have $\\{tag}=1$, and so will the child of rank~2; so will
one of the children of rank~4.

There is an external pointer called |F_heap|, which indicates a node
whose key is smallest. (If the heap is empty, |F_heap| is~|NULL|.)

@<Prior...@>=
void init_F_heap(d)
  long d;
{@+F_heap=NULL;@+}

@ @<Glob...@>=
Vertex *F_heap; /* pointer to the ring of root nodes */

@ We can save a bit of space and time by combining the \\{rank} and \\{tag}
fields into a single |rank_tag| field, which contains $\\{rank}*2+\\{tag}$.

Vertices in GraphBase graphs have six utility fields. That's just enough
for |parent|, |child|, |lsib|, |rsib|, |rank_tag|, and the key field
|dist|. But unfortunately we also need the |backlink| field, so
we are over the limit. That's not really so bad, however; we
can set up another array of $n$ records, and point to it. The
extra running time needed for indirect pointing does not have to
be charged to mems, because a production system involving Fibonacci
heaps would simply redefine |Vertex| records to have seven utility
fields instead of six. In this way we can simulate the behavior of larger
records without changing the basic GraphBase conventions.
@^discussion of \\{mems}@>

We will want an |Arc| record for each vertex in our next algorithm,
so we might as well allocate storage for it now even though Fibonacci
heaps need only two of the five fields.

@d newarc u.A /* |v->newarc| points to an |Arc| record associated with |v| */
@d parent newarc->tip
@d child newarc->a.V
@d lsib v.V
@d rsib w.V
@d rank_tag x.I

@<Allocate additional space needed by the more complex algorithms...@>=
{@+register Arc *aa;
  register Vertex *uu;
  aa=gb_typed_alloc(g->n,Arc,g->aux_data);
  if (aa==NULL) {
    printf(" and there isn't enough space to try the other methods.\n\n");
    goto done;
  }
  for (uu=g->vertices;uu<g->vertices+g->n;uu++,aa++)
    uu->newarc=aa;
}

@ The {\sl potential energy\/} of a Fibonacci heap, as we are
representing it, is defined to be the number of trees in the forest
plus twice the total number of tagged children. When we operate on a
heap, we will store potential energy to be used up later; then it will
be possible to do the later operations with only a small incremental
cost to the running time. (Potential energy is just a way to prove
that the amortized cost is small; it does not appear explicitly in our
implementation. It simply explains why the number of mems we compute
will always be $O(m+n\log n)$.)

Enqueueing is easy: We simply insert the new element as a new tree in
the forest. This costs a constant amount of time, including the cost of
one new unit of potential energy for the new tree.

We can assume that |F_heap->dist| appears in a register, so we need not
charge a mem to fetch~it.

@<Prior...@>=
void enq_F_heap(v,d)
  Vertex *v; /* vertex that is entering the queue */
  long d; /* its key (aka |dist|) */
{
  o,v->dist=d;
  o,v->parent=NULL;
  o,v->rank_tag=0; /* |v->child| need not be set */
  if (F_heap==NULL) {
    oo,F_heap=v->lsib=v->rsib=v;
  }@+else {@+register Vertex *u;
    o,u=F_heap->lsib;
    o,v->lsib=u;
    o,v->rsib=F_heap;
    oo,F_heap->lsib=u->rsib=v;
    if (F_heap->dist>d) F_heap=v;
  }
}

@ Requeueing is of medium difficulty. If the key is being decreased in
a root node, or if the decrease doesn't make the key less than the key
of its parent, no links need to change (except possibly |F_heap|
itself). Otherwise we detach the node and its descendants from its
present family and put this former subtree into the forest as a new
tree. (One unit of potential energy must be stored with it.)

The rank of the former parent, |p|, decreases by~1. If |p| is a root,
we're done. Otherwise if |p| was not tagged, we tag it (and pay for
two additional units of energy). Property~F still holds, because an
untagged node can always admit a decrease in rank. If |p| was tagged,
however, we detach |p| and its remaining descendants, making it another
new tree of the forest, with |p| no longer tagged. Removing the tag
releases enough stored energy to pay for the extra work of moving~|p|.
Then we must decrease the rank of |p|'s parent, and so on, until finally
we get to a root or to an untagged node. The total net cost is at most
three units of energy plus the cost of relinking the original node,
so it is $O(1)$.

We needn't clear the tag fields of root nodes, because we never
look at them.

@<Prior...@>=
void req_F_heap(v,d)
  Vertex *v; /* vertex whose key is being reduced */
  long d; /* its new |dist| */
{@+register Vertex *p,*pp; /* parent and grandparent of |v| */
  register Vertex *u,*w; /* other vertices being modified */
  register long r; /* twice the rank plus the tag */
  o,v->dist=d;
  o,p=v->parent;
  if (p==NULL) {
    if (F_heap->dist>d) F_heap=v;
  }@+else if (o,p->dist>d)
    while(1) {
      o,r=p->rank_tag;
      if (r>=4) /* |v| is not an only child */
        @<Remove |v| from its family@>;
      @<Insert |v| into the forest@>;
      o,pp=p->parent;
      if (pp==NULL) { /* the parent of |v| is a root */
        o,p->rank_tag=r-2;@+break;
      }
      if ((r&1)==0) { /* the parent of |v| is untagged */
        o,p->rank_tag=r-1;@+break; /* now it's tagged */
      }@+else o,p->rank_tag=r-2; /* tagged parent will become a root */
      v=p;@+p=pp;
    }
}

@ @<Remove |v| from its family@>=
{
  o,u=v->lsib;
  o,w=v->rsib;
  o,u->rsib=w;
  o,w->lsib=u;
  if (o,p->child==v) o,p->child=w;
}

@ @<Insert |v| into the forest@>=
o,v->parent=NULL;
o,u=F_heap->lsib;
o,v->lsib=u;
o,v->rsib=F_heap;
oo,F_heap->lsib=u->rsib=v;
if (F_heap->dist>d) F_heap=v; /* this can happen only with the original |v| */

@ The |del_min| operation is even more interesting; this, in fact,
is where most of the action lies. We know that |F_heap| points to the
vertex~$v$ we will be deleting. That's nice, but we need to figure out
the new value of |F_heap|. So we have to look at all the children of~$v$
and at all the root nodes in the forest. We have stored up enough
potential energy to do that, but we can reclaim the potential only if
we rebuild the Fibonacci heap so that the rebuilt version contains
relatively few trees.

The solution is to make sure that the new heap has at most one root
of each rank. Whenever we have two tree roots of equal rank, we can
make one the child of the other, thus reducing the number of
trees by~1. (The new child does not violate Property~F, nor is it
critical, so we can mark it untagged.) The largest rank is always
$O(\log n)$, if there are $n$ nodes altogether, and we can afford to
pay $\log n$ units of time for the work that isn't reclaimed from
potential energy.

An array of pointers to roots of known rank is used to help control
this part of the process.

@<Glob...@>=
Vertex *new_roots[46]; /* big enough for queues of size $2^{32}$ */

@ @<Prio...@>=
Vertex *del_F_heap()
{@+Vertex *final_v=F_heap; /* the node to return */
  register Vertex *t,*u,*v,*w; /* registers for manipulation of links */
  register long h=-1; /* the highest rank present in |new_roots| */
  register long r; /* rank of current tree */
  if (F_heap) {
    if (o,F_heap->rank_tag<2) o,v=F_heap->rsib;
    else {
      o,w=F_heap->child;
      o,v=w->rsib;
      oo,w->rsib=F_heap->rsib;
        /* link children of deleted node into the list */
      for (w=v;w!=F_heap->rsib;o,w=w->rsib)
        o,w->parent=NULL;
    }
    while (v!=F_heap) {
      o,w=v->rsib;
      @<Put the tree rooted at |v| into the |new_roots| forest@>;