\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\_\,GRAPH}


\N{1}{1}Introduction. This is {\sc GB\_\,GRAPH}, the data-structure module
used by all GraphBase routines to allocate memory. The basic data
types for graph representation are also defined~here.

Many examples of how to use these conventions appear in other GraphBase
modules. The best introduction to such examples can probably be found
in {\sc GB\_\,BASIC}, which contains subroutines for generating and
transforming various classical graphs.

\fi

\M{2}The code below is believed to be system-independent; it should
produce equivalent results on all systems, assuming that the standard
\\{calloc} and \\{free} functions of \CEE/ are available.

However, a test program helps build confidence that everything does in fact
work as it should. To make such a test, simply compile and run \.{test\_graph}.
This particular test is fairly rudimentary, but it should be passed before
more elaborate routines are tested.

\Y\B\4\X2:\.{test\_graph.c }\X${}\E{}$\6
\8\#\&{include} \.{"gb\_graph.h"}\C{ all users of {\sc GB\_\,GRAPH} should do
this }\6
\X19:Declarations of test variables\X\7
\&{int} \\{main}(\,)\1\1\2\2\6
${}\{{}$\1\6
\X36:Create a small graph\X;\6
\X18:Test some intentional errors\X;\6
\X38:Check that the small graph is still there\X;\6
\\{printf}(\.{"OK,\ the\ gb\_graph\ ro}\)\.{utines\ seem\ to\ work!}\)\.{%
\\n"});\6
\&{return} \T{0};\6
\4${}\}{}$\2\par
\fi

\M{3}The \CEE/ code for {\sc GB\_\,GRAPH} doesn't have a main routine;
it's just a bunch of subroutines waiting to be incorporated into
programs at a higher level via the system loading routine. Here is
the general outline of \.{gb\_graph.c}:

\Y\B\8\#\&{ifdef} \.{SYSV}\6
\8\#\&{include} \.{<string.h>}\6
\8\#\&{else}\6
\8\#\&{include} \.{<strings.h>}\6
\8\#\&{endif}\6
\8\#\&{include} \.{<stdio.h>}\6
\8\#\&{include} \.{<stdlib.h>}\6
\ATH\7
\X8:Type declarations\X\6
\X28:Private declarations\X\6
\X5:External declarations\X\6
\X13:External functions\X\par
\fi

\M{4}The type declarations of {\sc GB\_\,GRAPH} appear also in the header file
\.{gb\_graph.h}. For convenience, that header file also incorporates the
standard system headers for input/output and string manipulation.

Some system header files define an unsafe macro called \\{min}, which will
interfere with GraphBase use of a useful identifier. We scotch that.

\Y\B\4\X4:\.{gb\_graph.h }\X${}\E{}$\6
\8\#\&{include} \.{<stdio.h>}\6
\8\#\&{include} \.{<stdlib.h>}\6
\8\#\&{ifdef} \.{SYSV}\6
\8\#\&{include} \.{<string.h>}\6
\8\#\&{else}\6
\8\#\&{include} \.{<strings.h>}\6
\8\#\&{endif}\6
\8\#\&{undef} \\{min}\6
\X8:Type declarations\X\par
\As6, 7, 15, 17, 22, 25, 33, 41\ETs42.\fi

\M{5}GraphBase programs often have a ``verbose'' option, which needs to
be enabled by the setting of an external variable. They also tend to have
a variable called \\{panic\_code}, which helps identify unusual errors.
We might as well declare those variables here.

\Y\B\4\X5:External declarations\X${}\E{}$\6
\&{long} \\{verbose}${}\K\T{0}{}$;\C{ nonzero if ``verbose'' output is desired
}\6
\&{long} \\{panic\_code}${}\K\T{0}{}$;\C{ set nonzero if graph generator
returns null pointer }\par
\As14, 24\ETs32.
\U3.\fi

\M{6}Every external variable should be declared twice in this \.{CWEB}
file: once for {\sc GB\_\,GRAPH} itself (the ``real'' declaration for
storage allocation purposes) and once in \.{gb\_graph.h} (for
cross-references by {\sc GB\_\,GRAPH} users).

\Y\B\4\X4:\.{gb\_graph.h }\X${}\mathrel+\E{}$\6
\&{extern} \&{long} \\{verbose};\C{ nonzero if ``verbose'' output is desired }\6
\&{extern} \&{long} \\{panic\_code};\C{ set nonzero if graph generator panics }%
\par
\fi

\M{7}When \\{panic\_code} is assigned a nonzero value, one of the symbolic
names defined here is used to help pinpoint the problem.
Small values indicate memory limitations; values in the 10s and 20s
indicate input/output anomalies; values in the 30s and 40s indicate
errors in the parameters to a subroutine. Some panic codes
stand for cases the author doesn't think will ever arise, although
the program checks for them just to be extra safe. Multiple instances
of the same type of error within a single subroutine are distinguished
by adding an integer; for example, `$\\{syntax\_error}+\T{1}$' and `$\\{syntax%
\_error}+\T{2}$'
identify two different kinds of syntax error, as an aid in trouble-shooting.
The \\{early\_data\_fault} and \\{late\_data\_fault} codes are explained
further
by the value of \\{io\_errors}.

\Y\B\4\X4:\.{gb\_graph.h }\X${}\mathrel+\E{}$\6
\8\#\&{define} \\{alloc\_fault} \5${}({-}\T{1}{}$)\C{ a previous memory request
failed }\6
\8\#\&{define} \\{no\_room} \5\T{1}\C{ the current memory request failed }\6
\8\#\&{define} \\{early\_data\_fault} \5\T{10}\C{ error detected at beginning
of \.{.dat} file }\6
\8\#\&{define} \\{late\_data\_fault} \5\T{11}\C{ error detected at end of %
\.{.dat} file }\6
\8\#\&{define} \\{syntax\_error} \5\T{20}\C{ error detected while reading %
\.{.dat} file }\6
\8\#\&{define} \\{bad\_specs} \5\T{30}\C{ parameter out of range or otherwise
disallowed }\6
\8\#\&{define} \\{very\_bad\_specs} \5\T{40}\C{ parameter far out of range or
otherwise stupid }\6
\8\#\&{define} \\{missing\_operand} \5\T{50}\C{ graph parameter is $\NULL$ }\6
\8\#\&{define} \\{invalid\_operand} \5\T{60}\C{ graph parameter doesn't obey
assumptions }\6
\8\#\&{define} \\{impossible} \5\T{90}\C{ ``this can't happen'' }\par
\fi

\N{1}{8}Representation of graphs. The GraphBase programs employ a simple
and flexible set of data structures to represent and manipulate graphs
in computer memory.  Vertices appear in a sequential array of
\&{Vertex} records, and the arcs emanating from each vertex appear in
a linked list of \&{Arc} records. There is also a \&{Graph} record, to
provide information about the graph as a whole.

The structure layouts for \&{Vertex}, \&{Arc}, and \&{Graph} records
include a number of utility fields that can be used for any purpose by
algorithms that manipulate the graphs. Each utility field is a union
type that can be either a pointer of various kinds or a (long) integer.

Let's begin the formal definition of these data structures by declaring the
union type \&{util}. The suffixes .\|V, .\|A, .\|G, and .\|S on the name
of a utility variable mean that the variable is a pointer to a vertex, arc,
graph, or string, respectively; the suffix .\|I means that the variable is
an integer. (We use one-character names because such names are easy to type
when debugging.)

\Y\B\4\X8:Type declarations\X${}\E{}$\6
\&{typedef} \&{union} ${}\{{}$\1\6
\&{struct} \\{vertex\_struct} ${}{*}\|V{}$;\C{ pointer to \&{Vertex} }\6
\&{struct} \\{arc\_struct} ${}{*}\|A{}$;\C{ pointer to \&{Arc} }\6
\&{struct} \\{graph\_struct} ${}{*}\|G{}$;\C{ pointer to \&{Graph} }\6
\&{char} ${}{*}\|S{}$;\C{ pointer to string }\6
\&{long} \|I;\C{ integer }\2\6
${}\}{}$ \&{util};\par
\As9, 10, 12, 20\ETs34.
\Us3\ET4.\fi

