gb_dijk.w

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

observe that vertices are becoming known in order of true distance
plus |hh| value.

@<Print initial message@>=
{@+printf("Distances from %s", uu->name);
  if (hh!=dummy) printf(" [%ld]", uu->hh_val);
  printf(":\n");
}

@ @<Print the distance to |t|@>=
{@+printf(" %ld to %s", t->dist - t->hh_val + uu->hh_val, t->name);
  if (hh!=dummy) printf(" [%ld]", t->hh_val);
  printf(" via %s\n", t->backlink->name);
}

@ After |dijkstra| has found a shortest path, the backlinks from~|vv|
specify the steps of that path. We want to print the path in the forward
direction, so we reverse the links.

We also unreverse them again, just in case the user didn't want the backlinks
to be trashed. Indeed, this procedure can be used for any vertex |vv| whose
backlink is non-null, not only the |vv| that was a parameter to |dijkstra|.

List reversal is conveniently regarded as a process of popping off one stack
and pushing onto another.

@d print_dijkstra_result p_dijkstra_result /* shorthand for linker */

@<The |print_dijkstra_result| procedure@>=
void print_dijkstra_result(vv)
  Vertex *vv; /* ending vertex */
{@+register Vertex *t, *p, *q; /* registers for reversing links */
  t=NULL, p=vv;
  if (!p->backlink) {
    printf("Sorry, %s is unreachable.\n",p->name);
    return;
  }
  do@+{ /* pop an item from |p| to |t| */
    q=p->backlink;
    p->backlink=t;
    t=p;
    p=q;
  }@+while (t!=p); /* the loop stops with |t==p==uu| */
  do@+{
    printf("%10ld %s\n", t->dist-t->hh_val+p->hh_val, t->name);
    t=t->backlink;
  }@+while (t);
  t=p;
  do@+{ /* pop an item from |t| to |p| */
    q=t->backlink;
    t->backlink=p;
    p=t;
    t=q;
  }@+while (p!=vv);
}

@* Priority queues. Here we provide a simple doubly linked list
for queueing; this is a convenient default, good enough for applications
that aren't too large. (See {\sc MILES\_\,SPAN} for implementations of
other schemes that are more efficient when the queue gets large.)

The two queue links occupy two of a vertex's remaining utility fields.

@d llink v.V /* |llink| is stored in utility field |v| of a vertex */
@d rlink w.V /* |rlink| is stored in utility field |w| of a vertex */

@<Glob...@>=
void @[@] (*init_queue)() = init_dlist; /* create an empty dlist */
void @[@] (*enqueue)() = enlist; /* insert a new element in dlist */
void @[@] (*requeue)() = reenlist ;
  /* decrease the key of an element in dlist */
Vertex *(*del_min)() = del_first; /* remove element with smallest key */

@ There's a special list head, from which we get to everything else in the
queue in decreasing order of keys by following |llink| fields.

The following declaration actually provides for 128 list heads. Only the first
of these is used here, but we'll find something to do with the
other 127 later.

@<Prior...@>=
static Vertex head[128]; /* list-head elements that are always present */
@#
void init_dlist(d)
  long d;
{
  head->llink=head->rlink=head;
  head->dist=d-1; /* a value guaranteed to be smaller than any actual key */
}

@ It seems reasonable to assume that an element entering the queue for the
first time will tend to have a larger key than the other elements.

Indeed, in the special case that all arcs in the graph have the same
length, this strategy turns out to be quite fast. For in that case,
every vertex is added to the end of the queue and deleted from the
front, without any requeueing; the algorithm produces a strict
first-in-first-out queueing discipline and performs a breadth-first search.

@<Prior...@>=
void enlist(v,d)
  Vertex *v;
  long d;
{@+register Vertex *t=head->llink;
  v->dist=d;
  while (d<t->dist) t=t->llink;
  v->llink=t;
  (v->rlink=t->rlink)->llink=v;
  t->rlink=v;
}

