<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\input cwebmac
% This file is part of the Stanford GraphBase (c) Stanford University 1993
% This material goes at the beginning of all Stanford GraphBase CWEB files

\def\topofcontents{
  \leftline{\sc\today\ at \hours}\bigskip\bigskip
  \centerline{\titlefont\title}}

\font\ninett=cmtt9
\def\botofcontents{\vskip 0pt plus 1filll
    \ninerm\baselineskip10pt
    \noindent\copyright\ 1993 Stanford University
    \bigskip\noindent
    This file may be freely copied and distributed, provided that
    no changes whatsoever are made. All users are asked to help keep
    the Stanford GraphBase files consistent and ``uncorrupted,''
    identical everywhere in the world. Changes are permissible only
    if the modified file is given a new name, different from the names of
    existing files in the Stanford GraphBase, and only if the modified file is
    clearly identified as not being part of that GraphBase.
    (The {\ninett CWEB} system has a ``change file'' facility by
    which users can easily make minor alterations without modifying
    the master source files in any way. Everybody is supposed to use
    change files instead of changing the files.)
    The author has tried his best to produce correct and useful programs,
    in order to help promote computer science research,
    but no warranty of any kind should be assumed.
    \smallskip\noindent
    Preliminary work on the Stanford GraphBase project
    was supported in part by National Science
    Foundation grant CCR-86-10181.}

\def\prerequisite#1{\def\startsection{\noindent
    Important: Before reading {\sc\title},
    please read or at least skim the program for {\sc#1}.\bigskip
    \let\startsection=\stsec\stsec}}
\def\prerequisites#1#2{\def\startsection{\noindent
    Important: Before reading {\sc\title}, please read
    or at least skim the programs for {\sc#1} and {\sc#2}.\bigskip
    \let\startsection=\stsec\stsec}}



\def\title{GB\_\,MILES}

\prerequisites{GB\_\,GRAPH}{GB\_\,IO}

\N{1}{1}Introduction. This GraphBase module contains the \\{miles} subroutine,
which creates a family of undirected graphs based on highway mileage data
between North American cities. Examples of the use of this procedure can be
found in the demo programs {\sc MILES\_\,SPAN} and {\sc GB\_\,PLANE}.

\Y\B\4\X1:\.{gb\_miles.h }\X${}\E{}$\6
\&amp;{extern} \&amp;{Graph} ${}{*}\\{miles}(\,){}$;\par
\As2, 16\ETs21.\fi

\M{2}The subroutine call {\advance\thinmuskip 0mu plus 4mu
$\\{miles}(\|n,\\{north\_weight},\\{west\_weight},\\{pop\_weight},\\{max%
\_distance},\\{max\_degree},\\{seed})$}
constructs a graph based on the information in \.{miles.dat}.
Each vertex of the graph corresponds to one of the 128 cities whose
name is alphabetically greater than or equal to `Ravenna, Ohio' in
the 1949 edition of Rand McNally {\char`\&amp;} Company's {\sl Standard Highway
Mileage Guide}. Edges between vertices are assigned lengths representing
distances between cities, in miles. In most cases these mileages come
from the Rand McNally Guide, but several dozen entries needed to be changed
drastically because they were obviously too large or too small; in such cases
an educated guess was made. Furthermore, about 5\% of the entries were
adjusted slightly in order to
ensure that all distances satisfy the ``triangle inequality'': The
graph generated by \\{miles} has the property that the
distance from \|u to~\|v plus the distance from \|v to~\|w always exceeds
or equals the distance from \|u to~\|w.

The constructed graph will have $\min(n,128)$ vertices; the default value
$\|n\K\T{128}$ is substituted if $\|n\K\T{0}$. If \|n is less
than 128, the \|n cities will be selected by assigning a weight to
each city and choosing the \|n with largest weight, using random
numbers to break ties in case of equal weights. Weights are computed
by the formula
$$ \\{north\_weight}\cdot\\{lat}+\\{west\_weight}\cdot\\{lon}+\\{pop\_weight}%
\cdot\\{pop}, $$
where \\{lat} is latitude north of the equator, \\{lon} is longitude
west of Greenwich, and \\{pop} is the population in 1980. Both \\{lat} and %
\\{lon}
are given in ``centidegrees'' (hundredths of degrees). For example,
San Francisco has $\\{lat}\K\T{3778}$, $\\{lon}\K\T{12242}$, and $\\{pop}\K%
\T{678974}$;
this means that, before the recent earthquake, it was located at
$37.78^\circ$ north latitude and $122.42^\circ$ west longitude, and that it had
678,974 residents in the 1980 census. The weight parameters must satisfy
$$ \vert\\{north\_weight}\vert\le100{,}000,\quad
\vert\\{west\_weight}\vert\le100{,}000,\quad
\vert\\{pop\_weight}\vert\le100.$$

