Mercurial > hg > camir-aes2014
diff toolboxes/graph_visualisation/share/man/man3/graph.3 @ 0:e9a9cd732c1e tip
first hg version after svn
author | wolffd |
---|---|
date | Tue, 10 Feb 2015 15:05:51 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/toolboxes/graph_visualisation/share/man/man3/graph.3 Tue Feb 10 15:05:51 2015 +0000 @@ -0,0 +1,270 @@ +.TH LIBGRAPH 3 "01 MARCH 1993" +.SH NAME +\fBlibgraph\fR \- abstract graph library +.SH SYNOPSIS +.ta .75i 1.5i 2.25i 3i 3.75i 4.5i 5.25i 6i +.PP +.nf +\f5 +#include <graphviz/graph.h> +void aginit(); +Agraph_t *agread(FILE*); +int agwrite(Agraph_t*, FILE*); +int agerrors(); +Agraph_t *agopen(char *name, int kind); +void agclose(Agraph_t *g); +Agraph_t *agsubg(Agraph_t *g, char *name); +Agraph_t *agfindsubg(Agraph_t *g, char *name); +Agnode_t *agmetanode(Agraph_t *g); +Agraph_t *agusergraph(Agnode_t *metanode); +int agnnodes(Agraph_t *g), agnedges(Agraph_t *g); +.sp .i1 +int agcontains(Agraph_t *g, void *obj); +int aginsert(Agraph_t *g, void *obj); +int agdelete(Agraph_t *g, void *obj); +.sp .1i +Agnode_t *agnode(Agraph_t *g, char *name); +Agnode_t *agfindnode(Agraph_t *g, char *name); +Agnode_t *agfstnode(Agraph_t *g); +Agnode_t *agnxtnode(Agraph_t *g, Agnode_t *n); +Agnode_t *aglstnode(Agraph_t *g); +Agnode_t *agprvnode(Agraph_t *g, Agnode_t *n); +.sp .1i +Agedge_t *agedge(Agraph_t *g, Agnode_t *tail, Agnode_t *head); +Agedge_t *agfindedge(Agraph_t *g, Agnode_t *tail, Agnode_t *head); +Agedge_t *agfstedge(Agraph_t *g, Agnode_t *n); +Agedge_t *agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n); +Agedge_t *agfstin(Agraph_t *g, Agnode_t *n); +Agedge_t *agnxtin(Agraph_t *g, Agedge_t *e); +Agedge_t *agfstout(Agraph_t *g, Agnode_t *n); +Agedge_t *agnxtout(Agraph_t *g, Agedge_t *e); +.sp .1i +char *agget(void *obj, char *name); +char *agxget(void *obj, int index); +void agset(void *obj, char *name, char *value); +void agxset(void *obj, int index, char *value); +int agindex(void *obj, char *name); +.sp .1i +Agsym_t* agraphattr(Agraph_t *g,char *name,char *value); +Agsym_t* agnodeattr(Agraph_t *g,char *name,char *value); +Agsym_t* agedgeattr(Agraph_t *g,char *name,char *value); +Agsym_t* agfindattr(void *obj,char *name); +\fP +.fi +.SH DESCRIPTION +\fIlibgraph\fP maintains directed and undirected attributed graphs +in memory and reads and writes graph files. Graphs are composed of +nodes, edges, and nested subgraphs. A subgraph may contain any +nodes and edges of its parents, and may be passed to any +\fIlibgraph\fP function taking a graph pointer, except the three +that create new attributes (where a main graph is required). + +Attributes are internal or external. +Internal attributes are fields in the graph, node and edge structs +defined at compile time. +These allow efficient representation and direct access to values +such as marks, weights, and pointers for writing graph algorithms. +External attributes, on the other hand, are character strings +(name\(hyvalue pairs) dynamically allocated at runtime and accessed +through \fIlibgraph\fP calls. External attributes are used in +graph file I/O; internal attributes are not. Conversion between +internal and external attributes must be explicitly programmed. + +The subgraphs in a main graph are represented by an auxiliary directed +graph (a meta\(hygraph). Meta\(hynodes correspond to subgraphs, and meta\(hyedges +signify containment of one subgraph in another. +\f5agmetanode\fP and \f5agusergraph\fP map between +subgraphs and meta\(hynodes. The nodes and edges of the meta\(hygraph may +be traversed by the usual \fIlibgraph\fP functions for this purpose. + +.SH USE +1. Define types \f5Agraphinfo_t\fP, \f5Agnodeinfo_t\fP, +and \f5Agedgeinfo_t\fP (usually in a header file) before +including \f5<graphviz/graph.h>\fP. + +2. Call \f5aginit()\fP before any other \fIlibgraph\fP functions. +(This is a macro that calls \f5aginitlib()\fP to define the sizes +of Agraphinfo_t, Agnodeinfo_t, and Agedgeinfo_t.) + +3. Compile with \-lgraph \-lcdt. + +Except for the \fBu\fP fields, \fIlibgraph\fP +data structures must be considered read\(hyonly. +Corrupting their contents by direct updates can cause +catastrophic errors. + +.SH "GRAPHS" +.nf +\f5 +typedef struct Agraph_t { + char kind; + char *name; + Agraph_t *root; + char **attr; + graphdata_t *univ; + Dict_t *nodes,*inedges,*outedges; + proto_t *proto; + Agraphinfo_t u; +} Agraph_t; + +typedef struct graphdata_t { + Dict_t *node_dict; + attrdict_t *nodeattr, *edgeattr, *globattr; +} graphdata_t; + +typedef struct proto_t { + Agnode_t *n; + Agedge_t *e; + proto_t *prev; +} proto_t; +\fP +.fi +A graph \fIkind\fP is one of: +AGRAPH, AGRAPHSTRICT, AGDIGRAPH, or AGDIGRAPHSTRICT. +There are related macros for testing the properties of a graph: +AG_IS_DIRECTED(g) and AG_IS_STRICT(g). +Strict graphs cannot have self\(hyarcs or multi\(hyedges. +\fBattr\fP is the array of external attribute values. +\fBuniv\fP points to values shared by all subgraphs of a main graph. +\fBnodes\fP, \fBinedges\fP, and \fBoutedges\fP are sets maintained +by \fBcdt(3)\fP. Normally you don't access these dictionaries +directly, though the edge dictionaries may be re\(hyordered to support +programmer\(hydefined ordered edges (see \f5dtreorder\fP in \fIcdt(3)\fP). +\fBproto\fP is a stack of templates for node and edge initialization. +The attributes of these nodes and edges are set in the usual way (\f5agget\fP, +\f5agset\fP, etc.) to set defaults. +.PP +\f5agread\fP reads a file and returns a new graph if one +was succesfully parsed, otherwise returns NULL if +\f5EOF\fP or a syntax error was encountered. +Errors are reported on stderr and a count is returned from +\g5agerrors()\fP. +\f5write_graph\fP prints a graph on a file. +\f5agopen\fP and \f5agsubg\fP create new empty graph and subgraphs. +\f5agfindsubg\fP searches for a subgraph by name, returning NULL +when the search fails. + +.SH ALL OBJECTS +\f5agcontains\fP, \f5aginsert\fP, \f5agdelete\fP are generic functions +for nodes, edges, and graphs. \f5gcontains\fP is a predicate that tests +if an object belongs to the given graph. \f5aginsert\fP inserts an +object in a graph and \f5agdelete\fP undoes this operation. +A node or edge is destroyed (and its storage freed) at the time it +is deleted from the main graph. Likewise a subgraph is destroyed +when it is deleted from its last parent or when its last parent is deleted. + +.SH NODES +.nf +\f5 +typedef struct Agnode_t { + char *name; + Agraph_t *graph; + char **attr; + Agnodeinfo_t u; +} Agnode_t; +\fP +.fi + +\f5agnode\fP attempts to create a node. +If one with the requested name already exists, the old node +is returned unmodified. +Otherwise a new node is created, with attributed copied from g\->proto\->n. +\f5agfstnode\fP (\f5agnxtnode\fP) return the first (next) element +in the node set of a graph, respectively, or NULL. +\f5aglstnode\fP (\f5agprvnode\fP) return the last (previous) element +in the node set of a graph, respectively, or NULL. + +.SH EDGES +.nf +\f5 +typedef struct Agedge_t { + Agnode_t *head,*tail; + char **attr; + Agedgeinfo_t u; +} Agedge_t; +\fP +.fi +\f5agedge\fP creates a new edge with the attributes of g\->proto\->e +including its key if not empty. +\f5agfindedge\fP finds the first (u,v) edge in \f5g\fP. +\f5agfstedge\fP (\f5agnxtedge\fP) return the first (next) element +in the edge set of a graph, respectively, or NULL. +\f5agfstin\fP, \f5agnxtin\fP, \f5agfstout\fP, \f5agnxtout\fP +refer to in\(hy or out\(hyedge sets. +The idiomatic usage in a directed graph is: +.sp +\f5 for (e = agfstout(g,n); e; e = agnextout(g,e)) your_fun(e);\fP +.P +An edge is uniquely identified by its endpoints and its \f5key\fP +attribute (if there are multiple edges). +If the \f5key\fP of \f5g\->proto\->e\fP is empty, +new edges are assigned an internal value. +Edges also have \f5tailport\fP and \f5headport\fP values. +These have special syntax in the graph file language but are +not otherwise interpreted. +.PP +.SH ATTRIBUTES +.nf +\f5 +typedef struct attrsym_t { + char *name,*value; + int index; + unsigned char printed; +} attrsym_t; +.bp +typedef struct attrdict_t { + char *name; + Dict_t *dict; + attrsym_t **list; +} attrdict_t; +\fP +.fi +\f5agraphattr\fP, \f5agnodeattr\fP, and \f5agedgeattr\fP make new attributes. +\f5g\fP should be a main graph, or \f5NULL\fP for declarations +applying to all graphs subsequently read or created. +\f5agfindattr\fP searches for an existing attribute. +.PP +External attributes are accessed by \f5agget\fP and \f5agset\fP +These take a pointer to any graph, node, or edge, and an attribute name. +Also, each attribute has an integer index. For efficiency this index +may be passed instead of the name, by calling \f5agxget\fP and \f5agxset\fP. +The \f5printed\fP flag of an attribute may be set to 0 to skip it +when writing a graph file. +.PP +The \f5list\fP in an attribute dictionary is maintained in order of creation +and is NULL terminated. +Here is a program fragment to print node attribute names: +.nf + \f5attrsym_t *aptr; + for (i = 0; aptr = g\->univ\->nodedict\->list[i]; i++) puts(aptr\->name);\fP +.fi +.SH EXAMPLE GRAPH FILES +.nf +graph any_name { /* an undirected graph */ + a \-\- b; /* a simple edge */ + a \-\- x1 \-\- x2 \-\- x3; /* a chain of edges */ + "x3.a!" \-\- a; /* quotes protect special characters */ + b \-\- {q r s t}; /* edges that fan out */ + b [color="red",size=".5,.5"]; /* set various node attributes */ + node [color=blue]; /* set default attributes */ + b \-\- c [weight=25]; /* set edge attributes */ + subgraph sink_nodes {a b c}; /* make a subgraph */ +} + +digraph G { + size="8.5,11"; /* sets a graph attribute */ + a \-> b; /* makes a directed edge */ + chip12.pin1 \-> chip28.pin3; /* uses named node "ports" */ +} +.fi + +.SH SEE ALSO +.BR dot (1), +.BR neato (1), +.BR libdict (3) +.br +S. C. North and K. P. Vo, "Dictionary and Graph Libraries'' +1993 Winter USENIX Conference Proceedings, pp. 1\(hy11. + +.SH AUTHOR +Stephen North (north@ulysses.att.com), AT&T Bell Laboratories.