#define gb_alloc_type(n,t,s) (t*) gb_alloc((n) *sizeof(t) ,s)  \

#define n_1 u.i \

#define arcs_per_block 102 \

#define string_block_size 1016 \

#define hash_link u.v
#define hash_head v.v \

#define HASH_MULT 314159
#define HASH_PRIME 516595003 \

/*3:*/
#line 39 "gb_graph.w"

#include <stdio.h>
#include <stdlib.h>
#ifdef SYSV
#include <string.h>
#else
#include <strings.h>
#endif
/*8:*/
#line 125 "gb_graph.w"

typedef union{
struct vertex_struct*v;
struct arc_struct*a;
struct graph_struct*g;
char*s;
long i;
}util;

/*:8*//*9:*/
#line 151 "gb_graph.w"

typedef struct vertex_struct{
struct arc_struct*arcs;
char*name;
util u,v,w,x,y,z;
}Vertex;

/*:9*//*10:*/
#line 170 "gb_graph.w"

typedef struct arc_struct{
struct vertex_struct*tip;
struct arc_struct*next;
long len;
util a,b;
}Arc;

/*:10*//*12:*/
#line 223 "gb_graph.w"

#define init_area(s)  *s= NULL
struct area_pointers{
char*first;
struct area_pointers*next;

};

typedef struct area_pointers*Area[1];

/*:12*//*20:*/
#line 350 "gb_graph.w"

#define ID_FIELD_SIZE 161
typedef struct graph_struct{
Vertex*vertices;
long n;
long m;
char id[ID_FIELD_SIZE];
char format[15];
Area data;
Area aux_data;
util u,v,w,x,y,z;
}Graph;

/*:20*/
#line 46 "gb_graph.w"

/*28:*/
#line 492 "gb_graph.w"

static Arc*next_arc;
static Arc*bad_arc;
static char*next_string;
static char*bad_string;
static Arc dummy_arc[2];
static Graph dummy_graph;
static Graph*cur_graph= &dummy_graph;

/*:28*/
#line 47 "gb_graph.w"

/*5:*/
#line 69 "gb_graph.w"

int verbose= 0;
int panic_code= 0;

/*:5*//*14:*/
#line 268 "gb_graph.w"

int gb_alloc_trouble= 0;

/*:14*//*24:*/
#line 443 "gb_graph.w"

int extra_n= 4;
char null_string[1];

/*:24*//*32:*/
#line 621 "gb_graph.w"

unsigned long edge_trick= sizeof(Arc)-(sizeof(Arc)&(sizeof(Arc)-1));

/*:32*/
#line 48 "gb_graph.w"

/*13:*/
#line 246 "gb_graph.w"

char*gb_alloc(n,s)
long n;
Area s;
{int m= sizeof(char*);
Area t;
char*loc;
if(n<=0||n>0xffff00-2*m){
gb_alloc_trouble|= 2;
return NULL;
}
n= ((n+m-1)/m)*m;
loc= (char*)calloc((unsigned)((n+2*m+255)/256),256);
if(loc){
*t= (struct area_pointers*)(loc+n);
(*t)->first= loc;
(*t)->next= *s;
*s= *t;
}else gb_alloc_trouble|= 1;
return loc;
}

/*:13*//*16:*/
#line 277 "gb_graph.w"

void gb_free(s)
Area s;
{Area t;
while(*s){
*t= (*s)->next;
free((*s)->first);
*s= *t;
}
}

/*:16*//*23:*/
#line 416 "gb_graph.w"

Graph*gb_new_graph(n)
long n;
{
cur_graph= (Graph*)calloc(1,sizeof(Graph));
if(cur_graph){
cur_graph->vertices= gb_alloc_type(n+extra_n,Vertex,cur_graph->data);
if(cur_graph->vertices){Vertex*p;
cur_graph->n= n;
for(p= cur_graph->vertices+n+extra_n-1;p>=cur_graph->vertices;p--)
p->name= null_string;
sprintf(cur_graph->id,"gb_new_graph(%ld)",n);
strcpy(cur_graph->format,"ZZZZZZZZZZZZZZ");
}else{
free(cur_graph);
cur_graph= NULL;
}
}
next_arc= bad_arc= NULL;
next_string= bad_string= NULL;
gb_alloc_trouble= 0;
return cur_graph;
}

/*:23*//*27:*/
#line 458 "gb_graph.w"

make_compound_id(g,s1,gg,s2)
Graph*g;
char*s1;
Graph*gg;
char*s2;
{int avail= ID_FIELD_SIZE-strlen(s1)-strlen(s2);
char tmp[ID_FIELD_SIZE];
strcpy(tmp,gg->id);
if(strlen(tmp)<avail)sprintf(g->id,"%s%s%s",s1,tmp,s2);
else sprintf(g->id,"%s%.*s...)%s",s1,avail-5,tmp,s2);
}

make_double_compound_id(g,s1,gg,s2,ggg,s3)

Graph*g;
char*s1;
Graph*gg;
char*s2;
Graph*ggg;
char*s3;
{int avail= ID_FIELD_SIZE-strlen(s1)-strlen(s2)-strlen(s3);
if(strlen(gg->id)+strlen(ggg->id)<avail)
sprintf(g->id,"%s%s%s%s%s",s1,gg->id,s2,ggg->id,s3);
else sprintf(g->id,"%s%.*s...)%s%.*s...)%s",s1,avail/2-5,gg->id,
s2,(avail-9)/2,ggg->id,s3);
}