\M{9}Each \&{Vertex} has two standard fields and six utility fields; hence it
occupies 32 bytes on most systems, not counting the memory needed for
supplementary string data. The standard fields are
$$\vcenter{\halign{#,\ \ \hfil&#\hfil\cr
\\{arcs}&a pointer to an \&{Arc};\cr
\\{name}&a pointer to a string of characters.\cr}}$$
If \|v points to a \&{Vertex} and $\|v\MG\\{arcs}$ is $\NULL$, there are no
arcs
emanating from~\|v. But if $\|v\MG\\{arcs}$ is non-$\NULL$, it points to an %
\&{Arc}
record representing an arc from~\|v, and that record has a \\{next} field that
points in the same way to the representations of all other arcs from~\|v.

The utility fields are called \|u, \|v, \|w, \|x, \|y, \|z. Macros can
be used to give them syntactic sugar in particular applications. They are
typically used to record such things as the in-degree or out-degree, or
whether a vertex is `marked'. Utility fields might also link the vertex
to other vertices or arcs in one or more lists.

\Y\B\4\X8:Type declarations\X${}\mathrel+\E{}$\6
\&{typedef} \&{struct} \&{vertex\_struct} ${}\{{}$\1\6
\&{struct} \\{arc\_struct} ${}{*}\\{arcs}{}$;\C{ linked list of arcs coming out
of this vertex }\6
\&{char} ${}{*}\\{name}{}$;\C{ string identifying this vertex symbolically }\6
\&{util} \|u${},{}$ \|v${},{}$ \|w${},{}$ \|x${},{}$ \|y${},{}$ \|z;\C{
multipurpose fields }\2\6
${}\}{}$ \&{Vertex};\par
\fi

\M{10}Each \&{Arc} has three standard fields and two utility fields. Thus it
occupies 20~bytes on most computer systems. The standard fields are
$$\vcenter{\halign{#,\ \ \hfil&#\hfil\cr
\\{tip}&a pointer to a \&{Vertex};\cr
\\{next}&a pointer to an \&{Arc};\cr
\\{len}&a (long) integer.\cr}}$$
If \|a points to an \&{Arc} in the list of arcs from vertex~\|v, it represents
an arc of length $\|a\MG\\{len}$ from \|v to $\|a\MG\\{tip}$, and the next arc
from \|v
in the list is represented by $\|a\MG\\{next}$.

The utility fields are called \|a and \|b.

\Y\B\4\X8:Type declarations\X${}\mathrel+\E{}$\6
\&{typedef} \&{struct} \&{arc\_struct} ${}\{{}$\1\6
\&{struct} \&{vertex\_struct} ${}{*}\\{tip}{}$;\C{ the arc points to this
vertex }\6
\&{struct} \&{arc\_struct} ${}{*}\\{next}{}$;\C{ another arc pointing from the
same vertex }\6
\&{long} \\{len};\C{ length of this arc }\6
\&{util} \|a${},{}$ \|b;\C{ multipurpose fields }\2\6
${}\}{}$ \&{Arc};\par
\fi

\N{1}{11}Storage allocation. Memory space must be set aside dynamically for
vertices, arcs, and their attributes. The GraphBase routines provided by
{\sc GB\_\,GRAPH} accomplish this task with reasonable ease and efficiency
by using the concept of memory ``areas.'' The user should first declare an
\&{Area} variable by saying, for example,
$$\hbox{\&{Area} \|s;}$$
and if this variable isn't static or otherwise known to be zero, it must be
cleared initially by saying `\\{init\_area}(\|s)'. Then any number of
subroutine
calls of the form  `$\\{gb\_alloc}(\|n,\|s)$' can be given; \\{gb\_alloc}
will return a pointer to a block of \|n consecutive bytes, all cleared to zero.
Finally, the user can issue the command
$$\hbox{\\{gb\_free}(\|s);}$$
this statement will return all memory blocks currently allocated to area~\|s,
making them available for future allocation.

The number of bytes \|n specified to \\{gb\_alloc} must be positive, and
it should usually be 1000 or more, since this will reduce the number
of system calls. Other routines are provided below to allocate smaller
amounts of memory, such as the space needed for a single new \&{Arc}.

If no memory of the requested size is presently available, \\{gb\_alloc}
returns the null pointer $\NULL$. In such cases \\{gb\_alloc} also sets
the external variable \\{gb\_trouble\_code} to a nonzero value. The user
can therefore discover whether any one of an arbitrarily long series
of allocation requests has failed by making a single test, `\&{if} (\\{gb%
\_trouble\_code})'. The value of \\{gb\_trouble\_code} should be cleared to
zero
by every graph generation subroutine; therefore it need not be
initialized to zero.

A special macro $\\{gb\_typed\_alloc}(\|n,\|t,\|s)$ makes it convenient to
allocate
the space for \|n items of type~\|t in area~\|s.

\Y\B\4\D$\\{gb\_typed\_alloc}(\|n,\|t,\|s)$ \5
$(\|t*)\\{gb\_alloc}((\&{long})((\|n)*\&{sizeof}(\|t)),\39\|s{}$)\par
\fi

\M{12}The implementation of this scheme is almost ridiculously easy. The
value of~\|n is increased by twice the number of bytes in a pointer,
and the resulting number is rounded upwards if necessary so that it's
a multiple of 256. Then memory is allocated using \\{calloc}.  The extra
bytes will contain two pointers, one to the beginning of the block and
one to the next block associated with the same area variable.

The \&{Area} type is defined to be an array of length 1. This makes it possible
for users to say just `\|s' instead of `${\AND}\|s$' when using an area
variable as a parameter.

\Y\B\4\X8:Type declarations\X${}\mathrel+\E{}$\6
\8\#\&{define} \\{init\_area}(\|s) \5${}\hbox{\quad}{*}\|s\K\NULL{}$\6
\&{struct} \&{area\_pointers} ${}\{{}$\1\6
\&{char} ${}{*}\\{first}{}$;\C{ address of the beginning of this block }\6
\&{struct} \&{area\_pointers} ${}{*}\\{next}{}$;\C{ address of area pointers in
the previously         allocated block }\2\6
${}\};{}$\6
\&{typedef} \&{struct} \&{area\_pointers} ${}{*}\&{Area}[\T{1}]{}$;\par
\fi

\M{13}First we round \|n up, if necessary, so that it's a multiple of the
size of a pointer variable. Then we know we can put \&{area\_pointers} into
memory at a position \|n after any address returned by \\{calloc}. (This
logic should work whenever the number of bytes in a pointer variable
is a divisor of~256.)

The upper limit on \|n here is governed by old \CEE/ conventions in
which the first parameter to \\{calloc} must be less than~$2^{16}$.
Users who need graphs with more than half a million vertices might
want to raise this limit on their systems, but they would probably
be better off representing large graphs in a more compact way.

{\sl Important Note:\/}
Programs of the Stanford GraphBase implicitly assume that all
memory allocated by \\{calloc} comes from a single underlying memory array.
Pointer values are compared to each other in many places, even when
the objects pointed to have been allocated at different times. Strictly
speaking, this liberal use of pointer comparisons fails to conform to
the restrictions of ANSI Standard \CEE/, if the comparison involves
a less-than or greater-than relation. Users whose system supports only
the strict standard will need to make several dozen changes.

\Y\B\4\X13:External functions\X${}\E{}$\6
\&{char} ${}{*}\\{gb\_alloc}(\|n,\39\|s){}$\1\1\6
\&{long} \|n;\C{ number of consecutive bytes desired }\6
\&{Area} \|s;\C{ storage area that will contain the new block }\2\2\6
${}\{{}$\5
\1\&{long} \|m${}\K{}$\&{sizeof}(\&{char} ${}{*}){}$;\C{ \|m is the size of a
pointer variable }\6
\&{Area} \|t;\C{ a temporary pointer }\6
\&{char} ${}{*}\\{loc}{}$;\C{ the block address }\7
\&{if} ${}(\|n\Z\T{0}\V\|n>\T{\^ffff00}-\T{2}*\|m){}$\5
${}\{{}$\1\6
${}\\{gb\_trouble\_code}\MRL{{\OR}{\K}}\T{2}{}$;\C{ illegal request }\6
\&{return} ${}\NULL;{}$\6
\4${}\}{}$\2\6
${}\|n\K((\|n+\|m-\T{1})/\|m)*\|m{}$;\C{ round up to multiple of \|m }\6
${}\\{loc}\K{}$(\&{char} ${}{*}){}$ \\{calloc}${}((\&{unsigned})((\|n+\T{2}*%
\|m+\T{255})/\T{256}),\39\T{256});{}$\6
\&{if} (\\{loc})\5
${}\{{}$\1\6
${}{*}\|t\K{}$(\&{struct} \&{area\_pointers} ${}{*})(\\{loc}+\|n);{}$\6
${}({*}\|t)\MG\\{first}\K\\{loc};{}$\6
${}({*}\|t)\MG\\{next}\K{*}\|s;{}$\6
${}{*}\|s\K{*}\|t;{}$\6
\4${}\}{}$\5
\2\&{else}\1\5
${}\\{gb\_trouble\_code}\MRL{{\OR}{\K}}\T{1};{}$\2\6
\&{return} \\{loc};\6
\4${}\}{}$\2\par
\As16, 23, 26, 27, 29, 30, 31, 35, 39, 40, 44, 46, 47\ETs48.
\U3.\fi

