1LIBAGRAPH(3) Library Functions Manual LIBAGRAPH(3)
2
6 Agraph - abstract graph library
7
9 #include <graphviz/agraph.h>
10 TYPES
12 Agraph_t;
13 Agnode_t;
14 Agedge_t;
15 Agdesc_t;
16 Agdisc_t;
17 Agsym_t;
18 GRAPHS
20 Agraph_t *agopen(char *name, Agdesc_t kind, Agdisc_t *disc);
21 int agclose(Agraph_t *g);
22 Agraph_t *agread(void *file, Agdisc_t *);
23 Agraph_t *agconcat(Agraph_t *g, void *chan, Agdisc_t *disc)
24 int agwrite(Agraph_t *g, void *file);
25 int agnnodes(Agraph_t *g),agnedges(Agraph_t *g);
26 SUBGRAPHS
28 Agraph_t *agsubg(Agraph_t *g, char *name, int createflag);
29 Agraph_t *agfstsubg(Agraph_t *g), agnxtsubg(Agraph_t *);
30 Agraph_t *agparent(Agraph_t *g),*agroot(Agraph_t *g);
31 NODES
33 Agnode_t *agnode(Agraph_t *g, char *name, int createflag);
34 Agnode_t *agidnode(Agraph_t *g, ulong id, int createflag);
35 Agnode_t *agsubnode(Agraph_t *g, Agnode_t *n, int createflag);
36 Agnode_t *agfstnode(Agraph_t *g);
37 Agnode_t *agnxtnode(Agnode_t *n);
38 int agdelnode(Agraph_t *g, Agnode_t *n);
39 int agrename(Agraph_t *g, Agnode_t *n, char *newname);
40 int agdegree(Agnode_t *n, int use_inedges, int use_outedges);
41 EDGES
43 Agedge_t *agedge(Agnode_t *t, Agnode_t *h, char *name, int createflag);
44 Agedge_t *agsubedge(Agraph_t *g, Agedge_t *e, int createflag);
45 int agdeledge(Agraph_t *g, Agedge_t *e);
46 Agnode_t *aghead(Agedge_t *e), *agtail(Agedge_t *e);
48 Agedge_t *agfstedge(Agnode_t *n);
49 Agedge_t *agnxtedge(Agedge_t *e, Agnode_t *n);
50 Agedge_t *agfstin(Agnode_t *n);
51 Agedge_t *agnxtin(Agedge_t *e);
52 Agedge_t *agfstout(Agnode_t *n);
53 Agedge_t *agnxtout(Agedge_t *e);
54 FLATTENED LISTS
56 int agflatten(Agraph_t *graph, int flag);
57 Agnode_t *agfstn(Agraph_t *g), *agnxtn(Agnode_t *n);
58 Agedge_t *agfout(Agnode_t *n), *agfin(Agnode_t *n), *agnxte(Agedge_t *e);
59 STRING ATTRIBUTES
61 Agsym_t *agattr(Agraph_t *g, int kind, char *name, char *value);
62 Agsym_t *agattrnxt(Agraph_t *g, int kind, Agsym_t *attr);
63 char *agget(void *obj, char *name);
65 char *agxget(void *obj, Agsym_t *sym);
66 int agset(void *obj, char *name, char *value);
67 int agxset(void *obj, Agsym_t *sym, char *value);
68 RECORDS
70 void *agnewrec(Agraph_t *g, void *obj, char *name, unsigned int size);
71 Agrec_t *aggetrec(void *obj, char *name, int move_to_front);
72 int agdelrec(Agraph_t *g, void *obj, char *name);
73 CALLBACKS
75 Agcbdisc_t *agpopdisc(Agraph_t *g);
76 void agpushdisc(Agraph_t *g, Agcbdisc_t *disc);
77 void agmethod(Agraph_t *g, void *obj, Agcbdisc_t *disc, int initflag);
78 MEMORY
80 void *agalloc(Agraph_t *g, size_t request);
81 void *agrealloc(Agraph_t *g, void *ptr, size_t oldsize, size_t newsize);
82 void agfree(Agraph_t *g, void *ptr);
83 GENERIC OBJECTS
85 Agraph_t *agraphof(void*);
86 char *agnameof(void*);
87 int agisarootobj(void*);
88 Agrec_t *AGDATA(void *obj);
89 ulong AGID(void *obj);
90 int AGTYPE(void *obj);
91
93 Libagraph supports graph programming by maintaining graphs in memory
94 and reading and writing graph files. Graphs, nodes and edges may be
95 attributed with programmer-defined records and string name-value pairs.
96 Graphs are composed of nodes, edges, and nested subgraphs. Internally,
97 Libagraph depends extensively on Libcdt (formerly Libdict) for set rep‐
98 resentation.
99 All of Libagraph's global symbols have the prefix ag (case varying).
101
103 A ``main'' or ``root'' graph defines a namespace for a collection of
104 graph objects (subgraphs, nodes, edges) and their attributes. Objects
105 may be named by unique strings or by 32-bit IDs. By default data
106 points to runtime records containing application-dependent data, keyed
107 by name (see Attributes). desc records if a graph is directed or undi‐
108 rected, and if it is strict or allows multi-edges and self-arcs.
109 agopen creates a new graph with the given name and graph kind descrip‐
111 tor (global values are Agdirected, Agundirected, Agstrictdirected, and
112 Agstrictundirected). agclose deletes a graph, freeing all its associ‐
113 ated storage. agread and agwrite perform file I/O (see Graph File Lan‐
114 guage bellow). agsubg creates a new subgraph, which always inherits
115 the graph kind of its parent. The new subgraph is initially empty.
116 Nested subgraph trees may be created. The name of a subgraph is inter‐
117 preted only relative to the given parent graph. agsubglist returns a
118 list (possibly empty) of subgraphs of a given graph.
119 By default, nodes are kept in ordered sets in n_dict, allowing effi‐
121 cient random access to insert, find, and delete nodes. Similarly the
122 edges of each node are kept in ordered sets. The sets are maintained
123 as splay tree dictionaries. agflatten allows flattening trees into
124 linked lists, which may thereafter be traversed very quickly without
125 function calls for low overhead in critical sections of code. In this
126 mode, sets are locked to prevent updates or random access searches,
127 though it is still legal to call Libagraph to scan lists sequentially.
128 The flag argument requests flattening and locking (if boolean true), or
129 unlocking (if false). In-line functions or macros for list traversal
130 are given below under Nodes and Edges. Note that flattening a graph
131 does not automatically flatten its subgraphs.
132 agnnodes, agnedges, and agdegree return the cardinalities of node and
134 edge sets. The latter takes flags to select in-edges, out-edges, or
135 both.
136 Agdisc_t specifies callbacks invoked when initializing, modifying, or
138 finalizinf graph objects. (Casual users can ignore the following.)
139 Disciplines are kept on a stack. Libagraph automatically calls the
140 methods on the stack, top-down. A method can obtain its data (closure)
141 via aggetuserptr.
142 When Libagraph is compiled with Vmalloc, each graph has its own heap.
144 Programmers may allocate application-dependent data within the same
145 heap as the rest of the graph. The advantage is that a graph can be
146 deleted by atomically freeing its entire heap without scanning each
147 individual node and edge.
148
150 A node is identified uniquely by name and graph pointer. Node pointers
151 are not unique— separate node structs are created per subgraph. Name
152 pointers are unique, though, because each graph has its own shared
153 string pool.
154 agnode searches in a graph or subgraph for a node with the given name,
156 and returns it if found. If not found, if createflag is boolean true a
157 new node is created and returned, otherwise a nil pointer is returned.
158 agsubnode takes an existing node as a template, usually to find or
159 insert a node in a subgraph.
160 The default ordering of nodes is by order of creation (sequence).
162 Internally, Libagraph switches between ID searching and sequence order‐
163 ing as necessary. agfstnode and agnxtnode are the usual functions for
164 scanning node lists. When node sets are flattened it is permissible to
165 call agfstnode and agnxtnode, but conflicting attempts to insert,
166 delete, or search for nodes cause a runtime error.
167
169 An abstract edge is represented by two edge structs. There is one
170 pointing to each terminal node, and residing in an edge list of the
171 opposite node. The object tag distinguishes between these otherwise
172 symmetric records, to allow obtaining head and tail. If a graph has
173 multi-edges between the same nodes, the name field serves as a sec‐
174 ondary key.
175 agedge searches in a graph of subgraph for an edge between the given
177 endpoints (with an optional multi-edge selector name) and returns it if
178 found. Otherwise, if createflag is boolean true, a new edge is created
179 and returned: otherwise a nil pointer is returned. If the name is
180 (char*)0 then an anonymous internal value is generated. agfstin, agnx‐
181 tint, agfstout, and agnxtout visit directed in- and out- edge lists,
182 and ordinarily apply only in directed graphs. agfstedge and agnxtedge
183 visit all edges incident to a node. In traversing lists, e->node
184 always points to the ``other'' node of the edge, To resolve ambiguity
185 between in- and out-edge structs, aghead and agtail are macros or
186 inline functions to find endpoints by checking object tags. agopp
187 returns the ``opposite'' edge struct. Similarly agfout, agfin, and
188 agnedge operate on flattened edge lists.
189
192 Programmer-defined values may be dynamically attached to graphs, sub‐
193 graphs, nodes, and edges. Such values are either uninterpreted binary
194 records (for implementing efficient algorithms) or character string
195 data (for I/O). String attributes are handled automatically in reading
196 and writing graph files. Uninterpreted records are ignored; any
197 desired conversion must be coded explicitly by application programmers.
198 A string attribute is identified by name and by an internal symbol ta‐
200 ble entry (Agsym_t) created by Libagraph. Attributes of nodes, edges,
201 and graphs (with their subgraphs) have separate namespaces. The con‐
202 tents of an Agsym_t is listed below, followed by primitives to operate
203 on string attributes.
204 typedef struct Agsym_s { /* symbol in one of the above dictionaries */
205 Dtlink_t link;
206 char *name; /* attribute's name */
207 char *defval; /* its default value for initialization */
208 int id; /* its index in attr[] */
209 } Agsym_t;
210 agattr creates or looks up attributes. kind may be AGRAPH, AGNODE, or
212 AGEDGE. If value is (char*)0), the request is to search for an exist‐
213 ing attribute of the given kind and name. Otherwise, if the attribute
214 already exists, its default for creating new objects is set to the
215 given value; if it does not exist, a new attribute is created with the
216 given default, and the default is applied to all pre-existing objects
217 of the given kind.
218 agdictof returns a Libdict set of all the attributes of a given kind.
220 agdictsym is a utility function that finds an entry in one of these
221 dictionary sets.
222 agget and agset read and update string attributes. The first argument
224 should be a graph, node, or edge struct pointer. agxset and agxset
225 take a symbol table entry reference instead of a name, to avoid the
226 cost of looking up attribute names inside loops. Note that Libagraph
227 performs its own storage management of strings. The calling program
228 does not need to dynamically allocate storage.
229
232 Uninterpreted records may be attached to graphs (subgraphs), nodes, and
233 edges for efficient operations on values such as marks, weights,
234 counts, and pointers needed by algorithms. Application programmers
235 define the fields of these records, but they have a common header as
236 shown below.
237 typedef struct Agrec_s {
238 char *name;
239 struct Agrec_s *next;
240 /* programmer-defined follows */
241 } Agrec_t;
242 Records are created and managed by Libagraph. In each graph, node, or
243 edge, data points to a circular list of records. The name field dis‐
244 tinguishes various types of records, and is programmer defined (Liba‐
245 graph reserves the prefix _ag). next stores the list pointers. The
246 remainder of a record may contain application-dependent fields.
247 agnewrec creates one new record of the given size and attaches it to
248 the given object (graph, node, or edge). agdelrec is the corresponding
249 function to delete records. aggetrec finds a record with the given
250 name.
251 To allow referencing application-dependent data without function calls
253 or linear search, Libagraph allows setting and locking the data field
254 of a graph, node, or edge on a particular record. The move_to_front
255 flag may be AG_MTF_FALSE, AG_MTF_SOFT, or AG_MTF_HARD accordingly. The
256 AG_MTF_SOFT field is only a hint that decreases overhead in subsequent
257 calls of aggetrec; AG_MTF_HARD guarantees that a lock was obtained. To
258 release locks, use AG_MTF_SOFT or AG_MTF_FALSE. Use of this feature
259 implies cooperation or at least isolation from other functions also
260 using the move-to-front convention.
261 A cast (generally using a macro or inline function) is then needed to
263 convert the data pointer to an appropriate programmer-defined type.
264
267 Programmer-defined disciplines customize certain resources- ID names‐
268 pace, memory, and I/O - needed by Libagraph. A discipline struct (or
269 NIL) is passed at graph creation time.
270 struct Agdisc_s { /* user's discipline */
271 Agmemdisc_t *mem;
272 Agiddisc_t *id;
273 Agiodisc_t *io;
274 } ;
275 A default discipline is supplied when NIL is given for any of these
276 fields.
277 An ID allocator discipline allows a client to control assignment of IDs
279 (uninterpreted 32-bit values) to objects, and possibly how they are
280 mapped to and from strings.
281 struct Agiddisc_s { /* object ID allocator */
283 void *(*open)(Agraph_t *g); /* associated with a graph */
284 int (*map)(void *state, int objtype, char *str, ulong *id, int createflag);
285 int (*alloc)(void *state, int objtype, ulong id);
286 void (*free)(void *state, int objtype, ulong id);
287 char *(*print)(void *state, int objtype, ulong id);
288 void (*close)(void *state);
289 } ;
290 open permits the ID discipline to initialize any data structures that
292 maintains per individual graph. Its return value is then passed as the
293 first argument to all subsequent ID manager calls.
294 alloc informs the ID manager that Libagraph is attempting to create an
296 object with a specific ID that was given by a client. The ID manager
297 should return TRUE (nonzero) if the ID can be allocated, or FALSE
298 (which aborts the operation).
299 free is called to inform the ID manager that the object labeled with
301 the given ID is about to go out of existence.
302 map is called to create or look-up IDs by string name (if supported by
304 the ID manager). Returning TRUE (nonzero) in all cases means that the
305 request succeeded (with a valid ID stored through result. There are
306 four cases:
307 name != NULL and createflag == 1: This requests mapping a string (e.g.
309 a name in a graph file) into a new ID. If the ID manager can comply,
310 then it stores the result and returns TRUE. It is then also responsi‐
311 ble for being able to print the ID again as a string. Otherwise the ID
312 manager may return FALSE but it must implement the following (at least
313 for graph file reading and writing to work):
314 name == NULL and createflag == 1: The ID manager creates a unique new
316 ID of its own choosing. Although it may return FALSE if it does not
317 support anonymous objects, but this is strongly discouraged (to support
318 "local names" in graph files.)
319 name != NULL and createflag == 0: This is a namespace probe. If the
321 name was previously mapped into an allocated ID by the ID manager, then
322 the manager must return this ID. Otherwise, the ID manager may either
323 return FALSE, or may store any unallocated ID into result. (This is
324 convenient, for example, if names are known to be digit strings that
325 are directly converted into 32 bit values.)
326 name == NULL and createflag == 0: forbidden.
328 print should return print is allowed to return a pointer to a static
330 buffer; a caller must copy its value if needed past subsequent calls.
331 NULL should be returned by ID managers that do not map names.
332 The map and alloc calls do not pass a pointer to the newly allocated
334 object. If a client needs to install object pointers in a handle ta‐
335 ble, it can obtain them via new object callbacks.
336 struct Agiodisc_s {
337 int (*fread)(void *chan, char *buf, int bufsize);
338 int (*putstr)(void *chan, char *str);
339 int (*flush)(void *chan); /* sync */
340 /* error messages? */
341 } ;
342 struct Agmemdisc_s { /* memory allocator */
344 void *(*open)(void); /* independent of other resources */
345 void *(*alloc)(void *state, size_t req);
346 void *(*resize)(void *state, void *ptr, size_t old, size_t req);
347 void (*free)(void *state, void *ptr);
348 void (*close)(void *state);
349 } ;
350
353 #include <graphviz/agraph.h>
354 typedef struct mydata_s {int x,y,z;} mydata;
355 main(int argc, char **argv)
357 {
358 Agraph_t *g;
359 Agnode_t *v;
360 Agedge_t *e;
361 Agsym_t *attr;
362 Dict_t *d
363 int cnt;
364 mydata *p;
365 if (g = agread(stdin,NIL(Agdisc_t*))) {
367 /* dtsize() is a Libdict primitive */
368 fprintf(stderr,"%s has %d node attributes0,
369 dtsize(agdictof(g,AGNODE)));
370 attr = agattr(g,AGNODE,"color","blue");
371 /* create a new graph */
373 h = agopen("tmp",g->desc);
374 /* this is a way of counting all the edges of the graph */
376 cnt = 0;
377 for (v = agfstnode(g); v; v = agnxtnode(g,v))
378 for (e = agfstout(g,v); e; e = agnxtout(g,e))
379 cnt++;
380 /* using inline functions or macros, attach records to edges */
382 agflatten(g);
383 for (v = agfstn(g); v; v = agnxtn(v))
384 for (e = agfout(v); e; e; = agnxte(e)) {
385 p = (mydata*) agnewrec(g,e,"mydata",sizeof(mydata));
386 p->x = 27; /* meaningless example */
387 }
388 }
389 }
390
392 digraph G {
393 a -> b;
394 c [shape=box];
395 a -> c [weight=29,label="some text];
396 subgraph anything {
397 /* the following affects only x,y,z */
398 node [shape=circle];
399 a; x; y -> z; y -> z; /* multiple edges */
400 }
401 }
402 strict graph H {
404 n0 -- n1 -- n2 -- n0; /* a cycle */
405 n0 -- {a b c d}; /* a star */
406 n0 -- n3;
407 n0 -- n3 [weight=1]; /* same edge because graph is strict */
408 }
409
411 Libcdt(3)
412
415 The root graph name is treated as a comment.
416 There is no way to delete string attributes or modify edge keys.
418 Strings and uninterpreted records could be treatly more uniformly.
420
423 Stephen North, north@research.att.com, AT&T Research.
424 8 MARCH 1996 LIBAGRAPH(3)