Mercurial > hg > camir-aes2014

annotate toolboxes/graph_visualisation/share/man/man3/graph.3 @ 0:e9a9cd732c1e tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first hg version after svn
author wolffd
date Tue, 10 Feb 2015 15:05:51 +0000
parents
children
rev   line source
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.