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!
5
\def\title{TEST\_\,SAMPLE}
7
@* Introduction. This GraphBase program is intended to be used only
8
when the Stanford GraphBase is being installed. It invokes the
9
most critical subroutines and creates a file that can be checked
10
against the correct output.
11
The testing is not exhaustive by any means, but it is designed to detect
12
errors of portability---cases where different results might occur
13
on different systems. Thus, if nothing goes wrong, one can assume that
14
the GraphBase routines are probably installed satisfactorily.
16
The basic idea of {\sc TEST\_\,SAMPLE} is quite simple: We generate a graph,
17
then print out a few of its salient characteristics. Then we recycle
18
the graph and generate another, etc. The test is passed if the output
19
file matches a ``correct'' output file generated at Stanford by the author.
21
Actually there are two output files. The main one, containing samples of
22
graph characteristics, is the standard output. The other, called \.{test.gb},
23
is a graph that has been saved in ASCII format with |save_graph|.
26
#include "gb_graph.h" /* we use the {\sc GB\_\,GRAPH} data structures */
27
#include "gb_io.h" /* and the GraphBase input/output routines */
28
@<Include headers for all of the GraphBase generation modules@>@;
30
@<Private variables@>@;
33
{@+Graph *g,*gg;@+long i;@+Vertex *v; /* temporary registers */
34
printf("GraphBase samples generated by test_sample:\n");
35
@<Save a graph to be restored later@>;
36
@<Print samples of generated graphs@>;
37
return 0; /* normal exit */
40
@ @<Include headers for all of the GraphBase generation modules@>=
41
#include "gb_basic.h" /* we test the basic graph operations */
42
#include "gb_books.h" /* and the graphs based on literature */
43
#include "gb_econ.h" /* and the graphs based on economic data */
44
#include "gb_games.h" /* and the graphs based on football scores */
45
#include "gb_gates.h" /* and the graphs based on logic circuits */
46
#include "gb_lisa.h" /* and the graphs based on Mona Lisa */
47
#include "gb_miles.h" /* and the graphs based on mileage data */
48
#include "gb_plane.h" /* and the planar graphs */
49
#include "gb_raman.h" /* and the Ramanujan graphs */
50
#include "gb_rand.h" /* and the random graphs */
51
#include "gb_roget.h" /* and the graphs based on Roget's Thesaurus */
52
#include "gb_save.h" /* and we save results in ASCII format */
53
#include "gb_words.h" /* and we also test five-letter-word graphs */
55
@ The subroutine |print_sample(g,n)| will be specified later. It prints global
56
characteristics of |g| and local characteristics of the |n|th vertex.
58
We begin the test cautiously by generating a graph that requires no input data
59
and no pseudo-random numbers. If this test fails, the fault must lie either in
60
{\sc GB\_\,GRAPH} or {\sc GB\_\,RAMAN}.
62
@<Print samples of generated graphs@>=
63
print_sample(raman(31L,3L,0L,4L),4);
65
@ Next we test part of {\sc GB\_\,BASIC} that relies on a particular
66
interpretation of the operation `|w>>=1|'. If this part of the test
67
fails, please look up `system dependencies' in the index to {\sc
68
GB\_\,BASIC}, and correct the problem on your system by making a change file
69
\.{gb\_basic.ch}. (See \.{queen\_wrap.ch} for an example of a change file.)
71
On the other hand, if {\sc TEST\_\,SAMPLE} fails only in this particular test
72
while passing all those that follow, chances are excellent that
73
you have a pretty good implementation of the GraphBase anyway,
74
because the bug detected here will rarely show up in practice. Ask
75
yourself: Can I live comfortably with such a bug?
77
@<Print samples of generated graphs@>=
78
print_sample(board(1L,1L,2L,-33L,1L,-0x40000000L-0x40000000L,1L),2000);
79
/* coordinates 32 and 33 (only) should wrap around */
81
@ Another system-dependent part of {\sc GB\_\,BASIC} is tested here,
82
this time involving character codes.
84
@<Print samples of generated graphs@>=
85
print_sample(subsets(32L,18L,16L,0L,999L,-999L,0x80000000L,1L),1);
87
@ If \.{test.gb} fails to match \.{test.correct}, the most likely culprit
88
is |vert_offset|, a ``pointer hack'' in {\sc GB\_\,BASIC}. That macro
89
absolutely must be made to work properly, because it is used heavily.
90
In particular, it is used in the |complement| routine tested here,
91
and in the |gunion| routine tested below.
93
@<Save a graph to be restored later@>=
94
g=random_graph(3L,10L,1L,1L,0L,NULL,dst,1L,2L,1L);
95
/* a random multigraph with 3 vertices, 10 edges */
96
gg=complement(g,1L,1L,0L); /* a copy of |g|, without multiple edges */
97
v=gb_typed_alloc(1,Vertex,gg->data); /* we create a stray vertex too */
98
v->name=gb_save_string("Testing");
99
gg->util_types[10]='V';
100
gg->ww.V=v; /* the stray vertex is now part of |gg| */
101
save_graph(gg,"test.gb"); /* so it will appear in \.{test.gb} (we hope) */
102
gb_recycle(g);@+gb_recycle(gg);
105
static long dst[]={0x20000000,0x10000000,0x10000000};
106
/* a probability distribution with frequencies 50\%, 25\%, 25\% */
108
@ Now we try to reconstruct the graph we saved before, and we also randomize
111
@<Print samples...@>=
112
g=restore_graph("test.gb");
113
if (i=random_lengths(g,0L,10L,12L,dst,2L))
114
printf("\nFailure code %ld returned by random_lengths!\n",i);
116
gg=random_graph(3L,10L,1L,1L,0L,NULL,dst,1L,2L,1L); /* same as before */
117
print_sample(gunion(g,gg,1L,0L),2);
118
gb_recycle(g);@+gb_recycle(gg);
121
@ Partial evaluation of a RISC circuit involves fairly intricate pointer
122
manipulation, so this step should help to test the portability of the author's
123
favorite programming tricks.
125
@<Print samples...@>=
126
print_sample(partial_gates(risc(0L),1L,43210L,98765L,NULL),79);
128
@ Now we're ready to test the mechanics of reading data files,
129
sorting with {\sc GB\_\,SORT}, and heavy randomization. Lots of computation
130
takes place in this section.
133
print_sample(book("homer",500L,400L,2L,12L,10000L,-123456L,789L),81);
134
print_sample(econ(40L,0L,400L,-111L),11);
135
print_sample(games(60L,70L,80L,-90L,-101L,60L,0L,999999999L),14);
136
print_sample(miles(50L,-500L,100L,1L,500L,5L,314159L),20);
137
print_sample(plane_lisa(100L,100L,50L,1L,300L,1L,200L,
138
50L*299L*199L,200L*299L*199L),1294);
139
print_sample(plane_miles(50L,500L,-100L,1L,1L,40000L,271818L),14);
140
print_sample(random_bigraph(300L,3L,1000L,-1L,0L,dst,-500L,500L,666L),3);
141
print_sample(roget(1000L,3L,1009L,1009L),40);
143
@ Finally, here's a picky, picky test that is supposed to fail the first time,
144
succeed the second. (The weight vector just barely exceeds
145
the maximum weight threshold allowed by {\sc GB\_WORDS}. That test is
146
ultraconservative, but eminently reasonable nevertheless.)
148
@<Print samples...@>=
149
print_sample(words(100L,wt_vector,70000000L,69L),5);
151
print_sample(words(100L,wt_vector,70000000L,69L),5);
152
print_sample(words(0L,NULL,0L,69L),5555);
155
static long wt_vector[]=
156
{100,-80589,50000,18935,-18935,18935,18935,18935,18935};
158
@* Printing the sample data. Given a graph |g| in GraphBase format and
159
an integer~|n|, the subroutine |print_sample(g,n)| will output
160
global characteristics of~|g|, such as its name and size, together with
161
detailed information about its |n|th vertex. Then |g| will be shredded
162
and recycled; the calling routine should not refer to it again.
165
static void pr_vert();
166
/* a subroutine for printing a vertex is declared below */
167
static void pr_arc(); /* likewise for arcs */
168
static void pr_util(); /* and for utility fields in general */
169
static void print_sample(g,n)
170
Graph *g; /* graph to be sampled and destroyed */
171
int n; /* index to the sampled vertex */
175
printf("Ooops, we just ran into panic code %ld!\n",panic_code);
177
printf("(The I/O error code is 0x%lx)\n",(unsigned long)io_errors);
179
@<Print global characteristics of |g|@>;
180
@<Print information about the |n|th vertex@>;
185
@ The graph's |util_types| are used to determine how much information
186
should be printed. A level parameter also helps control the verbosity of
187
printout. In the most verbose mode, each utility field that points to a
188
vertex or arc, or contains integer or string data, will be printed.
191
static void pr_vert(v,l,s)
192
Vertex *v; /* vertex to be printed */
193
int l; /* |<=0| if the output should be terse */
194
char *s; /* format for graph utility fields */
196
if (v==NULL) printf("NULL");
197
else if (is_boolean(v)) printf("ONE"); /* see {\sc GB\_\,GATES} */
199
printf("\"%s\"",v->name);
200
pr_util(v->u,s[0],l-1,s);
201
pr_util(v->v,s[1],l-1,s);
202
pr_util(v->w,s[2],l-1,s);
203
pr_util(v->x,s[3],l-1,s);
204
pr_util(v->y,s[4],l-1,s);
205
pr_util(v->z,s[5],l-1,s);
206
if (l>0) {@+register Arc *a;
207
for (a=v->arcs;a;a=a->next) {
216
static void pr_arc(a,l,s)
217
Arc *a; /* non-null arc to be printed */
218
int l; /* |<=0| if the output should be terse */
219
char *s; /* format for graph utility fields */
224
printf( ", %ld",a->len);
225
pr_util(a->a,s[6],l-1,s);
226
pr_util(a->b,s[7],l-1,s);
231
static void pr_util(u,c,l,s)
232
util u; /* a utility field to be printed */
233
char c; /* its type code */
234
int l; /* 0 if output should be terse, |-1| if pointers omitted */
235
char *s; /* utility types for overall graph */
238
case 'I': printf("[%ld]",u.I);@+break;
239
case 'S': printf("[\"%s\"]",u.S?u.S:"(null)");@+break;
240
case 'A': if (l<0) break;
242
if (u.A==NULL) printf("NULL");
243
else pr_arc(u.A,l,s);
246
case 'V': if (l<0) break; /* avoid infinite recursion */
250
default: break; /* case |'Z'| does nothing, other cases won't occur */
254
@ @<Print information about the |n|th vertex@>=
256
if (n>=g->n || n<0) printf("index is out of range!\n");
258
pr_vert(g->vertices+n,1,g->util_types);
262
@ @<Print global characteristics of |g|@>=
263
printf("\"%s\"\n%ld vertices, %ld arcs, util_types %s",
264
g->id,g->n,g->m,g->util_types);
265
pr_util(g->uu,g->util_types[8],0,g->util_types);
266
pr_util(g->vv,g->util_types[9],0,g->util_types);
267
pr_util(g->ww,g->util_types[10],0,g->util_types);
268
pr_util(g->xx,g->util_types[11],0,g->util_types);
269
pr_util(g->yy,g->util_types[12],0,g->util_types);
270
pr_util(g->zz,g->util_types[13],0,g->util_types);
273
@* Index. We end with the customary list of identifiers, showing where
274
they are used and where they are defined.
added
removed
test_sample.w