The constructed graph will be ``complete''---that is, it will have
edges between every pair of vertices---unless special values are given to
the parameters
\\{max\_distance} or \\{max\_degree}. If $\\{max\_distance}\I\T{0}$, edges with
more
than \\{max\_distance} miles will not appear; if $\\{max\_degree}\I\T{0}$, each
vertex will be limited to at most \\{max\_degree} of its shortest edges.

Vertices of the graph will appear in order of decreasing weight.
The \\{seed} parameter defines the pseudo-random numbers used wherever
a ``random'' choice between equal-weight vertices or equal-length edges
needs to be made.

\Y\B\4\D$\.{MAX\_N}$ \5
\T{128}\par
\Y\B\4\X1:\.{gb\_miles.h }\X${}\mathrel+\E{}$\6
\8\#\&amp;{define} \.{MAX\_N} \5\T{128}\C{ maximum and default number of cities }%
\par
\fi

\M{3}Examples: The call $\\{miles}(\T{100},\T{0},\T{0},\T{1},\T{0},\T{0},%
\T{0})$ will construct a
complete graph on 100 vertices, representing the 100 most populous
cities in the database.  It turns out that San Diego, with a
population of 875,538, is the winning city by this criterion, followed
by San Antonio (population 786,023), San Francisco (678,974), and
Washington D.C. (638,432).

To get \|n cities in the western United States and Canada, you can say
$\\{miles}(n,0,1,0,\ldots\,)$; to get \|n cities in the Northeast, use a
call like $\\{miles}(n,1,-1,0,\ldots\,)$. A parameter setting like
$(50,-500,0,1,\ldots\,)$ produces mostly Southern cities, except for a
few large metropolises in the north.

