1
.TH LIBGRAPH 3 "01 MARCH 1993"
3
\fBlibgraph\fR \- abstract graph library
5
.ta .75i 1.5i 2.25i 3i 3.75i 4.5i 5.25i 6i
11
Agraph_t *agread(FILE*);
12
int agwrite(Agraph_t*, FILE*);
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);
22
int agcontains(Agraph_t *g, void *obj);
23
int aginsert(Agraph_t *g, void *obj);
24
int agdelete(Agraph_t *g, void *obj);
26
Agnode_t *agnode(Agraph_t *g, char *name);
27
Agnode_t *agfindnode(Agraph_t *g, char *name);
28
Agnode_t *agfstnode(Agraph_t *g);
29
Agnode_t *agnxtnode(Agraph_t *g, Agnode_t *n);
31
Agedge_t *agedge(Agraph_t *g, Agnode_t *tail, Agnode_t *head);
32
Agedge_t *agfindedge(Agraph_t *g, Agnode_t *tail, Agnode_t *head);
33
Agedge_t *agfstedge(Agraph_t *g, Agnode_t *n);
34
Agedge_t *agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n);
35
Agedge_t *agfstin(Agraph_t *g, Agnode_t *n);
36
Agedge_t *agnxtin(Agraph_t *g, Agedge_t *e);
37
Agedge_t *agfstout(Agraph_t *g, Agnode_t *n);
38
Agedge_t *agnxtout(Agraph_t *g, Agedge_t *e);
40
char *agget(void *obj, char *name);
41
char *agxget(void *obj, int index);
42
void agset(void *obj, char *name, char *value);
43
void agxset(void *obj, int index, char *value);
44
int agindex(void *obj, char *name);
46
Agsym_t* agraphattr(Agraph_t *g,char *name,char *value);
47
Agsym_t* agnodeattr(Agraph_t *g,char *name,char *value);
48
Agsym_t* agedgeattr(Agraph_t *g,char *name,char *value);
49
Agsym_t* agfindattr(void *obj,char *name);
53
\fIlibgraph\fP maintains directed and undirected attributed graphs
54
in memory and reads and writes graph files. Graphs are composed of
55
nodes, edges, and nested subgraphs. A subgraph may contain any
56
nodes and edges of its parents, and may be passed to any
57
\fIlibgraph\fP function taking a graph pointer, except the three
58
that create new attributes (where a main graph is required).
60
Attributes are internal or external.
61
Internal attributes are fields in the graph, node and edge structs
62
defined at compile time.
63
These allow efficient representation and direct access to values
64
such as marks, weights, and pointers for writing graph algorithms.
65
External attributes, on the other hand, are character strings
66
(name-value pairs) dynamically allocated at runtime and accessed
67
through \fIlibgraph\fP calls. External attributes are used in
68
graph file I/O; internal attributes are not. Conversion between
69
internal and external attributes must be explicitly programmed.
71
The subgraphs in a main graph are represented by an auxiliary directed
72
graph (a meta-graph). Meta-nodes correspond to subgraphs, and meta-edges
73
signify containment of one subgraph in another.
74
\f5agmetanode\fP and \f5agusergraph\fP map between
75
subgraphs and meta-nodes. The nodes and edges of the meta-graph may
76
be traversed by the usual \fIlibgraph\fP functions for this purpose.
79
1. Define types \f5Agraphinfo_t\fP, \f5Agnodeinfo_t\fP,
80
and \f5Agedgeinfo_t\fP (usually in a header file) before
81
including \f5<graph.h>\fP.
83
2. Call \f5aginit()\fP before any other \fIlibgraph\fP functions.
84
(This is a macro that calls \f5aginitlib()\fP to define the sizes
85
of Agraphinfo_t, Agnodeinfo_t, and Agedgeinfo_t.)
87
3. Compile with -lgraph -lcdt.
89
Except for the \fBu\fP fields, \fIlibgraph\fP
90
data structures must be considered read-only.
91
Corrupting their contents by direct updates can cause
97
typedef struct Agraph_t {
103
Dict_t *nodes,*inedges,*outedges;
108
typedef struct graphdata_t {
110
attrdict_t *nodeattr, *edgeattr, *globattr;
113
typedef struct proto_t {
120
A graph \fIkind\fP is one of:
121
AGRAPH, AGRAPHSTRICT, AGDIGRAPH, or AGDIGRAPHSTRICT.
122
There are related macros for testing the properties of a graph:
123
AG_IS_DIRECTED(g) and AG_IS_STRICT(g).
124
Strict graphs cannot have self-arcs or multi-edges.
125
\fBattr\fP is the array of external attribute values.
126
\fBuniv\fP points to values shared by all subgraphs of a main graph.
127
\fBnodes\fP, \fBinedges\fP, and \fBoutedges\fP are sets maintained
128
by \fBcdt(3)\fP. Normally you don't access these dictionaries
129
directly, though the edge dictionaries may be re-ordered to support
130
programmer-defined ordered edges (see \f5dtreorder\fP in \fIcdt(3)\fP).
131
\fBproto\fP is a stack of templates for node and edge initialization.
132
The attributes of these nodes and edges are set in the usual way (\f5agget\fP,
133
\f5agset\fP, etc.) to set defaults.
135
\f5agread\fP reads a file and returns a new graph if one
136
was succesfully parsed, otherwise returns NULL if
137
\f5EOF\fP or a syntax error was encountered.
138
Errors are reported on stderr and a count is returned from
140
\f5write_graph\fP prints a graph on a file.
141
\f5agopen\fP and \f5agsubg\fP create new empty graph and subgraphs.
142
\f5agfindsubg\fP searches for a subgraph by name, returning NULL
143
when the search fails.
146
\f5agcontains\fP, \f5aginsert\fP, \f5agdelete\fP are generic functions
147
for nodes, edges, and graphs. \f5gcontains\fP is a predicate that tests
148
if an object belongs to the given graph. \f5aginsert\fP inserts an
149
object in a graph and \f5agdelete\fP undoes this operation.
150
A node or edge is destroyed (and its storage freed) at the time it
151
is deleted from the main graph. Likewise a subgraph is destroyed
152
when it is deleted from its last parent or when its last parent is deleted.
157
typedef struct Agnode_t {
166
\f5agnode\fP attempts to create a node.
167
If one with the requested name already exists, the old node
168
is returned unmodified.
169
Otherwise a new node is created, with attributed copied from g->proto->n.
170
\f5agfstnode\fP (\f5agnxtnode\fP) return the first (next) element
171
in the node set of a graph, respectively, or NULL.
176
typedef struct Agedge_t {
177
Agnode_t *head,*tail;
183
\f5agedge\fP creates a new edge with the attributes of g->proto->e
184
including its key if not empty.
185
\f5agfindedge\fP finds the first (u,v) edge in \f5g\fP.
186
\f5agfstedge\fP (\f5agnxtedge\fP) return the first (next) element
187
in the edge set of a graph, respectively, or NULL.
188
\f5agfstin\fP, \f5agnxtin\fP, \f5agfstout\fP, \f5agnxtout\fP
189
refer to in- or out-edge sets.
190
The idiomatic usage in a directed graph is:
192
\f5 for (e = agfstout(g,n); e; e = agnextout(g,e)) your_fun(e);\fP
194
An edge is uniquely identified by its endpoints and its \f5key\fP
195
attribute (if there are multiple edges).
196
If the \f5key\fP of \f5g->proto->e\fP is empty,
197
new edges are assigned an internal value.
198
Edges also have \f5tailport\fP and \f5headport\fP values.
199
These have special syntax in the graph file language but are
200
not otherwise interpreted.
205
typedef struct attrsym_t {
208
unsigned char printed;
211
typedef struct attrdict_t {
218
\f5agraphattr\fP, \f5agnodeattr\fP, and \f5agedgeattr\fP make new attributes.
219
\f5g\fP should be a main graph, or \f5NULL\fP for declarations
220
applying to all graphs subsequently read or created.
221
\f5agfindattr\fP searches for an existing attribute.
223
External attributes are accessed by \f5agget\fP and \f5agset\fP
224
These take a pointer to any graph, node, or edge, and an attribute name.
225
Also, each attribute has an integer index. For efficiency this index
226
may be passed instead of the name, by calling \f5agxget\fP and \f5agxset\fP.
227
The \f5printed\fP flag of an attribute may be set to 0 to skip it
228
when writing a graph file.
230
The \f5list\fP in an attribute dictionary is maintained in order of creation
231
and is NULL terminated.
232
Here is a program fragment to print node attribute names:
235
for (i = 0; aptr = g->univ->nodedict->list[i]; i++) puts(aptr->name);\fP
237
.SH EXAMPLE GRAPH FILES
239
graph any_name { /* an undirected graph */
240
a -- b; /* a simple edge */
241
a -- x1 -- x2 -- x3; /* a chain of edges */
242
"x3.a!" -- a; /* quotes protect special characters */
243
b -- {q r s t}; /* edges that fan out */
244
b [color="red",size=".5,.5"]; /* set various node attributes */
245
node [color=blue]; /* set default attributes */
246
b -- c [weight=25]; /* set edge attributes */
247
subgraph sink_nodes {a b c}; /* make a subgraph */
251
bb="8.5,11"; /* sets a graph attribute */
252
a -> b; /* makes a directed edge */
253
chip12.pin1 -> chip28.pin3; /* uses named node "ports" */
262
S. C. North and K. P. Vo, "Dictionary and Graph Libraries''
263
1993 Winter USENIX Conference Proceedings, pp. 1-11.
266
Stephen North (north@ulysses.att.com), AT&T Bell Laboratories.
added
removed
graph/graph.3
