summaryrefslogtreecommitdiff
path: root/support/graphbase/test_sample.w
blob: c5ddb6cccc5e047f50aba642fa87819dcc0d8c89 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
% This file is part of the Stanford GraphBase (c) Stanford University 1992
\def\title{TEST\_\thinspace SAMPLE}
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!

@* Introduction. This GraphBase program is intended to be used only
when the Stanford GraphBase is being installed. It invokes the
most critical subroutines and creates a file that can be checked
against the correct output.
The testing is not by any means exhaustive, but it is designed to detect
errors of portability, i.e., cases where different results might occur
on different systems. Thus, if nothing goes wrong, one can assume that
the GraphBase routines are probably installed satisfactorily.

The basic idea of |test_sample| is quite simple: We generate a graph,
then print out a few of its salient characteristics. Then we recycle
the graph and generate another, etc. The test is passed if the output
file matches a ``correct'' output file generated at Stanford by the author.

Actually there are two output files. The main one, containing samples of
graph characteristics, is the standard output. The other, called \.{test.gb},
is a graph that has been saved in ASCII format with |save_graph|.

@f Graph int /* |gb_graph| defines the |Graph| type and a few others */
@f Vertex int
@f Area int
@f Arc int

@p
#include "gb_graph.h" /* we use the |gb_graph| data structures */
#include "gb_io.h" /* and the GraphBase input/output routines */
@<Include headers for all of the GraphBase generation modules@>@;
@#
@<Private variables@>@;
@<Procedures@>@;
main()
{@+Graph *g,*gg;@+int i;@+Vertex *v; /* temporary registers */
  printf("GraphBase samples generated by test_sample:\n");
  @<Save a graph to be restored later@>;
  @<Print samples of generated graphs@>;
}

@ @<Include headers for all of the GraphBase generation modules@>=
#include "gb_basic.h" /* we test the basic graph operations */
#include "gb_books.h" /* and the graphs based on literature */
#include "gb_econ.h" /* and the graphs based on economic data */
#include "gb_games.h" /* and the graphs based on football scores */
#include "gb_gates.h" /* and the graphs based on logic circuits */
#include "gb_miles.h" /* and the graphs based on mileage data */
#include "gb_mona.h" /* and the graphs based on Mona Lisa */
#include "gb_plane.h" /* and the planar graphs */
#include "gb_raman.h" /* and the Ramanujan graphs */
#include "gb_rand.h" /* and the random graphs */
#include "gb_roget.h" /* and the graphs based on Roget's Thesaurus */
#include "gb_save.h" /* and we save results in ASCII format */
#include "gb_words.h" /* and we also test five-letter-word graphs */

@ The subroutine |print_sample(g,n)| will be specified later. It prints global
characteristics of |g| and local characteristics of vertex |g->vertices+n|.

We begin the test cautiously by generating a graph that requires no input data
and no pseudorandom numbers. If this test fails, the fault must lie either in
|gb_graph| or |gb_raman|.

@<Print samples of generated graphs@>=
print_sample(raman(31,3,0,4),4);

@ Next we test part of |gb_basic| that relies on a particular interpretation
of the operation `|w>>=1|'. If this part of the test fails, please look up
`system dependencies' in the index to |gb_basic|, and correct the
problem on your system by making a change file \.{gb\_basic.ch}. (See
\.{queen\_wrap.ch} for an example of a change file.)

On the other hand, if |test_sample| fails only in this particular test
while passing all those that follow, chances are excellent that
you have a pretty good implementation of the GraphBase anyway,
because the bug detected here will rarely show up in practice. Ask
yourself: Can I live comfortably with such a bug?

@<Print samples of generated graphs@>=
print_sample(board(1,1,2,-33,1,-0x40000000-0x40000000,1),2000);
  /* coordinates 32 and 33 (only) should wrap around */

@ Another system-dependent part of |gb_basic| is tested here.

@<Print samples of generated graphs@>=
print_sample(subsets(32,18,16,0,999,-999,0x80000000,1),1);

@ If \.{test.gb} fails to match \.{test.correct}, the most likely culprit
is |vert_offset|, a ``pointer hack'' in |gb_basic|. That macro absolutely
has to be made to work properly, because it is used heavily.

@<Save a graph to be restored later@>=
  g=random_graph(3,10,1,1,0,NULL,dst,1,2,1);
  gg=complement(g,1,1,0); /* a copy of |g| */
  v=gb_alloc_type(1,@[Vertex@],gg->data); /* create a stray vertex too */
  v->name=gb_save_string("Testing");
  gg->format[10]='V';
  gg->w.v=v; /* the stray vertex is now part of |gg| */
  save_graph(gg,"test.gb"); /* so it will appear in \.{test.gb} (we hope) */
  gb_recycle(g);@+gb_recycle(gg);

@ @<Private...@>=
static long dst[]={0x20000000,0x10000000,0x10000000};
 /* a probability distribution with frequencies 50\%, 25\%, 25\% */

@ Now we try to reconstruct the graph we saved before, and randomize
its lengths.

@<Print samples...@>=
g=restore_graph("test.gb");
if (i=random_lengths(g,0,10,12,dst,2))
  printf("\nFailure code %d returned by random_lengths!\n",i);
else {
  gg=random_graph(3,10,1,1,0,NULL,dst,1,2,1); /* same as before */
  print_sample(gunion(g,gg,1,0),2);
  gb_recycle(g);@+gb_recycle(gg);
}

