1LIBGRAPH(3)                Library Functions Manual                LIBGRAPH(3)
2
3
4

NAME

6       libgraph - abstract graph library
7

SYNOPSIS

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
25       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
32       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
41       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
47       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

DESCRIPTION

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
60       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
70       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
77

USE

79       1.  Define  types Agraphinfo_t, Agnodeinfo_t, and Agedgeinfo_t (usually
80       in a header file) before including <graphviz/graph.h>.
81
82       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
86       3. Compile with -lgraph -lcdt.
87
88       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
92

GRAPHS

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
105       typedef struct graphdata_t {
106           Dict_t              *node_dict;
107           attrdict_t          *nodeattr, *edgeattr, *globattr;
108       } graphdata_t;
109
110       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 cdt(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
127       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
134

ALL OBJECTS

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
144

NODES

146       typedef struct Agnode_t {
147           char                *name;
148           Agraph_t            *graph;
149           char                **attr;
150           Agnodeinfo_t        u;
151       } Agnode_t;
152
153       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
160

EDGES

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
174           for (e = agfstout(g,n); e; e = agnextout(g,e)) your_fun(e);
175
176       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

ATTRIBUTES

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
198       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
205       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

EXAMPLE GRAPH FILES

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
223       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
229

SEE ALSO

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
235

AUTHOR

237       Stephen North (north@ulysses.att.com), AT&T Bell Laboratories.
238
239
240
241                                 01 MARCH 1993                     LIBGRAPH(3)
Impressum