14
.TH LIBGRAPH 3 "8 MARCH 1996"
16
\fBlibgraph\fR \- abstract graph library
18
."ta .75i 1.5i 2.25i 3i 3.75i 4.5i 5.25i 6i
35
Agraph_t *agopen(char *name, Agdesc_t kind, Agdisc_t *disc);
36
int agclose(Agraph_t *g);
37
Agraph_t *agread(void *file, Agdisc_t *);
38
Agraph_t *agconcat(Agraph_t *g, void *chan, Agdisc_t *disc)
39
int agwrite(Agraph_t *g, void *file);
40
int agnnodes(Agraph_t *g),agnedges(Agraph_t *g);
43
Agraph_t *agsubg(Agraph_t *g, char *name, int createflag);
44
Agraph_t *agfstsubg(Agraph_t *g), agnxtsubg(Agraph_t *);
45
Agraph_t *agparent(Agraph_t *g),*agroot(Agraph_t *g);
49
Agnode_t *agnode(Agraph_t *g, char *name, int createflag);
50
Agnode_t *agidnode(Agraph_t *g, ulong id, int createflag);
51
Agnode_t *agsubnode(Agraph_t *g, Agnode_t *n, int createflag);
52
Agnode_t *agfstnode(Agraph_t *g);
53
Agnode_t *agnxtnode(Agnode_t *n);
54
int agdelnode(Agraph_t *g, Agnode_t *n);
55
int agrename(Agraph_t *g, Agnode_t *n, char *newname);
56
int agdegree(Agnode_t *n, int use_inedges, int use_outedges);
60
Agedge_t *agedge(Agnode_t *t, Agnode_t *h, char *name, int createflag);
61
Agedge_t *agsubedge(Agraph_t *g, Agedge_t *e, int createflag);
62
int agdeledge(Agraph_t *g, Agedge_t *e);
64
Agnode_t *aghead(Agedge_t *e), *agtail(Agedge_t *e);
65
Agedge_t *agfstedge(Agnode_t *n);
66
Agedge_t *agnxtedge(Agedge_t *e, Agnode_t *n);
67
Agedge_t *agfstin(Agnode_t *n);
68
Agedge_t *agnxtin(Agedge_t *e);
69
Agedge_t *agfstout(Agnode_t *n);
70
Agedge_t *agnxtout(Agedge_t *e);
73
int agflatten(Agraph_t *graph, int flag);
74
Agnode_t *agfstn(Agraph_t *g), *agnxtn(Agnode_t *n);
75
Agedge_t *agfout(Agnode_t *n), *agfin(Agnode_t *n), *agnxte(Agedge_t *e);
77
.Ss "STRING ATTRIBUTES"
79
Agsym_t *agattr(Agraph_t *g, int kind, char *name, char *value);
80
Agsym_t *agattrnxt(Agraph_t *g, int kind, Agsym_t *attr);
82
char *agget(void *obj, char *name);
83
char *agxget(void *obj, Agsym_t *sym);
84
int agset(void *obj, char *name, char *value);
85
int agxset(void *obj, Agsym_t *sym, char *value);
89
void *agnewrec(Agraph_t *g, void *obj, char *name, unsigned int size);
90
Agrec_t *aggetrec(void *obj, char *name, int move_to_front);
91
int agdelrec(Agraph_t *g, void *obj, char *name);
95
Agcbdisc_t *agpopdisc(Agraph_t *g);
96
void agpushdisc(Agraph_t *g, Agcbdisc_t *disc);
97
void agmethod(Agraph_t *g, void *obj, Agcbdisc_t *disc, int initflag);
101
void *agalloc(Agraph_t *g, size_t request);
102
void *agrealloc(Agraph_t *g, void *ptr, size_t oldsize, size_t newsize);
103
void agfree(Agraph_t *g, void *ptr);
105
.Ss "GENERIC OBJECTS"
107
Agraph_t *agraphof(void*);
108
char *agnameof(void*);
109
int agisarootobj(void*);
110
Agrec_t *AGDATA(void *obj);
111
ulong AGID(void *obj);
112
int AGTYPE(void *obj);
115
Libgraph supports graph programming by maintaining graphs in memory
116
and reading and writing graph files. Graphs, nodes and edges
117
may be attributed with programmer-defined records and string
119
Graphs are composed of nodes, edges, and nested subgraphs.
120
Internally, Libgraph depends extensively on Libcdt (formerly
121
Libdict) for set representation.
123
All of Libgraph's global symbols have the prefix \fBag\fR (case varying).
126
A ``main'' or ``root'' graph defines a namespace for a collection of
127
graph objects (subgraphs, nodes, edges) and their attributes.
128
Objects may be named by unique strings or by 32-bit IDs.
131
\fBdata\fP points to runtime records containing application-dependent
132
data, keyed by name (see Attributes). \fBdesc\fP records
133
if a graph is directed or undirected, and if it is strict
134
or allows multi-edges and self-arcs.
136
\fBagopen\fP creates a new graph with the given name and graph kind
137
descriptor (global values are \fBAgdirected\fP, \fBAgundirected\fP,
138
\fBAgstrictdirected\fP, and \fBAgstrictundirected\fP).
139
\fBagclose\fP deletes a graph, freeing all its associated
140
storage. \fBagread\fP and \fBagwrite\fP perform file I/O
141
(see Graph File Language bellow). \fBagsubg\fP creates a new subgraph,
142
which always inherits the graph kind of its parent. The new subgraph is
143
initially empty. Nested subgraph trees may be created. The name of
144
a subgraph is interpreted only relative to the given parent graph.
145
\fBagsubglist\fP returns a list (possibly empty) of subgraphs of
148
By default, nodes are kept in ordered sets in \fBn_dict\fP,
149
allowing efficient random access to insert, find, and delete nodes.
150
Similarly the edges of each node are kept in ordered sets.
151
The sets are maintained as splay tree dictionaries.
152
\fBagflatten\fP allows flattening trees into linked lists,
153
which may thereafter be traversed very quickly without function
154
calls for low overhead in critical sections of code.
155
In this mode, sets are locked to prevent updates or random access searches,
156
though it is still legal to call Libgraph to scan lists sequentially.
157
The flag argument requests flattening and locking (if boolean true),
158
or unlocking (if false).
159
In-line functions or macros for list traversal are given below
160
under Nodes and Edges. Note that flattening a graph does not
161
automatically flatten its subgraphs.
163
\fBagnnodes\fP, \fBagnedges\fP, and \fBagdegree\fP return the
164
cardinalities of node and edge sets. The latter takes flags
165
to select in-edges, out-edges, or both.
167
\fBAgdisc_t\fP specifies callbacks invoked when initializing,
168
modifying, or finalizinf graph objects. (Casual users can ignore
169
the following.) Disciplines are kept on a stack. Libgraph automatically
170
calls the methods on the stack, top-down. A method can obtain its
171
data (closure) via \f5aggetuserptr\fP.
173
When Libgraph is compiled with Vmalloc, each graph has its own heap.
174
Programmers may allocate application-dependent data within the
175
same heap as the rest of the graph. The advantage is that
176
a graph can be deleted by atomically freeing its entire heap
177
without scanning each individual node and edge. (Vmalloc is not
178
available in Libgraph outside AT&T/Lucent.)
180
A node is identified uniquely by name and graph pointer.
181
Node pointers are not unique\(em separate node structs are created
182
per subgraph. Name pointers are unique, though, because each
183
graph has its own shared string pool.
185
\fBagnode\fP searches in a graph or subgraph for a node
186
with the given name, and returns it if found.
187
If not found, if \fBcreateflag\fP is boolean true
188
a new node is created and returned, otherwise a nil
190
\fBagsubnode\fP takes an existing node as a template,
191
usually to find or insert a node in a subgraph.
193
The default ordering of nodes is by order of creation (sequence).
194
Internally, Libgraph switches between ID searching and sequence
195
ordering as necessary. \fBagfstnode\fP and
196
\fBagnxtnode\fP are the usual functions for scanning
197
node lists. When node sets are flattened it is permissible to
198
call \fBagfstnode\fP and \fBagnxtnode\fP, but conflicting
199
attempts to insert, delete, or search for nodes cause a runtime error.
202
An abstract edge is represented by two edge structs.
203
There is one pointing to each terminal node, and
204
residing in an edge list of the opposite node.
205
The object tag distinguishes between these otherwise
206
symmetric records, to allow obtaining head and tail.
207
If a graph has multi-edges between the same nodes,
208
the name field serves as a secondary key.
210
\fBagedge\fP searches in a graph of subgraph for an
211
edge between the given endpoints (with an optional
212
multi-edge selector name) and returns it if found.
213
Otherwise, if \fBcreateflag\P is boolean true,
214
a new edge is created and returned: otherwise
215
a nil pointer is returned. If the \fBname\fP
216
is \f5(char*)0\fP then an anonymous internal
218
\fBagfstin\fP, \fBagnxtint\fP, \fBagfstout\fP, and
219
\fBagnxtout\fP visit directed in- and out- edge lists,
220
and ordinarily apply only in directed graphs.
221
\fBagfstedge\fP and \fBagnxtedge\fP visit all edges
222
incident to a node. In traversing lists, \f5e->node\fP
223
always points to the ``other'' node of the edge,
224
To resolve ambiguity between in- and out-edge structs,
225
\fBaghead\fP and \fBagtail\fP are macros or inline
226
functions to find endpoints by checking object tags.
227
\fBagopp\fP returns the ``opposite'' edge struct.
228
Similarly \fBagfout\fP, \fBagfin\fP, and \fBagnedge\fP
229
operate on flattened edge lists.
231
.SH "STRING ATTRIBUTES"
232
Programmer-defined values may be dynamically
233
attached to graphs, subgraphs, nodes, and edges. Such
234
values are either uninterpreted binary records
235
(for implementing efficient algorithms)
236
or character string data (for I/O).
237
String attributes are handled automatically in reading
238
and writing graph files. Uninterpreted records are
239
ignored; any desired conversion must be coded
240
explicitly by application programmers.
242
A string attribute is identified by name and by
243
an internal symbol table entry (\fBAgsym_t\fP) created by Libgraph.
244
Attributes of nodes, edges, and graphs (with their subgraphs)
245
have separate namespaces. The contents of an \fBAgsym_t\fP
246
is listed below, followed by primitives to operate on string
249
typedef struct Agsym_s { /* symbol in one of the above dictionaries */
251
char *name; /* attribute's name */
252
char *defval; /* its default value for initialization */
253
int id; /* its index in attr[] */
257
\fBagattr\fP creates or looks up attributes.
258
\fBkind\fP may be \fBAGRAPH\fP, \fBAGNODE\fP, or \fBAGEDGE\fP.
259
If \fBvalue\fP is \fB(char*)0)\fP, the request is to search
260
for an existing attribute of the given kind and name.
261
Otherwise, if the attribute already exists, its default
262
for creating new objects is set to the given value;
263
if it does not exist, a new attribute is created with the
264
given default, and the default is applied to all pre-existing
265
objects of the given kind.
267
\fBagdictof\fP returns a Libdict set of all the attributes
268
of a given kind. \fBagdictsym\fP is a utility function that
269
finds an entry in one of these dictionary sets.
271
\fBagget\fP and \fBagset\fP read and update string attributes.
272
The first argument should be a graph, node, or edge struct pointer.
273
\fBagxset\fP and \fBagxset\fP take a symbol table entry reference
274
instead of a name, to avoid the cost of looking up attribute names
276
Note that Libgraph performs its own storage management of strings.
277
The calling program does not need to dynamically allocate storage.
280
Uninterpreted records may be attached to graphs (subgraphs), nodes,
281
and edges for efficient operations on values such as marks, weights,
282
counts, and pointers needed by algorithms. Application programmers
283
define the fields of these records, but they have a common header
286
typedef struct Agrec_s {
288
struct Agrec_s *next;
289
/* programmer-defined follows */
292
Records are created and managed by Libgraph. In each graph, node,
293
or edge, \fBdata\fR points to a circular list of records.
294
The \fBname\fP field distinguishes various types of records, and is
295
programmer defined (Libgraph reserves the prefix \fB_ag\fR).
296
\fBnext\fP stores the list pointers.
297
The remainder of a record may contain application-dependent fields.
298
\fBagnewrec\fP creates one new record of the given size and attaches
299
it to the given object (graph, node, or edge). \fBagdelrec\fP
300
is the corresponding function to delete records. \fBaggetrec\fP
301
finds a record with the given name.
303
To allow referencing application-dependent data without function
304
calls or linear search, Libgraph allows setting and locking the
305
\fBdata\fP field of a graph, node, or edge on a particular record.
306
The \fBmove_to_front\fP flag may be \fBAG_MTF_FALSE\fP,
307
\fBAG_MTF_SOFT\fP, or \fBAG_MTF_HARD\fP accordingly.
308
The \fBAG_MTF_SOFT\fP field is only a hint that decreases
309
overhead in subsequent calls of \fBaggetrec\fP;
310
\fBAG_MTF_HARD\fP guarantees that a lock was obtained.
311
To release locks, use \fBAG_MTF_SOFT\fP or \fBAG_MTF_FALSE\fP.
312
Use of this feature implies cooperation or at least isolation
313
from other functions also using the move-to-front convention.
315
A cast (generally using a macro or inline function)
316
is then needed to convert the \fBdata\fP pointer to
317
an appropriate programmer-defined type.
320
Programmer-defined disciplines customize certain resources-
321
ID namespace, memory, and I/O - needed by Libgraph.
322
A discipline struct (or NIL) is passed at graph creation time.
324
struct Agdisc_s { /* user's discipline */
330
A default discipline is supplied when NIL is given for
333
An ID allocator discipline allows a client to control assignment
334
of IDs (uninterpreted 32-bit values) to objects, and possibly how
335
they are mapped to and from strings.
338
struct Agiddisc_s { /* object ID allocator */
339
void *(*open)(Agraph_t *g); /* associated with a graph */
340
int (*map)(void *state, int objtype, char *str, ulong *id, int createflag);
341
int (*alloc)(void *state, int objtype, ulong id);
342
void (*free)(void *state, int objtype, ulong id);
343
char *(*print)(void *state, int objtype, ulong id);
344
void (*close)(void *state);
348
\f5open\fP permits the ID discipline to initialize any data
349
structures that maintains per individual graph.
350
Its return value is then passed as the first argument to
351
all subsequent ID manager calls.
353
\f5alloc\fP informs the ID manager that Libgraph is attempting
354
to create an object with a specific ID that was given by a client.
355
The ID manager should return TRUE (nonzero) if the ID can be
356
allocated, or FALSE (which aborts the operation).
358
\f5free\fP is called to inform the ID manager that the
359
object labeled with the given ID is about to go out of existence.
361
\f5map\fP is called to create or look-up IDs by string name
362
(if supported by the ID manager). Returning TRUE (nonzero)
363
in all cases means that the request succeeded (with a valid
364
ID stored through \f5result\fP. There are four cases:
366
\f5name != NULL\fP and \f5createflag == 1\fP:
367
This requests mapping a string (e.g. a name in a graph file) into a new ID.
368
If the ID manager can comply, then it stores the result and returns TRUE.
369
It is then also responsible for being able to \f5print\fP the ID again
370
as a string. Otherwise the ID manager may return FALSE but it must
371
implement the following (at least for graph file reading and writing to work):
373
\f5name == NULL\fP and \f5createflag == 1\fP:
374
The ID manager creates a unique new ID of its own choosing.
375
Although it may return FALSE if it does not support anonymous objects,
376
but this is strongly discouraged (to support "local names" in graph files.)
378
\f5name != NULL\fP and \f5createflag == 0\fP:
379
This is a namespace probe. If the name was previously mapped into
380
an allocated ID by the ID manager, then the manager must return this ID.
381
Otherwise, the ID manager may either return FALSE, or may store
382
any unallocated ID into result. (This is convenient, for example,
383
if names are known to be digit strings that are directly converted into 32 bit values.)
385
\f5name == NULL\fP and \f5createflag == 0\fP: forbidden.
387
\f5print\fP should return
388
\5print\fP is allowed to return a pointer to a static buffer;
389
a caller must copy its value if needed past subsequent calls.
390
\f5NULL\fP should be returned by ID managers that do not map names.
392
The \f5map\fP and \f5alloc\fP calls do not pass a pointer to the
393
newly allocated object. If a client needs to install object
394
pointers in a handle table, it can obtain them via
395
new object callbacks.
398
int (*fread)(void *chan, char *buf, int bufsize);
399
int (*putstr)(void *chan, char *str);
400
int (*flush)(void *chan); /* sync */
401
/* error messages? */
404
struct Agmemdisc_s { /* memory allocator */
405
void *(*open)(void); /* independent of other resources */
406
void *(*alloc)(void *state, size_t req);
407
void *(*resize)(void *state, void *ptr, size_t old, size_t req);
408
void (*free)(void *state, void *ptr);
409
void (*close)(void *state);
413
.SH "EXAMPLE PROGRAM"
416
typedef struct mydata_s {int x,y,z;} mydata;
418
main(int argc, char **argv)
428
if (g = agread(stdin,NIL(Agdisc_t*))) {
429
/* dtsize() is a Libdict primitive */
430
fprintf(stderr,"%s has %d node attributes\n",
431
dtsize(agdictof(g,AGNODE)));
432
attr = agattr(g,AGNODE,"color","blue");
434
/* create a new graph */
435
h = agopen("tmp",g->desc);
437
/* this is a way of counting all the edges of the graph */
439
for (v = agfstnode(g); v; v = agnxtnode(g,v))
440
for (e = agfstout(g,v); e; e = agnxtout(g,e))
443
/* using inline functions or macros, attach records to edges */
445
for (v = agfstn(g); v; v = agnxtn(v))
446
for (e = agfout(v); e; e; = agnxte(e)) {
447
p = (mydata*) agnewrec(g,e,"mydata",sizeof(mydata));
448
p->x = 27; /* meaningless example */
453
.SH "EXAMPLE GRAPH FILES"
458
a -> c [weight=29,label="some text];
460
/* the following affects only x,y,z */
462
a; x; y -> z; y -> z; /* multiple edges */
467
n0 -- n1 -- n2 -- n0; /* a cycle */
468
n0 -- {a b c d}; /* a star */
470
n0 -- n3 [weight=1]; /* same edge because graph is strict */
477
The root graph \fBname\fP is treated as a comment.
479
There is no way to delete string attributes or modify edge keys.
481
Strings and uninterpreted records could be treatly more uniformly.
484
Stephen North, north@research.att.com, AT&T Research.
added
removed
agraph/agraph.3