/*:27*//*29:*/
#line 521 "gb_graph.w"

Arc*gb_virgin_arc()
{register Arc*cur_arc= next_arc;
if(cur_arc==bad_arc){
cur_arc= gb_alloc_type(arcs_per_block,Arc,cur_graph->data);
if(cur_arc==NULL)
cur_arc= dummy_arc;
else{
next_arc= cur_arc+1;
bad_arc= cur_arc+arcs_per_block;
}
}
else next_arc++;
return cur_arc;
}

/*:29*//*30:*/
#line 553 "gb_graph.w"

void gb_new_arc(u,v,len)
Vertex*u,*v;
long len;
{register Arc*cur_arc= gb_virgin_arc();
cur_arc->tip= v;cur_arc->next= u->arcs;cur_arc->len= len;
u->arcs= cur_arc;
cur_graph->m++;
}

/*:30*//*31:*/
#line 594 "gb_graph.w"

void gb_new_edge(u,v,len)
Vertex*u,*v;
long len;
{register Arc*cur_arc= gb_virgin_arc();
if(cur_arc!=dummy_arc)next_arc++;
if(u<v){
cur_arc->tip= v;cur_arc->next= u->arcs;
(cur_arc+1)->tip= u;(cur_arc+1)->next= v->arcs;
u->arcs= cur_arc;v->arcs= cur_arc+1;
}else{
(cur_arc+1)->tip= v;(cur_arc+1)->next= u->arcs;
u->arcs= cur_arc+1;
cur_arc->tip= u;cur_arc->next= v->arcs;
v->arcs= cur_arc;
}
cur_arc->len= (cur_arc+1)->len= len;
cur_graph->m+= 2;
}

/*:31*//*34:*/
#line 643 "gb_graph.w"

char*gb_save_string(s)
register char*s;
{register char*p= s;
register long len;
while(*p++);
len= p-s;
p= next_string;
if(p+len>bad_string){
long size= string_block_size;
if(len>size)
size= len;
p= gb_alloc(size,cur_graph->data);
if(p==NULL)
return null_string;
bad_string= p+size;
}
while(*s)*p++= *s++;
*p++= '\0';
next_string= p;
return p-len;
}

/*:34*//*38:*/
#line 725 "gb_graph.w"

void switch_to_graph(g)
Graph*g;
{
cur_graph->w.a= next_arc;cur_graph->x.a= bad_arc;
cur_graph->y.s= next_string;cur_graph->z.s= bad_string;
cur_graph= (g?g:&dummy_graph);
next_arc= cur_graph->w.a;bad_arc= cur_graph->x.a;
next_string= cur_graph->y.s;bad_string= cur_graph->z.s;
cur_graph->w.a= NULL;
cur_graph->x.a= NULL;
cur_graph->y.s= NULL;
cur_graph->z.s= NULL;
}

/*:38*//*39:*/
#line 743 "gb_graph.w"

void gb_recycle(g)
Graph*g;
{
if(g){
gb_free(g->data);
gb_free(g->aux_data);
free(g);
}
}

/*:39*//*43:*/
#line 805 "gb_graph.w"

void hash_in(v)
Vertex*v;
{register char*t= v->name;
register Vertex*u;
/*44:*/
#line 830 "gb_graph.w"

{register int h;
for(h= 0;*t;t++){
h+= (h^(h>>1))+HASH_MULT*(unsigned char)*t;
while(h>=HASH_PRIME)h-= HASH_PRIME;
}
u= cur_graph->vertices+(h%cur_graph->n);
}

/*:44*/
#line 810 "gb_graph.w"
;
v->hash_link= u->hash_head;
u->hash_head= v;
}

/*:43*//*45:*/
#line 845 "gb_graph.w"

Vertex*hash_out(s)
char*s;
{register char*t= s;
register Vertex*u;
/*44:*/
#line 830 "gb_graph.w"

{register int h;
for(h= 0;*t;t++){
h+= (h^(h>>1))+HASH_MULT*(unsigned char)*t;
while(h>=HASH_PRIME)h-= HASH_PRIME;
}
u= cur_graph->vertices+(h%cur_graph->n);
}

/*:44*/
#line 850 "gb_graph.w"
;
for(u= u->hash_head;u;u= u->hash_link)
if(strcmp(s,u->name)==0)return u;
return NULL;
}

/*:45*//*46:*/
#line 856 "gb_graph.w"

void hash_setup(g)
Graph*g;
{Graph*save_cur_graph;
if(g&&g->n>0){register Vertex*v;
save_cur_graph= cur_graph;
cur_graph= g;
for(v= g->vertices;v<g->vertices+g->n;v++)v->hash_head= NULL;
for(v= g->vertices;v<g->vertices+g->n;v++)hash_in(v);
*(g->format)= *(g->format+1)= 'V';

cur_graph= save_cur_graph;
}
}

/*:46*//*47:*/
#line 871 "gb_graph.w"

Vertex*hash_lookup(s,g)
char*s;
Graph*g;
{Graph*save_cur_graph;
if(g&&g->n>0){register Vertex*v;
save_cur_graph= cur_graph;
cur_graph= g;
v= hash_out(s);
cur_graph= save_cur_graph;
return v;
}
else return NULL;
}

/*:47*/
#line 49 "gb_graph.w"


/*:3*/