diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /support/graphbase/gb_graph.w |
Initial commit
Diffstat (limited to 'support/graphbase/gb_graph.w')
-rw-r--r-- | support/graphbase/gb_graph.w | 887 |
1 files changed, 887 insertions, 0 deletions
diff --git a/support/graphbase/gb_graph.w b/support/graphbase/gb_graph.w new file mode 100644 index 0000000000..1f047b1064 --- /dev/null +++ b/support/graphbase/gb_graph.w @@ -0,0 +1,887 @@ +% This file is part of the St588anford GraphBase (c) Stanford University 1992 +\def\title{GB\_\thinspace GRAPH} +@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES! + +@* Introduction. This is |gb_graph|, the data-structure module used by all +GraphBase routines to allocate memory. The basic data types for graph +representation are also defined here. + +Many examples of how to use these conventions appear in other GraphBase +modules. The best introduction to such examples can probably be found +in |gb_basic|, which contains subroutines for generating and transforming +various classical graphs. + +@ The code below is believed to be system-independent; it should +produce equivalent results on all systems, assuming that the standard +|calloc| and |cfree| functions of \Cee\ are available. + +However, a test program helps build confidence that everything does in fact +work as it should. To make such a test, simply compile and run |test_graph|. +This particular test is fairly rudimentary, but it should be passed before +more elaborate routines are tested. + +@(test_graph.c@>= +#include "gb_graph.h" /* all users of |gb_graph| should do this */ +@<Declarations of test variables@>@; +@# +main() +{ + @<Create a small graph@>; + @<Test some intentional errors@>; + @<Check that the small graph is still there@>; + printf("OK, the gb_graph routines seem to work!\n"); +} + +@ The \Cee\ code for |gb_graph| doesn't have a main routine; it's just a +bunch of subroutines to be incorporated into programs at a higher level, +via the system loading routine. Here is the general outline of \.{gb\_graph.c}: + +@p +#include <stdio.h> +#ifdef SYSV +#include <string.h> +#else +#include <strings.h> +#endif +@<Type declarations@>@; +@<Private declarations@>@; +@<External declarations@>@; +@<External functions@> + +@ The type declarations of |gb_graph| appear also in the header file +\.{gb\_graph.h}. For convenience, that header file also incorporates the +standard system headers for input/output and string manipulation. + +@(gb_graph.h@>= +#include <stdio.h> +#ifdef SYSV +#include <string.h> +#else +#include <strings.h> +#endif +@<Type declarations@>@; + +@ GraphBase programs often have a ``verbose'' option, which needs to +be enabled by the setting of an external variable. They also tend to have +a variable called |panic_code|, which helps identify unusual errors. +We might as well declare those variables here. + +@<External d...@>= +int verbose=0; /* nonzero if ``verbose'' output is desired */ +int panic_code=0; /* set nonzero if graph generator returns null pointer */ + +@ Every external variable should be declared twice in this \.{CWEB} file; +once for |gb_graph| itself (the ``real'' declaration for storage allocation +purposes), and once in \.{gb\_graph.h} (for cross-references by +|gb_graph| users). + +@(gb_graph.h@>= +extern int verbose; /* nonzero if ``verbose'' output is desired */ +extern int panic_code; /* set nonzero if graph generator panics */ + +@ When |panic_code| is assigned a nonzero value, one of the symbolic +names defined here is used to help pinpoint the problem. +Small values indicate memory limitations; values in the 10s and 20s +indicate input/output anomalies; values in the 30s and 40s indicate +errors in the parameters to a subroutine. Some panic codes +stand for cases the author doesn't think will ever arise, although +the program checks for them just to be extra safe. Multiple instances +of the same type of error within a single subroutine are distinguished +by adding an integer; for example, `|syntax_error+1|' and `|syntax_error+2|' +identify two different kinds of syntax error, as an aid in trouble-shooting. +The |early_data_fault| and |late_data_fault| codes are explained further +by the value of |io_errors|. + +@(gb_graph.h@>= +#define alloc_fault -1 /* a previous memory request failed */ +#define no_room 1 /* the current memory request failed */ +#define early_data_fault 10 /* error detected at beginning of \.{.dat} file */ +#define late_data_fault 11 /* error detected at end of \.{.dat} file */ +#define syntax_error 20 /* error detected while reading \.{.dat} file */ +#define bad_specs 30 /* parameter out of range or otherwise disallowed */ +#define very_bad_specs 40 /* parameter far out of range or otherwise stupid */ +#define missing_operand 50 /* graph parameter is |NULL| */ +#define invalid_operand 60 /* graph parameter doesn't obey assumptions */ +#define impossible 666 /* ``this can't happen'' */ + +@* Representation of graphs. The GraphBase programs employ a simple and flexible +set of data structures to represent and manipulate graphs in computer memory. +Vertices appear in a sequential array of \&{Vertex} records, and the arcs +emanating from each vertex appear in a linked list of \&{Arc} records. There +is also a \&{Graph} record, to provide information about the graph as a whole. + +The structure layouts for \&{Vertex}, \&{Arc}, and \&{Graph} records +include a number of utility fields that can be used for any purpose by +algorithms that manipulate the graphs. Each utility field is a union +type that can be either a pointer of various kinds or a (long) integer. + +Let's begin the formal definition of these data structures by declaring the +union type \&{util}. The suffixes .|v|, .|a|, .|g|, and .|s| on the name +of a utility variable will mean that it is a pointer to a vertex, arc, +graph, or string, respectively; the suffix .|i| will mean that it is +an integer. (We use one-character names because such names are easy to type +when debugging.) + +@<Type dec...@>= +typedef union { + struct vertex_struct *v; /* pointer to \&{Vertex} */ + struct arc_struct *a; /* pointer to \&{Arc} */ + struct graph_struct *g; /* pointer to \&{Graph} */ + char *s; /* pointer to string */ + long i; /* integer */ +} util; + +@ Each \&{Vertex} has two standard fields and six utility fields; hence it +occupies 32 bytes on most systems, not counting the memory needed for +supplementary string data. The standard fields are +$$\vcenter{\halign{#,\ \ \hfil&#\hfil\cr +|arcs|&a pointer to an \&{Arc};\cr +|name|&a pointer to a string of characters.\cr}}$$ +If |v| points to a \&{Vertex} and |v->arcs| is |NULL|, there are no arcs +emanating from~|v|. But if |v->arcs| is non-|NULL|, it points to an \&{Arc} +record representing an arc from~|v|, and that record has a |next| field that +points in the same way to the representations of all other arcs from~|v|. + +The utility fields are called |u|, |v|, |w|, |x|, |y|, |z|. Macros can +be used to give them syntactic sugar in particular applications. They are +typically used to record such things as the in-degree or out-degree, or +whether a vertex is `marked'; or they link the vertex to other vertices in +one or more lists. + +@<Type dec...@>= +typedef struct vertex_struct { + struct arc_struct *arcs; /* linked list of arcs coming out of this vertex */ + char *name; /* string identifying this vertex symbolically */ + util u,v,w,x,y,z; /* multipurpose fields */ +} Vertex; + +@ Each \&{Arc} has three standard fields and two utility fields. Thus it +occupies 20~bytes on most computer systems. The standard fields are +$$\vcenter{\halign{#,\ \ \hfil&#\hfil\cr +|tip|&a pointer to a |Vertex|;\cr +|next|&a pointer to an \&{Arc};\cr +|len|&a (long) integer.\cr}}$$ +If |a| points to an \&{Arc} in the list of arcs from vertex~|v|, it represents +an arc of length |a->len| from |v| to |a->tip|, and the next arc from |v| +in the list is represented by |a->next|. + +The utility fields are called |a| and |b|. + +@<Type dec...@>= +typedef struct arc_struct { + struct vertex_struct *tip; /* the arc points to this vertex */ + struct arc_struct *next; /* another arc pointing from the same vertex */ + long len; /* length of this arc */ + util a,b; /* multipurpose fields */ +} Arc; + +@* Storage allocation. Memory space must be set aside dynamically for +vertices, arcs, and their attributes. The GraphBase routines provided by +|gb_graph| accomplish this task with reasonable ease and efficiency +by using the concept of memory ``areas.'' The user should first declare an +\&{Area} variable by saying, for example, +$$\hbox{\&{Area} |s|;}$$ +and if this variable isn't static or otherwise known to be zero, it must be +cleared initially by saying `|init_area(s)|'. Then any number of subroutine +calls of the form `|gb_alloc(n,s)|' can be given; |gb_alloc| +will return a pointer to a block of |n| consecutive bytes, all cleared to zero. +Finally, the user can issue the statement +$$\hbox{|gb_free(s)|;}$$ +this will return all memory blocks currently allocated to area~|s|, making them +available for future allocation. + +The number of bytes |n| specified to |gb_alloc| must be positive, and +it should usually be 1000 or more, since this will reduce the number +of system calls. Other routines are provided below to allocate smaller +amounts of memory, such as the space needed for a single new \&{Arc}. + +If no memory of the requested size is presently available, |gb_alloc| +returns the null pointer |NULL|. In such cases |gb_alloc| also sets +the external variable |gb_alloc_trouble| to a nonzero value. The user +can therefore discover whether any one of an arbitrarily long series +of allocation requests has failed by making a single test, `|if +(gb_alloc_trouble)|'. The value of |gb_alloc_trouble| should be cleared to zero +by every graph generation subroutine; therefore it need not be +initialized to zero. + +A special macro |gb_alloc_type(n,t,s)| makes it convenient to allocate +the space for |n| items of type~|t| in area~|s|. + +@d gb_alloc_type(n,t,s) @[(t*)@]gb_alloc((n)*@[sizeof@](t),s) + +@ The implementation of this scheme is almost ridiculously easy. The +value of~|n| is increased by twice the number of bytes in a pointer, +and the resulting number is rounded upwards if necessary so that it's +a multiple of 256. Then memory is allocated using |calloc|. The extra +bytes will contain two pointers, one to the beginning of the block and +one to the next block associated with the same area variable. + +The \&{Area} type is defined to be an array of length 1. This makes it possible +for users to say just `|s|' instead of `|&s|' when using an area +variable as a parameter. + +@<Type...@>= +#define init_area(s) @t\quad@> @[*s=NULL@] +struct area_pointers { + char *first; /* address of the beginning of this block */ + struct area_pointers *next; /* address of area pointers in previously + allocated block */ +}; + +typedef struct area_pointers *Area[1]; + +@ First we round |n| up, if necessary, so that it's a multiple of the +size of a pointer variable. Then we know we can put |area_pointers| into +memory at a position |n| after any address returned by |calloc|. (This +logic should work whenever the number of bytes in a pointer variable +is a divisor of~256.) + +The upper limit on |n| here is governed by old \Cee\ conventions in +which the first parameter to |calloc| must be less than~$2^{16}$. +Users who need graphs with more than half a million vertices might +want to raise this limit on their systems, but they would probably +be better off representing large graphs in a more compact way. +@^system dependencies@> + +@<External fun...@>= +char *gb_alloc(n,s) + long n; /* number of consecutive bytes desired */ + Area s; /* storage area that will contain the new block */ +{@+int m=sizeof(char *); /* |m| is the size of a pointer variable */ + Area t; /* a temporary pointer */ + char *loc; /* the block address */ + if (n<=0 || n>0xffff00 -2*m) { + gb_alloc_trouble|=2; /* illegal request */ + return NULL; + } + n=((n+m-1)/m)*m; /* round up to multiple of |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; +} + +@ @<External d...@>= +int gb_alloc_trouble=0; /* did |gb_alloc| return |NULL|? */ + +@ @(gb_graph.h@>= +extern int gb_alloc_trouble; /* anomalies noted by |gb_alloc| */ + +@ Notice that |gb_free(s)| can be called twice in a row, because the list +of blocks is cleared out of the area variable~|s|. + +@<External fun...@>= +void gb_free(s) + Area s; +{@+Area t; + while (*s) { + *t=(*s)->next; + cfree((*s)->first); + *s=*t; + } +} + +@ The two external procedures we've defined above should be mentioned in +the header file, so let's do that before we forget. + +@(gb_graph.h@>= +extern char *gb_alloc(); /* allocate another block for an area */ +#define gb_alloc_type(n,t,s) @[@t\quad@>@[(t*)@]gb_alloc((n)*@[sizeof@](t),s)@] +extern void gb_free(); /* deallocate all blocks for an area */ + +@ Here we try to allocate 10 million bytes of memory. If we succeed, +fine; if not, we verify that the error was properly reported. + +(An early draft of this program attempted to allocate memory until +it was exhausted. That tactic provided a more thorough test, but it +was a bad idea because it brought certain large systems to their +knees; it was terribly unfriendly to other users who were innocently +trying to do their own work on the same machine.) + +@<Test some intentional errors@>= +if (gb_alloc(0,s)!=NULL || gb_alloc_trouble!=2) { + fprintf(stderr,"Allocation error 2 wasn't reported properly!\n"); + return -2; +} +for (;g->v.i<100;g->v.i++) if (gb_alloc(100000,s)) g->u.i++; +if (g->u.i<100 && gb_alloc_trouble!=3) { + fprintf(stderr,"Allocation error 1 wasn't reported properly!\n"); + return -1; +} +gb_free(s); /* we've exhausted memory, let's put some back */ +printf("Hey, I allocated %d00000 bytes successfully. Terrific...\n",g->u.i); + +gb_alloc_trouble=0; + +@ @<Decl...@>= +Area s; /* temporary allocations in the test routine */ + +@*Growing a graph. Now we're ready to look at the \&{Graph} type. This is +a data structure that can be passed to an algorithm that operates on +graphs---to find minimum spanning trees, or strong components, or whatever. + +A \&{Graph} record has seven standard fields and six utility fields. The +standard fields are +$$\vcenter{\halign{#,\ \ \hfil&#\hfil\cr +|vertices|&a pointer to an array of |Vertex| records;\cr +|n|&the total number of vertices;\cr +|m|&the total number of arcs;\cr +|id|&a symbolic identification giving parameters of the GraphBase procedure\cr +\omit& that generated this graph;\cr +|format|&a symbolic representation of the data types in utility fields;\cr +|data|&an |Area| used for |Arc| storage and string storage;\cr +|aux_data|&an |Area| used for auxiliary information that some users may\cr +\omit &wish to discard.\cr}}$$ +The utility fields are called |u|, |v|, |w|, |x|, |y|, and |z|. + +As a consequence of these conventions, we can visit all arcs of a +graph~|g| by using the following program: +$$\vcenter{\halign{#\hfil\cr +|Vertex *v;|\cr +|Arc *a;|\cr +|for (v=g->vertices; v<g->vertices+g->n; v++)|\cr +\quad|for (a=v->arcs; a; a=a->next)|\cr +\qquad\\{visit}|(v,a)|;\cr}}$$ + +@<Type...@>= +#define ID_FIELD_SIZE 161 +typedef struct graph_struct { + Vertex *vertices; /* beginning of the vertex array */ + long n; /* total number of vertices */ + long m; /* total number of arcs */ + char id[ID_FIELD_SIZE]; /* GraphBase identification */ + char format[15]; /* usage of utility fields */ + Area data; /* the main data blocks */ + Area aux_data; /* subsidiary data blocks */ + util u,v,w,x,y,z; /* multipurpose fields */ +} Graph; + +@ The |format| field should always hold a string of length 14, followed +as usual by a null character to terminate that string. The first six +characters of |format| specify the usage of utility fields |u|, |v|, +|w|, |x|, |y|, and~|z| in |Vertex| records; the next two characters give the +format of the utility fields in |Arc| records; the last six give the +format of the utility fields in |Graph| records. Each character +should be either \.I (denoting a |long| integer), +\.S (denoting a pointer to a string), +\.V (denoting a pointer to a |Vertex|), \.A (denoting a pointer to an +|Arc|), \.G (denoting a pointer to a |Graph|), or \.Z (denoting an +unused field that remains zero). The default |format| is +|"ZZZZZZZZZZZZZZ"|, when none of the utility fields is being used. + +For example, suppose that a bipartite graph |g| is using field |g->u.i| +to specify the size of its first part; suppose further that it has a +string in utility field |a| of each |Arc|, and that it uses +utility field |w| of |Vertex| records to point to an |Arc|. If |g| +leaves all other utility fields untouched, its |format| should be +|"ZZAZZZSZIZZZZZ"|. + +The |format| string is presently examined only by the |save_graph| and +|restore_graph| routines, which convert GraphBase graphs from internal +data structures to symbolic external files and vice versa. Therefore +users need not update the |format| when they write algorithms to +manipulate graphs, unless they are going to use |save_graph| to output +a graph in symbolic form, or unless they are using some other +GraphBase-related software that might rely on the |format| +conventions. (Such software is not part of the ``official'' Stanford +GraphBase, but it may conceivably exist some day.) + +@ Some applications of bipartite graphs require all vertices of the first +part to appear at the beginning of the |vertices| array. In such cases, +utility field |u.i| is traditionally given the symbolic name |n_1|, and +it is set equal to the size of that first part. The size of the other +part is then |g->n - g->n_1|. +@^bipartite graph@> + +@d n_1 u.i /* utility field |u| may denote size of bipartite first part */ + +@(gb_graph.h@>= +#define n_1 @t\quad@> u.i +#define mark_bipartite(g,n1) @[g->n_1=n1,g->format[8]='I'@] + +@ A new graph is created by calling |gb_new_graph(n)|, which returns a +pointer to a |Graph| record for a graph with |n| vertices and no arcs. +This function also initalizes several private variables that are used +by the |gb_new_arc|, |gb_new_edge|, |gb_virgin_arc|, and |gb_save_string| +procedures below. + +We actually reserve space for |n+extra_n| vertices, although claiming only~$n$, +because several graph manipulation algorithms like to add a special vertex +or two to the graphs they deal with. + +@<External f...@>= +Graph *gb_new_graph(n) + long n; /* desired number of vertices */ +{ + 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 { + cfree(cur_graph); + cur_graph=NULL; + } + } + next_arc=bad_arc=NULL; + next_string=bad_string=NULL; + gb_alloc_trouble=0; + return cur_graph; +} + +@ The value of |extra_n| is ordinarily~4, and it should probably always be at +least~4. + +@<External d...@>= +int extra_n=4; /* the number of shadow vertices allocated by |gb_new_graph| */ +char null_string[1]; /* a null string constant */ + +@ @(gb_graph.h@>= +extern int extra_n; + /* the number of shadow vertices allocated by |gb_new_graph| */ +extern char null_string[]; /* a null string constant */ +extern make_compound_id(); /* routine to set one |id| field from another */ +extern make_double_compound_id(); /* ditto, but from two others */ + +@ The |id| field of a graph is sometimes manufactured from the |id| field +of another graph. The following routine does this without allowing the +string to get too long after repeated copying. + +@ @<External f...@>= +make_compound_id(g,s1,gg,s2) /* |sprintf(g->id,"%s%s%s",s1,gg->id,s2)| */ + Graph *g; /* graph whose |id| is to be set */ + char *s1; /* string for the beginning of the new |id| */ + Graph *gg; /* graph whose |id| is to be copied */ + char *s2; /* string for the end of the new |id| */ +{@+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) + /* |sprintf(g->id,"%s%s%s%s%s",s1,gg->id,s2,ggg->id,s3)| */ + Graph *g; /* graph whose |id| is to be set */ + char *s1; /* string for the beginning of the new |id| */ + Graph *gg; /* first graph whose |id| is to be copied */ + char *s2; /* string for the middle of the new |id| */ + Graph *ggg; /* second graph whose |id| is to be copied */ + char *s3; /* string for the end of the new |id| */ +{@+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); +} + +@ But how do the arcs get there? That's where the private variables in +|gb_new_graph| come in. If |next_arc| is unequal to |bad_arc|, it points to +an unused |Arc| record in a previously allocated block of |Arc| records. +Similarly, |next_string| and |bad_string| are addresses used to +place strings into a block of memory allocated for that purpose. + +@<Private...@>= +static Arc *next_arc; /* the next |Arc| available for allocation */ +static Arc *bad_arc; /* but if |next_arc=bad_arc|, that |Arc| isn't there */ +static char *next_string; /* the next byte available for storing a string */ +static char *bad_string; /* but if |next_string=bad_string|, don't byte */ +static Arc dummy_arc[2]; /* an |Arc| record to point to in an emergency */ +static Graph dummy_graph; /* a |Graph| record that's normally unused */ +static Graph *cur_graph=&dummy_graph; /* the |Graph| most recently created */ + +@ All new |Arc| records that are created by the automatic |next_arc|/|bad_arc| +scheme originate in a procedure called |gb_virgin_arc|, which returns the +address of a new record having type |Arc|. + +When a new block of |Arc| records is needed, we create 102 of them at once; +this strategy causes exactly 2048 bytes to be allocated on most +computer systems---a nice round number. The routine will work, however, +if 102 is replaced by any positive even number. The new block goes into +the |data| area of |cur_graph|. + +Graph-building programs do not usually call |gb_virgin_arc| directly; +they generally invoke one of the higher-level routines |gb_new_arc| +or |gb_new_edge| described below. + +If memory space has been exhausted, |gb_virgin_arc| will return a +pointer to |dummy_arc|, so that the calling procedure can safely +refer to fields of the result even though |gb_alloc_trouble| is nonzero. + +@d arcs_per_block 102 + +@<External f...@>= +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; +} + +@ The routine |gb_new_arc(u,v,len)| creates a new arc of length |len| +from vertex~|u| to vertex~|v|. The arc becomes part of the graph that +was most recently created by |gb_new_graph|, i.e., of the graph +pointed to by the private variable |cur_graph|. This routine assumes +that |u| and |v| are both vertices in that graph. + +The new arc will be pointed to by |u->arcs|, immediately after +|gb_new_arc(u,v,len)| has acted. If there is no room for the new arc, +|gb_alloc_trouble| is set nonzero, but |u->arcs| will point to the non-|NULL| +record |dummy_arc| +so that additional information can safely be stored in its utility fields +without risking system crashes before |gb_alloc_trouble| is tested. +However, the linking structure of arcs is apt to be fouled up in such +cases; programs should make sure that |gb_alloc_trouble==0| before doing any +extensive computation on a graph. + +@<External f...@>= +void gb_new_arc(u,v,len) + Vertex *u, *v; /* a newly created arc will go from |u| to |v| */ + long len; /* its length */ +{@+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++; +} + +@ An undirected graph has ``edges'' instead of arcs. We represent an edge +by two arcs, one going each way. +@^undirected graph@> + +The fact that |arcs_per_block| is even means that the |gb_new_edge| routine +needs to call |gb_virgin_arc| only once instead of twice. + +Caveats: This routine, like |gb_new_arc|, should be used only after +|gb_new_graph| has caused the private variable |cur_graph| to point to +the graph containing the new edge. The routine |gb_new_edge| must +not be used together with |gb_new_arc| or |gb_virgin_arc| when +building a graph, unless |gb_new_arc| and |gb_virgin_arc| have been +called an even number of times before |gb_new_edge| is invoked. + +The new edge will be pointed to by |u->arcs| and by |v->arcs| immediately +after |gb_new_edge| has created it, assuming that |u!=v|. The two arcs +appear next to each other in memory; indeed, |gb_new_edge| rigs things so +that |v->arcs| is |u->arcs+1| when |u<v|. + +On many computers it turns out that the first |Arc| record of every such +pair of arcs will have an address that is a multiple of~8, and the +second |Arc| record will have an address that is not a multiple of~8 (because +the first |Arc| will be 20 bytes long, and because |calloc| always returns +a multiple of~8). However, it is not safe to assume this when writing +portable code. Algorithms for undirected graphs can still make good use of +the fact that arcs for edges are paired, without needing any mod~8 assumptions, +if all edges have been created and linked into the graph by |gb_new_edge|: +The inverse of an arc~|a| from |u| to~|v| will be arc |a+1| if and only if +|u<v| or |a->next=a+1|; it will be arc |a-1| if and only if |u>=v| and +|a->next!=a+1|. The condition |a->next=a+1| can hold only if |u=v|. + +@<External f...@>= +void gb_new_edge(u,v,len) + Vertex *u, *v; /* new arcs will go from |u| to |v| and from |v| to |u| */ + long len; /* their length */ +{@+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; /* do this now in case |u==v| */ + 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; +} + +@ Sometimes (let us hope rarely) we may need to use a dirty trick +hinted at in the previous discussion. On most computers, the mate to +arc~|a| will be |a-1| if and only if |edge_trick&(unsigned long)a| +is nonzero. +@^system dependencies@> +@^pointer hacks@> + +@<External d...@>= +unsigned long edge_trick=sizeof(Arc)-(sizeof(Arc)&(sizeof(Arc)-1)); + +@ @(gb_graph.h@>= +extern unsigned long edge_trick; /* least significant 1 bit in |sizeof(Arc)| */ + +@ Vertices generally have a symbolic name, and we need a place to put +such names. The |gb_save_string| function is a convenient utility +for this purpose: +Given a null-terminated string of any length, |gb_save_string| stashes +it away in a safe place and returns a pointer to that place. Memory is +conserved by combining strings from the current graph into largish blocks +of a convenient size. + +Note that |gb_save_string| should be used only after |gb_new_graph| has provided +suitable initialization, because the private variable |cur_graph| must +point to the graph for which storage is currently being allocated, and +the private variables |next_string| and |bad_string| must also have +suitable values. + +@d string_block_size 1016 /* $1024-8$ is usually efficient */ + +@<External f...@>= +char *gb_save_string(s) + register char *s; /* the string to be copied */ +{@+register char *p=s; + register long len; /* length of the string and following null character */ + while (*p++) ; /* advance to end of string */ + len=p-s; + p=next_string; + if (p+len>bad_string) { /* not enough room in current block */ + long size=string_block_size; + if (len>size) + size=len; + p=gb_alloc(size,cur_graph->data); + if (p==NULL) + return null_string; /* return a pointer to |""| if memory ran out */ + bad_string=p+size; + } + while (*s) *p++=*s++; /* copy the non-null bytes of the string */ + *p++='\0'; /* and append a null character */ + next_string=p; + return p-len; +} + +@ The test routine illustrates some of these basic maneuvers. + +@<Create a small graph@>= +g=gb_new_graph(2); +if (g==NULL) { + fprintf(stderr,"Oops, I couldn't even create a trivial graph!\n"); + return -3; +} +u=g->vertices;@+ v=u+1; +u->name=gb_save_string("vertex 0"); +v->name=gb_save_string("vertex 1"); + +@ @<Decl...@>= +Graph *g; +Vertex *u,*v; + +@ If the ``edge trick'' fails, the standard GraphBase routines are +unaffected except for the demonstration program |miles_span|. (And +that program uses |edge_trick| only when printing verbose comments.) +@^edge trick failure@> + +@<Check that the small graph is still there@>= +if (strncmp(u->name,v->name,7)) { + fprintf(stderr,"Something is fouled up in the string storage machinery!\n"); + return -4; +} +gb_new_edge(v,u,-1); +gb_new_edge(u,u,1); +gb_new_arc(v,u,-1); +if ((edge_trick&(unsigned long)(u->arcs))|| + (edge_trick&(unsigned long)(u->arcs->next->next))|| + !(edge_trick&(unsigned long)(v->arcs->next))) + printf("Warning: The \"edge trick\" failed!\n"); +if (v->name[7]+g->n!=v->arcs->next->tip->name[7]+g->m-2) { + /* |'1'+2!='0'+5-2| */ + fprintf(stderr,"Sorry, the graph data structures aren't working yet.\n"); + return -5; +} + +@ Some applications may need to add arcs to several graphs at a time, +violating the assumptions stated above about |cur_graph| and the other +private variables. The |switch_to_graph| function gets around that +restriction, by using the utility slots |w|, |x|, |y|, and +|z| of |Graph| records to save and restore the private variables. + +Just say |switch_to_graph(g)| in order to make |cur_graph| be~|g| and +to restore the other private variables that are needed by +|gb_new_arc|, |gb_virgin_arc|, |gb_new_edge|, and |gb_save_string|. +Restriction: The graph |g| being switched to must have previously been +switched from; i.e., it must have been |cur_graph| when |switch_to_graph| +was called previously. Otherwise its private allocation variables will +not have been saved. To meet this restriction, you should say +|switch_to_graph(NULL)| just before calling |gb_new_graph|, if you +intend to switch back to the current graph later. + +(The swap-in-swap-out nature of these conventions may seem inelegant, but +convenience and efficiency are more important than elegance when most +applications do not need the ability to switch between graphs.) + +@<External f...@>= +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; +} + +@ Finally, +here's a routine that obliterates an entire graph when it is no longer needed: + +@<External fun...@>= +void gb_recycle(g) + Graph *g; +{ + if (g) { + gb_free(g->data); + gb_free(g->aux_data); + cfree(g); /* the user must not refer to |g| again */ + } +} + +@ @(gb_graph.h@>= +extern Graph*gb_new_graph(); /* create a new graph structure */ +extern void gb_new_arc(); /* append an arc to the current graph */ +extern Arc*gb_virgin_arc(); /* allocate a new |Arc| record */ +extern void gb_new_edge(); /* append an edge (two arcs) to the current graph */ +extern char*gb_save_string(); /* store a string in the current graph */ +extern void switch_to_graph(); /* save allocation variables, swap in others */ +extern void gb_recycle(); /* delete a graph structure */ + +@* Searching for vertices. We sometimes want to be able to find a vertex, given +its name, and it is nice to do this in a standard way. The following simple +subroutines can be used: + +{\narrower +\smallskip|hash_in(v)| puts the name of vertex |v| into the hash table; +\smallskip|hash_out(s)| finds a vertex named |s|, if present in the hash table; +\smallskip|hash_setup(g)| prepares a hash table for all vertices of graph~|g|; +\smallskip|hash_lookup(s,g)| looks up the name |s| in the hash table of |g|. +\smallskip} + +\noindent Routines |hash_in| and |hash_out| apply to the current graph being +created, while |hash_setup| and |hash_lookup| apply to arbitrary graphs. + +Important: Utility fields |u| and |v| of each vertex are reserved for use by +the search routine when hashing is active. You can crash the system +if you try to fool around with these values yourself, or if you use any +subroutines that change those fields. The first two characters in the +current graph's |format| field should be \.{VV} if the hash table information +is to be saved by |gb_save|. + +Warning: Users of this hash scheme must preserve the number of +vertices |g->n| in the current graph~|g|. If |g->n| is changed, +the hash table will be worthless, unless |hash_setup| is used to +rehash everything. + +@<gb_graph.h@>= +extern void hash_in(); /* input a name to the hash table of current graph */ +extern Vertex* hash_out(); /* find a name in hash table of current graph */ +extern void hash_setup(); /* create a hash table for a given graph */ +extern Vertex* hash_lookup(); /* find a name in a given graph */ + +@ The lookup scheme is quite simple: We compute a more-or-less random +value |h| based on the vertex name, where |0<=h<n|, assuming that +the graph has |n|~vertices. There is a list of all vertices whose hash +address is~|h|, starting at |(g->vertices+h)->hash_head| and linked +together in the |hash_link| fields, where |hash_head| and |hash_link| are +utility fields |u.v| and |v.v|. + +@d hash_link u.v +@d hash_head v.v + +@ @<External fun...@>= +void hash_in(v) + Vertex *v; +{@+ register char *t=v->name; + register Vertex *u; + @<Find vertex |u|, whose location is the hash code for string |t|@>; + v->hash_link=u->hash_head; + u->hash_head=v; +} + +@ The hash code for a string $c_1c_2\ldots c_l$ of length $l$ is +a nonlinear function of the characters that appears to produce reasonably +random results between 0 and the number of vertices in the current graph. + +Caution: This hash coding scheme is system-dependent, because it +uses the system's character codes. If you create a graph on +a machine with ASCII code and save it with |gb_save|, and if you ship the +resulting text file to some friend whose machine does not use ASCII code, +your friend will have to rebuild the hash structure with |hash_setup| +before being able to use |hash_lookup| successfully. +@^character-set dependencies@> + +@d HASH_MULT 314159 /* random multiplier */ +@d HASH_PRIME 516595003 /* the 27182818th prime; it's less than $2^{29}$ */ + +@<Find vertex |u|...@>= +{@+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); +} + +@ If the hash function were truly random, the average number of +string comparisons made would be less than $(e^2+7)/8\approx 1.80$ on +a successful search, and less than $(e^2+1)/4\approx2.10$ on an +unsuccessful search [{\sl Sorting and Searching}, Section 6.4, +Eqs.~(15) and~(16)]. + +@<External fun...@>= +Vertex* hash_out(s) + char* s; +{@+register char *t=s; + register Vertex *u; + @<Find vertex |u|...@>; + for (u=u->hash_head;u;u=u->hash_link) + if (strcmp(s,u->name)==0) return u; + return NULL; /* not found */ +} + +@ @<External fun...@>= +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'; + /* indicate usage of |hash_head| and |hash_link| */ + cur_graph=save_cur_graph; + } +} + +@ @<External fun...@>= +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; +} + +@* Index. Here is a list that shows where the identifiers of this program are +defined and used. |