1LIBCGRAPH(3) Library Functions Manual LIBCGRAPH(3)
2
6 libcgraph - abstract graph library
7
9 #include <graphviz/cgraph.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 *channel, Agdisc_t *);
23 void agreadline(int line_no);
24 void agsetfile(char *file_name);
25 Agraph_t *agconcat(Agraph_t *g, void *channel, Agdisc_t *disc)
26 int agwrite(Agraph_t *g, void *channel);
27 int agnnodes(Agraph_t *g),agnedges(Agraph_t *g);
28 int agisdirected(Agraph_t * g),agisundirected(Agraph_t * g),agisstrict(Agraph_t * g), agissimple(Agraph_t * g);
29 SUBGRAPHS
31 Agraph_t *agsubg(Agraph_t *g, char *name, int createflag);
32 Agraph_t *agidsubg(Agraph_t * g, unsigned long id, int cflag);
33 Agraph_t *agfstsubg(Agraph_t *g), agnxtsubg(Agraph_t *);
34 Agraph_t *agparent(Agraph_t *g);
35 int agdelsubg(Agraph_t * g, Agraph_t * sub); /* same as agclose() */
36 NODES
38 Agnode_t *agnode(Agraph_t *g, char *name, int createflag);
39 Agnode_t *agidnode(Agraph_t *g, ulong id, int createflag);
40 Agnode_t *agsubnode(Agraph_t *g, Agnode_t *n, int createflag);
41 Agnode_t *agfstnode(Agraph_t *g);
42 Agnode_t *agnxtnode(Agraph_t *g, Agnode_t *n);
43 Agnode_t *agprvnode(Agraph_t *g, Agnode_t *n);
44 Agnode_t *aglstnode(Agraph_t *g);
45 int agdelnode(Agraph_t *g, Agnode_t *n);
46 int agdegree(Agnode_t *n, int use_inedges, int use_outedges);
47 EDGES
49 Agedge_t *agedge(Agraph_t* g, Agnode_t *t, Agnode_t *h, char *name, int createflag);
50 Agedge_t *agidedge(Agraph_t * g, Agnode_t * t, Agnode_t * h, unsigned long id, int createflag);
51 Agedge_t *agsubedge(Agraph_t *g, Agedge_t *e, int createflag);
52 Agnode_t *aghead(Agedge_t *e), *agtail(Agedge_t *e);
53 Agedge_t *agfstedge(Agraph_t* g, Agnode_t *n);
54 Agedge_t *agnxtedge(Agraph_t* g, Agedge_t *e, Agnode_t *n);
55 Agedge_t *agfstin(Agraph_t* g, Agnode_t *n);
56 Agedge_t *agnxtin(Agraph_t* g, Agedge_t *e);
57 Agedge_t *agfstout(Agraph_t* g, Agnode_t *n);
58 Agedge_t *agnxtout(Agraph_t* g, Agedge_t *e);
59 int agdeledge(Agraph_t *g, Agedge_t *e);
60 STRING ATTRIBUTES
62 Agsym_t *agattr(Agraph_t *g, int kind, char *name, char *value);
63 Agsym_t *agattrsym(void *obj, char *name);
64 Agsym_t *agnxtattr(Agraph_t *g, int kind, Agsym_t *attr);
65 char *agget(void *obj, char *name);
66 char *agxget(void *obj, Agsym_t *sym);
67 int agset(void *obj, char *name, char *value);
68 int agxset(void *obj, Agsym_t *sym, char *value);
69 int agsafeset(void *obj, char *name, char *value, char *def);
70 RECORDS
72 void *agbindrec(void *obj, char *name, unsigned int size, move_to_front);
73 Agrec_t *aggetrec(void *obj, char *name, int move_to_front);
74 int agdelrec(Agraph_t *g, void *obj, char *name);
75 int agcopyattr(void *, void *);
76 void aginit(Agraph_t * g, int kind, char *rec_name, int rec_size, int move_to_front);
77 void agclean(Agraph_t * g, int kind, char *rec_name);
78 CALLBACKS
80 Agcbdisc_t *agpopdisc(Agraph_t *g);
81 void agpushdisc(Agraph_t *g, Agcbdisc_t *disc);
82 void agmethod(Agraph_t *g, void *obj, Agcbdisc_t *disc, int initflag);
83 MEMORY
85 void *agalloc(Agraph_t *g, size_t request);
86 void *agrealloc(Agraph_t *g, void *ptr, size_t oldsize, size_t newsize);
87 void agfree(Agraph_t *g, void *ptr);
88 STRINGS
90 char *agstrdup(Agraph_t *, char *);
91 char *agstrdup_html(Agraph_t *, char *);
92 int aghtmlstr(char *);
93 char *agstrbind(Agraph_t * g, char *);
94 int strfree(Agraph_t *, char *);
95 char *agcanonStr(char *);
96 char *agstrcanon(char *, char *);
97 GENERIC OBJECTS
99 Agraph_t *agraphof(void*);
100 Agraph_t *agroot(void*);
101 int agcontains(Agraph_t*, void*);
102 char *agnameof(void*);
103 void agdelete(Agraph_t *g, void *obj);
104 int agobjkind(void *obj);
105 Agrec_t *AGDATA(void *obj);
106 ulong AGID(void *obj);
107 int AGTYPE(void *obj);
108
110 Libcgraph supports graph programming by maintaining graphs in memory
111 and reading and writing graph files. Graphs are composed of nodes,
112 edges, and nested subgraphs. These graph objects may be attributed
113 with string name-value pairs and programmer-defined records (see
114 Attributes).
115 All of Libcgraph's global symbols have the prefix ag (case varying).
117
119 A ``main'' or ``root'' graph defines a namespace for a collection of
120 graph objects (subgraphs, nodes, edges) and their attributes. Objects
121 may be named by unique strings or by 32-bit IDs.
122 agopen creates a new graph with the given name and kind. (Graph kinds
124 are Agdirected, Agundirected, Agstrictdirected, and Agstrictundirected.
125 A strict graph cannot have multi-edges or self-arcs.) agclose deletes
126 a graph, freeing its associated storage. agread, agwrite, and agconcat
127 perform file I/O using the graph file language described below. agread
128 constructs a new graph while agconcat merges the file contents with a
129 pre-existing graph. Though I/O methods may be overridden, the default
130 is that the channel argument is a stdio FILE pointer. agsetfile and
131 agreadline are helper functions that simply set the current file name
132 and input line number for subsequent error reporting.
133 agsubg finds or creates a subgraph by name. A new subgraph is is ini‐
135 tially empty and is of the same kind as its parent. Nested subgraph
136 trees may be created. A subgraph's name is only interpreted relative
137 to its parent. A program can scan subgraphs under a given graph using
138 agfstsubg and agnxtsubg. A subgraph is deleted with agdelsubg (or
139 agclose).
140 By default, nodes are stored in ordered sets for efficient random
142 access to insert, find, and delete nodes. The edges of a node are also
143 stored in ordered sets. The sets are maintained internally as splay
144 tree dictionaries using Phong Vo's cdt library.
145 agnnodes, agnedges, and agdegree return the sizes of node and edge sets
147 of a graph. The agdegree returns the size of the edge set of a nodes,
148 and takes flags to select in-edges, out-edges, or both.
149 An Agdisc_t defines callbacks to be invoked by libcgraph when initial‐
151 izing, modifying, or finalizing graph objects. (Casual users can
152 ignore the following.) Disciplines are kept on a stack. Libcgraph
153 automatically calls the methods on the stack, top-down. Callbacks are
154 installed with agpushdisc, uninstalled with agpopdisc, and can be held
155 pending or released via agcallbacks.
156 (Casual users may ignore the following. When Libcgraph is compiled
158 with Vmalloc (which is not the default), each graph has its own heap.
159 Programmers may allocate application-dependent data within the same
160 heap as the rest of the graph. The advantage is that a graph can be
161 deleted by atomically freeing its entire heap without scanning each
162 individual node and edge.
163
165 A node is created by giving a unique string name or programmer defined
166 32-bit ID, and is represented by a unique internal object. (Node equal‐
167 ity can checked by pointer comparison.)
168 agnode searches in a graph or subgraph for a node with the given name,
170 and returns it if found. If not found, if createflag is boolean true a
171 new node is created and returned, otherwise a nil pointer is returned.
172 agidnode allows a programmer to specify the node by a unique 32-bit ID.
173 agsubnode performs a similar operation on an existing node and a sub‐
174 graph. agfstnode and agnxtnode scan node lists. agprvnode and aglstn‐
175 ode are symmetric but scan backward. The default sequence is order of
176 creation (object timestamp.) agdelnode removes a node from a graph or
177 subgraph.
178
180 An abstract edge has two endpoint nodes called tail and head where the
181 all outedges of the same node have it as the tail value and similarly
182 all inedges have it as the head. In an undirected graph, head and tail
183 are interchangable. If a graph has multi-edges between the same pair
184 of nodes, the edge's string name behaves as a secondary key. agedge
185 searches in a graph of subgraph for an edge between the given endpoints
186 (with an optional multi-edge selector name) and returns it if found.
187 Otherwise, if createflag is boolean true, a new edge is created and
188 returned: otherwise a nil pointer is returned. If the name is NULL,
189 then an anonymous internal value is generated. agidedge allows a pro‐
190 grammer to create an edge by giving its unique 32-bit ID. agfstin,
191 agnxtint, agfstout, and agnxtout visit directed in- and out- edge
192 lists, and ordinarily apply only in directed graphs. agfstedge and
193 agnxtedge visit all edges incident to a node. agtail and aghead get
194 the endpoint of an edge.
195
197 Programmer-defined values may be dynamically attached to graphs, sub‐
198 graphs, nodes, and edges. Such values are either uninterpreted binary
199 records (for implementing efficient algorithms) or character string
200 data (for I/O).
201
203 String attributes are handled automatically in reading and writing
204 graph files. A string attribute is identified by name and by an inter‐
205 nal symbol table entry (Agsym_t) created by Libcgraph. Attributes of
206 nodes, edges, and graphs (with their subgraphs) have separate names‐
207 paces. The contents of an Agsym_t is listed below, followed by primi‐
208 tives to operate on string attributes.
209 typedef struct Agsym_s { /* symbol in one of the above dictionaries */
210 Dtlink_t link;
211 char *name; /* attribute's name */
212 char *defval; /* its default value for initialization */
213 int id; /* its index in attr[] */
214 unsigned char kind; /* referent object type */
215 unsigned char fixed; /* immutable value */
216 } Agsym_t;
217 agattr creates or looks up attributes. kind may be AGRAPH, AGNODE, or
219 AGEDGE. If value is (char*)0), the request is to search for an exist‐
220 ing attribute of the given kind and name. Otherwise, if the attribute
221 already exists, its default for creating new objects is set to the
222 given value; if it does not exist, a new attribute is created with the
223 given default, and the default is applied to all pre-existing objects
224 of the given kind. If g is NIL, the default is set for all graphs cre‐
225 ated subsequently. agattrsym is a helper function that looks up an
226 attribute for a graph object given as an argument. agnxtattr permits
227 traversing the list of attributes of a given type. If NIL is passed as
228 an argument it gets the first attribute, otherwise it returns the next
229 one in succession or returns NIL at the end of the list. agget and
230 agset allow fetching and updating a string attribute for an object tak‐
231 ing the attribute name as an argument. agxget and agxset do this but
232 with an attribute symbol table entry as an argument (to avoid the cost
233 of the string lookup). agsafeset is a convenience function that
234 ensures the given attribute is declared before setting it locally on an
235 object.
236
239 Libcgraph performs its own storage management of strings as reference-
240 counted strings. The caller does not need to dynamically allocate
241 storage.
242 agstrdup returns a pointer to a reference-counted copy of the argument
244 string, creating one if necessary. agstrbind returns a pointer to a
245 reference-counted string if it exists, or NULL if not. All uses of
246 cgraph strings need to be freed using agstrfree in order to correctly
247 maintain the reference count.
248 agcanonStr returns a pointer to a version of the input string canoni‐
250 calized for output for later re-parsing. This includes quoting special
251 characters and keywords. It uses its own internal buffer, so the value
252 will be lost on the next call to agcanonStr. agstrcanon is an unsafe
253 version of agcanonStr, in which the application passes in a buffer as
254 the second argument. Note that the buffer may not be used; if the input
255 string is in canonical form, the function will just return a pointer to
256 it.
257 The cgraph parser handles HTML-like strings. These should be indistin‐
259 guishable from other strings for most purposes. To create an HTML-like
260 string, use agstrdup_html. The aghtmlstr function can be used to query
261 if a string is an ordinary string or an HTML-like string.
262
264 Uninterpreted records may be attached to graphs, subgraphs, nodes, and
265 edges for efficient operations on values such as marks, weights,
266 counts, and pointers needed by algorithms. Application programmers
267 define the fields of these records, but they must be declared with a
268 common header as shown below.
269 typedef struct Agrec_s {
270 Agrec_t header;
271 /* programmer-defined fields follow */
272 } Agrec_t;
273 Records are created and managed by Libcgraph. A programmer must explic‐
274 itly attach them to the objects in a graph, either to individual
275 objects one at a time via agbindrec, or to all the objects of the same
276 class in a graph via aginit. (Note that for graphs, aginit is applied
277 recursively to the graph and its subgraphs if rec_size is negative (of
278 the actual rec_size.)) The name argument a record distinguishes vari‐
279 ous types of records, and is programmer defined (Libcgraph reserves the
280 prefix _ag). If size is 0, the call to agbindrec is simply a lookup.
281 agdelrec is the deletes records one at a time. agclean does the same
282 for all objects of the same class in an entire graph.
283 Internally, records are maintained in circular linked lists attached to
285 graph objects. To allow referencing application-dependent data without
286 function calls or search, Libcgraph allows setting and locking the list
287 pointer of a graph, node, or edge on a particular record. This pointer
288 can be obtained with the macro AGDATA(obj). A cast, generally within a
289 macro or inline function, is usually applied to convert the list
290 pointer to an appropriate programmer-defined type.
291 To control the setting of this pointer, the move_to_front flag may be
293 AG_MTF_FALSE, AG_MTF_SOFT, or AG_MTF_HARD accordingly. The AG_MTF_SOFT
294 field is only a hint that decreases overhead in subsequent calls of
295 aggetrec; AG_MTF_HARD guarantees that a lock was obtained. To release
296 locks, use AG_MTF_SOFT or AG_MTF_FALSE. Use of this feature implies
297 cooperation or at least isolation from other functions also using the
298 move-to-front convention.
299
302 (The following is not intended for casual users.) Programmer-defined
303 disciplines customize certain resources- ID namespace, memory, and I/O
304 - needed by Libcgraph. A discipline struct (or NIL) is passed at graph
305 creation time.
306 struct Agdisc_s { /* user's discipline */
307 Agmemdisc_t *mem;
308 Agiddisc_t *id;
309 Agiodisc_t *io;
310 } ;
311 A default discipline is supplied when NIL is given for any of these
312 fields.
313 An ID allocator discipline allows a client to control assignment of IDs
315 (uninterpreted 32-bit values) to objects, and possibly how they are
316 mapped to and from strings.
317 struct Agiddisc_s { /* object ID allocator */
319 void *(*open)(Agraph_t *g); /* associated with a graph */
320 int (*map)(void *state, int objtype, char *str, ulong *id, int createflag);
321 int (*alloc)(void *state, int objtype, ulong id);
322 void (*free)(void *state, int objtype, ulong id);
323 char *(*print)(void *state, int objtype, ulong id);
324 void (*close)(void *state);
325 } ;
326 open permits the ID discipline to initialize any data structures that
328 maintains per individual graph. Its return value is then passed as the
329 first argument to all subsequent ID manager calls.
330 alloc informs the ID manager that Libcgraph is attempting to create an
332 object with a specific ID that was given by a client. The ID manager
333 should return TRUE (nonzero) if the ID can be allocated, or FALSE
334 (which aborts the operation).
335 free is called to inform the ID manager that the object labeled with
337 the given ID is about to go out of existence.
338 map is called to create or look-up IDs by string name (if supported by
340 the ID manager). Returning TRUE (nonzero) in all cases means that the
341 request succeeded (with a valid ID stored through result. There are
342 four cases:
343 name != NULL and createflag == 1: This requests mapping a string (e.g.
345 a name in a graph file) into a new ID. If the ID manager can comply,
346 then it stores the result and returns TRUE. It is then also responsi‐
347 ble for being able to print the ID again as a string. Otherwise the ID
348 manager may return FALSE but it must implement the following (at least
349 for graph file reading and writing to work):
350 name == NULL and createflag == 1: The ID manager creates a unique new
352 ID of its own choosing. Although it may return FALSE if it does not
353 support anonymous objects, but this is strongly discouraged (to support
354 "local names" in graph files.)
355 name != NULL and createflag == 0: This is a namespace probe. If the
357 name was previously mapped into an allocated ID by the ID manager, then
358 the manager must return this ID. Otherwise, the ID manager may either
359 return FALSE, or may store any unallocated ID into result. (This is
360 convenient, for example, if names are known to be digit strings that
361 are directly converted into 32 bit values.)
362 name == NULL and createflag == 0: forbidden.
364 print is allowed to return a pointer to a static buffer; a caller must
366 copy its value if needed past subsequent calls. NULL should be
367 returned by ID managers that do not map names.
368 The map and alloc calls do not pass a pointer to the newly allocated
370 object. If a client needs to install object pointers in a handle ta‐
371 ble, it can obtain them via new object callbacks.
372 struct Agiodisc_s {
373 int (*fread)(void *chan, char *buf, int bufsize);
374 int (*putstr)(void *chan, char *str);
375 int (*flush)(void *chan); /* sync */
376 /* error messages? */
377 } ;
378 struct Agmemdisc_s { /* memory allocator */
380 void *(*open)(void); /* independent of other resources */
381 void *(*alloc)(void *state, size_t req);
382 void *(*resize)(void *state, void *ptr, size_t old, size_t req);
383 void (*free)(void *state, void *ptr);
384 void (*close)(void *state);
385 } ;
386
389 #include <graphviz/cgraph.h>
390 typedef struct mydata_s {Agrec_t hdr; int x,y,z;} mydata;
391 main(int argc, char **argv)
393 {
394 Agraph_t *g;
395 Agnode_t *v;
396 Agedge_t *e;
397 Agsym_t *attr;
398 Dict_t *d
399 int cnt;
400 mydata *p;
401 if (g = agread(stdin,NIL(Agdisc_t*))) {
403 cnt = 0; attr = 0;
404 while (attr = agnxtattr(g, AGNODE, attr)) cnt++;
405 printf("The graph %s has %d attributes0,agnameof(g),cnt);
406 /* make the graph have a node color attribute, default is blue */
408 attr = agattr(g,AGNODE,"color","blue");
409 /* create a new graph of the same kind as g */
411 h = agopen("tmp",g->desc);
412 /* this is a way of counting all the edges of the graph */
414 cnt = 0;
415 for (v = agfstnode(g); v; v = agnxtnode(g,v))
416 for (e = agfstout(g,v); e; e = agnxtout(g,e))
417 cnt++;
418 /* attach records to edges */
420 for (v = agfstnode(g); v; v = agnxtnode(g,v))
421 for (e = agfstout(g,v); e; e; = agnxtout(g,e)) {
422 p = (mydata*) agbindrec(g,e,"mydata",sizeof(mydata),TRUE);
423 p->x = 27; /* meaningless data access example */
424 ((mydata*)(AGDATA(e)))->y = 999; /* another example */
425 }
426 }
427 }
428
430 digraph G {
431 a -> b;
432 c [shape=box];
433 a -> c [weight=29,label="some text];
434 subgraph anything {
435 /* the following affects only x,y,z */
436 node [shape=circle];
437 a; x; y -> z; y -> z; /* multiple edges */
438 }
439 }
440 strict graph H {
442 n0 -- n1 -- n2 -- n0; /* a cycle */
443 n0 -- {a b c d}; /* a star */
444 n0 -- n3;
445 n0 -- n3 [weight=1]; /* same edge because graph is strict */
446 }
447
449 Libcdt(3)
450
453 It is difficult to change endpoints of edges, delete string attributes
454 or modify edge keys. The work-around is to create a new object and
455 copy the contents of an old one (but new object obviously has a differ‐
456 ent ID, internal address, and object creation timestamp).
457 The API lacks convenient functions to substitute programmer-defined
459 ordering of nodes and edges but in principle this can be supported.
460
462 Stephen North, north@research.att.com, AT&T Research.
463 30 JULY 2007 LIBCGRAPH(3)