1LIBGRAPH(3) Library Functions Manual LIBGRAPH(3)
2
6 libgraph - abstract graph library
7
9 #include <graphviz/graph.h>
10 void aginit();
11 Agraph_t *agread(FILE*);
12 int agwrite(Agraph_t*, FILE*);
13 int agerrors();
14 Agraph_t *agopen(char *name, int kind);
15 void agclose(Agraph_t *g);
16 Agraph_t *agsubg(Agraph_t *g, char *name);
17 Agraph_t *agfindsubg(Agraph_t *g, char *name);
18 Agnode_t *agmetanode(Agraph_t *g);
19 Agraph_t *agusergraph(Agnode_t *metanode);
20 int agnnodes(Agraph_t *g), agnedges(Agraph_t *g);
21 int agcontains(Agraph_t *g, void *obj);
22 int aginsert(Agraph_t *g, void *obj);
23 int agdelete(Agraph_t *g, void *obj);
24 Agnode_t *agnode(Agraph_t *g, char *name);
26 Agnode_t *agfindnode(Agraph_t *g, char *name);
27 Agnode_t *agfstnode(Agraph_t *g);
28 Agnode_t *agnxtnode(Agraph_t *g, Agnode_t *n);
29 Agnode_t *aglstnode(Agraph_t *g);
30 Agnode_t *agprvnode(Agraph_t *g, Agnode_t *n);
31 Agedge_t *agedge(Agraph_t *g, Agnode_t *tail, Agnode_t *head);
33 Agedge_t *agfindedge(Agraph_t *g, Agnode_t *tail, Agnode_t *head);
34 Agedge_t *agfstedge(Agraph_t *g, Agnode_t *n);
35 Agedge_t *agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n);
36 Agedge_t *agfstin(Agraph_t *g, Agnode_t *n);
37 Agedge_t *agnxtin(Agraph_t *g, Agedge_t *e);
38 Agedge_t *agfstout(Agraph_t *g, Agnode_t *n);
39 Agedge_t *agnxtout(Agraph_t *g, Agedge_t *e);
40 char *agget(void *obj, char *name);
42 char *agxget(void *obj, int index);
43 void agset(void *obj, char *name, char *value);
44 void agxset(void *obj, int index, char *value);
45 int agindex(void *obj, char *name);
46 Agsym_t* agraphattr(Agraph_t *g,char *name,char *value);
48 Agsym_t* agnodeattr(Agraph_t *g,char *name,char *value);
49 Agsym_t* agedgeattr(Agraph_t *g,char *name,char *value);
50 Agsym_t* agfindattr(void *obj,char *name);
51
53 libgraph maintains directed and undirected attributed graphs in memory
54 and reads and writes graph files. Graphs are composed of nodes, edges,
55 and nested subgraphs. A subgraph may contain any nodes and edges of
56 its parents, and may be passed to any libgraph function taking a graph
57 pointer, except the three that create new attributes (where a main
58 graph is required).
59 Attributes are internal or external. Internal attributes are fields in
61 the graph, node and edge structs defined at compile time. These allow
62 efficient representation and direct access to values such as marks,
63 weights, and pointers for writing graph algorithms. External
64 attributes, on the other hand, are character strings (name‐value pairs)
65 dynamically allocated at runtime and accessed through libgraph calls.
66 External attributes are used in graph file I/O; internal attributes are
67 not. Conversion between internal and external attributes must be
68 explicitly programmed.
69 The subgraphs in a main graph are represented by an auxiliary directed
71 graph (a meta‐graph). Meta‐nodes correspond to subgraphs, and meta‐
72 edges signify containment of one subgraph in another. agmetanode and
73 agusergraph map between subgraphs and meta‐nodes. The nodes and edges
74 of the meta‐graph may be traversed by the usual libgraph functions for
75 this purpose.
76
79 1. Define types Agraphinfo_t, Agnodeinfo_t, and Agedgeinfo_t (usually
80 in a header file) before including <graphviz/graph.h>.
81 2. Call aginit() before any other libgraph functions. (This is a macro
83 that calls aginitlib() to define the sizes of Agraphinfo_t, Agnode‐
84 info_t, and Agedgeinfo_t.)
85 3. Compile with -lgraph -lcdt.
87 Except for the u fields, libgraph data structures must be considered
89 read‐only. Corrupting their contents by direct updates can cause cata‐
90 strophic errors.
91 Warning: the library is not thread-safe.
93
96 typedef struct Agraph_t {
97 char kind;
98 char *name;
99 Agraph_t *root;
100 char **attr;
101 graphdata_t *univ;
102 Dict_t *nodes,*inedges,*outedges;
103 proto_t *proto;
104 Agraphinfo_t u;
105 } Agraph_t;
106 typedef struct graphdata_t {
108 Dict_t *node_dict;
109 attrdict_t *nodeattr, *edgeattr, *globattr;
110 } graphdata_t;
111 typedef struct proto_t {
113 Agnode_t *n;
114 Agedge_t *e;
115 proto_t *prev;
116 } proto_t;
117 A graph kind is one of: AGRAPH, AGRAPHSTRICT, AGDIGRAPH, or AGDIGRAPH‐
118 STRICT. There are related macros for testing the properties of a
119 graph: AG_IS_DIRECTED(g) and AG_IS_STRICT(g). Strict graphs cannot
120 have self‐arcs or multi‐edges. attr is the array of external attribute
121 values. univ points to values shared by all subgraphs of a main graph.
122 nodes, inedges, and outedges are sets maintained by cdt(3). Normally
123 you don't access these dictionaries directly, though the edge dictio‐
124 naries may be re‐ordered to support programmer‐defined ordered edges
125 (see dtreorder in [22mcdt(3)). proto is a stack of templates for node and
126 edge initialization. The attributes of these nodes and edges are set
127 in the usual way (agget, agset, etc.) to set defaults.
128 agread reads a file and returns a new graph if one was successfully
130 parsed, otherwise returns NULL if EOF or a syntax error was encoun‐
131 tered. Errors are reported on stderr and a count is returned from
132 agerrors(). write_graph prints a graph on a file. agopen and agsubg
133 create new empty graph and subgraphs. agfindsubg searches for a sub‐
134 graph by name, returning NULL when the search fails.
135
138 agcontains, aginsert, agdelete are generic functions for nodes, edges,
139 and graphs. gcontains is a predicate that tests if an object belongs
140 to the given graph. aginsert inserts an object in a graph and agdelete
141 undoes this operation. A node or edge is destroyed (and its storage
142 freed) at the time it is deleted from the main graph. Likewise a sub‐
143 graph is destroyed when it is deleted from its last parent or when its
144 last parent is deleted.
145
148 typedef struct Agnode_t {
149 char *name;
150 Agraph_t *graph;
151 char **attr;
152 Agnodeinfo_t u;
153 } Agnode_t;
154 agnode attempts to create a node. If one with the requested name
156 already exists, the old node is returned unmodified. Otherwise a new
157 node is created, with attributed copied from g->proto->n. agfstnode
158 (agnxtnode) return the first (next) element in the node set of a graph,
159 respectively, or NULL. aglstnode (agprvnode) return the last (previ‐
160 ous) element in the node set of a graph, respectively, or NULL.
161
164 typedef struct Agedge_t {
165 Agnode_t *head,*tail;
166 char **attr;
167 Agedgeinfo_t u;
168 } Agedge_t;
169 agedge creates a new edge with the attributes of g->proto->e including
170 its key if not empty. agfindedge finds the first (u,v) edge in g.
171 agfstedge (agnxtedge) return the first (next) element in the edge set
172 of a graph, respectively, or NULL. agfstin, agnxtin, agfstout,
173 agnxtout refer to in‐ or out‐edge sets. The idiomatic usage in a
174 directed graph is:
175 for (e = agfstout(g,n); e; e = agnextout(g,e)) your_fun(e);
177 An edge is uniquely identified by its endpoints and its key attribute
179 (if there are multiple edges). If the key of g->proto->e is empty, new
180 edges are assigned an internal value. Edges also have tailport and
181 headport values. These have special syntax in the graph file language
182 but are not otherwise interpreted.
183
185 typedef struct attrsym_t {
186 char *name,*value;
187 int index;
188 unsigned char printed;
189 } attrsym_t;
190 typedef struct attrdict_t {
191 char *name;
192 Dict_t *dict;
193 attrsym_t **list;
194 } attrdict_t;
195 agraphattr, agnodeattr, and agedgeattr make new attributes. g should
196 be a main graph, or NULL for declarations applying to all graphs subse‐
197 quently read or created. agfindattr searches for an existing
198 attribute.
199 External attributes are accessed by agget and agset These take a
201 pointer to any graph, node, or edge, and an attribute name. Also, each
202 attribute has an integer index. For efficiency this index may be
203 passed instead of the name, by calling agxget and agxset. The printed
204 flag of an attribute may be set to 0 to skip it when writing a graph
205 file.
206 The list in an attribute dictionary is maintained in order of creation
208 and is NULL terminated. Here is a program fragment to print node
209 attribute names:
210 attrsym_t *aptr;
211 for (i = 0; aptr = g->univ->nodedict->list[i]; i++) puts(aptr->name);
212
214 graph any_name { /* an undirected graph */
215 a -- b; /* a simple edge */
216 a -- x1 -- x2 -- x3; /* a chain of edges */
217 "x3.a!" -- a; /* quotes protect special characters */
218 b -- {q r s t}; /* edges that fan out */
219 b [color="red",size=".5,.5"]; /* set various node attributes */
220 node [color=blue]; /* set default attributes */
221 b -- c [weight=25]; /* set edge attributes */
222 subgraph sink_nodes {a b c}; /* make a subgraph */
223 }
224 digraph G {
226 size="8.5,11"; /* sets a graph attribute */
227 a -> b; /* makes a directed edge */
228 chip12.pin1 -> chip28.pin3; /* uses named node "ports" */
229 }
230
233 dot(1), neato(1), libdict(3)
234 S. C. North and K. P. Vo, "Dictionary and Graph Libraries'' 1993 Winter
235 USENIX Conference Proceedings, pp. 1‐11.
236
239 Stephen North (north@ulysses.att.com), AT&T Bell Laboratories.
240 01 MARCH 1993 LIBGRAPH(3)