If you ask for $\\{miles}(\|n,\|a,\|b,\|c,\T{0},\T{1},\T{0})$, you get an edge
between cities if
and only if each city is the nearest to the other, among the \|n cities
selected. (The graph is always undirected: There is an arc from \|u to~\|v
if and only if there's an arc of the same length from \|v to~\|u.)

A random selection of cities can be obtained by calling
$\\{miles}(\|n,\T{0},\T{0},\T{0},\|m,\|d,\|s)$.  Different choices of the seed
number \|s will
produce different selections, in a system-independent manner;
identical results will be obtained on all computers when identical
parameters have been specified.  Equivalent experiments on algorithms
for graph manipulation can therefore be performed by researchers in
different parts of the world. Any value of \|s between 0 and
$2^{31}-1$ is permissible.

\fi

\M{4}If the \\{miles} routine encounters a problem, it returns $\NULL$
(\.{NULL}), after putting a code number into the external variable
\\{panic\_code}. This code number identifies the type of failure.
Otherwise \\{miles} returns a pointer to the newly created graph, which
will be represented with the data structures explained in {\sc GB\_\,GRAPH}.
(The external variable \\{panic\_code} is itself defined in {\sc GB\_\,GRAPH}.)

\Y\B\4\D$\\{panic}(\|c)$ \5
${}\{{}$\5
\1${}\\{panic\_code}\K\|c{}$;\5
${}\\{gb\_trouble\_code}\K\T{0}{}$;\5
\&amp;{return} ${}\NULL{}$;\5
${}\}{}$\2\par
\fi

\M{5}The \CEE/ file \.{gb\_miles.c} has the following overall shape:

\Y\B\8\#\&amp;{include} \.{"gb\_io.h"}\C{ we will use the {\sc GB\_\,IO} routines
for input }\6
\8\#\&amp;{include} \.{"gb\_flip.h"}\C{ we will use the {\sc GB\_\,FLIP} routines
for random numbers }\6
\8\#\&amp;{include} \.{"gb\_graph.h"}\C{ we will use the {\sc GB\_\,GRAPH} data
structures }\6
\8\#\&amp;{include} \.{"gb\_sort.h"}\C{ and the linksort routine }\6
\ATH\7
\X9:Type declarations\X\6
\X10:Private variables\X\7
\&amp;{Graph} ${}{*}\\{miles}(\|n,\39\\{north\_weight},\39\\{west\_weight},\39%
\\{pop\_weight},\39\\{max\_distance},\39\\{max\_degree},\39\\{seed}){}$\1\1\6
\&amp;{unsigned} \&amp;{long} \|n;\C{ number of vertices desired }\6
\&amp;{long} \\{north\_weight};\C{ coefficient of latitude in the weight function }%
\6
\&amp;{long} \\{west\_weight};\C{ coefficient of longitude in the weight function }%
\6
\&amp;{long} \\{pop\_weight};\C{ coefficient of population in the weight function }%
\6
\&amp;{unsigned} \&amp;{long} \\{max\_distance};\C{ maximum distance in an edge, if
nonzero }\6
\&amp;{unsigned} \&amp;{long} \\{max\_degree};\C{ maximum number of edges per vertex,
if nonzero }\6
\&amp;{long} \\{seed};\C{ random number seed }\2\2\6
${}\{{}$\5
\1\X6:Local variables\X\7
\\{gb\_init\_rand}(\\{seed});\6
\X7:Check that the parameters are valid\X;\6
\X8:Set up a graph with \|n vertices\X;\6
\X11:Read the data file \.{miles.dat} and compute city weights\X;\6
\X14:Determine the \|n cities to use in the graph\X;\6
\X17:Put the appropriate edges into the graph\X;\6
\&amp;{if} (\\{gb\_trouble\_code})\5
${}\{{}$\1\6
\\{gb\_recycle}(\\{new\_graph});\6
\\{panic}(\\{alloc\_fault});\C{ oops, we ran out of memory somewhere back there
}\6
\4${}\}{}$\2\6
\&amp;{return} \\{new\_graph};\6
\4${}\}{}$\2\par
\fi

\M{6}\B\X6:Local variables\X${}\E{}$\6
\&amp;{Graph} ${}{*}\\{new\_graph}{}$;\C{ the graph constructed by \\{miles} }\6
\&amp;{register} \&amp;{long} \|j${},{}$ \|k;\C{ all-purpose indices }\par
\U5.\fi

\M{7}\B\X7:Check that the parameters are valid\X${}\E{}$\6
\&amp;{if} ${}(\|n\E\T{0}\V\|n&gt;\.{MAX\_N}){}$\1\5
${}\|n\K\.{MAX\_N};{}$\2\6
\&amp;{if} ${}(\\{max\_degree}\E\T{0}\V\\{max\_degree}\G\|n){}$\1\5
${}\\{max\_degree}\K\|n-\T{1};{}$\2\6
\&amp;{if} ${}(\\{north\_weight}&gt;\T{100000}\V\\{west\_weight}&gt;\T{100000}\V\\{pop%
\_weight}&gt;\T{100}\3{-1}\V\\{north\_weight}&lt;{-}\T{100000}\V\\{west\_weight}&lt;{-}%
\T{100000}\V\\{pop\_weight}&lt;{-}\T{100}){}$\1\5
\\{panic}(\\{bad\_specs});\C{ the magnitude of at least one weight is too big }%
\2\par
\U5.\fi

\M{8}\B\X8:Set up a graph with \|n vertices\X${}\E{}$\6
$\\{new\_graph}\K\\{gb\_new\_graph}(\|n);{}$\6
\&amp;{if} ${}(\\{new\_graph}\E\NULL){}$\1\5
\\{panic}(\\{no\_room});\C{ out of memory before we're even started }\2\6
${}\\{sprintf}(\\{new\_graph}\MG\\{id},\39\.{"miles(\%lu,\%ld,\%ld,\%}\)\.{ld,%
\%lu,\%lu,\%ld)"},\39\|n,\39\\{north\_weight},\39\\{west\_weight},\39\\{pop%
\_weight},\39\\{max\_distance},\39\\{max\_degree},\39\\{seed});{}$\6
${}\\{strcpy}(\\{new\_graph}\MG\\{util\_types},\39\.{"ZZIIIIZZZZZZZZ"}){}$;\par
\U5.\fi

