path: root/support/graphbase/test_sample.w

% 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.