\datethis @i gb_types.w \input epsf @* Introduction. This program takes an algebraic specification of a series-parallel graph and converts it to Stanford GraphBase format. The given graph is specified using a simple right-Polish syntax $$ G\,\to\,\.-\,\mid\,G\,G\,\,\.s\,\mid\,G\,G\,\,\.p $$ so that, for example, the specifications \.{----ps-sp--sp} and \.{----p-ss--spp} both denote the graph $$ \epsfbox{spspan.1} $$ (The conventions are identical to those of {\mc SPSPAN}, so that I can compare that program with {\mc GRAYSPAN}.) @c #include "gb_graph.h" #include "gb_save.h" @h@# @@; @@; main (int argc, char*argv[]) { register int j,k; if (argc!=3) { fprintf(stderr,"Usage: %s SPformula foo.gb\n", argv[0]);@+ exit(0); } @; @; k=save_graph(g,argv[2]); if (k) printf("I had trouble saving in %s (anomalies %x)!\n",argv[2],k); else printf("Graph %s saved successfully in %s.\n",g->id,argv[2]); } @ In the following code, we have scanned $j$ binary operators (including |jj| of type \.s) and there are $k$~items on the stack. @d abort(mess) {@+fprintf(stderr,"Parsing error: %.*s|%s, %s!\n", p-argv[1],argv[1],p,mess);@+exit(-1);@+} @= { register char*p=argv[1]; for (j=k=0; *p; p++) if (*p=='-') @@; else if (*p=='s' || *p=='p') @@; else abort("bad symbol"); if (k!=1) abort("disconnected graph"); } @ @d maxn 1000 /* the maximum number of leaves; {\it not checked\/} */ @= int stack[maxn]; /* stack for parsing */ int llink[maxn],rlink[maxn]; /* binary subtrees */ char buffer[8]; /* for sprinting */ int jj; Graph *g; @ @= stack[k++]=0; @ @= { if (k<2) abort("missing operand"); rlink[++j]=stack[--k]; llink[j]=stack[k-1]; if (*p=='s') jj++; stack[k-1]=(*p=='s'? 0x100: 0)+j; } @ Now we convert the binary tree to the desired graph, working top down. @d vert(k) (g->vertices+(k)) @= g=gb_new_graph(jj+2); if (!g) { fprintf(stderr,"Can't create the graph!\n"); exit(-1); } sprintf(g->id,"SP%.152s",argv[1]); for (k=0;kn;k++) { sprintf(buffer,"v%d",k); vert(k)->name=gb_save_string(buffer); } build(stack[0],0,1); @ A recursive subroutine called |build| governs the construction process. @= void build(int stackitem, int lft, int rt) { register int t,j; if (stackitem==0) gb_new_edge(vert(lft),vert(rt),0); else { t=stackitem>>8, j=stackitem&0xff; /* type and location of a binary op */ if (t) t=--jj+2,build(llink[j],lft,t),build(rlink[j],t,rt); else build(llink[j],lft,rt),build(rlink[j],lft,rt); } } @*Index.