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 ERROR REPORTING
110 typedef enum { AGWARN, AGERR, AGMAX, AGPREV } agerrlevel_t;
111 typedef int (*agusererrf) (char*);
112 agerrlevel_t agerrno;
113 agerrlevel_t agseterr(agerrlevel_t);
114 char *aglasterr(void);
115 int agerr(agerrlevel_t level, char *fmt, ...);
116 void agerrorf(char *fmt, ...);
117 void agwarningf(char *fmt, ...);
118 int agerrors(void);
119 agusererrf agseterrf(agusererrf);
120
122 Libcgraph supports graph programming by maintaining graphs in memory
123 and reading and writing graph files. Graphs are composed of nodes,
124 edges, and nested subgraphs. These graph objects may be attributed
125 with string name-value pairs and programmer-defined records (see
126 Attributes).
127 All of Libcgraph's global symbols have the prefix ag (case varying).
129
131 A ``main'' or ``root'' graph defines a namespace for a collection of
132 graph objects (subgraphs, nodes, edges) and their attributes. Objects
133 may be named by unique strings or by integer IDs.
134 agopen creates a new graph with the given name and kind. (Graph kinds
136 are Agdirected, Agundirected, Agstrictdirected, and Agstrictundirected.
137 A strict graph cannot have multi-edges or self-arcs.) agclose deletes
138 a graph, freeing its associated storage. agread, agwrite, and agconcat
139 perform file I/O using the graph file language described below. agread
140 constructs a new graph while agconcat merges the file contents with a
141 pre-existing graph. Though I/O methods may be overridden, the default
142 is that the channel argument is a stdio FILE pointer. agsetfile and
143 agreadline are helper functions that simply set the current file name
144 and input line number for subsequent error reporting.
145 agsubg finds or creates a subgraph by name. A new subgraph is is ini‐
147 tially empty and is of the same kind as its parent. Nested subgraph
148 trees may be created. A subgraph's name is only interpreted relative
149 to its parent. A program can scan subgraphs under a given graph using
150 agfstsubg and agnxtsubg. A subgraph is deleted with agdelsubg (or
151 agclose).
152 By default, nodes are stored in ordered sets for efficient random
154 access to insert, find, and delete nodes. The edges of a node are also
155 stored in ordered sets. The sets are maintained internally as splay
156 tree dictionaries using Phong Vo's cdt library.
157 agnnodes, agnedges, and agdegree return the sizes of node and edge sets
159 of a graph. The agdegree returns the size of the edge set of a nodes,
160 and takes flags to select in-edges, out-edges, or both.
161 An Agdisc_t defines callbacks to be invoked by libcgraph when initial‐
163 izing, modifying, or finalizing graph objects. (Casual users can
164 ignore the following.) Disciplines are kept on a stack. Libcgraph
165 automatically calls the methods on the stack, top-down. Callbacks are
166 installed with agpushdisc, uninstalled with agpopdisc, and can be held
167 pending or released via agcallbacks.
168 (Casual users may ignore the following. When Libcgraph is compiled
170 with Vmalloc (which is not the default), each graph has its own heap.
171 Programmers may allocate application-dependent data within the same
172 heap as the rest of the graph. The advantage is that a graph can be
173 deleted by atomically freeing its entire heap without scanning each
174 individual node and edge.
175
177 A node is created by giving a unique string name or programmer defined
178 integer ID, and is represented by a unique internal object. (Node
179 equality can checked by pointer comparison.)
180 agnode searches in a graph or subgraph for a node with the given name,
182 and returns it if found. If not found, if createflag is boolean true a
183 new node is created and returned, otherwise a nil pointer is returned.
184 agidnode allows a programmer to specify the node by a unique integer
185 ID. agsubnode performs a similar operation on an existing node and a
186 subgraph.
187 agfstnode and agnxtnode scan node lists. agprvnode and aglstnode are
189 symmetric but scan backward. The default sequence is order of creation
190 (object timestamp.) agdelnode removes a node from a graph or subgraph.
191
193 An abstract edge has two endpoint nodes called tail and head where the
194 all outedges of the same node have it as the tail value and similarly
195 all inedges have it as the head. In an undirected graph, head and tail
196 are interchangeable. If a graph has multi-edges between the same pair
197 of nodes, the edge's string name behaves as a secondary key.
198 agedge searches in a graph of subgraph for an edge between the given
200 endpoints (with an optional multi-edge selector name) and returns it if
201 found. Otherwise, if createflag is boolean true, a new edge is created
202 and returned: otherwise a nil pointer is returned. If the name is
203 NULL, then an anonymous internal value is generated. agidedge allows a
204 programmer to create an edge by giving its unique integer ID. agfstin,
205 agnxtint, agfstout, and agnxtout visit directed in- and out- edge
206 lists, and ordinarily apply only in directed graphs. agfstedge and
207 agnxtedge visit all edges incident to a node. agtail and aghead get
208 the endpoint of an edge.
209
211 Programmer-defined values may be dynamically attached to graphs, sub‐
212 graphs, nodes, and edges. Such values are either uninterpreted binary
213 records (for implementing efficient algorithms) or character string
214 data (for I/O).
215
217 String attributes are handled automatically in reading and writing
218 graph files. A string attribute is identified by name and by an inter‐
219 nal symbol table entry (Agsym_t) created by Libcgraph. Attributes of
220 nodes, edges, and graphs (with their subgraphs) have separate names‐
221 paces. The contents of an Agsym_t is listed below, followed by primi‐
222 tives to operate on string attributes.
223 typedef struct Agsym_s { /* symbol in one of the above dictionaries */
224 Dtlink_t link;
225 char *name; /* attribute's name */
226 char *defval; /* its default value for initialization */
227 int id; /* its index in attr[] */
228 unsigned char kind; /* referent object type */
229 unsigned char fixed; /* immutable value */
230 } Agsym_t;
231 agattr creates or looks up attributes. kind may be AGRAPH, AGNODE, or
233 AGEDGE. If value is (char*)0), the request is to search for an exist‐
234 ing attribute of the given kind and name. Otherwise, if the attribute
235 already exists, its default for creating new objects is set to the
236 given value; if it does not exist, a new attribute is created with the
237 given default, and the default is applied to all pre-existing objects
238 of the given kind. If g is NIL, the default is set for all graphs cre‐
239 ated subsequently. agattrsym is a helper function that looks up an
240 attribute for a graph object given as an argument. agnxtattr permits
241 traversing the list of attributes of a given type. If NIL is passed as
242 an argument it gets the first attribute, otherwise it returns the next
243 one in succession or returns NIL at the end of the list. agget and
244 agset allow fetching and updating a string attribute for an object tak‐
245 ing the attribute name as an argument. agxget and agxset do this but
246 with an attribute symbol table entry as an argument (to avoid the cost
247 of the string lookup). agsafeset is a convenience function that
248 ensures the given attribute is declared before setting it locally on an
249 object.
250
253 Libcgraph performs its own storage management of strings as reference-
254 counted strings. The caller does not need to dynamically allocate
255 storage.
256 agstrdup returns a pointer to a reference-counted copy of the argument
258 string, creating one if necessary. agstrbind returns a pointer to a
259 reference-counted string if it exists, or NULL if not. All uses of
260 cgraph strings need to be freed using agstrfree in order to correctly
261 maintain the reference count.
262 agcanonStr returns a pointer to a version of the input string canoni‐
264 calized for output for later re-parsing. This includes quoting special
265 characters and keywords. It uses its own internal buffer, so the value
266 will be lost on the next call to agcanonStr. agstrcanon is an unsafe
267 version of agcanonStr, in which the application passes in a buffer as
268 the second argument. Note that the buffer may not be used; if the input
269 string is in canonical form, the function will just return a pointer to
270 it.
271 The cgraph parser handles HTML-like strings. These should be indistin‐
273 guishable from other strings for most purposes. To create an HTML-like
274 string, use agstrdup_html. The aghtmlstr function can be used to query
275 if a string is an ordinary string or an HTML-like string.
276
278 Uninterpreted records may be attached to graphs, subgraphs, nodes, and
279 edges for efficient operations on values such as marks, weights,
280 counts, and pointers needed by algorithms. Application programmers
281 define the fields of these records, but they must be declared with a
282 common header as shown below.
283 typedef struct Agrec_s {
285 Agrec_t header;
286 /* programmer-defined fields follow */
287 } Agrec_t;
288 Records are created and managed by Libcgraph. A programmer must explic‐
290 itly attach them to the objects in a graph, either to individual
291 objects one at a time via agbindrec, or to all the objects of the same
292 class in a graph via aginit. (Note that for graphs, aginit is applied
293 recursively to the graph and its subgraphs if rec_size is negative (of
294 the actual rec_size.)) The name argument a record distinguishes vari‐
295 ous types of records, and is programmer defined (Libcgraph reserves the
296 prefix _ag). If size is 0, the call to agbindrec is simply a lookup.
297 agdelrec is the deletes records one at a time. agclean does the same
298 for all objects of the same class in an entire graph.
299 Internally, records are maintained in circular linked lists attached to
301 graph objects. To allow referencing application-dependent data without
302 function calls or search, Libcgraph allows setting and locking the list
303 pointer of a graph, node, or edge on a particular record. This pointer
304 can be obtained with the macro AGDATA(obj). A cast, generally within a
305 macro or inline function, is usually applied to convert the list
306 pointer to an appropriate programmer-defined type.
307 To control the setting of this pointer, the move_to_front flag may be
309 AG_MTF_FALSE, AG_MTF_SOFT, or AG_MTF_HARD accordingly. The AG_MTF_SOFT
310 field is only a hint that decreases overhead in subsequent calls of
311 aggetrec; AG_MTF_HARD guarantees that a lock was obtained. To release
312 locks, use AG_MTF_SOFT or AG_MTF_FALSE. Use of this feature implies
313 cooperation or at least isolation from other functions also using the
314 move-to-front convention.
315
318 (The following is not intended for casual users.) Programmer-defined
319 disciplines customize certain resources- ID namespace, memory, and I/O
320 - needed by Libcgraph. A discipline struct (or NIL) is passed at graph
321 creation time.
322 struct Agdisc_s { /* user's discipline */
324 Agmemdisc_t *mem;
325 Agiddisc_t *id;
326 Agiodisc_t *io;
327 } ;
328 A default discipline is supplied when NIL is given for any of these
330 fields.
331 An ID allocator discipline allows a client to control assignment of IDs
333 (uninterpreted integer values) to objects, and possibly how they are
334 mapped to and from strings.
335 struct Agiddisc_s { /* object ID allocator */
337 void *(*open) (Agraph_t * g, Agdisc_t*); /* associated with a graph */
338 long (*map) (void *state, int objtype, char *str, unsigned long *id, int createflag);
339 long (*alloc) (void *state, int objtype, unsigned long id);
340 void (*free) (void *state, int objtype, unsigned long id);
341 char *(*print) (void *state, int objtype, unsigned long id);
342 void (*close) (void *state);
343 };
344 open permits the ID discipline to initialize any data structures that
346 it maintains per individual graph. Its return value is then passed as
347 the first argument (void *state) to all subsequent ID manager calls.
348 alloc informs the ID manager that Libcgraph is attempting to create an
350 object with a specific ID that was given by a client. The ID manager
351 should return TRUE (nonzero) if the ID can be allocated, or FALSE
352 (which aborts the operation).
353 free is called to inform the ID manager that the object labeled with
355 the given ID is about to go out of existence.
356 map is called to create or look-up IDs by string name (if supported by
358 the ID manager). Returning TRUE (nonzero) in all cases means that the
359 request succeeded (with a valid ID stored through result. There are
360 four cases:
361 name != NULL and createflag == 1: This requests mapping a string (e.g.
363 a name in a graph file) into a new ID. If the ID manager can comply,
364 then it stores the result and returns TRUE. It is then also responsi‐
365 ble for being able to print the ID again as a string. Otherwise the ID
366 manager may return FALSE but it must implement the following (at least
367 for graph file reading and writing to work):
368 name == NULL and createflag == 1: The ID manager creates a unique new
370 ID of its own choosing. Although it may return FALSE if it does not
371 support anonymous objects, but this is strongly discouraged (to support
372 "local names" in graph files.)
373 name != NULL and createflag == 0: This is a namespace probe. If the
375 name was previously mapped into an allocated ID by the ID manager, then
376 the manager must return this ID. Otherwise, the ID manager may either
377 return FALSE, or may store any unallocated ID into result. (This is
378 convenient, for example, if names are known to be digit strings that
379 are directly converted into integer values.)
380 name == NULL and createflag == 0: forbidden.
382 print is allowed to return a pointer to a static buffer; a caller must
384 copy its value if needed past subsequent calls. NULL should be
385 returned by ID managers that do not map names.
386 The map and alloc calls do not pass a pointer to the newly allocated
388 object. If a client needs to install object pointers in a handle ta‐
389 ble, it can obtain them via new object callbacks.
390 struct Agiodisc_s {
391 int (*fread)(void *chan, char *buf, int bufsize);
392 int (*putstr)(void *chan, char *str);
393 int (*flush)(void *chan); /* sync */
394 /* error messages? */
395 } ;
396 struct Agmemdisc_s { /* memory allocator */
398 void *(*open)(Agdisc_t*); /* independent of other resources */
399 void *(*alloc)(void *state, size_t req);
400 void *(*resize)(void *state, void *ptr, size_t old, size_t req);
401 void (*free)(void *state, void *ptr);
402 void (*close)(void *state);
403 } ;
404
407 agroot takes any graph object (graph, subgraph, node, edge) and returns
408 the root graph in which it lives. agraphof does the same, except it is
409 the identity function on graphs and subgraphs. Note that there is no
410 function to return the least subgraph containing an object, in part
411 because this is not well-defined as nodes and edges may be in incompa‐
412 rable subgraphs.
413 agcontains(g,obj) returns non-zero if obj is a member of (sub)graph g.
415 agdelete(g,obj) is equivalent to agclose, agdelnode, and agclose for
416 obj being a graph, node or edge, respectively. It returns -1 if obj
417 does not belong to g.
418 agnameof returns a string descriptor for the object. It returns the
420 name of the node or graph, and the key of an edge. agobjkind is a syn‐
421 onym for AGTYPE.
422 AGDATA, AGID, and AGTYPE are macros returning the specified fields of
424 the argument object. The first is described in the RECORDS section
425 above. The second returns the unique integer ID associated with the
426 object. The last returns AGRAPH, AGNODE, and AGEDGE depending on the
427 type of the object.
428 typedef int (*agusererrf) (char*); agusererrf agseterrf(agusererrf);
430
432 The library provides a variety of mechanisms to control the reporting
433 of errors and warnings. At present, there are basically two types of
434 messages: warnings and errors. A message is only written if its type
435 has higher priority than a programmer-controlled minimum, which is
436 AGWARN by default. The programmer can set this value using agseterr,
437 which returns the previous value. Calling agseterr(AGMAX) turns off the
438 writing of messages.
439 The function agerr if the main entry point for reporting an anomaly.
441 The first argument indicates the type of message. Usually, the first
442 argument in AGWARN or AGERR to indicate warnings and errors, respec‐
443 tively. Sometimes additional context information is only available in
444 functions calling the function where the error is actually caught. In
445 this case, the calling function can indicate that it is continuing the
446 current error by using AGPREV as the first argument. The remaining
447 arguments to agerr are the same as the arguments to printf.
448 The functions agwarningf and agerrorf are shorthand for
450 agerr(AGERR,...) and agerr(AGWARN,...), respectively.
451 Some applications desire to directly control the writing of messages.
453 Such an application can use the function agseterrf to register the
454 function that the library should call to actually write the message.
455 The previous error function is returned. By default, the message is
456 written to stderr.
457 Errors not written are stored in a log file. The last recorded error
459 can be retreived by calling aglasterr.
460 The function agerrors returns non-zero if errors have been reported.
462
464 #include <graphviz/cgraph.h>
465 typedef struct mydata_s {Agrec_t hdr; int x,y,z;} mydata;
466 main(int argc, char **argv)
468 {
469 Agraph_t *g;
470 Agnode_t *v;
471 Agedge_t *e;
472 Agsym_t *attr;
473 Dict_t *d
474 int cnt;
475 mydata *p;
476 if (g = agread(stdin,NIL(Agdisc_t*))) {
478 cnt = 0; attr = 0;
479 while (attr = agnxtattr(g, AGNODE, attr)) cnt++;
480 printf("The graph %s has %d attributes0,agnameof(g),cnt);
481 /* make the graph have a node color attribute, default is blue */
483 attr = agattr(g,AGNODE,"color","blue");
484 /* create a new graph of the same kind as g */
486 h = agopen("tmp",g->desc);
487 /* this is a way of counting all the edges of the graph */
489 cnt = 0;
490 for (v = agfstnode(g); v; v = agnxtnode(g,v))
491 for (e = agfstout(g,v); e; e = agnxtout(g,e))
492 cnt++;
493 /* attach records to edges */
495 for (v = agfstnode(g); v; v = agnxtnode(g,v))
496 for (e = agfstout(g,v); e; e; = agnxtout(g,e)) {
497 p = (mydata*) agbindrec(g,e,"mydata",sizeof(mydata),TRUE);
498 p->x = 27; /* meaningless data access example */
499 ((mydata*)(AGDATA(e)))->y = 999; /* another example */
500 }
501 }
502 }
503
505 digraph G {
506 a -> b;
507 c [shape=box];
508 a -> c [weight=29,label="some text];
509 subgraph anything {
510 /* the following affects only x,y,z */
511 node [shape=circle];
512 a; x; y -> z; y -> z; /* multiple edges */
513 }
514 }
515 strict graph H {
517 n0 -- n1 -- n2 -- n0; /* a cycle */
518 n0 -- {a b c d}; /* a star */
519 n0 -- n3;
520 n0 -- n3 [weight=1]; /* same edge because graph is strict */
521 }
522
524 Libcdt(3)
525
528 It is difficult to change endpoints of edges, delete string attributes
529 or modify edge keys. The work-around is to create a new object and
530 copy the contents of an old one (but new object obviously has a differ‐
531 ent ID, internal address, and object creation timestamp).
532 The API lacks convenient functions to substitute programmer-defined
534 ordering of nodes and edges but in principle this can be supported.
535 The library is not thread safe.
537
539 Stephen North, north@research.att.com, AT&T Research.
540 30 JULY 2007 LIBCGRAPH(3)