\N{1}{9}Vertices.  As we read in the data, we construct a list of nodes,
each of which contains a city's name, latitude, longitude, population,
and weight. These nodes conform to the specifications stipulated in
the {\sc GB\_\,SORT} module. After the list has been sorted by weight, the
top \|n entries will be the vertices of the new graph.

\Y\B\4\X9:Type declarations\X${}\E{}$\6
\&amp;{typedef} \&amp;{struct} \&amp;{node\_struct} ${}\{{}$\C{ records to be sorted by %
\\{gb\_linksort} }\1\6
\&amp;{long} \\{key};\C{ the nonnegative sort key (weight plus $2^{30}$) }\6
\&amp;{struct} \&amp;{node\_struct} ${}{*}\\{link}{}$;\C{ pointer to next record }\6
\&amp;{long} \\{kk};\C{ index of city in the original database }\6
\&amp;{long} \\{lat}${},{}$ \\{lon}${},{}$ \\{pop};\C{ latitude, longitude,
population }\6
\&amp;{char} \\{name}[\T{30}];\C{ \.{"City\ Name,\ ST"} }\2\6
${}\}{}$ \&amp;{node};\par
\U5.\fi

\M{10}The constants defined here are taken from the specific data in %
\.{miles.dat},
because this routine is not intended to be perfectly general.

\Y\B\4\X10:Private variables\X${}\E{}$\6
\&amp;{static} \&amp;{long} \\{min\_lat}${}\K\T{2672},{}$ \\{max\_lat}${}\K\T{5042},{}$
\\{min\_lon}${}\K\T{7180},{}$ \\{max\_lon}${}\K\T{12312},{}$ \\{min\_pop}${}\K%
\T{2521},{}$ \\{max\_pop}${}\K\T{875538}{}$;\C{ tight bounds on data entries }\6
\&amp;{static} \&amp;{node} ${}{*}\\{node\_block}{}$;\C{ array of nodes holding city
info }\6
\&amp;{static} \&amp;{long} ${}{*}\\{distance}{}$;\C{ array of distances }\par
\U5.\fi

