wolffd@0
|
1 .TH LIBGRAPH 3 "01 MARCH 1993"
|
wolffd@0
|
2 .SH NAME
|
wolffd@0
|
3 \fBlibgraph\fR \- abstract graph library
|
wolffd@0
|
4 .SH SYNOPSIS
|
wolffd@0
|
5 .ta .75i 1.5i 2.25i 3i 3.75i 4.5i 5.25i 6i
|
wolffd@0
|
6 .PP
|
wolffd@0
|
7 .nf
|
wolffd@0
|
8 \f5
|
wolffd@0
|
9 #include <graphviz/graph.h>
|
wolffd@0
|
10 void aginit();
|
wolffd@0
|
11 Agraph_t *agread(FILE*);
|
wolffd@0
|
12 int agwrite(Agraph_t*, FILE*);
|
wolffd@0
|
13 int agerrors();
|
wolffd@0
|
14 Agraph_t *agopen(char *name, int kind);
|
wolffd@0
|
15 void agclose(Agraph_t *g);
|
wolffd@0
|
16 Agraph_t *agsubg(Agraph_t *g, char *name);
|
wolffd@0
|
17 Agraph_t *agfindsubg(Agraph_t *g, char *name);
|
wolffd@0
|
18 Agnode_t *agmetanode(Agraph_t *g);
|
wolffd@0
|
19 Agraph_t *agusergraph(Agnode_t *metanode);
|
wolffd@0
|
20 int agnnodes(Agraph_t *g), agnedges(Agraph_t *g);
|
wolffd@0
|
21 .sp .i1
|
wolffd@0
|
22 int agcontains(Agraph_t *g, void *obj);
|
wolffd@0
|
23 int aginsert(Agraph_t *g, void *obj);
|
wolffd@0
|
24 int agdelete(Agraph_t *g, void *obj);
|
wolffd@0
|
25 .sp .1i
|
wolffd@0
|
26 Agnode_t *agnode(Agraph_t *g, char *name);
|
wolffd@0
|
27 Agnode_t *agfindnode(Agraph_t *g, char *name);
|
wolffd@0
|
28 Agnode_t *agfstnode(Agraph_t *g);
|
wolffd@0
|
29 Agnode_t *agnxtnode(Agraph_t *g, Agnode_t *n);
|
wolffd@0
|
30 Agnode_t *aglstnode(Agraph_t *g);
|
wolffd@0
|
31 Agnode_t *agprvnode(Agraph_t *g, Agnode_t *n);
|
wolffd@0
|
32 .sp .1i
|
wolffd@0
|
33 Agedge_t *agedge(Agraph_t *g, Agnode_t *tail, Agnode_t *head);
|
wolffd@0
|
34 Agedge_t *agfindedge(Agraph_t *g, Agnode_t *tail, Agnode_t *head);
|
wolffd@0
|
35 Agedge_t *agfstedge(Agraph_t *g, Agnode_t *n);
|
wolffd@0
|
36 Agedge_t *agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n);
|
wolffd@0
|
37 Agedge_t *agfstin(Agraph_t *g, Agnode_t *n);
|
wolffd@0
|
38 Agedge_t *agnxtin(Agraph_t *g, Agedge_t *e);
|
wolffd@0
|
39 Agedge_t *agfstout(Agraph_t *g, Agnode_t *n);
|
wolffd@0
|
40 Agedge_t *agnxtout(Agraph_t *g, Agedge_t *e);
|
wolffd@0
|
41 .sp .1i
|
wolffd@0
|
42 char *agget(void *obj, char *name);
|
wolffd@0
|
43 char *agxget(void *obj, int index);
|
wolffd@0
|
44 void agset(void *obj, char *name, char *value);
|
wolffd@0
|
45 void agxset(void *obj, int index, char *value);
|
wolffd@0
|
46 int agindex(void *obj, char *name);
|
wolffd@0
|
47 .sp .1i
|
wolffd@0
|
48 Agsym_t* agraphattr(Agraph_t *g,char *name,char *value);
|
wolffd@0
|
49 Agsym_t* agnodeattr(Agraph_t *g,char *name,char *value);
|
wolffd@0
|
50 Agsym_t* agedgeattr(Agraph_t *g,char *name,char *value);
|
wolffd@0
|
51 Agsym_t* agfindattr(void *obj,char *name);
|
wolffd@0
|
52 \fP
|
wolffd@0
|
53 .fi
|
wolffd@0
|
54 .SH DESCRIPTION
|
wolffd@0
|
55 \fIlibgraph\fP maintains directed and undirected attributed graphs
|
wolffd@0
|
56 in memory and reads and writes graph files. Graphs are composed of
|
wolffd@0
|
57 nodes, edges, and nested subgraphs. A subgraph may contain any
|
wolffd@0
|
58 nodes and edges of its parents, and may be passed to any
|
wolffd@0
|
59 \fIlibgraph\fP function taking a graph pointer, except the three
|
wolffd@0
|
60 that create new attributes (where a main graph is required).
|
wolffd@0
|
61
|
wolffd@0
|
62 Attributes are internal or external.
|
wolffd@0
|
63 Internal attributes are fields in the graph, node and edge structs
|
wolffd@0
|
64 defined at compile time.
|
wolffd@0
|
65 These allow efficient representation and direct access to values
|
wolffd@0
|
66 such as marks, weights, and pointers for writing graph algorithms.
|
wolffd@0
|
67 External attributes, on the other hand, are character strings
|
wolffd@0
|
68 (name\(hyvalue pairs) dynamically allocated at runtime and accessed
|
wolffd@0
|
69 through \fIlibgraph\fP calls. External attributes are used in
|
wolffd@0
|
70 graph file I/O; internal attributes are not. Conversion between
|
wolffd@0
|
71 internal and external attributes must be explicitly programmed.
|
wolffd@0
|
72
|
wolffd@0
|
73 The subgraphs in a main graph are represented by an auxiliary directed
|
wolffd@0
|
74 graph (a meta\(hygraph). Meta\(hynodes correspond to subgraphs, and meta\(hyedges
|
wolffd@0
|
75 signify containment of one subgraph in another.
|
wolffd@0
|
76 \f5agmetanode\fP and \f5agusergraph\fP map between
|
wolffd@0
|
77 subgraphs and meta\(hynodes. The nodes and edges of the meta\(hygraph may
|
wolffd@0
|
78 be traversed by the usual \fIlibgraph\fP functions for this purpose.
|
wolffd@0
|
79
|
wolffd@0
|
80 .SH USE
|
wolffd@0
|
81 1. Define types \f5Agraphinfo_t\fP, \f5Agnodeinfo_t\fP,
|
wolffd@0
|
82 and \f5Agedgeinfo_t\fP (usually in a header file) before
|
wolffd@0
|
83 including \f5<graphviz/graph.h>\fP.
|
wolffd@0
|
84
|
wolffd@0
|
85 2. Call \f5aginit()\fP before any other \fIlibgraph\fP functions.
|
wolffd@0
|
86 (This is a macro that calls \f5aginitlib()\fP to define the sizes
|
wolffd@0
|
87 of Agraphinfo_t, Agnodeinfo_t, and Agedgeinfo_t.)
|
wolffd@0
|
88
|
wolffd@0
|
89 3. Compile with \-lgraph \-lcdt.
|
wolffd@0
|
90
|
wolffd@0
|
91 Except for the \fBu\fP fields, \fIlibgraph\fP
|
wolffd@0
|
92 data structures must be considered read\(hyonly.
|
wolffd@0
|
93 Corrupting their contents by direct updates can cause
|
wolffd@0
|
94 catastrophic errors.
|
wolffd@0
|
95
|
wolffd@0
|
96 .SH "GRAPHS"
|
wolffd@0
|
97 .nf
|
wolffd@0
|
98 \f5
|
wolffd@0
|
99 typedef struct Agraph_t {
|
wolffd@0
|
100 char kind;
|
wolffd@0
|
101 char *name;
|
wolffd@0
|
102 Agraph_t *root;
|
wolffd@0
|
103 char **attr;
|
wolffd@0
|
104 graphdata_t *univ;
|
wolffd@0
|
105 Dict_t *nodes,*inedges,*outedges;
|
wolffd@0
|
106 proto_t *proto;
|
wolffd@0
|
107 Agraphinfo_t u;
|
wolffd@0
|
108 } Agraph_t;
|
wolffd@0
|
109
|
wolffd@0
|
110 typedef struct graphdata_t {
|
wolffd@0
|
111 Dict_t *node_dict;
|
wolffd@0
|
112 attrdict_t *nodeattr, *edgeattr, *globattr;
|
wolffd@0
|
113 } graphdata_t;
|
wolffd@0
|
114
|
wolffd@0
|
115 typedef struct proto_t {
|
wolffd@0
|
116 Agnode_t *n;
|
wolffd@0
|
117 Agedge_t *e;
|
wolffd@0
|
118 proto_t *prev;
|
wolffd@0
|
119 } proto_t;
|
wolffd@0
|
120 \fP
|
wolffd@0
|
121 .fi
|
wolffd@0
|
122 A graph \fIkind\fP is one of:
|
wolffd@0
|
123 AGRAPH, AGRAPHSTRICT, AGDIGRAPH, or AGDIGRAPHSTRICT.
|
wolffd@0
|
124 There are related macros for testing the properties of a graph:
|
wolffd@0
|
125 AG_IS_DIRECTED(g) and AG_IS_STRICT(g).
|
wolffd@0
|
126 Strict graphs cannot have self\(hyarcs or multi\(hyedges.
|
wolffd@0
|
127 \fBattr\fP is the array of external attribute values.
|
wolffd@0
|
128 \fBuniv\fP points to values shared by all subgraphs of a main graph.
|
wolffd@0
|
129 \fBnodes\fP, \fBinedges\fP, and \fBoutedges\fP are sets maintained
|
wolffd@0
|
130 by \fBcdt(3)\fP. Normally you don't access these dictionaries
|
wolffd@0
|
131 directly, though the edge dictionaries may be re\(hyordered to support
|
wolffd@0
|
132 programmer\(hydefined ordered edges (see \f5dtreorder\fP in \fIcdt(3)\fP).
|
wolffd@0
|
133 \fBproto\fP is a stack of templates for node and edge initialization.
|
wolffd@0
|
134 The attributes of these nodes and edges are set in the usual way (\f5agget\fP,
|
wolffd@0
|
135 \f5agset\fP, etc.) to set defaults.
|
wolffd@0
|
136 .PP
|
wolffd@0
|
137 \f5agread\fP reads a file and returns a new graph if one
|
wolffd@0
|
138 was succesfully parsed, otherwise returns NULL if
|
wolffd@0
|
139 \f5EOF\fP or a syntax error was encountered.
|
wolffd@0
|
140 Errors are reported on stderr and a count is returned from
|
wolffd@0
|
141 \g5agerrors()\fP.
|
wolffd@0
|
142 \f5write_graph\fP prints a graph on a file.
|
wolffd@0
|
143 \f5agopen\fP and \f5agsubg\fP create new empty graph and subgraphs.
|
wolffd@0
|
144 \f5agfindsubg\fP searches for a subgraph by name, returning NULL
|
wolffd@0
|
145 when the search fails.
|
wolffd@0
|
146
|
wolffd@0
|
147 .SH ALL OBJECTS
|
wolffd@0
|
148 \f5agcontains\fP, \f5aginsert\fP, \f5agdelete\fP are generic functions
|
wolffd@0
|
149 for nodes, edges, and graphs. \f5gcontains\fP is a predicate that tests
|
wolffd@0
|
150 if an object belongs to the given graph. \f5aginsert\fP inserts an
|
wolffd@0
|
151 object in a graph and \f5agdelete\fP undoes this operation.
|
wolffd@0
|
152 A node or edge is destroyed (and its storage freed) at the time it
|
wolffd@0
|
153 is deleted from the main graph. Likewise a subgraph is destroyed
|
wolffd@0
|
154 when it is deleted from its last parent or when its last parent is deleted.
|
wolffd@0
|
155
|
wolffd@0
|
156 .SH NODES
|
wolffd@0
|
157 .nf
|
wolffd@0
|
158 \f5
|
wolffd@0
|
159 typedef struct Agnode_t {
|
wolffd@0
|
160 char *name;
|
wolffd@0
|
161 Agraph_t *graph;
|
wolffd@0
|
162 char **attr;
|
wolffd@0
|
163 Agnodeinfo_t u;
|
wolffd@0
|
164 } Agnode_t;
|
wolffd@0
|
165 \fP
|
wolffd@0
|
166 .fi
|
wolffd@0
|
167
|
wolffd@0
|
168 \f5agnode\fP attempts to create a node.
|
wolffd@0
|
169 If one with the requested name already exists, the old node
|
wolffd@0
|
170 is returned unmodified.
|
wolffd@0
|
171 Otherwise a new node is created, with attributed copied from g\->proto\->n.
|
wolffd@0
|
172 \f5agfstnode\fP (\f5agnxtnode\fP) return the first (next) element
|
wolffd@0
|
173 in the node set of a graph, respectively, or NULL.
|
wolffd@0
|
174 \f5aglstnode\fP (\f5agprvnode\fP) return the last (previous) element
|
wolffd@0
|
175 in the node set of a graph, respectively, or NULL.
|
wolffd@0
|
176
|
wolffd@0
|
177 .SH EDGES
|
wolffd@0
|
178 .nf
|
wolffd@0
|
179 \f5
|
wolffd@0
|
180 typedef struct Agedge_t {
|
wolffd@0
|
181 Agnode_t *head,*tail;
|
wolffd@0
|
182 char **attr;
|
wolffd@0
|
183 Agedgeinfo_t u;
|
wolffd@0
|
184 } Agedge_t;
|
wolffd@0
|
185 \fP
|
wolffd@0
|
186 .fi
|
wolffd@0
|
187 \f5agedge\fP creates a new edge with the attributes of g\->proto\->e
|
wolffd@0
|
188 including its key if not empty.
|
wolffd@0
|
189 \f5agfindedge\fP finds the first (u,v) edge in \f5g\fP.
|
wolffd@0
|
190 \f5agfstedge\fP (\f5agnxtedge\fP) return the first (next) element
|
wolffd@0
|
191 in the edge set of a graph, respectively, or NULL.
|
wolffd@0
|
192 \f5agfstin\fP, \f5agnxtin\fP, \f5agfstout\fP, \f5agnxtout\fP
|
wolffd@0
|
193 refer to in\(hy or out\(hyedge sets.
|
wolffd@0
|
194 The idiomatic usage in a directed graph is:
|
wolffd@0
|
195 .sp
|
wolffd@0
|
196 \f5 for (e = agfstout(g,n); e; e = agnextout(g,e)) your_fun(e);\fP
|
wolffd@0
|
197 .P
|
wolffd@0
|
198 An edge is uniquely identified by its endpoints and its \f5key\fP
|
wolffd@0
|
199 attribute (if there are multiple edges).
|
wolffd@0
|
200 If the \f5key\fP of \f5g\->proto\->e\fP is empty,
|
wolffd@0
|
201 new edges are assigned an internal value.
|
wolffd@0
|
202 Edges also have \f5tailport\fP and \f5headport\fP values.
|
wolffd@0
|
203 These have special syntax in the graph file language but are
|
wolffd@0
|
204 not otherwise interpreted.
|
wolffd@0
|
205 .PP
|
wolffd@0
|
206 .SH ATTRIBUTES
|
wolffd@0
|
207 .nf
|
wolffd@0
|
208 \f5
|
wolffd@0
|
209 typedef struct attrsym_t {
|
wolffd@0
|
210 char *name,*value;
|
wolffd@0
|
211 int index;
|
wolffd@0
|
212 unsigned char printed;
|
wolffd@0
|
213 } attrsym_t;
|
wolffd@0
|
214 .bp
|
wolffd@0
|
215 typedef struct attrdict_t {
|
wolffd@0
|
216 char *name;
|
wolffd@0
|
217 Dict_t *dict;
|
wolffd@0
|
218 attrsym_t **list;
|
wolffd@0
|
219 } attrdict_t;
|
wolffd@0
|
220 \fP
|
wolffd@0
|
221 .fi
|
wolffd@0
|
222 \f5agraphattr\fP, \f5agnodeattr\fP, and \f5agedgeattr\fP make new attributes.
|
wolffd@0
|
223 \f5g\fP should be a main graph, or \f5NULL\fP for declarations
|
wolffd@0
|
224 applying to all graphs subsequently read or created.
|
wolffd@0
|
225 \f5agfindattr\fP searches for an existing attribute.
|
wolffd@0
|
226 .PP
|
wolffd@0
|
227 External attributes are accessed by \f5agget\fP and \f5agset\fP
|
wolffd@0
|
228 These take a pointer to any graph, node, or edge, and an attribute name.
|
wolffd@0
|
229 Also, each attribute has an integer index. For efficiency this index
|
wolffd@0
|
230 may be passed instead of the name, by calling \f5agxget\fP and \f5agxset\fP.
|
wolffd@0
|
231 The \f5printed\fP flag of an attribute may be set to 0 to skip it
|
wolffd@0
|
232 when writing a graph file.
|
wolffd@0
|
233 .PP
|
wolffd@0
|
234 The \f5list\fP in an attribute dictionary is maintained in order of creation
|
wolffd@0
|
235 and is NULL terminated.
|
wolffd@0
|
236 Here is a program fragment to print node attribute names:
|
wolffd@0
|
237 .nf
|
wolffd@0
|
238 \f5attrsym_t *aptr;
|
wolffd@0
|
239 for (i = 0; aptr = g\->univ\->nodedict\->list[i]; i++) puts(aptr\->name);\fP
|
wolffd@0
|
240 .fi
|
wolffd@0
|
241 .SH EXAMPLE GRAPH FILES
|
wolffd@0
|
242 .nf
|
wolffd@0
|
243 graph any_name { /* an undirected graph */
|
wolffd@0
|
244 a \-\- b; /* a simple edge */
|
wolffd@0
|
245 a \-\- x1 \-\- x2 \-\- x3; /* a chain of edges */
|
wolffd@0
|
246 "x3.a!" \-\- a; /* quotes protect special characters */
|
wolffd@0
|
247 b \-\- {q r s t}; /* edges that fan out */
|
wolffd@0
|
248 b [color="red",size=".5,.5"]; /* set various node attributes */
|
wolffd@0
|
249 node [color=blue]; /* set default attributes */
|
wolffd@0
|
250 b \-\- c [weight=25]; /* set edge attributes */
|
wolffd@0
|
251 subgraph sink_nodes {a b c}; /* make a subgraph */
|
wolffd@0
|
252 }
|
wolffd@0
|
253
|
wolffd@0
|
254 digraph G {
|
wolffd@0
|
255 size="8.5,11"; /* sets a graph attribute */
|
wolffd@0
|
256 a \-> b; /* makes a directed edge */
|
wolffd@0
|
257 chip12.pin1 \-> chip28.pin3; /* uses named node "ports" */
|
wolffd@0
|
258 }
|
wolffd@0
|
259 .fi
|
wolffd@0
|
260
|
wolffd@0
|
261 .SH SEE ALSO
|
wolffd@0
|
262 .BR dot (1),
|
wolffd@0
|
263 .BR neato (1),
|
wolffd@0
|
264 .BR libdict (3)
|
wolffd@0
|
265 .br
|
wolffd@0
|
266 S. C. North and K. P. Vo, "Dictionary and Graph Libraries''
|
wolffd@0
|
267 1993 Winter USENIX Conference Proceedings, pp. 1\(hy11.
|
wolffd@0
|
268
|
wolffd@0
|
269 .SH AUTHOR
|
wolffd@0
|
270 Stephen North (north@ulysses.att.com), AT&T Bell Laboratories.
|