miles_span.w

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

% 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{MILES\_\,SPAN}
\def\<#1>{$\langle${\rm#1}$\rangle$}

\prerequisite{GB\_\,MILES}
@* Minimum spanning trees.
A classic paper by R. L. Graham and Pavol Hell about the history of
@^Graham, Ronald Lewis@>
@^Hell, Pavol@>
algorithms to find the minimum-length spanning tree of a graph
[{\sl Annals of the History of Computing \bf7} (1985), 43--57]
describes three main approaches to that problem. Algorithm~1,
``two nearest fragments,'' repeatedly adds a shortest edge that joins
two hitherto unconnected fragments of the graph; this algorithm was
first published by J.~B. Kruskal in 1956. Algorithm~2, ``nearest
@^Kruskal, Joseph Bernard@>
neighbor,'' repeatedly adds a shortest edge that joins a particular
fragment to a vertex not in that fragment; this algorithm was first
published by V. Jarn\'{\i}k in 1930. Algorithm~3, ``all nearest
@^Jarn{\'\i}k, Vojt\u ech@>
fragments,'' repeatedly adds to each existing fragment the shortest
edge that joins it to another fragment; this method, seemingly the
most sophisticated in concept, also turns out to be the oldest,
being first published by Otakar Bor{\accent23u}vka in 1926.
@^Bor{\accent23u}vka, Otakar@>

The present program contains simple implementations of all three
approaches, in an attempt to make practical comparisons of how
they behave on ``realistic'' data. One of the main goals of this
program is to demonstrate a simple way to make machine-independent
comparisons of programs written in \CEE/, by counting memory
references or ``mems.'' In other words, this program is intended
to be read, not just performed.

The author believes that mem counting sheds considerable light on
the problem of determining the relative efficiency of competing
algorithms for practical problems. He hopes other researchers will
enjoy rising to the challenge of devising algorithms that find minimum
spanning trees in significantly fewer mem units than the algorithms
presented here, on problems of the size considered here.

Indeed, mem counting promises to be significant for combinatorial
algorithms of all kinds. The standard graphs available in the
Stanford GraphBase should make it possible to carry out a large
number of machine-independent experiments concerning the practical
efficiency of algorithms that have previously been studied
only asymptotically.

@ The graphs we will deal with are produced by the |miles| subroutine,
found in the {\sc GB\_\,MILES} module. As explained there,
|miles(n,north_weight,west_weight,pop_weight,0,max_degree,seed)| produces a
graph of |n<=128| vertices based on the driving distances between
North American cities. By default we take |n=100|, |north_weight=west_weight
=pop_weight=0|, and |max_degree=10|; this gives billions of different sparse
graphs, when different |seed| values are specified, since a different
random number seed generally results in the selection of another
one of the $\,128\,\choose100$ possible subgraphs.

The default parameters can be changed by specifying options on the
command line, at least in a \UNIX/ implementation, thereby obtaining a
variety of special effects. For example, the value of |n| can be
raised or lowered and/or the graph can be made more or less sparse.
The user can bias the selection by ranking cities according to their
population and/or position, if nonzero values are given to any of the
parameters |north_weight|, |west_weight|, or |pop_weight|.
Command-line options \.{-n}\<number>, \.{-N}\<number>, \.{-W}\<number>,
\.{-P}\<number>, \.{-d}\<number>, and \.{-s}\<number>
are used to specify non-default values of the respective quantities |n|,
|north_weight|, |west_weight|, |pop_weight|, |max_degree|, and |seed|.

If the user specifies a \.{-r} option, for example by saying `\.{miles\_span}
\.{-r10}', this program will investigate the spanning trees of a
series of, say, 10 graphs having consecutive |seed| values. (This
option makes sense only if |north_weight=west_weight=pop_weight=0|,
because |miles| chooses the top |n| cities by weight. The procedure rarely
needs to use random numbers to break ties when the weights are nonzero,
because cities rarely have exactly the same weight in that case.)

The special command-line option \.{-g}$\langle\,$filename$\,\rangle$
overrides all others. It substitutes an external graph previously saved by
|save_graph| for the graphs produced by |miles|. 

@^UNIX dependencies@>

Here is the overall layout of this \CEE/ program:

@p
#include "gb_graph.h" /* the GraphBase data structures */
#include "gb_save.h" /* |restore_graph| */
#include "gb_miles.h" /* the |miles| routine */
@h@#
@<Global variables@>@;
@<Procedures to be declared early@>@;
@<Priority queue subroutines@>@;
@<Subroutines@>@;
main(argc,argv)
  int argc; /* the number of command-line arguments */
  char *argv[]; /* an array of strings containing those arguments */
{@+unsigned long n=100; /* the desired number of vertices */
  unsigned long n_weight=0; /* the |north_weight| parameter */
  unsigned long w_weight=0; /* the |west_weight| parameter */
  unsigned long p_weight=0; /* the |pop_weight| parameter */
  unsigned long d=10; /* the |max_degree| parameter */
  long s=0; /* the random number seed */
  unsigned long r=1; /* the number of repetitions */
  char *file_name=NULL; /* external graph to be restored */
  @<Scan the command-line options@>;
  while (r--) {
    if (file_name) g=restore_graph(file_name);
    else g=miles(n,n_weight,w_weight,p_weight,0L,d,s);
    if (g==NULL || g->n<=1) {
      fprintf(stderr,"Sorry, can't create the graph! (error code %ld)\n",
               panic_code);
      return -1; /* error code 0 means the graph is too small */
    }
    @<Report the number of mems needed to compute a minimum spanning tree
       of |g| by various algorithms@>;
    gb_recycle(g);
    s++; /* increase the |seed| value */
  }
  return 0; /* normal exit */
}

@ @<Global...@>=
Graph *g; /* the graph we will work on */

@ @<Scan the command-line options@>=
while (--argc) {
@^UNIX dependencies@>
  if (sscanf(argv[argc],"-n%lu",&n)==1) ;
  else if (sscanf(argv[argc],"-N%lu",&n_weight)==1) ;
  else if (sscanf(argv[argc],"-W%lu",&w_weight)==1) ;
  else if (sscanf(argv[argc],"-P%lu",&p_weight)==1) ;
  else if (sscanf(argv[argc],"-d%lu",&d)==1) ;
  else if (sscanf(argv[argc],"-r%lu",&r)==1) ;
  else if (sscanf(argv[argc],"-s%ld",&s)==1) ;
  else if (strcmp(argv[argc],"-v")==0) verbose=1;
  else if (strncmp(argv[argc],"-g",2)==0) file_name=argv[argc]+2;
  else {
    fprintf(stderr,
             "Usage: %s [-nN][-dN][-rN][-sN][-NN][-WN][-PN][-v][-gfoo]\n",
             argv[0]);
    return -2;
  }
}
if (file_name) r=1;

@ We will try out four basic algorithms that have received prominent
attention in the literature. Graham and Hell's Algorithm~1 is represented
by the |krusk| procedure, which uses Kruskal's algorithm after the
edges have been sorted by length with a radix sort. Their Algorithm~2
is represented by the |jar_pr| procedure, which incorporates a 
priority queue structure that we implement in two ways, either as
a simple binary heap or as a Fibonacci heap. And their Algorithm~3
is represented by the |cher_tar_kar| procedure, which implements a
method similar to Bor{\accent23u}vka's that was independently
discovered by Cheriton and Tarjan and later simplified and refined by
Karp and Tarjan.
@^Cheriton, David Ross@>
@^Tarjan, Robert Endre@>
@^Karp, Richard Manning@>

@d INFINITY (unsigned long)-1
 /* value returned when there's no spanning tree */

@<Report the number...@>=
printf("The graph %s has %ld edges,\n",g->id,g->m/2);
sp_length=krusk(g);
if (sp_length==INFINITY) printf("  and it isn't connected.\n");
else printf("  and its minimum spanning tree has length %ld.\n",sp_length);
printf(" The Kruskal/radix-sort algorithm takes %ld mems;\n",mems);
@<Execute |jar_pr(g)| with binary heaps as the priority queue algorithm@>;
printf(" the Jarnik/Prim/binary-heap algorithm takes %ld mems;\n",mems);
@<Allocate additional space needed by the more complex algorithms;
    or |goto done| if there isn't enough room@>;
@<Execute |jar_pr(g)| with Fibonacci heaps as
     the priority queue algorithm@>;
printf(" the Jarnik/Prim/Fibonacci-heap algorithm takes %ld mems;\n",mems);
if (sp_length!=cher_tar_kar(g)) {
  if (gb_trouble_code) printf(" ...oops, I've run out of memory!\n");
  else printf(" ...oops, I've got a bug, please fix fix fix\n");
  return -3;
}
printf(" the Cheriton/Tarjan/Karp algorithm takes %ld mems.\n\n",mems);
done:;

@ @<Glob...@>=
unsigned long sp_length; /* length of the minimum spanning tree */

@ When the |verbose| switch is nonzero, edges found by the various
algorithms will call the |report| subroutine.

@<Sub...@>=
report(u,v,l)
  Vertex *u,*v; /* adjacent vertices in the minimum spanning tree */
  long l; /* the length of the edge between them */
{ printf("  %ld miles between %s and %s [%ld mems]\n",
           l,u->name,v->name,mems);
}

@*Strategies and ground rules.
Let us say that a {\sl fragment\/} is any subtree of a minimum
spanning tree. All three algorithms we implement make use of a basic
principle first stated in full generality by R.~C. Prim in 1957:
@^Prim, Robert Clay@>
``If a fragment~$F$ does not include all the vertices, and if $e$~is
a shortest edge joining $F$ to a vertex not in~$F$, then $F\cup e$
is a fragment.'' To prove Prim's principle, let $T$ be a minimum
spanning tree that contains $F$ but not~$e$. Adding $e$ to~$T$ creates
a circuit containing some edge $e'\ne e$, where $e'$ runs from a vertex
in~$F$ to a vertex not in~$F$. Deleting $e'$ from
$T\cup e$ produces a spanning tree~$T'$ of total length no larger
than the total length of~$T$. Hence $T'$ is a minimum spanning
tree containing $F\cup e$, QED.

@ The graphs produced by |miles| have special properties, and it is fair game
to make use of those properties if we can.

First, the length of each edge is a positive integer less than $2^{12}$.

Second, the $k$th vertex $v_k$ of the graph is represented in \CEE/ programs by
the pointer expression |g->vertices+k|. If weights have been assigned,
these vertices will be in order by weight. For example, if |north_weight=1|
but |west_weight=pop_weight=0|, vertex $v_0$ will be the most northerly city
and vertex $v_{n-1}$ will be the most southerly.

Third, the edges accessible from a vertex |v| appear in a linked list
starting at |v->arcs|. An edge from |v| to $v_j$ will precede an
edge from |v| to $v_k$ in this list if and only if $j>k$.

Fourth, the vertices have coordinates |v->x_coord| and |v->y_coord|
that are correlated with the length of edges between them: The
Euclidean distance between the coordinates of two vertices tends to be small
if and only if those vertices are connected by a relatively short edge.
(This is only a tendency, not a certainty; for example, some cities
around Chesapeake Bay are fairly close together as the crow flies, but not
within easy driving range of each other.)

Fifth, the edge lengths satisfy the triangle inequality: Whenever
three edges form a cycle, the longest is no longer than the sum of
the lengths of the two others. (It can be proved that
the triangle inequality is of no use in finding minimum spanning
trees; we mention it here only to exhibit yet another way in which
the data produced by |miles| is known to be nonrandom.)

Our implementation of Kruskal's algorithm will make use of the first
property, and it also uses part of the third to avoid considering an
edge more than once. We will not exploit the other properties, but a
reader who wants to design algorithms that use fewer mems to find minimum
spanning trees of these graphs is free to use any idea that helps.

@ Speaking of mems, here are the simple \CEE/ instrumentation macros that we
use to count memory references. The macros are called |o|, |oo|, |ooo|,
and |oooo|; hence Jon Bentley has called this a ``little oh analysis.''
@^Bentley, Jon Louis@>
Implementors who want to count mems are supposed to say, e.g., `|oo|,'
just before an assignment statement or boolean expression that makes
two references to memory. The \CEE/ preprocessor will convert this
to a statement that increases |mems| by~2 as that statement or expression
is evaluated.

The semantics of \CEE/ tell us that the evaluation of an expression
like `|a&&(o,a->len>10)|' will increment |mems| if and only if the
pointer variable~|a| is non-null. Warning: The parentheses are very
important in this example, because \CEE/'s operator |&&| (i.e.,
\.{\&\&}) has higher precedence than comma.

Values of significant variables, like |a| in the previous example,
can be assumed to be in ``registers,'' and no charge is made for
arithmetic computations that involve only registers. But the total
number of registers in an implementation must be finite and fixed,
independent of the problem size.
@^discussion of \\{mems}@>

\CEE/ does not allow the |o| macros to appear in declarations, so we cannot
take full advantage of \CEE/'s initialization mechanism when we are
counting mems. But it's easy to initialize variables in separate
statements after the declarations are done.

@d o mems++
@d oo mems+=2
@d ooo mems+=3
@d oooo mems+=4

@<Glob...@>=
long mems; /* the number of memory references counted */

@ Examples of these mem-counting conventions appear throughout the
program that follows. Some people will undoubtedly ask why the insertion of
macros by hand is being recommended here, when it would be possible to
develop a fancy system that counts mems automatically. The author
believes that it is best to rely on programmers to introduce |o| and
|oo|, etc., by themselves, for several reasons. (1)~The macros can be
inserted easily and quickly using a text editor. (2)~An implementation
need not pay for mems that could be avoided by a suitable optimizing
compiler or by making the \CEE/ program text slightly more complex;
thus, authors can use their good judgment to keep programs more
readable than if the code were overly hand-optimized. (3)~The
programmer should be able to see exactly where mems are being charged,
as an aid to bottleneck elimination. Occurrences of |o| and |oo| make
this plain without messing up the program text. (4)~An implementation
need not be charged for mems that merely provide diagnostic output, or
mems that do redundant computations just to double-check the validity
of ``proven'' assertions as a program is being tested.
@^discussion of \\{mems}@>

Computer architecture is converging rapidly these days to the
design of machines in which the exact running time of a program
depends on complicated interactions between pipelined circuitry and
the dynamic properties of cache mapping in a memory hierarchy,
not to mention the effects of compilers and operating systems.
But a good approximation to running time is usually obtained if we
assume that the amount of computation is proportional to the activity
of the memory bus between registers and main memory. This
approximation is likely to get even better in the future, as
RISC computers get faster and faster in comparison to memory devices.
Although the mem measure is far from perfect, it appears to be
significantly less distorted than any other measurement that can
be obtained without considerably more work. An implementation that
is designed to use few mems will almost certainly be efficient
on today's sequential computers, as well as on the sequential computers
we can expect to be built in the foreseeable future. And the converse
statement is even more true: An algorithm that runs fast will not
consume many mems.

Of course authors are expected to be reasonable and fair when they