\M{11}The data in \.{miles.dat} appears in 128 groups of lines, one for each
city, in reverse alphabetical order. These groups have the general form
$$\vcenter{\halign{\tt#\hfil\cr
City Name, ST[lat,lon]pop\cr
d1 d2 d3 d4 d5 d6 ... (possibly several lines' worth)\cr
}}$$
where \.{City Name} is the name of the city (possibly including spaces);
\.{ST} is the two-letter state code; \.{lat} and \.{lon} are latitude
and longitude in hundredths of degrees; \.{pop} is the population; and
the remaining numbers \.{d1}, \.{d2}, \dots\ are distances to the
previously named cities in reverse order. Each distance is separated
from the previous item by either a blank space or a newline character.
For example, the line
$$\hbox{\tt San Francisco, CA[3778,12242]678974}$$
specifies the data about San Francisco that was mentioned earlier.
From the first few groups
$$\vcenter{\halign{\tt#\hfil\cr
Youngstown, OH[4110,8065]115436\cr
Yankton, SD[4288,9739]12011\cr
966\cr
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.

\Y\B\4\X11:Read the data file \.{miles.dat} and compute city weights\X${}\E{}$\6
$\\{node\_block}\K\\{gb\_typed\_alloc}(\.{MAX\_N},\39\&amp;{node},\39\\{new\_graph}%
\MG\\{aux\_data});{}$\6
${}\\{distance}\K\\{gb\_typed\_alloc}(\.{MAX\_N}*\.{MAX\_N},\39\&amp;{long},\39%
\\{new\_graph}\MG\\{aux\_data});{}$\6
\&amp;{if} (\\{gb\_trouble\_code})\5
${}\{{}$\1\6
${}\\{gb\_free}(\\{new\_graph}\MG\\{aux\_data});{}$\6
${}\\{panic}(\\{no\_room}+\T{1}){}$;\C{ no room to copy the data }\6
\4${}\}{}$\2\6
\&amp;{if} ${}(\\{gb\_open}(\.{"miles.dat"})\I\T{0}){}$\1\5
\\{panic}(\\{early\_data\_fault});\C{ couldn't open \.{"miles.dat"} using
GraphBase conventions;                  \\{io\_errors} tells why }\2\6
\&amp;{for} ${}(\|k\K\.{MAX\_N}-\T{1};{}$ ${}\|k\G\T{0};{}$ ${}\|k\MM){}$\1\5
\X12:Read and store data for city \|k\X;\2\6
\&amp;{if} ${}(\\{gb\_close}(\,)\I\T{0}){}$\1\5
\\{panic}(\\{late\_data\_fault});\C{ something's wrong with \.{"miles.dat"};
see \\{io\_errors} }\2\par
\U5.\fi

\M{12}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}$.

\Y\B\4\X12:Read and store data for city \|k\X${}\E{}$\6
${}\{{}$\5
\1\&amp;{register} \&amp;{node} ${}{*}\|p;{}$\7
${}\|p\K\\{node\_block}+\|k;{}$\6
${}\|p\MG\\{kk}\K\|k;{}$\6
\&amp;{if} (\|k)\1\5
${}\|p\MG\\{link}\K\|p-\T{1};{}$\2\6
${}\\{gb\_string}(\|p\MG\\{name},\39\.{'['});{}$\6
\&amp;{if} ${}(\\{gb\_char}(\,)\I\.{'['}){}$\1\5
\\{panic}(\\{syntax\_error});\C{ out of sync in \.{miles.dat} }\2\6
${}\|p\MG\\{lat}\K\\{gb\_number}(\T{10});{}$\6
\&amp;{if} ${}(\|p\MG\\{lat}&lt;\\{min\_lat}\V\|p\MG\\{lat}&gt;\\{max\_lat}\V\\{gb%
\_char}(\,)\I\.{','}){}$\1\5
${}\\{panic}(\\{syntax\_error}+\T{1}){}$;\C{ latitude data was clobbered }\2\6
${}\|p\MG\\{lon}\K\\{gb\_number}(\T{10});{}$\6
\&amp;{if} ${}(\|p\MG\\{lon}&lt;\\{min\_lon}\V\|p\MG\\{lon}&gt;\\{max\_lon}\V\\{gb%
\_char}(\,)\I\.{']'}){}$\1\5
${}\\{panic}(\\{syntax\_error}+\T{2}){}$;\C{ longitude data was clobbered }\2\6
${}\|p\MG\\{pop}\K\\{gb\_number}(\T{10});{}$\6
\&amp;{if} ${}(\|p\MG\\{pop}&lt;\\{min\_pop}\V\|p\MG\\{pop}&gt;\\{max\_pop}){}$\1\5
${}\\{panic}(\\{syntax\_error}+\T{3}){}$;\C{ population data was clobbered }\2\6
${}\|p\MG\\{key}\K\\{north\_weight}*(\|p\MG\\{lat}-\\{min\_lat})+\\{west%
\_weight}*(\|p\MG\\{lon}-\\{min\_lon})+\\{pop\_weight}*(\|p\MG\\{pop}-\\{min%
\_pop})+\T{\^40000000};{}$\6
\X13:Read the mileage data for city \|k\X;\6
\\{gb\_newline}(\,);\6
\4${}\}{}$\2\par
\U11.\fi

\M{13}\B\D$\|d(\|j,\|k)$ \5
${*}(\\{distance}+(\.{MAX\_N}*\|j+\|k){}$)\par
\Y\B\4\X13:Read the mileage data for city \|k\X${}\E{}$\6
${}\{{}$\1\6
\&amp;{for} ${}(\|j\K\|k+\T{1};{}$ ${}\|j&lt;\.{MAX\_N};{}$ ${}\|j\PP){}$\5
${}\{{}$\1\6
\&amp;{if} ${}(\\{gb\_char}(\,)\I\.{'\ '}){}$\1\5
\\{gb\_newline}(\,);\2\6
${}\|d(\|j,\39\|k)\K\|d(\|k,\39\|j)\K\\{gb\_number}(\T{10});{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U12.\fi

\M{14}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.

\Y\B\4\X14:Determine the \|n cities to use in the graph\X${}\E{}$\6
${}\{{}$\5
\1\&amp;{register} \&amp;{node} ${}{*}\|p{}$;\C{ the current node being considered }\6
\&amp;{register} \&amp;{Vertex} ${}{*}\|v\K\\{new\_graph}\MG\\{vertices}{}$;\C{ the
first unfilled vertex }\7
${}\\{gb\_linksort}(\\{node\_block}+\.{MAX\_N}-\T{1});{}$\6
\&amp;{for} ${}(\|j\K\T{127};{}$ ${}\|j\G\T{0};{}$ ${}\|j\MM){}$\1\6
\&amp;{for} ${}(\|p\K{}$(\&amp;{node} ${}{*}){}$ \\{gb\_sorted}[\|j]; \|p; ${}\|p\K\|p%
\MG\\{link}){}$\5
${}\{{}$\1\6
\&amp;{if} ${}(\|v&lt;\\{new\_graph}\MG\\{vertices}+\|n){}$\1\5
\X15:Add city $\|p\MG\\{kk}$ to the graph\X\2\6
\&amp;{else}\1\5
${}\|p\MG\\{pop}\K\T{0}{}$;\C{ this city is not being used }\2\6
\4${}\}{}$\2\2\6
\4${}\}{}$\2\par
\U5.\fi

\M{15}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.

\Y\B\4\D$\\{x\_coord}$ \5
$\|x.{}$\|I\par
\B\4\D$\\{y\_coord}$ \5
$\|y.{}$\|I\par
\B\4\D$\\{index\_no}$ \5
$\|z.{}$\|I\par
\B\4\D$\\{people}$ \5
$\|w.{}$\|I\par
\Y\B\4\X15:Add city $\|p\MG\\{kk}$ to the graph\X${}\E{}$\6
${}\{{}$\1\6
${}\|v\MG\\{x\_coord}\K\\{max\_lon}-\|p\MG\\{lon}{}$;\C{ \|x coordinate is
complement of longitude }\6
${}\|v\MG\\{y\_coord}\K\|p\MG\\{lat}-\\{min\_lat};{}$\6
${}\|v\MG\\{y\_coord}\MRL{+{\K}}(\|v\MG\\{y\_coord})\GG\T{1}{}$;\C{ \|y
coordinate is 1.5 times latitude }\6
${}\|v\MG\\{index\_no}\K\|p\MG\\{kk};{}$\6
${}\|v\MG\\{people}\K\|p\MG\\{pop};{}$\6
${}\|v\MG\\{name}\K\\{gb\_save\_string}(\|p\MG\\{name});{}$\6
${}\|v\PP;{}$\6
\4${}\}{}$\2\par
\U14.\fi

\M{16}\B\X1:\.{gb\_miles.h }\X${}\mathrel+\E{}$\6
\8\#\&amp;{define} ${}\\{x\_coord}\hbox{\quad}\|x.\|I{}$\C{ utility field
definitions for the header file }\6
\8\#\&amp;{define} ${}\\{y\_coord}\hbox{\quad}\|y.\|I{}$\6
\8\#\&amp;{define} ${}\\{index\_no}\hbox{\quad}\|z.\|I{}$\6
\8\#\&amp;{define} ${}\\{people}\hbox{\quad}\|w.\|I{}$\par
\fi

\N{1}{17}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.

\Y\B\4\X17:Put the appropriate edges into the graph\X${}\E{}$\6
\&amp;{if} ${}(\\{max\_distance}&gt;\T{0}\V\\{max\_degree}&gt;\T{0}){}$\1\5
\X18:Prune unwanted edges by negating their distances\X;\2\6
${}\{{}$\5
\1\&amp;{register} \&amp;{Vertex} ${}{*}\|u,{}$ ${}{*}\|v;{}$\7
\&amp;{for} ${}(\|u\K\\{new\_graph}\MG\\{vertices};{}$ ${}\|u&lt;\\{new\_graph}\MG%
\\{vertices}+\|n;{}$ ${}\|u\PP){}$\5
${}\{{}$\1\6
${}\|j\K\|u\MG\\{index\_no};{}$\6
\&amp;{for} ${}(\|v\K\|u+\T{1};{}$ ${}\|v&lt;\\{new\_graph}\MG\\{vertices}+\|n;{}$ ${}%
\|v\PP){}$\5
${}\{{}$\1\6
${}\|k\K\|v\MG\\{index\_no};{}$\6
\&amp;{if} ${}(\|d(\|j,\39\|k)&gt;\T{0}\W\|d(\|k,\39\|j)&gt;\T{0}){}$\1\5
${}\\{gb\_new\_edge}(\|u,\39\|v,\39\|d(\|j,\39\|k));{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U5.\fi

\M{18}\B\X18:Prune unwanted edges by negating their distances\X${}\E{}$\6
${}\{{}$\5
\1\&amp;{register} \&amp;{node} ${}{*}\|p;{}$\7
\&amp;{if} ${}(\\{max\_degree}\E\T{0}){}$\1\5
${}\\{max\_degree}\K\.{MAX\_N};{}$\2\6
\&amp;{if} ${}(\\{max\_distance}\E\T{0}){}$\1\5
${}\\{max\_distance}\K\T{30000};{}$\2\6
\&amp;{for} ${}(\|p\K\\{node\_block};{}$ ${}\|p&lt;\\{node\_block}+\.{MAX\_N};{}$ ${}%
\|p\PP){}$\1\6
\&amp;{if} ${}(\|p\MG\\{pop}){}$\5
${}\{{}$\C{ this city not deleted }\1\6
${}\|k\K\|p\MG\\{kk};{}$\6
\X19:Blank out all undesired edges from city \|k\X;\6
\4${}\}{}$\2\2\6
\4${}\}{}$\2\par
\U17.\fi

\M{19}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?

\Y\B\4\X19:Blank out all undesired edges from city \|k\X${}\E{}$\6
${}\{{}$\5
\1\&amp;{register} \&amp;{node} ${}{*}\|q;{}$\6
\&amp;{register} \&amp;{node} ${}{*}\|s\K\NULL{}$;\C{ list of nodes containing edges
from city \|k }\7
\&amp;{for} ${}(\|q\K\\{node\_block};{}$ ${}\|q&lt;\\{node\_block}+\.{MAX\_N};{}$ ${}%
\|q\PP){}$\1\6
\&amp;{if} ${}(\|q\MG\\{pop}\W\|q\I\|p){}$\5
${}\{{}$\C{ another city not deleted }\1\6
${}\|j\K\|d(\|k,\39\|q\MG\\{kk}){}$;\C{ distance from \|p to \|q }\6
\&amp;{if} ${}(\|j&gt;\\{max\_distance}){}$\1\5
${}\|d(\|k,\39\|q\MG\\{kk})\K{-}\|j;{}$\2\6
\&amp;{else}\5
${}\{{}$\1\6
${}\|q\MG\\{key}\K\\{max\_distance}-\|j;{}$\6
${}\|q\MG\\{link}\K\|s;{}$\6
${}\|s\K\|q;{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\2\6
\\{gb\_linksort}(\|s);\C{ now all the surviving edges from \|p are in the list %
\\{gb\_sorted}[\T{0}] }\6
${}\|j\K\T{0}{}$;\C{ \|j counts how many edges have been accepted }\6
\&amp;{for} ${}(\|q\K{}$(\&amp;{node} ${}{*}){}$ \\{gb\_sorted}[\T{0}]; \|q; ${}\|q\K%
\|q\MG\\{link}){}$\1\6
\&amp;{if} ${}(\PP\|j&gt;\\{max\_degree}){}$\1\5
${}\|d(\|k,\39\|q\MG\\{kk})\K{-}\|d(\|k,\39\|q\MG\\{kk});{}$\2\2\6
\4${}\}{}$\2\par
\U18.\fi

\M{20}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)&lt;\T{0}$ when $\\{miles%
\_distance}(\|v,\|u)&gt;\T{0}$,
if the distance in question was suppressed by the \\{max\_degree} constraint
on~\|u but not on~\|v.

\Y\B\&amp;{long} ${}\\{miles\_distance}(\|u,\39\|v){}$\1\1\6
\&amp;{Vertex} ${}{*}\|u,{}$ ${}{*}\|v;\2\2{}$\6
${}\{{}$\1\6
\&amp;{return} \|d${}(\|u\MG\\{index\_no},\39\|v\MG\\{index\_no});{}$\6
\4${}\}{}$\2\par
\fi

\M{21}\B\X1:\.{gb\_miles.h }\X${}\mathrel+\E{}$\6
\&amp;{extern} \&amp;{long} \\{miles\_distance}(\,);\par
\fi

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


\inx
\fin
\con
</pre></body></html>