@ @<Prior...@>=
void reenlist(v,d)
  Vertex *v;
  long d;
{@+register Vertex *t=v->llink;
  (t->rlink=v->rlink)->llink=v->llink; /* remove |v| */
  v->dist=d; /* we assume that the new |dist| is smaller than it was before */
  while (d<t->dist) t=t->llink;
  v->llink=t;
  (v->rlink=t->rlink)->llink=v;
  t->rlink=v;
}

@ @<Prior...@>=
Vertex *del_first()
{@+Vertex *t;
  t=head->rlink;
  if (t==head) return NULL;
  (head->rlink=t->rlink)->llink=head;
  return t;
}

@* A special case. When the arc lengths in the graph are all fairly small,
we can substitute another queueing discipline that does each operation
quickly. Suppose the only lengths are 0, 1, \dots,~|k-1|; then we can
prove easily that the priority queue will never contain more than |k|
different values at once. Moreover, we can implement it by maintaining
|k| doubly linked lists, one for each key value mod~|k|.

For example, let |k=128|.  Here is an alternate set of queue commands,
to be used when the arc lengths are known to be less than~128.

@ @<Prior...@>=
static long master_key; /* smallest key that may be present in the priority queue */
@#
void init_128(d)
  long d;
{@+register Vertex *u;
  master_key=d;
  for (u=head; u<head+128; u++)
    u->llink=u->rlink=u;
}

@ If the number of lists were not a power of 2, we would calculate a remainder
by division instead of by logical-anding.

@<Prior...@>=
Vertex *del_128()
{@+long d;
  register Vertex *u, *t;
  for (d=master_key; d<master_key+128; d++) {
    u=head+(d&0x7f); /* that's |d%128| */
    t=u->rlink;
    if (t!=u) { /* we found a nonempty list with minimum key */
      master_key=d;
      (u->rlink = t->rlink)->llink = u;
      return t; /* incidentally, |t->dist = d| */
    }
  }
  return NULL; /* all 128 lists are empty */
}

@ @<Prior...@>=
void enq_128(v,d)
  Vertex *v; /* new vertex for the queue */
  long d; /* its |dist| */
{@+register Vertex *u=head+(d&0x7f);
  v->dist = d;
  (v->llink = u->llink)->rlink = v;
  v->rlink = u;
  u->llink = v;
}

@ All of these operations have been so simple, one wonders why the lists
should be doubly linked. Single linking would indeed be plenty---if we
didn't have to support the |requeue| operation.

But requeueing involves deleting an arbitrary element from the middle of
its list. And we do seem to need two links for that.

In the application to Dijkstra's algorithm, the new |d| will always
be |master_key| or more. But we want to implement requeueing in general,
so that this procedure can be used also for other algorithms
such as the calculation of minimum spanning trees (see {\sc MILES\_\,SPAN}).

@<Prior...@>=
void req_128(v,d)
  Vertex *v; /* vertex to be moved to another list */
  long d; /* its new |dist| */
{@+register Vertex *u=head+(d&0x7f);
  (v->llink->rlink=v->rlink)->llink=v->llink; /* remove |v| */  
  v->dist=d; /* the new |dist| is smaller than it was before */
  (v->llink=u->llink)->rlink = v;
  v->rlink = u;
  u->llink = v;
  if (d<master_key) master_key=d; /* not needed for Dijkstra's algorithm */
}

@ The user of {\sc GB\_\,DIJK} needs to know the names of these
queueing procedures if changes to the defaults are made, so we'd
better put the necessary info into the header file.

@(gb_dijk.h@>=
extern void init_dlist();
extern void enlist();
extern void reenlist();
extern Vertex *del_first();
extern void init_128();
extern Vertex *del_128();
extern void enq_128();
extern void req_128();

@* Index. Here is a list that shows where the identifiers of this program are
defined and used.