summaryrefslogtreecommitdiff
path: root/support/graphbase/gb_roget.w
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /support/graphbase/gb_roget.w
Initial commit
Diffstat (limited to 'support/graphbase/gb_roget.w')
-rw-r--r--support/graphbase/gb_roget.w224
1 files changed, 224 insertions, 0 deletions
diff --git a/support/graphbase/gb_roget.w b/support/graphbase/gb_roget.w
new file mode 100644
index 0000000000..fba3536c19
--- /dev/null
+++ b/support/graphbase/gb_roget.w
@@ -0,0 +1,224 @@
+% This file is part of the Stanford GraphBase (c) Stanford University 1992
+\def\title{GB\_\thinspace ROGET}
+@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
+
+\prerequisites{GB\_\thinspace GRAPH}{GB\_\thinspace IO}
+@* 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
+|roget_components|.
+
+@(gb_roget.h@>=
+extern Graph *roget();
+
+@ 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 1882 edition of Peter Mark Roget's {\sl Thesaurus of English Words
+and Phrases}. 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=1022| is substituted when |n=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
+nuumbers differ by less than |min_distance|. For example, if
+|min_distance>1|, the arc between categories 312 and~313 will not
+be included. (Roget sometimes formed clusters of three interrelated
+categories; to avoid cross-references among these, you can set
+|min_distance=3|.)
+
+If |prob>0|, arcs that would ordinarily be included in the graph are
+rejected with probability |prob/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(1000,3,32768,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.
+
+@d MAX_N 1022 /* the number of categories in Roget's book */
+
+@ 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 |gb_graph|.
+(The external variable |@!panic_code| is itself defined in |gb_graph|.)
+
+@d panic(c) @+{@+panic_code=c;@+gb_alloc_trouble=0;@+return NULL;@+}
+@#
+@f Graph int /* |gb_graph| defines the |Graph| type and a few others */
+@f Vertex int
+@f Arc int
+
+@ The \Cee\ file \.{gb\_roget.c} has the following general shape:
+
+@p
+#include "gb_io.h" /* we will use the |gb_io| routines for input */
+#include "gb_flip.h"
+ /* we will use the |gb_flip| routines for random numbers */
+#include "gb_graph.h" /* and we will use the |gb_graph| data structures */
+@#
+@<Private variables@>@;
+@#
+Graph *roget(n,min_distance,prob,seed)
+ unsigned n; /* number of vertices desired */
+ unsigned min_distance; /* smallest inter-category distance allowed
+ in an arc */
+ unsigned long prob; /* 65536 times the probability of rejecting an arc */
+ long seed; /* random number seed */
+{@+@<Local variables@>@;
+ gb_init_rand(seed);
+ if (n==0 || n>MAX_N) n=MAX_N;
+ @<Set up a graph with |n| vertices@>;
+ @<Determine the |n| categories to use in the graph@>;
+ @<Input \.{roget.dat} and build the graph@>;
+ if (gb_alloc_trouble) {
+ gb_recycle(new_graph);
+ panic(alloc_fault); /* oops, we ran out of memory somewhere back there */
+ }
+ return new_graph;
+}
+
+@ @<Local var...@>=
+Graph *new_graph; /* the graph constructed by |roget| */
+
+@* Vertices.
+
+@<Set up a graph with |n| vertices@>=
+new_graph=gb_new_graph(n);
+if (new_graph==NULL)
+ panic(no_room); /* out of memory before we're even started */
+sprintf(new_graph->id,"roget(%u,%u,%lu,%ld)",n,min_distance,prob,seed);
+strcpy(new_graph->format,"IZZZZZZZZZZZZZ");
+
+@ 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]| will be non-|NULL| for exactly |n| randomly selected
+category numbers~|k|, i.e., values of~|k| in the range |1<=k<=MAX_N|.
+Moreover, these non-|NULL| values will be a random permutation of the
+vertices of the graph.
+
+@<Priv...@>=
+Vertex *mapping[MAX_N+1]; /* the vertex corresponding to a given category */
+int cats[MAX_N]; /* table of category numbers that have not yet been used */
+
+@ In the loop on |v| below, |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.
+
+@<Determine the |n| categories to use in the graph@>=
+for (k=0; k<MAX_N; k++)
+ cats[k]=k+1,@,mapping[k+1]=NULL;
+for (v=new_graph->vertices+n-1; v>=new_graph->vertices; v--) {
+ j=gb_unif_rand(k);
+ mapping[cats[j]]=v; cats[j]=cats[--k];
+}
+
+@ @<Local...@>=
+register int j,k; /* all-purpose indices */
+register Vertex *v; /* current vertex */
+
+@* 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 above. First comes the
+category number, then the category name, then a colon, then zero or more
+numbers specifying arcs to other categories, 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.
+
+@<Input \.{roget.dat} and build the graph@>=
+if (gb_open("roget.dat")!=0)
+ panic(early_data_fault);
+ /* couldn't open |"roget.dat"| using GraphBase conventions */
+for (k=1; !gb_eof(); k++)
+ @<Read the data for category |k|, and put it in the graph if it
+ has been selected@>;
+if (gb_close()!=0)
+ panic(late_data_fault);
+ /* something's wrong with |"roget.dat"|; see |io_errors| */
+if (k!=MAX_N+1) panic(impossible);
+ /* we don't have the right value of |MAX_N| */
+
+@ We want to 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.
+
+@d cat_no u.i /* utility field |u| of each vertex holds the category number */
+
+@<Read the data for category |k|, and put it in the graph if it
+ has been selected@>=
+{
+ if (mapping[k]) { /* yes, this category has been selected */
+ if (gb_number(10)!=k) panic(syntax_error); /* out of synch */
+ (void)gb_string(str_buf,':');
+ if (gb_char()!=':') panic(syntax_error+1); /* no colon found */
+ v=mapping[k];
+ v->name=gb_save_string(str_buf);
+ v->cat_no=k;
+ @<Add arcs from |v| for every category that's both listed on the line
+ and selected@>;
+ } else @<Skip past the data for one category@>;
+}
+
+@ @(gb_roget.h@>=
+#define cat_no @t\quad@> u.i
+ /* definition of |cat_no| is repeated in the header file */
+
+@ @d iabs(x) ((x)<0? -(x): (x))
+
+@<Add arcs from |v| for every...@>=
+j=gb_number(10);
+if (j==0) goto done; /* some categories lead to no arcs at all */
+while (1) {@+Arc *a;
+ if (j>MAX_N) panic(syntax_error+2); /* category code out of range */
+ if (mapping[j] && iabs(j-k)>=min_distance &&
+ (prob==0 || ((gb_next_rand()>>15)>=prob)))
+ gb_new_arc(v,mapping[j],1);
+ switch (gb_char()) {
+ case '\\': gb_newline();
+ if (gb_char()!=' ')
+ panic(syntax_error+3); /* space should begin a continuation line */
+ /* fall through to the space case */
+ case ' ': j=gb_number(10);@+break;
+ case '\n': goto done;
+ default: panic(syntax_error+4);
+ /* illegal character following category number */
+ }
+}
+done: gb_newline();
+
+@ 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.)
+
+@<Skip past the data for one category@>=
+{
+ if (*(gb_string(str_buf,'\n')-2)=='\\')
+ gb_newline(); /* the first line ended with backslash */
+ gb_newline();
+}
+
+@* Index. Here is a list that shows where the identifiers of this program are
+defined and used.