gb_miles.w

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

Yakima, WA[4660,12051]49826\cr
1513 2410\cr
Worcester, MA[4227,7180]161799\cr
2964 1520 604\cr
}}$$
we learn that the distance from Worcester, Massachusetts, to Yakima,
Washington, is 2964 miles; from Worcester to Youngstown it is 604 miles.

The following two-letter ``state codes'' are used for Canadian provinces:
$\.{BC}=\null$British Columbia,
$\.{MB}=\null$Manitoba,
$\.{ON}=\null$Ontario,
$\.{SK}=\null$Saskatchewan.

@<Read the data file \.{miles.dat} and compute city weights@>=
node_block=gb_typed_alloc(MAX_N,node,new_graph->aux_data);
distance=gb_typed_alloc(MAX_N*MAX_N,long,new_graph->aux_data);
if (gb_trouble_code) {
  gb_free(new_graph->aux_data);
  panic(no_room+1); /* no room to copy the data */
}
if (gb_open("miles.dat")!=0)
  panic(early_data_fault);
    /* couldn't open |"miles.dat"| using GraphBase conventions;
                 |io_errors| tells why */
for (k=MAX_N-1; k>=0; k--) @<Read and store data for city |k|@>;
if (gb_close()!=0)
  panic(late_data_fault);
    /* something's wrong with |"miles.dat"|; see |io_errors| */

@ The bounds we've imposed on |north_weight|, |west_weight|, and |pop_weight|
guarantee that the key value computed here will be between 0 and~$2^{31}$.

@<Read and store...@>=
{@+register node *p;
  p=node_block+k;
  p->kk=k;
  if (k) p->link=p-1;
  gb_string(p->name,'[');
  if (gb_char()!='[') panic(syntax_error); /* out of sync in \.{miles.dat} */
  p->lat=gb_number(10);
  if (p->lat<min_lat || p->lat>max_lat || gb_char()!=',')
    panic(syntax_error+1); /* latitude data was clobbered */
  p->lon=gb_number(10);
  if (p->lon<min_lon || p->lon>max_lon || gb_char()!=']')
    panic(syntax_error+2); /* longitude data was clobbered */
  p->pop=gb_number(10);
  if (p->pop<min_pop || p->pop>max_pop)
    panic(syntax_error+3); /* population data was clobbered */
  p->key=north_weight*(p->lat-min_lat)
   +west_weight*(p->lon-min_lon)
   +pop_weight*(p->pop-min_pop)+0x40000000;
  @<Read the mileage data for city |k|@>;
  gb_newline();
}

@ @d d(j,k) *(distance+(MAX_N*j+k))

@<Read the mileage...@>=
{
  for (j=k+1; j<MAX_N; j++) {
    if (gb_char()!=' ')
      gb_newline();
    d(j,k)=d(k,j)=gb_number(10);
  }
}

@ Once all the nodes have been set up, we can use the |gb_linksort| routine
to sort them into the desired order. This routine, which is part of
the \\{gb\_graph} module, builds 128 lists from which the desired nodes
are readily accessed in decreasing order of weight, using random numbers
to break ties.

We set the population to zero in every city that isn't chosen. Then
that city will be excluded when edges are examined later.
 
@<Determine the |n| cities to use in the graph@>=
{@+register node *p; /* the current node being considered */
  register Vertex *v=new_graph->vertices; /* the first unfilled vertex */
  gb_linksort(node_block+MAX_N-1);
  for (j=127; j>=0; j--)
    for (p=(node*)gb_sorted[j]; p; p=p->link) {
      if (v<new_graph->vertices+n) @<Add city |p->kk| to the graph@>@;
      else p->pop=0; /* this city is not being used */
    }
}

@ Utility fields |x| and |y| for each vertex are set to coordinates that
can be used in geometric computations; these coordinates are obtained by
simple linear transformations of latitude and longitude (not by any
kind of sophisticated polyconic projection). We will have
$$0\le x\le5132, \qquad 0\le y\le 3555.$$
Utility field~|z| is set to the city's index number (0 to 127) in the
original database. Utility field~|w| is set to the city's population.

