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
94 typedef struct Agraph_t {
95 char kind;
96 char *name;
97 Agraph_t *root;
98 char **attr;
99 graphdata_t *univ;
100 Dict_t *nodes,*inedges,*outedges;
101 proto_t *proto;
102 Agraphinfo_t u;
103 } Agraph_t;
104 typedef struct graphdata_t {
106 Dict_t *node_dict;
107 attrdict_t *nodeattr, *edgeattr, *globattr;
108 } graphdata_t;
109 typedef struct proto_t {
111 Agnode_t *n;
112 Agedge_t *e;
113 proto_t *prev;
114 } proto_t;
115 A graph kind is one of: AGRAPH, AGRAPHSTRICT, AGDIGRAPH, or AGDIGRAPH‐
116 STRICT. There are related macros for testing the properties of a
117 graph: AG_IS_DIRECTED(g) and AG_IS_STRICT(g). Strict graphs cannot
118 have self‐arcs or multi‐edges. attr is the array of external attribute
119 values. univ points to values shared by all subgraphs of a main graph.
120 nodes, inedges, and outedges are sets maintained by cdt(3). Normally
121 you don't access these dictionaries directly, though the edge dictio‐
122 naries may be re‐ordered to support programmer‐defined ordered edges
123 (see dtreorder in [22mcdt(3)). proto is a stack of templates for node and
124 edge initialization. The attributes of these nodes and edges are set
125 in the usual way (agget, agset, etc.) to set defaults.
126 agread reads a file and returns a new graph if one was succesfully
128 parsed, otherwise returns NULL if EOF or a syntax error was encoun‐
129 tered. Errors are reported on stderr and a count is returned from
130 agerrors(). write_graph prints a graph on a file. agopen and agsubg
131 create new empty graph and subgraphs. agfindsubg searches for a sub‐
132 graph by name, returning NULL when the search fails.
133
136 agcontains, aginsert, agdelete are generic functions for nodes, edges,
137 and graphs. gcontains is a predicate that tests if an object belongs
138 to the given graph. aginsert inserts an object in a graph and agdelete
139 undoes this operation. A node or edge is destroyed (and its storage
140 freed) at the time it is deleted from the main graph. Likewise a sub‐
141 graph is destroyed when it is deleted from its last parent or when its
142 last parent is deleted.
143
146 typedef struct Agnode_t {
147 char *name;
148 Agraph_t *graph;
149 char **attr;
150 Agnodeinfo_t u;
151 } Agnode_t;
152 agnode attempts to create a node. If one with the requested name
154 already exists, the old node is returned unmodified. Otherwise a new
155 node is created, with attributed copied from g->proto->n. agfstnode
156 (agnxtnode) return the first (next) element in the node set of a graph,
157 respectively, or NULL. aglstnode (agprvnode) return the last (previ‐
158 ous) element in the node set of a graph, respectively, or NULL.
159
162 typedef struct Agedge_t {
163 Agnode_t *head,*tail;
164 char **attr;
165 Agedgeinfo_t u;
166 } Agedge_t;
167 agedge creates a new edge with the attributes of g->proto->e including
168 its key if not empty. agfindedge finds the first (u,v) edge in g.
169 agfstedge (agnxtedge) return the first (next) element in the edge set
170 of a graph, respectively, or NULL. agfstin, agnxtin, agfstout,
171 agnxtout refer to in‐ or out‐edge sets. The idiomatic usage in a
172 directed graph is:
173 for (e = agfstout(g,n); e; e = agnextout(g,e)) your_fun(e);
175 An edge is uniquely identified by its endpoints and its key attribute
177 (if there are multiple edges). If the key of g->proto->e is empty, new
178 edges are assigned an internal value. Edges also have tailport and
179 headport values. These have special syntax in the graph file language
180 but are not otherwise interpreted.
181
183 typedef struct attrsym_t {
184 char *name,*value;
185 int index;
186 unsigned char printed;
187 } attrsym_t;
188 typedef struct attrdict_t {
189 char *name;
190 Dict_t *dict;
191 attrsym_t **list;
192 } attrdict_t;
193 agraphattr, agnodeattr, and agedgeattr make new attributes. g should
194 be a main graph, or NULL for declarations applying to all graphs subse‐
195 quently read or created. agfindattr searches for an existing
196 attribute.
197 External attributes are accessed by agget and agset These take a
199 pointer to any graph, node, or edge, and an attribute name. Also, each
200 attribute has an integer index. For efficiency this index may be
201 passed instead of the name, by calling agxget and agxset. The printed
202 flag of an attribute may be set to 0 to skip it when writing a graph
203 file.
204 The list in an attribute dictionary is maintained in order of creation
206 and is NULL terminated. Here is a program fragment to print node
207 attribute names:
208 attrsym_t *aptr;
209 for (i = 0; aptr = g->univ->nodedict->list[i]; i++) puts(aptr->name);
210
212 graph any_name { /* an undirected graph */
213 a -- b; /* a simple edge */
214 a -- x1 -- x2 -- x3; /* a chain of edges */
215 "x3.a!" -- a; /* quotes protect special characters */
216 b -- {q r s t}; /* edges that fan out */
217 b [color="red",size=".5,.5"]; /* set various node attributes */
218 node [color=blue]; /* set default attributes */
219 b -- c [weight=25]; /* set edge attributes */
220 subgraph sink_nodes {a b c}; /* make a subgraph */
221 }
222 digraph G {
224 size="8.5,11"; /* sets a graph attribute */
225 a -> b; /* makes a directed edge */
226 chip12.pin1 -> chip28.pin3; /* uses named node "ports" */
227 }
228
231 dot(1), neato(1), libdict(3)
232 S. C. North and K. P. Vo, "Dictionary and Graph Libraries'' 1993 Winter
233 USENIX Conference Proceedings, pp. 1‐11.
234
237 Stephen North (north@ulysses.att.com), AT&T Bell Laboratories.
238 01 MARCH 1993 LIBGRAPH(3)