gb_roget.w
上传用户:rrhhcc
上传日期:2015-12-11
资源大小:54129k
文件大小:9k
源码类别:

通讯编程

开发平台:

Visual C++

  1. % This file is part of the Stanford GraphBase (c) Stanford University 1993
  2. @i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
  3. @i gb_types.w
  4. deftitle{GB_,ROGET}
  5. prerequisites{GB_,GRAPH}{GB_,IO}
  6. @* Introduction. This GraphBase module contains the |roget| subroutine,
  7. which creates a family of graphs based on Roget's Thesaurus. An example
  8. of the use of this procedure can be found in the demo program
  9. {sc ROGET_,COMPONENTS}.
  10. @(gb_roget.h@>=
  11. extern Graph *roget();
  12. @ The subroutine call |roget(n,min_distance,prob,seed)|
  13. constructs a graph based on the information in .{roget.dat}.
  14. Each vertex of the graph corresponds to one of the 1022 categories in
  15. the 1879 edition of Peter Mark Roget's {sl Thesaurus of English Words
  16. @^Roget, Peter Mark@>@^Roget, John Lewis@>
  17. and Phrases}, edited by John Lewis Roget.
  18. An arc goes from one category to another if Roget gave a
  19. reference to the latter among the words and phrases of the former,
  20. or if the two categories were directly related to each other by their
  21. positions in Roget's book. For example, the vertex for category 312
  22. (`ascent') has arcs to the vertices for categories 224 (`obliquity'),
  23. 313 (`descent'), and 316 (`leap'), because Roget gave explicit
  24. cross-references from 312 to 224 and~316, and because category 312
  25. was implicitly paired with 313 in his scheme.
  26. The constructed graph will have $min(n,1022)$ vertices; however, the
  27. default value |n=1022| is substituted when |n=0|. If |n| is less
  28. than 1022, the |n| categories will be selected at random,
  29. and all arcs to unselected categories will be omitted.
  30. Arcs will also be omitted if they correspond to categories whose
  31. numbers differ by less than |min_distance|. For example, if
  32. |min_distance>1|, the arc between categories 312 and~313 will not
  33. be included. (Roget sometimes formed clusters of three interrelated
  34. categories; to avoid cross-references within all such clusters, you can set
  35. |min_distance=3|.)
  36. If |prob>0|, arcs that would ordinarily be included in the graph are
  37. rejected with probability |prob/65536|. This provides a way
  38. to obtain sparser graphs.
  39. The vertices will appear in random order. However, all ``randomness''
  40. in GraphBase graphs is reproducible; it depends only on the value of
  41. a given |seed|, which can be any nonnegative integer less than~$2^{31}$.
  42. For example, everyone who asks for |roget(1000,3,32768,50)| will
  43. obtain exactly the same graph, regardless of their computer system.
  44. Changing the value of |prob| will affect only the arcs of the
  45. generated graph; it will change neither the choice of vertices
  46. nor the vertex order.
  47. @d MAX_N 1022 /* the number of categories in Roget's book */
  48. @ If the |roget| routine encounters a problem, it returns |NULL|
  49. (.{NULL}), after putting a code number into the external variable
  50. |panic_code|. This code number identifies the type of failure.
  51. Otherwise |roget| returns a pointer to the newly created graph, which
  52. will be represented with the data structures explained in {sc GB_,GRAPH}.
  53. (The external variable |panic_code| is itself defined in {sc GB_,GRAPH}.)
  54. @d panic(c) @+{@+panic_code=c;@+gb_trouble_code=0;@+return NULL;@+}
  55. @ The CEE/ file .{gb_roget.c} has the following general shape:
  56. @p
  57. #include "gb_io.h" /* we will use the {sc GB_,IO} routines for input */
  58. #include "gb_flip.h"
  59.  /* we will use the {sc GB_,FLIP} routines for random numbers */
  60. #include "gb_graph.h"
  61.  /* and we will use the {sc GB_,GRAPH} data structures */
  62. @h@#
  63. @<Private variables@>@;
  64. @#
  65. Graph *roget(n,min_distance,prob,seed)
  66.   unsigned long n; /* number of vertices desired */
  67.   unsigned long min_distance; /* smallest inter-category distance allowed
  68.                             in an arc */
  69.   unsigned long prob; /* 65536 times the probability of rejecting an arc */
  70.   long seed; /* random number seed */
  71. {@+@<Local variables@>@;@#
  72.   gb_init_rand(seed);
  73.   if (n==0 || n>MAX_N) n=MAX_N;
  74.   @<Set up a graph with |n| vertices@>;
  75.   @<Determine the |n| categories to use in the graph@>;
  76.   @<Input .{roget.dat} and build the graph@>;
  77.   if (gb_trouble_code) {
  78.     gb_recycle(new_graph);
  79.     panic(alloc_fault); /* oops, we ran out of memory somewhere back there */
  80.   }
  81.   return new_graph;
  82. }
  83. @ @<Local var...@>=
  84. Graph *new_graph; /* the graph constructed by |roget| */
  85. @* Vertices.
  86. @<Set up a graph with |n| vertices@>=
  87. new_graph=gb_new_graph(n);
  88. if (new_graph==NULL)
  89.   panic(no_room); /* out of memory before we're even started */
  90. sprintf(new_graph->id,"roget(%lu,%lu,%lu,%ld)",n,min_distance,prob,seed);
  91. strcpy(new_graph->util_types,"IZZZZZZZZZZZZZ");
  92. @ The first nontrivial thing we need to do is find a random selection and
  93. permutation of |n| vertices. We will compute a |mapping| table such that
  94. |mapping[k]| is non-|NULL| for exactly |n| randomly selected
  95. category numbers~|k|.
  96. Moreover, these non-|NULL| values will be a random permutation of the
  97. vertices of the graph.
  98. @<Priv...@>=
  99. static Vertex *mapping[MAX_N+1];
  100.  /* the vertex corresponding to a given category */
  101. static long cats[MAX_N];
  102.  /* table of category numbers that have not yet been used */
  103. @ During the loop on |v| in this step, |k| is the number of categories
  104. whose |mapping| value is still~|NULL|.
  105. The first |k| entries of |cats| will contain
  106. those category numbers in some order.
  107. @<Determine the |n| categories to use in the graph@>=
  108. for (k=0; k<MAX_N; k++)
  109.   cats[k]=k+1,@,mapping[k+1]=NULL;
  110. for (v=new_graph->vertices+n-1; v>=new_graph->vertices; v--) {
  111.   j=gb_unif_rand(k);
  112.   mapping[cats[j]]=v; cats[j]=cats[--k];
  113. }
  114. @ @<Local...@>=
  115. register long j,k; /* all-purpose indices */
  116. register Vertex *v; /* current vertex */
  117. @* Arcs. The data in .{roget.dat} appears in 1022 lines, one for each
  118. category. For example, the line
  119. $$hbox{tt 312ascent:224 313 316}$$
  120. specifies the arcs from category 312 as explained earlier. First comes the
  121. category number, then the category name, then a colon, then zero or more
  122. numbers specifying arcs to other categories; the numbers are
  123. separated by spaces.
  124. Some categories have too many arcs to fit on a single line; the data
  125. for these categories can be found on two lines, the first line ending
  126. with a backslash and the second line beginning with a space.
  127. @<Input .{roget.dat} and build the graph@>=
  128. if (gb_open("roget.dat")!=0)
  129.   panic(early_data_fault);
  130.     /* couldn't open |"roget.dat"| using GraphBase conventions */
  131. for (k=1; !gb_eof(); k++)
  132.   @<Read the data for category |k|, and put it in the graph if it
  133.     has been selected@>;
  134. if (gb_close()!=0)
  135.   panic(late_data_fault);
  136.     /* something's wrong with |"roget.dat"|; see |io_errors| */
  137. if (k!=MAX_N+1) panic(impossible);
  138.   /* we don't have the right value of |MAX_N| */
  139. @ We check that the data isn't garbled, except that we don't
  140. bother to look at unselected categories.
  141. The original category number is stored in vertex utility field |cat_no|,
  142. in case anybody wants to see it.
  143. @d cat_no u.I /* utility field |u| of each vertex holds the category number */
  144. @<Read the data for category |k|, and put it in the graph if it
  145.    has been selected@>=
  146. {
  147.   if (mapping[k]) { /* yes, this category has been selected */
  148.     if (gb_number(10)!=k) panic(syntax_error); /* out of synch */
  149.     (void)gb_string(str_buf,':');
  150.     if (gb_char()!=':') panic(syntax_error+1); /* no colon found */
  151.     v=mapping[k];
  152.     v->name=gb_save_string(str_buf);
  153.     v->cat_no=k;
  154.     @<Add arcs from |v| for every category that's both listed on the line
  155.           and selected@>;
  156.   }@+else @<Skip past the data for one category@>;
  157. }
  158. @ @(gb_roget.h@>=
  159. #define cat_no @tquad@> u.I
  160.  /* definition of |cat_no| is repeated in the header file */
  161. @ @d iabs(x) ((x)<0? -(x): (x))
  162. @<Add arcs from |v| for every...@>=
  163. j=gb_number(10);
  164. if (j==0) goto done; /* some categories lead to no arcs at all */
  165. while (1) {
  166.   if (j>MAX_N) panic(syntax_error+2); /* category code out of range */
  167.   if (mapping[j] && iabs(j-k)>=min_distance &&
  168.        (prob==0 || ((gb_next_rand()>>15)>=prob)))
  169.     gb_new_arc(v,mapping[j],1L);
  170.   switch (gb_char()) {
  171.   case '\': gb_newline();
  172.     if (gb_char()!=' ')
  173.       panic(syntax_error+3); /* space should begin a continuation line */
  174.     /* fall through to the space case */
  175.   case ' ': j=gb_number(10);@+break;
  176.   case 'n': goto done;
  177.   default: panic(syntax_error+4);
  178.     /* illegal character following category number */
  179.   }
  180. }
  181. done: gb_newline();
  182. @ We want to call |gb_newline()| twice if the current line ends with a
  183. backslash; otherwise we want to call it just once. There's an obvious
  184. way to do that, and there's also a faster and trickier way.  The
  185. author apologizes here for succumbing to some old-fashioned impulses.
  186. (Recall that |gb_string| returns the location just following the
  187. |''| it places at the end of a scanned string.)
  188. @<Skip past the data for one category@>=
  189. {
  190.   if (*(gb_string(str_buf,'n')-2)=='\')
  191.     gb_newline(); /* the first line ended with backslash */
  192.   gb_newline();
  193. }
  194. @* Index. Here is a list that shows where the identifiers of this program are
  195. defined and used.