The coordinates computed here are compatible with those in the \TEX/ file
\.{cities.texmap}. Users might want to incorporate edited copies of that file
into documents that display results obtained with |miles| graphs.
@.cities.texmap@>

@d x_coord x.I
@d y_coord y.I
@d index_no z.I
@d people w.I

@<Add city |p->kk| to the graph@>=
{
  v->x_coord=max_lon-p->lon; /* |x| coordinate is complement of longitude */
  v->y_coord=p->lat-min_lat;
  v->y_coord+=(v->y_coord)>>1; /* |y| coordinate is 1.5 times latitude */
  v->index_no=p->kk;
  v->people=p->pop;
  v->name=gb_save_string(p->name);
  v++;
}

@ @(gb_miles.h@>=
#define x_coord @t\quad@> x.I
 /* utility field definitions for the header file */
#define y_coord @t\quad@> y.I
#define index_no @t\quad@> z.I
#define people @t\quad@> w.I

@* Arcs.  We make the distance negative in the matrix entry for an arc
that is not to be included.  Nothing needs to be done in this regard
unless the user has specified a maximum degree or a maximum edge length.

@<Put the approp...@>=
if (max_distance>0 || max_degree>0)
  @<Prune unwanted edges by negating their distances@>;
{@+register Vertex *u,*v;
  for (u=new_graph->vertices;u<new_graph->vertices+n;u++) {
    j=u->index_no;
    for (v=u+1;v<new_graph->vertices+n;v++) {
      k=v->index_no;
      if (d(j,k)>0 && d(k,j)>0)
        gb_new_edge(u,v,d(j,k));
    }
  }
}

@ @<Prune...@>=
{@+register node *p;
  if (max_degree==0) max_degree=MAX_N;
  if (max_distance==0) max_distance=30000;
  for (p=node_block; p<node_block+MAX_N; p++)
    if (p->pop) { /* this city not deleted */
      k=p->kk;
      @<Blank out all undesired edges from city |k|@>;
    }
}

@ Here we reuse the key fields of the nodes, storing complementary distances
there instead of weights. We also let the sorting routine change the
link fields. The other fields, however---especially |pop|---remain
unchanged. Yes, the author knows this is a wee bit tricky, but why~not?

@<Blank...@>=
{@+register node *q;
  register node*s=NULL; /* list of nodes containing edges from city |k| */
  for (q=node_block; q<node_block+MAX_N; q++)
    if (q->pop && q!=p) { /* another city not deleted */
      j=d(k,q->kk); /* distance from |p| to |q| */
      if (j>max_distance)
        d(k,q->kk)=-j;
      else {
        q->key=max_distance-j;
        q->link=s;
        s=q;
      }
    }
  gb_linksort(s);
  /* now all the surviving edges from |p| are in the list |gb_sorted[0]| */
  j=0; /* |j| counts how many edges have been accepted */
  for (q=(node*)gb_sorted[0]; q; q=q->link)
    if (++j>max_degree)
      d(k,q->kk)=-d(k,q->kk);
}

@ Random access to the distance matrix is provided to users via
the external function |miles_distance|. Caution: This function can be
used only with the graph most recently made by |miles|, and only when
the graph's |aux_data| has not been recycled, and only when the
|z| utility fields have not been used for another purpose.

The result might be negative when an edge has been suppressed. Moreover,
we can in fact have |miles_distance(u,v)<0| when |miles_distance(v,u)>0|,
if the distance in question was suppressed by the |max_degree| constraint
on~|u| but not on~|v|.

@p long miles_distance(u,v)
  Vertex *u,*v;
{
  return d(u->index_no,v->index_no);
}

@ @(gb_miles.h@>=
extern long miles_distance();

@* Index. As usual, we close with an index that
shows where the identifiers of \\{gb\_miles} are defined and used.