\M{14}\B\X5:External declarations\X${}\mathrel+\E{}$\6
\&{long} \\{gb\_trouble\_code}${}\K\T{0}{}$;\C{ did \\{gb\_alloc} return $%
\NULL$? }\par
\fi

\M{15}\B\X4:\.{gb\_graph.h }\X${}\mathrel+\E{}$\6
\&{extern} \&{long} \\{gb\_trouble\_code};\C{ anomalies noted by \\{gb\_alloc}
}\par
\fi

\M{16}Notice that \\{gb\_free}(\|s) can be called twice in a row, because the
list
of blocks is cleared out of the area variable~\|s.

\Y\B\4\X13:External functions\X${}\mathrel+\E{}$\6
\&{void} \\{gb\_free}(\|s)\1\1\6
\&{Area} \|s;\2\2\6
${}\{{}$\5
\1\&{Area} \|t;\7
\&{while} ${}({*}\|s){}$\5
${}\{{}$\1\6
${}{*}\|t\K({*}\|s)\MG\\{next};{}$\6
${}\\{free}(({*}\|s)\MG\\{first});{}$\6
${}{*}\|s\K{*}\|t;{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\fi

\M{17}The two external procedures we've defined above should be mentioned in
the header file, so let's do that before we forget.

\Y\B\4\X4:\.{gb\_graph.h }\X${}\mathrel+\E{}$\6
\&{extern} \&{char} ${}{*}\\{gb\_alloc}(\,){}$;\C{ allocate another block for
an area }\6
\8\#\&{define} ${}\\{gb\_typed\_alloc}(\|n,\39\|t,\39\|s) \5\hbox{\quad}(\|t*)%
\\{gb\_alloc}((\&{long})((\|n)*\&{sizeof}(\|t)),\39\|s){}$\6
\&{extern} \&{void} \\{gb\_free}(\,);\C{ deallocate all blocks for an area }\par
\fi

\M{18}Here we try to allocate 10 million bytes of memory. If we succeed,
fine; if not, we verify that the error was properly reported.

(An early draft of this program attempted to allocate memory until all
space was exhausted. That tactic provided a more thorough test, but it
was a bad idea because it brought certain large systems to their
knees; it was terribly unfriendly to other users who were innocently
trying to do their own work on the same machine.)

\Y\B\4\X18:Test some intentional errors\X${}\E{}$\6
\&{if} ${}(\\{gb\_alloc}(\T{0\$L},\39\|s)\I\NULL\V\\{gb\_trouble\_code}\I%
\T{2}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Allocation\ error\ 2\ }\)\.{wasn't\ reported\
prop}\)\.{erly!\\n"}){}$;\5
\&{return} ${}{-}\T{2};{}$\6
\4${}\}{}$\2\6
\&{for} ( ; ${}\|g\MG\\{vv}.\|I<\T{100};{}$ ${}\|g\MG\\{vv}.\|I\PP{}$)\5
\1\&{if} ${}(\\{gb\_alloc}(\T{100000\$L},\39\|s)){}$\5
${}\{{}$\1\6
${}\|g\MG\\{uu}.\|I\PP;{}$\6
\\{printf}(\.{"."});\6
\\{fflush}(\\{stdout});\6
\4${}\}{}$\2\2\6
\&{if} ${}(\|g\MG\\{uu}.\|I<\T{100}\W\\{gb\_trouble\_code}\I\T{3}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Allocation\ error\ 1\ }\)\.{wasn't\ reported\
prop}\)\.{erly!\\n"}){}$;\5
\&{return} ${}{-}\T{1};{}$\6
\4${}\}{}$\2\6
\&{if} ${}(\|g\MG\\{uu}.\|I\E\T{0}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"I\ couldn't\ allocate}\)\.{\ any\ memory!%
\\n"}){}$;\5
\&{return} ${}{-}\T{3};{}$\6
\4${}\}{}$\2\6
\\{gb\_free}(\|s);\C{ we've exhausted memory, let's put some back }\6
${}\\{printf}(\.{"Hey,\ I\ allocated\ \%l}\)\.{d00000\ bytes\ success}\)%
\.{fully.\ Terrific...\\n}\)\.{"},\39\|g\MG\\{uu}.\|I);{}$\6
${}\\{gb\_trouble\_code}\K\T{0}{}$;\par
\U2.\fi

\M{19}\B\X19:Declarations of test variables\X${}\E{}$\6
\&{Area} \|s;\C{ temporary allocations in the test routine }\par
\A37.
\U2.\fi

\N{1}{20}Growing a graph. Now we're ready to look at the \&{Graph} type. This
is
a data structure that can be passed to an algorithm that operates on
graphs---to find minimum spanning trees, or strong components, or whatever.

A \&{Graph} record has seven standard fields and six utility fields. The
standard fields are
$$\vcenter{\halign{#,\ \ \hfil&#\hfil\cr
\\{vertices}&a pointer to an array of \&{Vertex} records;\cr
\|n&the total number of vertices;\cr
\|m&the total number of arcs;\cr
\\{id}&a symbolic identification giving parameters of the GraphBase procedure%
\cr
\omit& that generated this graph;\cr
\\{util\_types}&a symbolic representation of the data types in utility fields;%
\cr
\\{data}&an \&{Area} used for \&{Arc} storage and string storage;\cr
\\{aux\_data}&an \&{Area} used for auxiliary information that some users might%
\cr
\omit     &want to discard.\cr}}$$
The utility fields are called \\{uu}, \\{vv}, \\{ww}, \\{xx}, \\{yy}, and %
\\{zz}.

As a consequence of these conventions, we can visit all arcs of a
graph~\|g by using the following program:
$$\vcenter{\halign{#\hfil\cr
\&{Vertex} ${}{*}\|v;$\cr
\&{Arc} ${}{*}\|a;$\cr
\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$
${}\|v\PP)$\cr
\quad\&{for} ${}(\|a\K\|v\MG\\{arcs};{}$ \|a; ${}\|a\K\|a\MG\\{next})$\cr
\qquad\\{visit}$(\|v,\|a)$;\cr}}$$

\Y\B\4\X8:Type declarations\X${}\mathrel+\E{}$\6
\8\#\&{define} \.{ID\_FIELD\_SIZE} \5\T{161}\6
\&{typedef} \&{struct} \&{graph\_struct} ${}\{{}$\1\6
\&{Vertex} ${}{*}\\{vertices}{}$;\C{ beginning of the vertex array }\6
\&{long} \|n;\C{ total number of vertices }\6
\&{long} \|m;\C{ total number of arcs }\6
\&{char} \\{id}[\.{ID\_FIELD\_SIZE}];\C{ GraphBase identification }\6
\&{char} \\{util\_types}[\T{15}];\C{ usage of utility fields }\6
\&{Area} \\{data};\C{ the main data blocks }\6
\&{Area} \\{aux\_data};\C{ subsidiary data blocks }\6
\&{util} \\{uu}${},{}$ \\{vv}${},{}$ \\{ww}${},{}$ \\{xx}${},{}$ \\{yy}${},{}$ %
\\{zz};\C{ multipurpose fields }\2\6
${}\}{}$ \&{Graph};\par
\fi

\M{21}The \\{util\_types} field should always hold a string of length 14,
followed
as usual by a null character to terminate that string. The first six
characters of \\{util\_types} specify the usage of utility fields \|u, \|v,
\|w, \|x, \|y, and~\|z in \&{Vertex} records; the next two characters give the
format of the utility fields in \&{Arc} records; the last six give the
format of the utility fields in \&{Graph} records.  Each character
should be either \.I (denoting a \&{long} integer),
\.S (denoting a pointer to a string),
\.V (denoting a pointer to a \&{Vertex}), \.A (denoting a pointer to an
\&{Arc}), \.G (denoting a pointer to a \&{Graph}), or \.Z (denoting an
unused field that remains zero). The default for \\{util\_types} is
\.{"ZZZZZZZZZZZZZZ"}, when none of the utility fields is being used.

For example, suppose that a bipartite graph \|g is using field $\|g\MG\\{uu}.%
\|I$
to specify the size of its first part. Suppose further that \|g has a
string in utility field \|a of each \&{Arc} and uses
utility field \|w of \&{Vertex} records to point to an \&{Arc}. If \|g
leaves all other utility fields untouched, its \\{util\_types} should be
\.{"ZZAZZZSZIZZZZZ"}.

The \\{util\_types} string is presently examined only by the \\{save\_graph}
and
\\{restore\_graph} routines, which convert GraphBase graphs from internal
data structures to symbolic external files and vice versa. Therefore
users need not update the \\{util\_types} when they write algorithms to
manipulate graphs, unless they are going to use \\{save\_graph} to output
a graph in symbolic form, or unless they are using some other
GraphBase-related software that might rely on the conventions of
\\{util\_types}.  (Such software is not part of the ``official'' Stanford
GraphBase, but it might conceivably exist some~day.)

\fi

\M{22}Some applications of bipartite graphs require all vertices of the first
part to appear at the beginning of the \\{vertices} array. In such cases,
utility field $\\{uu}.\|I$ is traditionally given the symbolic name \\{n\_1},
and
it is set equal to the size of that first part. The size of the other
part is then $\|g\MG\|n-\|g\MG\\{n\_1}$.

\Y\B\4\D$\\{n\_1}$ \5
$\\{uu}.{}$\|I\C{ utility field \\{uu} may denote size of bipartite first part
}\par
\Y\B\4\X4:\.{gb\_graph.h }\X${}\mathrel+\E{}$\6
\8\#\&{define} ${}\\{n\_1}\hbox{\quad}\\{uu}.\|I{}$\6
\8\#\&{define} ${}\\{mark\_bipartite}(\|g,\39\\{n1}) \5\|g\MG\\{n\_1}\K\\{n1},%
\39\|g\MG\\{util\_types}[\T{8}]\K\.{'I'}{}$\par
\fi

\M{23}A new graph is created by calling \\{gb\_new\_graph}(\|n), which returns
a
pointer to a \&{Graph} record for a graph with \|n vertices and no arcs.
This function also initializes several private variables that are used
by the \\{gb\_new\_arc}, \\{gb\_new\_edge}, \\{gb\_virgin\_arc}, and \\{gb%
\_save\_string}
procedures below.

We actually reserve space for $\|n+\\{extra\_n}$ vertices, although claiming
only~$n$,
because several graph manipulation algorithms like to add a special vertex
or two to the graphs they deal with.

\Y\B\4\X13:External functions\X${}\mathrel+\E{}$\6
\&{Graph} ${}{*}\\{gb\_new\_graph}(\|n){}$\1\1\6
\&{long} \|n;\C{ desired number of vertices }\2\2\6
${}\{{}$\1\6
${}\\{cur\_graph}\K{}$(\&{Graph} ${}{*}){}$ \\{calloc}${}(\T{1},\39\&{sizeof}(%
\&{Graph}));{}$\6
\&{if} (\\{cur\_graph})\5
${}\{{}$\1\6
${}\\{cur\_graph}\MG\\{vertices}\K\\{gb\_typed\_alloc}(\|n+\\{extra\_n},\39%
\&{Vertex},\39\\{cur\_graph}\MG\\{data});{}$\6
\&{if} ${}(\\{cur\_graph}\MG\\{vertices}){}$\5
${}\{{}$\1\6
\&{Vertex} ${}{*}\|p;{}$\7
${}\\{cur\_graph}\MG\|n\K\|n;{}$\6
\&{for} ${}(\|p\K\\{cur\_graph}\MG\\{vertices}+\|n+\\{extra\_n}-\T{1};{}$ ${}%
\|p\G\\{cur\_graph}\MG\\{vertices};{}$ ${}\|p\MM){}$\1\5
${}\|p\MG\\{name}\K\\{null\_string};{}$\2\6
${}\\{sprintf}(\\{cur\_graph}\MG\\{id},\39\.{"gb\_new\_graph(\%ld)"},\39%
\|n);{}$\6
${}\\{strcpy}(\\{cur\_graph}\MG\\{util\_types},\39\.{"ZZZZZZZZZZZZZZ"});{}$\6
\4${}\}{}$\5
\2\&{else}\5
${}\{{}$\1\6
\\{free}((\&{char} ${}{*}){}$ \\{cur\_graph});\6
${}\\{cur\_graph}\K\NULL;{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
${}\\{next\_arc}\K\\{bad\_arc}\K\NULL;{}$\6
${}\\{next\_string}\K\\{bad\_string}\K\NULL;{}$\6
${}\\{gb\_trouble\_code}\K\T{0};{}$\6
\&{return} \\{cur\_graph};\6
\4${}\}{}$\2\par
\fi

\M{24}The value of \\{extra\_n} is ordinarily~4, and it should probably always
be at
least~4.

\Y\B\4\X5:External declarations\X${}\mathrel+\E{}$\6
\&{long} \\{extra\_n}${}\K\T{4}{}$;\C{ the number of shadow vertices allocated
by \\{gb\_new\_graph} }\6
\&{char} \\{null\_string}[\T{1}];\C{ a null string constant }\par
\fi

\M{25}\B\X4:\.{gb\_graph.h }\X${}\mathrel+\E{}$\6
\&{extern} \&{long} \\{extra\_n};\C{ the number of shadow vertices allocated by
\\{gb\_new\_graph} }\6
\&{extern} \&{char} \\{null\_string}[\,];\C{ a null string constant }\6
\&{extern} \&{void} \\{make\_compound\_id}(\,);\C{ routine to set one \\{id}
field from another }\6
\&{extern} \&{void} \\{make\_double\_compound\_id}(\,);\C{ ditto, but from two
others }\par
\fi

\M{26}The \\{id} field of a graph is sometimes manufactured from the \\{id}
field
of another graph. The following routines do this without allowing the
string to get too long after repeated copying.

\Y\B\4\X13:External functions\X${}\mathrel+\E{}$\6
\&{void} ${}\\{make\_compound\_id}(\|g,\39\\{s1},\39\\{gg},\39\\{s2}{}$)\C{ $%
\\{sprintf}(\|g\MG\\{id},\.{"\%s\%s\%s"},\\{s1},\\{gg}\MG\\{id},\\{s2})$ }\1\1\6
\&{Graph} ${}{*}\|g{}$;\C{ graph whose \\{id} is to be set }\6
\&{char} ${}{*}\\{s1}{}$;\C{ string for the beginning of the new \\{id} }\6
\&{Graph} ${}{*}\\{gg}{}$;\C{ graph whose \\{id} is to be copied }\6
\&{char} ${}{*}\\{s2}{}$;\C{ string for the end of the new \\{id} }\2\2\6
${}\{{}$\5
\1\&{int} \\{avail}${}\K\.{ID\_FIELD\_SIZE}-\\{strlen}(\\{s1})-\\{strlen}(%
\\{s2});{}$\6
\&{char} \\{tmp}[\.{ID\_FIELD\_SIZE}];\7
${}\\{strcpy}(\\{tmp},\39\\{gg}\MG\\{id});{}$\6
\&{if} ${}(\\{strlen}(\\{tmp})<\\{avail}){}$\1\5
${}\\{sprintf}(\|g\MG\\{id},\39\.{"\%s\%s\%s"},\39\\{s1},\39\\{tmp},\39%
\\{s2});{}$\2\6
\&{else}\1\5
${}\\{sprintf}(\|g\MG\\{id},\39\.{"\%s\%.*s...)\%s"},\39\\{s1},\39\\{avail}-%
\T{5},\39\\{tmp},\39\\{s2});{}$\2\6
\4${}\}{}$\2\par
\fi

\M{27}\B\X13:External functions\X${}\mathrel+\E{}$\6
\&{void} ${}\\{make\_double\_compound\_id}(\|g,\39\\{s1},\39\\{gg},\39\\{s2},%
\39\\{ggg},\39\\{s3}{}$)\C{ $\\{sprintf}(\|g\MG\\{id},\.{"\%s\%s\%s\%s\%s"},%
\\{s1},\\{gg}\MG\\{id},\\{s2},\\{ggg}\MG\\{id},\\{s3})$ }\1\1\6
\&{Graph} ${}{*}\|g{}$;\C{ graph whose \\{id} is to be set }\6
\&{char} ${}{*}\\{s1}{}$;\C{ string for the beginning of the new \\{id} }\6
\&{Graph} ${}{*}\\{gg}{}$;\C{ first graph whose \\{id} is to be copied }\6
\&{char} ${}{*}\\{s2}{}$;\C{ string for the middle of the new \\{id} }\6
\&{Graph} ${}{*}\\{ggg}{}$;\C{ second graph whose \\{id} is to be copied }\6
\&{char} ${}{*}\\{s3}{}$;\C{ string for the end of the new \\{id} }\2\2\6
${}\{{}$\5
\1\&{int} \\{avail}${}\K\.{ID\_FIELD\_SIZE}-\\{strlen}(\\{s1})-\\{strlen}(%
\\{s2})-\\{strlen}(\\{s3});{}$\7
\&{if} ${}(\\{strlen}(\\{gg}\MG\\{id})+\\{strlen}(\\{ggg}\MG\\{id})<%
\\{avail}){}$\1\5
${}\\{sprintf}(\|g\MG\\{id},\39\.{"\%s\%s\%s\%s\%s"},\39\\{s1},\39\\{gg}\MG%
\\{id},\39\\{s2},\39\\{ggg}\MG\\{id},\39\\{s3});{}$\2\6
\&{else}\1\5
${}\\{sprintf}(\|g\MG\\{id},\39\.{"\%s\%.*s...)\%s\%.*s...}\)\.{)\%s"},\39%
\\{s1},\39\\{avail}/\T{2}-\T{5},\39\\{gg}\MG\\{id},\39\\{s2},\39(\\{avail}-%
\T{9})/\T{2},\39\\{ggg}\MG\\{id},\39\\{s3});{}$\2\6
\4${}\}{}$\2\par
\fi

\M{28}But how do the arcs get there? That's where the private variables in
\\{gb\_new\_graph} come in. If \\{next\_arc} is unequal to \\{bad\_arc}, it
points to
an unused \&{Arc} record in a previously allocated block of \&{Arc} records.
Similarly, \\{next\_string} and \\{bad\_string} are addresses used to
place strings into a block of memory allocated for that purpose.

\Y\B\4\X28:Private declarations\X${}\E{}$\6
\&{static} \&{Arc} ${}{*}\\{next\_arc}{}$;\C{ the next \&{Arc} available for
allocation }\6
\&{static} \&{Arc} ${}{*}\\{bad\_arc}{}$;\C{ but if $\\{next\_arc}\K\\{bad%
\_arc}$, that \&{Arc} isn't there }\6
\&{static} \&{char} ${}{*}\\{next\_string}{}$;\C{ the next byte available for
storing a string }\6
\&{static} \&{char} ${}{*}\\{bad\_string}{}$;\C{ but if $\\{next\_string}\K%
\\{bad\_string}$, don't byte }\6
\&{static} \&{Arc} \\{dummy\_arc}[\T{2}];\C{ an \&{Arc} record to point to in
an emergency }\6
\&{static} \&{Graph} \\{dummy\_graph};\C{ a \&{Graph} record that's normally
unused }\6
\&{static} \&{Graph} ${}{*}\\{cur\_graph}\K{\AND}\\{dummy\_graph}{}$;\C{ the %
\&{Graph} most recently created }\par
\U3.\fi

\M{29}All new \&{Arc} records that are created by the automatic \\{next\_arc}/%
\\{bad\_arc}
scheme originate in a procedure called \\{gb\_virgin\_arc}, which returns the
address of a new record having type \&{Arc}.

When a new block of \&{Arc} records is needed, we create 102 of them at once.
This strategy causes exactly 2048 bytes to be allocated on most
computer systems---a nice round number. The routine will still work, however,
if 102 is replaced by any positive even number. The new block goes into
the \\{data} area of \\{cur\_graph}.

Graph-building programs do not usually call \\{gb\_virgin\_arc} directly;
they generally invoke one of the higher-level routines \\{gb\_new\_arc}
or \\{gb\_new\_edge} described below.

If memory space has been exhausted, \\{gb\_virgin\_arc} will return a
pointer to \\{dummy\_arc}, so that the calling procedure can safely
refer to fields of the result even though \\{gb\_trouble\_code} is nonzero.

\Y\B\4\D$\\{arcs\_per\_block}$ \5
\T{102}\par
\Y\B\4\X13:External functions\X${}\mathrel+\E{}$\6
\&{Arc} ${}{*}\\{gb\_virgin\_arc}(\,){}$\1\1\2\2\6
${}\{{}$\5
\1\&{register} \&{Arc} ${}{*}\\{cur\_arc}\K\\{next\_arc};{}$\7
\&{if} ${}(\\{cur\_arc}\E\\{bad\_arc}){}$\5
${}\{{}$\1\6
${}\\{cur\_arc}\K\\{gb\_typed\_alloc}(\\{arcs\_per\_block},\39\&{Arc},\39\\{cur%
\_graph}\MG\\{data});{}$\6
\&{if} ${}(\\{cur\_arc}\E\NULL){}$\1\5
${}\\{cur\_arc}\K\\{dummy\_arc};{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{next\_arc}\K\\{cur\_arc}+\T{1};{}$\6
${}\\{bad\_arc}\K\\{cur\_arc}+\\{arcs\_per\_block};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\\{next\_arc}\PP;{}$\2\6
\&{return} \\{cur\_arc};\6
\4${}\}{}$\2\par
\fi

\M{30}The routine $\\{gb\_new\_arc}(\|u,\|v,\\{len})$ creates a new arc of
length \\{len}
from vertex~\|u to vertex~\|v. The arc becomes part of the graph that
was most recently created by \\{gb\_new\_graph}---the graph
pointed to by the private variable \\{cur\_graph}. This routine assumes
that \|u and \|v are both vertices in \\{cur\_graph}.

The new arc will be pointed to by $\|u\MG\\{arcs}$, immediately after
$\\{gb\_new\_arc}(\|u,\|v,\\{len})$ has acted. If there is no room for the new
arc,
\\{gb\_trouble\_code} is set nonzero, but $\|u\MG\\{arcs}$ will point to the
non-$\NULL$
record \\{dummy\_arc}
so that additional information can safely be stored in its utility fields
without risking system crashes before \\{gb\_trouble\_code} is tested.
However, the linking structure of arcs is apt to be fouled up in such
cases; programs should make sure that $\\{gb\_trouble\_code}\E\T{0}$ before
doing any
extensive computation on a graph.

\Y\B\4\X13:External functions\X${}\mathrel+\E{}$\6
\&{void} ${}\\{gb\_new\_arc}(\|u,\39\|v,\39\\{len}){}$\1\1\6
\&{Vertex} ${}{*}\|u,{}$ ${}{*}\|v{}$;\C{ a newly created arc will go from \|u
to \|v }\6
\&{long} \\{len};\C{ its length }\2\2\6
${}\{{}$\5
\1\&{register} \&{Arc} ${}{*}\\{cur\_arc}\K\\{gb\_virgin\_arc}(\,);{}$\7
${}\\{cur\_arc}\MG\\{tip}\K\|v{}$;\5
${}\\{cur\_arc}\MG\\{next}\K\|u\MG\\{arcs}{}$;\5
${}\\{cur\_arc}\MG\\{len}\K\\{len};{}$\6
${}\|u\MG\\{arcs}\K\\{cur\_arc};{}$\6
${}\\{cur\_graph}\MG\|m\PP;{}$\6
\4${}\}{}$\2\par
\fi

\M{31}An undirected graph has ``edges'' instead of arcs. We represent an edge
by two arcs, one going each way.

The fact that \\{arcs\_per\_block} is even means that the \\{gb\_new\_edge}
routine needs to call \\{gb\_virgin\_arc} only once instead of twice.

Caveats: This routine, like \\{gb\_new\_arc}, should be used only after
\\{gb\_new\_graph} has caused the private variable \\{cur\_graph} to point to
the graph containing the new edge. The routine \\{gb\_new\_edge} must
not be used together with \\{gb\_new\_arc} or \\{gb\_virgin\_arc} when
building a graph, unless \\{gb\_new\_arc} and \\{gb\_virgin\_arc} have been
called an even number of times before \\{gb\_new\_edge} is invoked.

The new edge will be pointed to by $\|u\MG\\{arcs}$ and by $\|v\MG\\{arcs}$
immediately
after \\{gb\_new\_edge} has created it, assuming that $\|u\I\|v$. The two arcs
appear next to each other in memory; indeed, \\{gb\_new\_edge} rigs things so
that $\|v\MG\\{arcs}$ is $\|u\MG\\{arcs}+\T{1}$ when $\|u<\|v$.

On many computers it turns out that the first \&{Arc} record of every such
pair of arcs will have an address that is a multiple of~8, and the
second \&{Arc} record will have an address that is not a multiple of~8 (because
the first \&{Arc} will be 20 bytes long, and because \\{calloc} always returns
a multiple of~8). However, it is not safe to assume this when writing
portable code. Algorithms for undirected graphs can still make good use of
the fact that arcs for edges are paired, without needing any mod~8 assumptions,
if all edges have been created and linked into the graph by \\{gb\_new\_edge}:
The inverse of an arc~\|a from \|u to~\|v will be arc $\|a+\T{1}$ if and only
if
$\|u<\|v$ or $\|a\MG\\{next}\K\|a+\T{1}$; it will be arc $\|a-\T{1}$ if and
only if $\|u\G\|v$ and
$\|a\MG\\{next}\I\|a+\T{1}$. The condition $\|a\MG\\{next}\K\|a+\T{1}$ can hold
only if $\|u\K\|v$.

\Y\B\4\D$\\{gb\_new\_graph}$ \5
\\{gb\_nugraph}\C{ abbreviations for Procrustean linkers }\par
\B\4\D$\\{gb\_new\_arc}$ \5
\\{gb\_nuarc}\par
\B\4\D$\\{gb\_new\_edge}$ \5
\\{gb\_nuedge}\par
\Y\B\4\X13:External functions\X${}\mathrel+\E{}$\6
\&{void} ${}\\{gb\_new\_edge}(\|u,\39\|v,\39\\{len}){}$\1\1\6
\&{Vertex} ${}{*}\|u,{}$ ${}{*}\|v{}$;\C{ new arcs will go from \|u to \|v and
from \|v to \|u }\6
\&{long} \\{len};\C{ their length }\2\2\6
${}\{{}$\5
\1\&{register} \&{Arc} ${}{*}\\{cur\_arc}\K\\{gb\_virgin\_arc}(\,);{}$\7
\&{if} ${}(\\{cur\_arc}\I\\{dummy\_arc}){}$\1\5
${}\\{next\_arc}\PP;{}$\2\6
\&{if} ${}(\|u<\|v){}$\5
${}\{{}$\1\6
${}\\{cur\_arc}\MG\\{tip}\K\|v{}$;\5
${}\\{cur\_arc}\MG\\{next}\K\|u\MG\\{arcs};{}$\6
${}(\\{cur\_arc}+\T{1})\MG\\{tip}\K\|u{}$;\5
${}(\\{cur\_arc}+\T{1})\MG\\{next}\K\|v\MG\\{arcs};{}$\6
${}\|u\MG\\{arcs}\K\\{cur\_arc};{}$\6
${}\|v\MG\\{arcs}\K\\{cur\_arc}+\T{1};{}$\6
\4${}\}{}$\5
\2\&{else}\5
${}\{{}$\1\6
${}(\\{cur\_arc}+\T{1})\MG\\{tip}\K\|v{}$;\5
${}(\\{cur\_arc}+\T{1})\MG\\{next}\K\|u\MG\\{arcs};{}$\6
${}\|u\MG\\{arcs}\K\\{cur\_arc}+\T{1}{}$;\C{ do this now in case $\|u\E\|v$ }\6
${}\\{cur\_arc}\MG\\{tip}\K\|u{}$;\5
${}\\{cur\_arc}\MG\\{next}\K\|v\MG\\{arcs};{}$\6
${}\|v\MG\\{arcs}\K\\{cur\_arc};{}$\6
\4${}\}{}$\2\6
${}\\{cur\_arc}\MG\\{len}\K(\\{cur\_arc}+\T{1})\MG\\{len}\K\\{len};{}$\6
${}\\{cur\_graph}\MG\|m\MRL{+{\K}}\T{2};{}$\6
\4${}\}{}$\2\par
\fi

\M{32}Sometimes (let us hope rarely) we might need to use a dirty trick
hinted at in the previous discussion. On most computers, the mate to
arc~\|a will be $\|a-\T{1}$ if and only if $\\{edge\_trick}\AND{}$(\&{siz\_t}) %
\|a
is nonzero.

\Y\B\4\X5:External declarations\X${}\mathrel+\E{}$\6
\&{siz\_t} \\{edge\_trick}${}\K\&{sizeof}(\&{Arc})-(\&{sizeof}(\&{Arc})\AND(%
\&{sizeof}(\&{Arc})-\T{1})){}$;\par
\fi

\M{33}\B\X4:\.{gb\_graph.h }\X${}\mathrel+\E{}$\6
\&{extern} \&{siz\_t} \\{edge\_trick};\C{ least significant 1 bit in %
\&{sizeof}(\&{Arc}) }\par
\fi

\M{34}The type \&{siz\_t} just mentioned should be the type returned by \CEE/'s
\&{sizeof} operation; it's the basic unsigned type for machine
addresses in pointers. ANSI standard \CEE/ calls this type \&{size\_t},
but we cannot safely use \&{size\_t} in all the GraphBase programs
because some older \CEE/
systems mistakenly define \&{size\_t} to be a signed type.

\Y\B\F\\{siz\_t} \5
\\{int}\par
\Y\B\4\X8:Type declarations\X${}\mathrel+\E{}$\6
\&{typedef} \&{unsigned} \&{long} \&{siz\_t};\C{ basic machine address, as
signless integer }\par
\fi

\M{35}Vertices generally have a symbolic name, and we need a place to put
such names. The \\{gb\_save\_string} function is a convenient utility
for this purpose:
Given a null-terminated string of any length, \\{gb\_save\_string} stashes
it away in a safe place and returns a pointer to that place. Memory is
conserved by combining strings from the current graph into largish blocks
of a convenient size.

Note that \\{gb\_save\_string} should be used only after \\{gb\_new\_graph}
has provided suitable initialization, because the private variable
\\{cur\_graph} must point to the graph for which storage is currently
being allocated, and because the private variables \\{next\_string} and
\\{bad\_string} must also have suitable values.

\Y\B\4\D$\\{string\_block\_size}$ \5
\T{1016}\C{ $1024-8$ is usually efficient }\par
\Y\B\4\X13:External functions\X${}\mathrel+\E{}$\6
\&{char} ${}{*}\\{gb\_save\_string}(\|s){}$\1\1\6
\&{register} \&{char} ${}{*}\|s{}$;\C{ the string to be copied }\2\2\6
${}\{{}$\5
\1\&{register} \&{char} ${}{*}\|p\K\|s;{}$\6
\&{register} \&{long} \\{len};\C{ length of the string and the following null
character }\7
\&{while} ${}({*}\|p\PP){}$\1\5
;\C{ advance to the end of the string }\2\6
${}\\{len}\K\|p-\|s;{}$\6
${}\|p\K\\{next\_string};{}$\6
\&{if} ${}(\|p+\\{len}>\\{bad\_string}){}$\5
${}\{{}$\C{ not enough room in the current block }\1\6
\&{long} \\{size}${}\K\\{string\_block\_size};{}$\7
\&{if} ${}(\\{len}>\\{size}){}$\1\5
${}\\{size}\K\\{len};{}$\2\6
${}\|p\K\\{gb\_alloc}(\\{size},\39\\{cur\_graph}\MG\\{data});{}$\6
\&{if} ${}(\|p\E\NULL){}$\1\5
\&{return} \\{null\_string};\C{ return a pointer to \.{""} if memory ran out }%
\2\6
${}\\{bad\_string}\K\|p+\\{size};{}$\6
\4${}\}{}$\2\6
\&{while} ${}({*}\|s){}$\1\5
${}{*}\|p\PP\K{*}\|s\PP{}$;\C{ copy the non-null bytes of the string }\2\6
${}{*}\|p\PP\K\.{'\\0'}{}$;\C{ and append a null character }\6
${}\\{next\_string}\K\|p;{}$\6
\&{return} \|p${}-\\{len};{}$\6
\4${}\}{}$\2\par
\fi

\M{36}The test routine illustrates some of these basic maneuvers.

\Y\B\4\X36:Create a small graph\X${}\E{}$\6
$\|g\K\\{gb\_new\_graph}(\T{2\$L});{}$\6
\&{if} ${}(\|g\E\NULL){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Oops,\ I\ couldn't\ ev}\)\.{en\ create\ a\
trivial\ }\)\.{graph!\\n"});{}$\6
\&{return} ${}{-}\T{4};{}$\6
\4${}\}{}$\2\6
${}\|u\K\|g\MG\\{vertices}{}$;\5
${}\|v\K\|u+\T{1};{}$\6
${}\|u\MG\\{name}\K\\{gb\_save\_string}(\.{"vertex\ 0"});{}$\6
${}\|v\MG\\{name}\K\\{gb\_save\_string}(\.{"vertex\ 1"}){}$;\par
\U2.\fi

\M{37}\B\X19:Declarations of test variables\X${}\mathrel+\E{}$\6
\&{Graph} ${}{*}\|g;{}$\6
\&{Vertex} ${}{*}\|u,{}$ ${}{*}\|v{}$;\par
\fi

\M{38}If the ``edge trick'' fails, the standard GraphBase routines are
unaffected except for the demonstration program {\sc MILES\_\,SPAN}. (And
that program uses \\{edge\_trick} only when printing verbose comments.)

\Y\B\4\X38:Check that the small graph is still there\X${}\E{}$\6
\&{if} ${}(\\{strncmp}(\|u\MG\\{name},\39\|v\MG\\{name},\39\T{7})){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Something\ is\ fouled}\)\.{\ up\ in\ the\
string\ st}\)\.{orage\ machinery!\\n"});{}$\6
\&{return} ${}{-}\T{5};{}$\6
\4${}\}{}$\2\6
${}\\{gb\_new\_edge}(\|v,\39\|u,\39{-}\T{1\$L});{}$\6
${}\\{gb\_new\_edge}(\|u,\39\|u,\39\T{1\$L});{}$\6
${}\\{gb\_new\_arc}(\|v,\39\|u,\39{-}\T{1\$L});{}$\6
\&{if} ${}((\\{edge\_trick}\AND(\&{siz\_t})(\|u\MG\\{arcs}))\V(\\{edge\_trick}%
\AND(\&{siz\_t})(\|u\MG\\{arcs}\MG\\{next}\MG\\{next}))\V\R(\\{edge\_trick}%
\AND(\&{siz\_t})(\|v\MG\\{arcs}\MG\\{next}))){}$\1\5
\\{printf}(\.{"Warning:\ The\ \\"edge}\)\.{\ trick\\"\ failed!\\n"});\2\6
\&{if} ${}(\|v\MG\\{name}[\T{7}]+\|g\MG\|n\I\|v\MG\\{arcs}\MG\\{next}\MG\\{tip}%
\MG\\{name}[\T{7}]+\|g\MG\|m-\T{2}){}$\5
${}\{{}$\C{ $\.{'1'}+\T{2}\I\.{'0'}+\T{5}-\T{2}$ }\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Sorry,\ the\ graph\ da}\)\.{ta\ structures\
aren't}\)\.{\ working\ yet.\\n"});{}$\6
\&{return} ${}{-}\T{6};{}$\6
\4${}\}{}$\2\par
\U2.\fi

\M{39}Some applications might need to add arcs to several graphs at a time,
violating the assumptions stated above about \\{cur\_graph} and the other
private variables. The \\{switch\_to\_graph} function gets around that
restriction, by using the utility slots \\{ww}, \\{xx}, \\{yy}, and
\\{zz} of \&{Graph} records to save and restore the private variables.

Just say \\{switch\_to\_graph}(\|g) in order to make \\{cur\_graph} be~\|g and
to restore the other private variables that are needed by
\\{gb\_new\_arc}, \\{gb\_virgin\_arc}, \\{gb\_new\_edge}, and \\{gb\_save%
\_string}.
Restriction: The graph \|g being switched to must have previously been
switched from; that is, it must have been \\{cur\_graph} when \\{switch\_to%
\_graph}
was called previously. Otherwise its private allocation variables will
not have been saved. To meet this restriction, you should say
$\\{switch\_to\_graph}(\NULL)$ just before calling \\{gb\_new\_graph}, if you
intend to switch back to the current graph later.

(The swap-in-swap-out nature of these conventions may seem inelegant, but
convenience and efficiency are more important than elegance when most
applications do not need the ability to switch between graphs.)

\Y\B\4\X13:External functions\X${}\mathrel+\E{}$\6
\&{void} \\{switch\_to\_graph}(\|g)\1\1\6
\&{Graph} ${}{*}\|g;\2\2{}$\6
${}\{{}$\1\6
${}\\{cur\_graph}\MG\\{ww}.\|A\K\\{next\_arc}{}$;\5
${}\\{cur\_graph}\MG\\{xx}.\|A\K\\{bad\_arc};{}$\6
${}\\{cur\_graph}\MG\\{yy}.\|S\K\\{next\_string}{}$;\5
${}\\{cur\_graph}\MG\\{zz}.\|S\K\\{bad\_string};{}$\6
${}\\{cur\_graph}\K(\|g\?\|g:{\AND}\\{dummy\_graph});{}$\6
${}\\{next\_arc}\K\\{cur\_graph}\MG\\{ww}.\|A{}$;\5
${}\\{bad\_arc}\K\\{cur\_graph}\MG\\{xx}.\|A;{}$\6
${}\\{next\_string}\K\\{cur\_graph}\MG\\{yy}.\|S{}$;\5
${}\\{bad\_string}\K\\{cur\_graph}\MG\\{zz}.\|S;{}$\6
${}\\{cur\_graph}\MG\\{ww}.\|A\K\NULL;{}$\6
${}\\{cur\_graph}\MG\\{xx}.\|A\K\NULL;{}$\6
${}\\{cur\_graph}\MG\\{yy}.\|S\K\NULL;{}$\6
${}\\{cur\_graph}\MG\\{zz}.\|S\K\NULL;{}$\6
\4${}\}{}$\2\par
\fi

\M{40}Finally,
here's a routine that obliterates an entire graph when it is no longer needed:

\Y\B\4\X13:External functions\X${}\mathrel+\E{}$\6
\&{void} \\{gb\_recycle}(\|g)\1\1\6
\&{Graph} ${}{*}\|g;\2\2{}$\6
${}\{{}$\1\6
\&{if} (\|g)\5
${}\{{}$\1\6
${}\\{gb\_free}(\|g\MG\\{data});{}$\6
${}\\{gb\_free}(\|g\MG\\{aux\_data});{}$\6
\\{free}((\&{char} ${}{*}){}$ \|g);\C{ the user must not refer to \|g again }\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\fi

\M{41}\B\X4:\.{gb\_graph.h }\X${}\mathrel+\E{}$\6
\8\#\&{define} \\{gb\_new\_graph} \5\\{gb\_nugraph}\C{ abbreviations for
external linkage }\6
\8\#\&{define} \\{gb\_new\_arc} \5\\{gb\_nuarc}\6
\8\#\&{define} \\{gb\_new\_edge} \5\\{gb\_nuedge}\6
\&{extern} \&{Graph} ${}{*}\\{gb\_new\_graph}(\,){}$;\C{ create a new graph
structure }\6
\&{extern} \&{void} \\{gb\_new\_arc}(\,);\C{ append an arc to the current graph
}\6
\&{extern} \&{Arc} ${}{*}\\{gb\_virgin\_arc}(\,){}$;\C{ allocate a new \&{Arc}
record }\6
\&{extern} \&{void} \\{gb\_new\_edge}(\,);\C{ append an edge (two arcs) to the
current graph }\6
\&{extern} \&{char} ${}{*}\\{gb\_save\_string}(\,){}$;\C{ store a string in the
current graph }\6
\&{extern} \&{void} \\{switch\_to\_graph}(\,);\C{ save allocation variables,
swap in others }\6
\&{extern} \&{void} \\{gb\_recycle}(\,);\C{ delete a graph structure }\par
\fi

\N{1}{42}Searching for vertices. We sometimes want to be able to find a vertex,
given
its name, and it is nice to do this in a standard way. The following simple
subroutines can be used:

{\narrower
\smallskip\\{hash\_in}(\|v) puts the name of vertex \|v into the hash table;
\smallskip\\{hash\_out}(\|s) finds a vertex named \|s, if present in the hash
table;
\smallskip\\{hash\_setup}(\|g) prepares a hash table for all vertices of graph~%
\|g;
\smallskip$\\{hash\_lookup}(\|s,\|g)$ looks up the name \|s in the hash table
of \|g.
\smallskip}

\noindent Routines \\{hash\_in} and \\{hash\_out} apply to the current graph
being
created, while \\{hash\_setup} and \\{hash\_lookup} apply to arbitrary graphs.

Important: Utility fields \|u and \|v of each vertex are reserved for use by
the search routine when hashing is active. You can crash the system
if you try to fool around with these values yourself, or if you use any
subroutines that change those fields. The first two characters in the
current graph's \\{util\_types} field should be \.{VV} if the hash table
information is to be saved by {\sc GB\_\,SAVE}.

Warning: Users of this hash scheme must preserve the number of
vertices $\|g\MG\|n$ in the current graph~\|g. If $\|g\MG\|n$ is changed,
the hash table will be worthless, unless \\{hash\_setup} is used to
rehash everything.

\Y\B\4\X4:\.{gb\_graph.h }\X${}\mathrel+\E{}$\6
\&{extern} \&{void} \\{hash\_in}(\,);\C{ input a name to the hash table of
current graph }\6
\&{extern} \&{Vertex} ${}{*}\\{hash\_out}(\,){}$;\C{ find a name in hash table
of current graph }\6
\&{extern} \&{void} \\{hash\_setup}(\,);\C{ create a hash table for a given
graph }\6
\&{extern} \&{Vertex} ${}{*}\\{hash\_lookup}(\,){}$;\C{ find a name in a given
graph }\par
\fi

\M{43}The lookup scheme is quite simple. We compute a more-or-less random
value \|h based on the vertex name, where $\T{0}\Z\|h<\|n$, assuming that
the graph has \|n~vertices. There is a list of all vertices whose hash
address is~\|h, starting at $(\|g\MG\\{vertices}+\|h)\MG\\{hash\_head}$ and
linked
together in the \\{hash\_link} fields, where \\{hash\_head} and \\{hash\_link}
are
utility fields $\|u.\|V$ and $\|v.\|V$.

\Y\B\4\D$\\{hash\_link}$ \5
$\|u.{}$\|V\par
\B\4\D$\\{hash\_head}$ \5
$\|v.{}$\|V\par
\fi

\M{44}\B\X13:External functions\X${}\mathrel+\E{}$\6
\&{void} \\{hash\_in}(\|v)\1\1\6
\&{Vertex} ${}{*}\|v;\2\2{}$\6
${}\{{}$\5
\1\&{register} \&{char} ${}{*}\|t\K\|v\MG\\{name};{}$\6
\&{register} \&{Vertex} ${}{*}\|u;{}$\7
\X45:Find vertex \|u, whose location is the hash code for string \|t\X;\6
${}\|v\MG\\{hash\_link}\K\|u\MG\\{hash\_head};{}$\6
${}\|u\MG\\{hash\_head}\K\|v;{}$\6
\4${}\}{}$\2\par
\fi

\M{45}The hash code for a string $c_1c_2\ldots c_l$ of length $l$ is a
nonlinear function of the characters; this function appears to produce
reasonably random results between 0 and the number of vertices in the
current graph.  Simpler approaches were noticeably poorer in the
author's tests.

Caution: This hash coding scheme is system-dependent, because it
uses the system's character codes. If you create a graph on a
machine with ASCII code and save it with {\sc GB\_\,SAVE}, and if you
subsequently ship the
resulting text file to some friend whose machine does not use ASCII code,
your friend will have to rebuild the hash structure with \\{hash\_setup}
before being able to use \\{hash\_lookup} successfully.

\Y\B\4\D$\.{HASH\_MULT}$ \5
\T{314159}\C{ random multiplier }\par
\B\4\D$\.{HASH\_PRIME}$ \5
\T{516595003}\C{ the 27182818th prime; it's less than $2^{29}$ }\par
\Y\B\4\X45:Find vertex \|u, whose location is the hash code for string \|t\X${}%
\E{}$\6
${}\{{}$\5
\1\&{register} \&{long} \|h;\7
\&{for} ${}(\|h\K\T{0};{}$ ${}{*}\|t;{}$ ${}\|t\PP){}$\5
${}\{{}$\1\6
${}\|h\MRL{+{\K}}(\|h\XOR(\|h\GG\T{1}))+\.{HASH\_MULT}*{}$(\&{unsigned} %
\&{char}) ${}{*}\|t;{}$\6
\&{while} ${}(\|h\G\.{HASH\_PRIME}){}$\1\5
${}\|h\MRL{-{\K}}\.{HASH\_PRIME};{}$\2\6
\4${}\}{}$\2\6
${}\|u\K\\{cur\_graph}\MG\\{vertices}+(\|h\MOD\\{cur\_graph}\MG\|n);{}$\6
\4${}\}{}$\2\par
\Us44\ET46.\fi

\M{46}If the hash function were truly random, the average number of
string comparisons made would be less than $(e^2+7)/8\approx 1.80$ on
a successful search, and less than $(e^2+1)/4\approx2.10$ on an
unsuccessful search [{\sl Sorting and Searching}, Section 6.4,
Eqs.~(15) and~(16)].

\Y\B\4\X13:External functions\X${}\mathrel+\E{}$\6
\&{Vertex} ${}{*}\\{hash\_out}(\|s){}$\1\1\6
\&{char} ${}{*}\|s;\2\2{}$\6
${}\{{}$\5
\1\&{register} \&{char} ${}{*}\|t\K\|s;{}$\6
\&{register} \&{Vertex} ${}{*}\|u;{}$\7
\X45:Find vertex \|u, whose location is the hash code for string \|t\X;\6
\&{for} ${}(\|u\K\|u\MG\\{hash\_head};{}$ \|u; ${}\|u\K\|u\MG\\{hash\_link}){}$%
\1\6
\&{if} ${}(\\{strcmp}(\|s,\39\|u\MG\\{name})\E\T{0}){}$\1\5
\&{return} \|u;\2\2\6
\&{return} ${}\NULL{}$;\C{ not found }\6
\4${}\}{}$\2\par
\fi

\M{47}\B\X13:External functions\X${}\mathrel+\E{}$\6
\&{void} \\{hash\_setup}(\|g)\1\1\6
\&{Graph} ${}{*}\|g;\2\2{}$\6
${}\{{}$\5
\1\&{Graph} ${}{*}\\{save\_cur\_graph};{}$\7
\&{if} ${}(\|g\W\|g\MG\|n>\T{0}){}$\5
${}\{{}$\5
\1\&{register} \&{Vertex} ${}{*}\|v;{}$\7
${}\\{save\_cur\_graph}\K\\{cur\_graph};{}$\6
${}\\{cur\_graph}\K\|g;{}$\6
\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$
${}\|v\PP){}$\1\5
${}\|v\MG\\{hash\_head}\K\NULL;{}$\2\6
\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$
${}\|v\PP){}$\1\5
\\{hash\_in}(\|v);\2\6
${}\|g\MG\\{util\_types}[\T{0}]\K\|g\MG\\{util\_types}[\T{1}]\K\.{'V'}{}$;\C{
indicate usage of \\{hash\_head} and \\{hash\_link} }\6
${}\\{cur\_graph}\K\\{save\_cur\_graph};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\fi

\M{48}\B\X13:External functions\X${}\mathrel+\E{}$\6
\&{Vertex} ${}{*}\\{hash\_lookup}(\|s,\39\|g){}$\1\1\6
\&{char} ${}{*}\|s;{}$\6
\&{Graph} ${}{*}\|g;\2\2{}$\6
${}\{{}$\5
\1\&{Graph} ${}{*}\\{save\_cur\_graph};{}$\7
\&{if} ${}(\|g\W\|g\MG\|n>\T{0}){}$\5
${}\{{}$\5
\1\&{register} \&{Vertex} ${}{*}\|v;{}$\7
${}\\{save\_cur\_graph}\K\\{cur\_graph};{}$\6
${}\\{cur\_graph}\K\|g;{}$\6
${}\|v\K\\{hash\_out}(\|s);{}$\6
${}\\{cur\_graph}\K\\{save\_cur\_graph};{}$\6
\&{return} \|v;\6
\4${}\}{}$\2\6
\&{else}\1\5
\&{return} ${}\NULL;{}$\2\6
\4${}\}{}$\2\par
\fi

\N{1}{49}Index. Here is a list that shows where the identifiers of this program
are
defined and used.
\fi


\inx
\fin
\con
