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

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

\N{1}{1}Introduction. This GraphBase module contains the \\{roget} subroutine,
which creates a family of graphs based on Roget's Thesaurus. An example
of the use of this procedure can be found in the demo program
{\sc ROGET\_\,COMPONENTS}.

\Y\B\4\X1:\.{gb\_roget.h }\X${}\E{}$\6
\&{extern} \&{Graph} ${}{*}\\{roget}(\,){}$;\par
\A12.\fi

\M{2}The subroutine call $\\{roget}(\|n,\\{min\_distance},\\{prob},\\{seed})$
constructs a graph based on the information in \.{roget.dat}.
Each vertex of the graph corresponds to one of the 1022 categories in
the 1879 edition of Peter Mark Roget's {\sl Thesaurus of English Words
and Phrases}, edited by John Lewis Roget.
An arc goes from one category to another if Roget gave a
reference to the latter among the words and phrases of the former,
or if the two categories were directly related to each other by their
positions in Roget's book. For example, the vertex for category 312
(`ascent') has arcs to the vertices for categories 224 (`obliquity'),
313 (`descent'), and 316 (`leap'), because Roget gave explicit
cross-references from 312 to 224 and~316, and because category 312
was implicitly paired with 313 in his scheme.

The constructed graph will have $\min(n,1022)$ vertices; however, the
default value $\|n\K\T{1022}$ is substituted when $\|n\K\T{0}$. If \|n is less
than 1022, the \|n categories will be selected at random,
and all arcs to unselected categories will be omitted.
Arcs will also be omitted if they correspond to categories whose
numbers differ by less than \\{min\_distance}. For example, if
$\\{min\_distance}>\T{1}$, the arc between categories 312 and~313 will not
be included. (Roget sometimes formed clusters of three interrelated
categories; to avoid cross-references within all such clusters, you can set
$\\{min\_distance}\K\T{3}$.)

If $\\{prob}>\T{0}$, arcs that would ordinarily be included in the graph are
rejected with probability $\\{prob}/\T{65536}$. This provides a way
to obtain sparser graphs.

The vertices will appear in random order. However, all ``randomness''
in GraphBase graphs is reproducible; it depends only on the value of
a given \\{seed}, which can be any nonnegative integer less than~$2^{31}$.
For example, everyone who asks for $\\{roget}(\T{1000},\T{3},\T{32768},\T{50})$
will
obtain exactly the same graph, regardless of their computer system.

Changing the value of \\{prob} will affect only the arcs of the
generated graph; it will change neither the choice of vertices
nor the vertex order.

\Y\B\4\D$\.{MAX\_N}$ \5
\T{1022}\C{ the number of categories in Roget's book }\par
\fi

\M{3}If the \\{roget} 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 \\{roget} 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
\&{return} ${}\NULL{}$;\5
${}\}{}$\2\par
\fi

\M{4}The \CEE/ file \.{gb\_roget.c} has the following general shape:

\Y\B\8\#\&{include} \.{"gb\_io.h"}\C{ we will use the {\sc GB\_\,IO} routines
for input }\6
\8\#\&{include} \.{"gb\_flip.h"}\C{ we will use the {\sc GB\_\,FLIP} routines
for random numbers }\6
\8\#\&{include} \.{"gb\_graph.h"}\C{ and we will use the {\sc GB\_\,GRAPH} data
structures }\6
\ATH\7
\X7:Private variables\X\7
\&{Graph} ${}{*}\\{roget}(\|n,\39\\{min\_distance},\39\\{prob},\39\\{seed}){}$%
\1\1\6
\&{unsigned} \&{long} \|n;\C{ number of vertices desired }\6
\&{unsigned} \&{long} \\{min\_distance};\C{ smallest inter-category distance
allowed                             in an arc }\6
\&{unsigned} \&{long} \\{prob};\C{ 65536 times the probability of rejecting an
arc }\6
\&{long} \\{seed};\C{ random number seed }\2\2\6
${}\{{}$\5
\1\X5:Local variables\X\7
\\{gb\_init\_rand}(\\{seed});\6
\&{if} ${}(\|n\E\T{0}\V\|n>\.{MAX\_N}){}$\1\5
${}\|n\K\.{MAX\_N};{}$\2\6
\X6:Set up a graph with \|n vertices\X;\6
\X8:Determine the \|n categories to use in the graph\X;\6
\X10:Input \.{roget.dat} and build the graph\X;\6
\&{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
\&{return} \\{new\_graph};\6
\4${}\}{}$\2\par
\fi

\M{5}\B\X5:Local variables\X${}\E{}$\6
\&{Graph} ${}{*}\\{new\_graph}{}$;\C{ the graph constructed by \\{roget} }\par
\A9.
\U4.\fi

\N{1}{6}Vertices.

\Y\B\4\X6:Set up a graph with \|n vertices\X${}\E{}$\6
$\\{new\_graph}\K\\{gb\_new\_graph}(\|n);{}$\6
\&{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\.{"roget(\%lu,\%lu,\%lu,\%}\)%
\.{ld)"},\39\|n,\39\\{min\_distance},\39\\{prob},\39\\{seed});{}$\6
${}\\{strcpy}(\\{new\_graph}\MG\\{util\_types},\39\.{"IZZZZZZZZZZZZZ"}){}$;\par
\U4.\fi

\M{7}The first nontrivial thing we need to do is find a random selection and
permutation of \|n vertices. We will compute a \\{mapping} table such that
\\{mapping}[\|k] is non-$\NULL$ for exactly \|n randomly selected
category numbers~\|k.
Moreover, these non-$\NULL$ values will be a random permutation of the
vertices of the graph.

\Y\B\4\X7:Private variables\X${}\E{}$\6
\&{static} \&{Vertex} ${}{*}\\{mapping}[\.{MAX\_N}+\T{1}]{}$;\C{ the vertex
corresponding to a given category }\6
\&{static} \&{long} \\{cats}[\.{MAX\_N}];\C{ table of category numbers that
have not yet been used }\par
\U4.\fi

\M{8}During the loop on \|v in this step, \|k is the number of categories
whose \\{mapping} value is still~$\NULL$.
The first \|k entries of \\{cats} will contain
those category numbers in some order.

\Y\B\4\X8:Determine the \|n categories to use in the graph\X${}\E{}$\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\.{MAX\_N};{}$ ${}\|k\PP){}$\1\5
${}\\{cats}[\|k]\K\|k+\T{1},\,\39\\{mapping}[\|k+\T{1}]\K\NULL;{}$\2\6
\&{for} ${}(\|v\K\\{new\_graph}\MG\\{vertices}+\|n-\T{1};{}$ ${}\|v\G\\{new%
\_graph}\MG\\{vertices};{}$ ${}\|v\MM){}$\5
${}\{{}$\1\6
${}\|j\K\\{gb\_unif\_rand}(\|k);{}$\6
${}\\{mapping}[\\{cats}[\|j]]\K\|v;{}$\6
${}\\{cats}[\|j]\K\\{cats}[\MM\|k];{}$\6
\4${}\}{}$\2\par
\U4.\fi

\M{9}\B\X5:Local variables\X${}\mathrel+\E{}$\6
\&{register} \&{long} \|j${},{}$ \|k;\C{ all-purpose indices }\6
\&{register} \&{Vertex} ${}{*}\|v{}$;\C{ current vertex }\par
\fi

\N{1}{10}Arcs. The data in \.{roget.dat} appears in 1022 lines, one for each
category. For example, the line
$$\hbox{\tt 312ascent:224 313 316}$$
specifies the arcs from category 312 as explained earlier. First comes the
category number, then the category name, then a colon, then zero or more
numbers specifying arcs to other categories; the numbers are
separated by spaces.

Some categories have too many arcs to fit on a single line; the data
for these categories can be found on two lines, the first line ending
with a backslash and the second line beginning with a space.

\Y\B\4\X10:Input \.{roget.dat} and build the graph\X${}\E{}$\6
\&{if} ${}(\\{gb\_open}(\.{"roget.dat"})\I\T{0}){}$\1\5
\\{panic}(\\{early\_data\_fault});\C{ couldn't open \.{"roget.dat"} using
GraphBase conventions }\2\6
\&{for} ${}(\|k\K\T{1};{}$ ${}\R\\{gb\_eof}(\,);{}$ ${}\|k\PP){}$\1\5
\X11:Read the data for category \|k, and put it in the graph if it has been
selected\X;\2\6
\&{if} ${}(\\{gb\_close}(\,)\I\T{0}){}$\1\5
\\{panic}(\\{late\_data\_fault});\C{ something's wrong with \.{"roget.dat"};
see \\{io\_errors} }\2\6
\&{if} ${}(\|k\I\.{MAX\_N}+\T{1}){}$\1\5
\\{panic}(\\{impossible});\C{ we don't have the right value of \.{MAX\_N} }\2%
\par
\U4.\fi

\M{11}We check that the data isn't garbled, except that we don't
bother to look at unselected categories.

The original category number is stored in vertex utility field \\{cat\_no},
in case anybody wants to see it.

\Y\B\4\D$\\{cat\_no}$ \5
$\|u.{}$\|I\C{ utility field \|u of each vertex holds the category number }\par
\Y\B\4\X11:Read the data for category \|k, and put it in the graph if it has
been selected\X${}\E{}$\6
${}\{{}$\1\6
\&{if} (\\{mapping}[\|k])\5
${}\{{}$\C{ yes, this category has been selected }\1\6
\&{if} ${}(\\{gb\_number}(\T{10})\I\|k){}$\1\5
\\{panic}(\\{syntax\_error});\C{ out of synch }\2\6
(\&{void}) \\{gb\_string}${}(\\{str\_buf},\39\.{':'});{}$\6
\&{if} ${}(\\{gb\_char}(\,)\I\.{':'}){}$\1\5
${}\\{panic}(\\{syntax\_error}+\T{1}){}$;\C{ no colon found }\2\6
${}\|v\K\\{mapping}[\|k];{}$\6
${}\|v\MG\\{name}\K\\{gb\_save\_string}(\\{str\_buf});{}$\6
${}\|v\MG\\{cat\_no}\K\|k;{}$\6
\X13:Add arcs from \|v for every category that's both listed on the line and
selected\X;\6
\4${}\}{}$\5
\2\&{else}\1\5
\X14:Skip past the data for one category\X;\2\6
\4${}\}{}$\2\par
\U10.\fi

\M{12}\B\X1:\.{gb\_roget.h }\X${}\mathrel+\E{}$\6
\8\#\&{define} ${}\\{cat\_no}\hbox{\quad}\|u.\|I{}$\C{ definition of \\{cat%
\_no} is repeated in the header file }\par
\fi

\M{13}\B\D$\\{iabs}(\|x)$ \5
$((\|x)<\T{0}\?{-}(\|x):(\|x){}$)\par
\Y\B\4\X13:Add arcs from \|v for every category that's both listed on the line
and selected\X${}\E{}$\6
$\|j\K\\{gb\_number}(\T{10});{}$\6
\&{if} ${}(\|j\E\T{0}){}$\1\5
\&{goto} \\{done};\C{ some categories lead to no arcs at all }\2\6
\&{while} (\T{1})\5
${}\{{}$\1\6
\&{if} ${}(\|j>\.{MAX\_N}){}$\1\5
${}\\{panic}(\\{syntax\_error}+\T{2}){}$;\C{ category code out of range }\2\6
\&{if} ${}(\\{mapping}[\|j]\W\\{iabs}(\|j-\|k)\G\\{min\_distance}\W(\\{prob}\E%
\T{0}\V((\\{gb\_next\_rand}(\,)\GG\T{15})\G\\{prob}))){}$\1\5
${}\\{gb\_new\_arc}(\|v,\39\\{mapping}[\|j],\39\T{1\$L});{}$\2\6
\&{switch} (\\{gb\_char}(\,))\5
${}\{{}$\1\6
\4\&{case} \.{'\\\\'}:\5
\\{gb\_newline}(\,);\6
\&{if} ${}(\\{gb\_char}(\,)\I\.{'\ '}){}$\1\5
${}\\{panic}(\\{syntax\_error}+\T{3}){}$;\C{ space should begin a continuation
line }\C{ fall through to the space case }\2\6
\4\&{case} \.{'\ '}:\5
${}\|j\K\\{gb\_number}(\T{10}){}$;\5
\&{break};\6
\4\&{case} \.{'\\n'}:\5
\&{goto} \\{done};\6
\4\&{default}:\5
${}\\{panic}(\\{syntax\_error}+\T{4}){}$;\C{ illegal character following
category number }\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4\\{done}:\5
\\{gb\_newline}(\,);\par
\U11.\fi

\M{14}We want to call \\{gb\_newline}(\,) twice if the current line ends with a
backslash; otherwise we want to call it just once. There's an obvious
way to do that, and there's also a faster and trickier way.  The
author apologizes here for succumbing to some old-fashioned impulses.
(Recall that \\{gb\_string} returns the location just following the
\.{'\\0'} it places at the end of a scanned string.)

\Y\B\4\X14:Skip past the data for one category\X${}\E{}$\6
${}\{{}$\1\6
\&{if} ${}({*}(\\{gb\_string}(\\{str\_buf},\39\.{'\\n'})-\T{2})\E\.{'\\\\'}){}$%
\1\5
\\{gb\_newline}(\,);\C{ the first line ended with backslash }\2\6
\\{gb\_newline}(\,);\6
\4${}\}{}$\2\par
\U11.\fi

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


\inx
\fin
\con