@ Partial evaluation of a RISC circuit involves fairly intricate pointer
manipulation, so this should help test the portability of the author's
favorite tricks.

@<Print samples...@>=
print_sample(partial_gates(risc(0),1,43210,98765,NULL),79);

@ Now we're ready to test the mechanics of reading data files,
sorting with |gb_sort|, and heavy randomization. Lots of computation
takes place in this section.

@<Print samp...@>=
print_sample(book("homer",500,400,2,12,10000,-123456,789),81);
print_sample(econ(40,0,400,-111),11);
print_sample(games(60,70,80,-90,-101,60,0,999999999),14);
print_sample(miles(50,-500,100,1,500,5,314159),20);
print_sample(plane_mona(100,100,50,1,300,1,200,50*299*199,200*299*199),1294);
print_sample(plane_miles(50,500,-100,1,1,40000,271818),14);
print_sample(random_bigraph(300,3,1000,-1,0,dst,-500,500,666),3);
print_sample(roget(1000,3,1009,1009),40);

@ Finally, here's a picky, picky test that is supposed to fail the first time,
succeed the second. (The weight vector just barely exceeds
the maximum weight threshold allowed by |gb_words|. That test is
ultraconservative, but eminently reasonable nevertheless.)

@<Print samples...@>=
print_sample(words(100,wt_vector,70000000,69),5);
wt_vector[1]++;
print_sample(words(100,wt_vector,70000000,69),5);

@ @<Private...@>=
static int wt_vector[]=
  {100,-80589,50000,18935,-18935,18935,18935,18935,18935};

@* Printing the sample data. Given a graph |g| in GraphBase format and
an integer~|n|, the subroutine |print_sample(g,n)| will output
global characteristics of~|g|, such as its name and size, together with
detailed information about its |n|th vertex. Then |g| will be recycled.

@<Procedures@>=
void print_vert(); /* a subroutine for printing a vertex is declared below */
void print_arc(); /* likewise for arcs */
void print_util(); /* and for utility fields in general */
void print_sample(g,n)
  Graph *g; /* graph to be sampled and destroyed */
  int n; /* index to the sampled vertex */
{
  printf("\n");
  if (g==NULL) {
    printf("Ooops, we just ran into panic code %d!\n",panic_code);
    if (io_errors)
      printf("(The I/O error code is 0x%x)\n",io_errors);
  } else {
    @<Print global characteristics of |g|@>;
    @<Print information about the |n|th vertex@>;
    gb_recycle(g);
  }
}

@ The graph's |format| field is used to determine how much information
should be printed. A level parameter also helps control the verbosity of
printout. In the most verbose mode, each utility field that points to a
vertex or arc or contains integer or string data will be printed.

@<Procedures@>=
void print_vert(v,l,s)
  Vertex *v; /* vertex to be printed */
  int l; /* |<=0| if the output should be terse */
  char *s; /* format for graph utility fields */
{
  if (v==NULL) printf("NULL");
  else if (is_boolean(v)) printf("ONE"); /* see |gb_gates| */
  else {
    printf("\"%s\"",v->name);
    print_util(v->u,s[0],l-1,s);
    print_util(v->v,s[1],l-1,s);
    print_util(v->w,s[2],l-1,s);
    print_util(v->x,s[3],l-1,s);
    print_util(v->y,s[4],l-1,s);
    print_util(v->z,s[5],l-1,s);
    if (l>0) {@+register Arc *a;
      for (a=v->arcs;a;a=a->next) {
        printf("\n   ");
        print_arc(a,1,s);
      }
    }
  }
}

@ @<Pro...@>=
void print_arc(a,l,s)
  Arc *a; /* non-null arc to be printed */
  int l; /* |<=0| if the output should be terse */
  char *s; /* format for graph utility fields */
{
  printf("->");
  print_vert(a->tip,0,s);
  if (l>0) {
    printf( ", %d",a->len);
    print_util(a->a,s[6],l-1,s);
    print_util(a->b,s[7],l-1,s);
  }
}

@ @<Procedures@>=
void print_util(u,c,l,s)
  util u; /* a utility field to be printed */
  char c; /* its format code */
  int l; /* 0 if output should be terse, |-1| if pointers omitted */
  char *s; /* format for overall graph */
{
  switch (c) {
  case 'I': printf("[%d]",u.i);@+break;
  case 'S': printf("[\"%s\"]",u.s);@+break;
  case 'A': if (l<0) break;
    printf("[");
    if (u.a==NULL) printf("NULL");
    else print_arc(u.a,l,s);
    printf("]");
    break;
  case 'V': if (l<0) break; /* avoid infinite recursion */
    printf("[");
    print_vert(u.v,l,s);
    printf("]");
  default: break; /* case |'Z'| does nothing, other cases won't occur */
  }
}

@ @<Print information about the |n|th vertex@>=
printf("V%d: ",n);
if (n>g->n || n<0) printf("index is out of range!\n");
else {
  print_vert(g->vertices+n,1,g->format);
  printf("\n");
}

@ @<Print global characteristics of |g|@>=
printf("\"%s\"\n%d vertices, %d arcs, format %s",
      g->id,g->n,g->m,g->format);
print_util(g->u,g->format[8],0,g->format);
print_util(g->v,g->format[9],0,g->format);
print_util(g->w,g->format[10],0,g->format);
print_util(g->x,g->format[11],0,g->format);
print_util(g->y,g->format[12],0,g->format);
print_util(g->z,g->format[13],0,g->format);
printf("\n");

@* Index.