Mercurial > hg > camir-aes2014
diff toolboxes/graph_visualisation/share/man/man3/cgraph.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/cgraph.3 Tue Feb 10 15:05:51 2015 +0000 @@ -0,0 +1,522 @@ +.de P0 +.nf +\f5 +.. +.de P1 +\fP +.fi +.. +.de Ss +.fl +.ne 2 +.SS "\\$1" +.. +.TH LIBCGRAPH 3 "30 JULY 2007" +.SH "NAME" +\fBlibcgraph\fR \- abstract graph library +.SH "SYNOPSIS" +."ta .75i 1.5i 2.25i 3i 3.75i 4.5i 5.25i 6i +.PP +.nf +.P0 +#include <graphviz/cgraph.h> +.P1 +.SS "TYPES" +.P0 +Agraph_t; +Agnode_t; +Agedge_t; +Agdesc_t; +Agdisc_t; +Agsym_t; +.P1 +.SS "GRAPHS" +.P0 +Agraph_t *agopen(char *name, Agdesc_t kind, Agdisc_t *disc); +int agclose(Agraph_t *g); +Agraph_t *agread(void *channel, Agdisc_t *); +void agreadline(int line_no); +void agsetfile(char *file_name); +Agraph_t *agconcat(Agraph_t *g, void *channel, Agdisc_t *disc) +int agwrite(Agraph_t *g, void *channel); +int agnnodes(Agraph_t *g),agnedges(Agraph_t *g); +int agisdirected(Agraph_t * g),agisundirected(Agraph_t * g),agisstrict(Agraph_t * g), agissimple(Agraph_t * g); +.SS "SUBGRAPHS" +.P0 +Agraph_t *agsubg(Agraph_t *g, char *name, int createflag); +Agraph_t *agidsubg(Agraph_t * g, unsigned long id, int cflag); +Agraph_t *agfstsubg(Agraph_t *g), agnxtsubg(Agraph_t *); +Agraph_t *agparent(Agraph_t *g); +int agdelsubg(Agraph_t * g, Agraph_t * sub); /* same as agclose() */ +.P1 +.SS "NODES" +.P0 +Agnode_t *agnode(Agraph_t *g, char *name, int createflag); +Agnode_t *agidnode(Agraph_t *g, ulong id, int createflag); +Agnode_t *agsubnode(Agraph_t *g, Agnode_t *n, int createflag); +Agnode_t *agfstnode(Agraph_t *g); +Agnode_t *agnxtnode(Agraph_t *g, Agnode_t *n); +Agnode_t *agprvnode(Agraph_t *g, Agnode_t *n); +Agnode_t *aglstnode(Agraph_t *g); +int agdelnode(Agraph_t *g, Agnode_t *n); +int agdegree(Agnode_t *n, int use_inedges, int use_outedges); +.P1 +.SS "EDGES" +.P0 +Agedge_t *agedge(Agraph_t* g, Agnode_t *t, Agnode_t *h, char *name, int createflag); +Agedge_t *agidedge(Agraph_t * g, Agnode_t * t, Agnode_t * h, unsigned long id, int createflag); +Agedge_t *agsubedge(Agraph_t *g, Agedge_t *e, int createflag); +Agnode_t *aghead(Agedge_t *e), *agtail(Agedge_t *e); +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); +int agdeledge(Agraph_t *g, Agedge_t *e); +.SS "STRING ATTRIBUTES" +.P0 +Agsym_t *agattr(Agraph_t *g, int kind, char *name, char *value); +Agsym_t *agattrsym(void *obj, char *name); +Agsym_t *agnxtattr(Agraph_t *g, int kind, Agsym_t *attr); +char *agget(void *obj, char *name); +char *agxget(void *obj, Agsym_t *sym); +int agset(void *obj, char *name, char *value); +int agxset(void *obj, Agsym_t *sym, char *value); +int agsafeset(void *obj, char *name, char *value, char *def); +.P1 +.SS "RECORDS" +.P0 +void *agbindrec(void *obj, char *name, unsigned int size, move_to_front); +Agrec_t *aggetrec(void *obj, char *name, int move_to_front); +int agdelrec(Agraph_t *g, void *obj, char *name); +int agcopyattr(void *, void *); +void aginit(Agraph_t * g, int kind, char *rec_name, int rec_size, int move_to_front); +void agclean(Agraph_t * g, int kind, char *rec_name); +.P1 +.SS "CALLBACKS" +.P0 +Agcbdisc_t *agpopdisc(Agraph_t *g); +void agpushdisc(Agraph_t *g, Agcbdisc_t *disc); +void agmethod(Agraph_t *g, void *obj, Agcbdisc_t *disc, int initflag); +.P1 +.SS "MEMORY" +.P0 +void *agalloc(Agraph_t *g, size_t request); +void *agrealloc(Agraph_t *g, void *ptr, size_t oldsize, size_t newsize); +void agfree(Agraph_t *g, void *ptr); +.P1 +.SS "STRINGS" +.P0 +char *agstrdup(Agraph_t *, char *); +char *agstrdup_html(Agraph_t *, char *); +int aghtmlstr(char *); +char *agstrbind(Agraph_t * g, char *); +int strfree(Agraph_t *, char *); +char *agcanonStr(char *); +char *agstrcanon(char *, char *); +.P1 +.SS "GENERIC OBJECTS" +.P0 +Agraph_t *agraphof(void*); +Agraph_t *agroot(void*); +int agcontains(Agraph_t*, void*); +char *agnameof(void*); +void agdelete(Agraph_t *g, void *obj); +int agobjkind(void *obj); +Agrec_t *AGDATA(void *obj); +ulong AGID(void *obj); +int AGTYPE(void *obj); +.P1 +.SH "DESCRIPTION" +Libcgraph supports graph programming by maintaining graphs in memory +and reading and writing graph files. +Graphs are composed of nodes, edges, and nested subgraphs. +These graph objects may be attributed with string name-value pairs +and programmer-defined records (see Attributes). +.PP +All of Libcgraph's global symbols have the prefix \fBag\fR (case varying). +.SH "GRAPH AND SUBGRAPHS" +.PP +A ``main'' or ``root'' graph defines a namespace for a collection of +graph objects (subgraphs, nodes, edges) and their attributes. +Objects may be named by unique strings or by 32-bit IDs. +.PP +\fBagopen\fP creates a new graph with the given name and kind. +(Graph kinds are \fBAgdirected\fP, \fBAgundirected\fP, +\fBAgstrictdirected\fP, and \fBAgstrictundirected\fP. +A strict graph cannot have multi-edges or self-arcs.) +\fBagclose\fP deletes a graph, freeing its associated storage. +\fBagread\fP, \fBagwrite\fP, and \fBagconcat\fP perform file I/O +using the graph file language described below. \fBagread\fP +constructs a new graph while \fBagconcat\fP merges the file +contents with a pre-existing graph. Though I/O methods may +be overridden, the default is that the channel argument is +a stdio FILE pointer. \fBagsetfile\fP and \fBagreadline\fP +are helper functions that simply set the current file name +and input line number for subsequent error reporting. +.PP +\fBagsubg\fP finds or creates +a subgraph by name. A new subgraph is is initially empty and +is of the same kind as its parent. Nested subgraph trees may be created. +A subgraph's name is only interpreted relative to its parent. +A program can scan subgraphs under a given graph +using \fBagfstsubg\fP and \fRagnxtsubg\fP. A subgraph is +deleted with \fBagdelsubg\fP (or \fBagclose\fP). +.PP +By default, nodes are stored in ordered sets for efficient random +access to insert, find, and delete nodes. +The edges of a node are also stored in ordered sets. +The sets are maintained internally as splay tree dictionaries +using Phong Vo's cdt library. +.PP +\fBagnnodes\fP, \fBagnedges\fP, and \fBagdegree\fP return the +sizes of node and edge sets of a graph. The \fBagdegree\fP returns +the size of the edge set of a nodes, and takes flags +to select in-edges, out-edges, or both. +.PP +An \fBAgdisc_t\fP defines callbacks to be invoked by libcgraph when +initializing, modifying, or finalizing graph objects. (Casual users can ignore +the following.) Disciplines are kept on a stack. Libcgraph automatically +calls the methods on the stack, top-down. Callbacks are installed +with \fBagpushdisc\fP, uninstalled with \fBagpopdisc\fP, and +can be held pending or released via \fBagcallbacks\fP. +.PP +(Casual users may ignore the following. +When Libcgraph is compiled with Vmalloc (which is not the default), +each graph has its own heap. +Programmers may allocate application-dependent data within the +same heap as the rest of the graph. The advantage is that +a graph can be deleted by atomically freeing its entire heap +without scanning each individual node and edge. +.SH "NODES" +A node is created by giving a unique string name or +programmer defined 32-bit ID, and is represented by a +unique internal object. (Node equality can checked +by pointer comparison.) +.PP +\fBagnode\fP searches in a graph or subgraph for a node +with the given name, and returns it if found. +If not found, if \fBcreateflag\fP is boolean true +a new node is created and returned, otherwise a nil +pointer is returned. +\fBagidnode\fP allows a programmer to specify the node +by a unique 32-bit ID. +\fBagsubnode\fP performs a similar operation on +an existing node and a subgraph. +.Pp +\fBagfstnode\fP and \fBagnxtnode\fP scan node lists. +\fBagprvnode\fP and \fPaglstnode\fP are symmetric but scan backward. +The default sequence is order of creation (object timestamp.) +\fBagdelnode\fP removes a node from a graph or subgraph. +.SH "EDGES" +.PP +An abstract edge has two endpoint nodes called tail and head +where the all outedges of the same node have it as the tail +value and similarly all inedges have it as the head. +In an undirected graph, head and tail are interchangable. +If a graph has multi-edges between the same pair of nodes, +the edge's string name behaves as a secondary key. +.Pp +\fBagedge\fP searches in a graph of subgraph for an +edge between the given endpoints (with an optional +multi-edge selector name) and returns it if found. +Otherwise, if \fBcreateflag\fP is boolean true, +a new edge is created and returned: otherwise +a nil pointer is returned. If the \fBname\fP +is NULL, then an anonymous internal +value is generated. \fBagidedge\fP allows a programmer +to create an edge by giving its unique 32-bit ID. +\fBagfstin\fP, \fBagnxtint\fP, \fBagfstout\fP, and +\fBagnxtout\fP visit directed in- and out- edge lists, +and ordinarily apply only in directed graphs. +\fBagfstedge\fP and \fBagnxtedge\fP visit all edges +incident to a node. \fBagtail\fP and \fBaghead\fP +get the endpoint of an edge. +.SH "INTERNAL ATTRIBUTES" +Programmer-defined values may be dynamically +attached to graphs, subgraphs, nodes, and edges. +Such values are either uninterpreted binary records +(for implementing efficient algorithms) +or character string data (for I/O). +.SH "STRING ATTRIBUTES" +String attributes are handled automatically in reading +and writing graph files. +A string attribute is identified by name and by +an internal symbol table entry (\fBAgsym_t\fP) created by Libcgraph. +Attributes of nodes, edges, and graphs (with their subgraphs) +have separate namespaces. The contents of an \fBAgsym_t\fP +is listed below, followed by primitives to operate on string +attributes. +.P0 +typedef struct Agsym_s { /* symbol in one of the above dictionaries */ + Dtlink_t link; + char *name; /* attribute's name */ + char *defval; /* its default value for initialization */ + int id; /* its index in attr[] */ + unsigned char kind; /* referent object type */ + unsigned char fixed; /* immutable value */ +} Agsym_t; +.P1 +.PP +\fBagattr\fP creates or looks up attributes. +\fBkind\fP may be \fBAGRAPH\fP, \fBAGNODE\fP, or \fBAGEDGE\fP. +If \fBvalue\fP is \fB(char*)0)\fP, the request is to search +for an existing attribute of the given kind and name. +Otherwise, if the attribute already exists, its default +for creating new objects is set to the given value; +if it does not exist, a new attribute is created with the +given default, and the default is applied to all pre-existing +objects of the given kind. If \fBg\fP is NIL, the default is +set for all graphs created subsequently. +\fBagattrsym\fP is a helper function +that looks up an attribute for a graph object given as an argument. +\fBagnxtattr\fP permits traversing the list of attributes of +a given type. If \fBNIL\fP is passed as an argument it gets +the first attribute, otherwise it returns the next one in +succession or returns \fBNIL\fP at the end of the list. +\fBagget\fP and \fPagset\fP allow fetching and updating a +string attribute for an object taking the attribute name as +an argument. \fBagxget\fP and \fBagxset\fP do this but with +an attribute symbol table entry as an argument (to avoid +the cost of the string lookup). \fBagsafeset\fP is a +convenience function that ensures the given attribute is +declared before setting it locally on an object. + +.SH "STRINGS" +Libcgraph performs its own storage management of strings as +reference-counted strings. +The caller does not need to dynamically allocate storage. +.PP +\fBagstrdup\fP returns a pointer to a reference-counted copy of +the argument string, creating one if necessary. \fBagstrbind\fP +returns a pointer to a reference-counted string if it exists, or NULL if not. +All uses of cgraph strings need to be freed using \fBagstrfree\fP +in order to correctly maintain the reference count. +.PP +\fBagcanonStr\fP returns a pointer to a version of the input string +canonicalized for output for later re-parsing. This includes quoting +special characters and keywords. It uses its own internal buffer, so +the value will be lost on the next call to \fBagcanonStr\fP. +\fBagstrcanon\fP is an unsafe version of \fBagcanonStr\fP, in which +the application passes in a buffer as the second argument. Note that +the buffer may not be used; if the input string is in canonical form, +the function will just return a pointer to it. +.PP +The cgraph parser handles HTML-like strings. These should be +indistinguishable from other strings for most purposes. To create +an HTML-like string, use \fBagstrdup_html\fP. The \fBaghtmlstr\fP +function can be used to query if a string is an ordinary string or +an HTML-like string. +.SH "RECORDS" +Uninterpreted records may be attached to graphs, subgraphs, nodes, +and edges for efficient operations on values such as marks, weights, +counts, and pointers needed by algorithms. Application programmers +define the fields of these records, but they must be declared with +a common header as shown below. +.P0 +typedef struct Agrec_s { + Agrec_t header; + /* programmer-defined fields follow */ +} Agrec_t; +.P1 +Records are created and managed by Libcgraph. A programmer must +explicitly attach them to the objects in a graph, either to +individual objects one at a time via \fBagbindrec\fP, or to +all the objects of the same class in a graph via \fBaginit\fP. +The \fBname\fP argument a record distinguishes various types of records, +and is programmer defined (Libcgraph reserves the prefix \fB_ag\fR). +If size is 0, the call to \fBagbindrec\fP is simply a lookup. +\fBagdelrec\fP is the deletes records one at a time. +\fBagclean\fP does the same for all objects of the same +class in an entire graph. + +Internally, records are maintained in circular linked lists +attached to graph objects. +To allow referencing application-dependent data without function +calls or search, Libcgraph allows setting and locking the list +pointer of a graph, node, or edge on a particular record. +This pointer can be obtained with the macro \fBAGDATA(obj)\fP. +A cast, generally within a macro or inline function, +is usually applied to convert the list pointer to +an appropriate programmer-defined type. + +To control the setting of this pointer, +the \fBmove_to_front\fP flag may be \fBAG_MTF_FALSE\fP, +\fBAG_MTF_SOFT\fP, or \fBAG_MTF_HARD\fP accordingly. +The \fBAG_MTF_SOFT\fP field is only a hint that decreases +overhead in subsequent calls of \fBaggetrec\fP; +\fBAG_MTF_HARD\fP guarantees that a lock was obtained. +To release locks, use \fBAG_MTF_SOFT\fP or \fBAG_MTF_FALSE\fP. +Use of this feature implies cooperation or at least isolation +from other functions also using the move-to-front convention. + +.SH "DISCIPLINES" +(The following is not intended for casual users.) +Programmer-defined disciplines customize certain resources- +ID namespace, memory, and I/O - needed by Libcgraph. +A discipline struct (or NIL) is passed at graph creation time. +.P0 +struct Agdisc_s { /* user's discipline */ + Agmemdisc_t *mem; + Agiddisc_t *id; + Agiodisc_t *io; +} ; +.P1 +A default discipline is supplied when NIL is given for +any of these fields. + +An ID allocator discipline allows a client to control assignment +of IDs (uninterpreted 32-bit values) to objects, and possibly how +they are mapped to and from strings. + +.P0 +struct Agiddisc_s { /* object ID allocator */ + void *(*open)(Agraph_t *g); /* associated with a graph */ + int (*map)(void *state, int objtype, char *str, ulong *id, int createflag); + int (*alloc)(void *state, int objtype, ulong id); + void (*free)(void *state, int objtype, ulong id); + char *(*print)(void *state, int objtype, ulong id); + void (*close)(void *state); +} ; +.P1 + +\f5open\fP permits the ID discipline to initialize any data +structures that maintains per individual graph. +Its return value is then passed as the first argument to +all subsequent ID manager calls. + +\f5alloc\fP informs the ID manager that Libcgraph is attempting +to create an object with a specific ID that was given by a client. +The ID manager should return TRUE (nonzero) if the ID can be +allocated, or FALSE (which aborts the operation). + +\f5free\fP is called to inform the ID manager that the +object labeled with the given ID is about to go out of existence. + +\f5map\fP is called to create or look-up IDs by string name +(if supported by the ID manager). Returning TRUE (nonzero) +in all cases means that the request succeeded (with a valid +ID stored through \f5result\fP. There are four cases: +.PP +\f5name != NULL\fP and \f5createflag == 1\fP: +This requests mapping a string (e.g. a name in a graph file) into a new ID. +If the ID manager can comply, then it stores the result and returns TRUE. +It is then also responsible for being able to \f5print\fP the ID again +as a string. Otherwise the ID manager may return FALSE but it must +implement the following (at least for graph file reading and writing to work): +.PP +\f5name == NULL\fP and \f5createflag == 1\fP: +The ID manager creates a unique new ID of its own choosing. +Although it may return FALSE if it does not support anonymous objects, +but this is strongly discouraged (to support "local names" in graph files.) +.PP +\f5name != NULL\fP and \f5createflag == 0\fP: +This is a namespace probe. If the name was previously mapped into +an allocated ID by the ID manager, then the manager must return this ID. +Otherwise, the ID manager may either return FALSE, or may store +any unallocated ID into result. (This is convenient, for example, +if names are known to be digit strings that are directly converted into 32 bit values.) +.PP +\f5name == NULL\fP and \f5createflag == 0\fP: forbidden. +.PP +\f5print\fP is allowed to return a pointer to a static buffer; +a caller must copy its value if needed past subsequent calls. +\f5NULL\fP should be returned by ID managers that do not map names. +.PP +The \f5map\fP and \f5alloc\fP calls do not pass a pointer to the +newly allocated object. If a client needs to install object +pointers in a handle table, it can obtain them via +new object callbacks. +.P0 +struct Agiodisc_s { + int (*fread)(void *chan, char *buf, int bufsize); + int (*putstr)(void *chan, char *str); + int (*flush)(void *chan); /* sync */ + /* error messages? */ +} ; + +struct Agmemdisc_s { /* memory allocator */ + void *(*open)(void); /* independent of other resources */ + void *(*alloc)(void *state, size_t req); + void *(*resize)(void *state, void *ptr, size_t old, size_t req); + void (*free)(void *state, void *ptr); + void (*close)(void *state); +} ; +.P1 + +.SH "EXAMPLE PROGRAM" +.P0 +#include <graphviz/cgraph.h> +typedef struct mydata_s {Agrec_t hdr; int x,y,z;} mydata; + +main(int argc, char **argv) +{ + Agraph_t *g; + Agnode_t *v; + Agedge_t *e; + Agsym_t *attr; + Dict_t *d + int cnt; + mydata *p; + + if (g = agread(stdin,NIL(Agdisc_t*))) { + cnt = 0; attr = 0; + while (attr = agnxtattr(g, AGNODE, attr)) cnt++; + printf("The graph %s has %d attributes\n",agnameof(g),cnt); + + /* make the graph have a node color attribute, default is blue */ + attr = agattr(g,AGNODE,"color","blue"); + + /* create a new graph of the same kind as g */ + h = agopen("tmp",g->desc); + + /* this is a way of counting all the edges of the graph */ + cnt = 0; + for (v = agfstnode(g); v; v = agnxtnode(g,v)) + for (e = agfstout(g,v); e; e = agnxtout(g,e)) + cnt++; + + /* attach records to edges */ + for (v = agfstnode(g); v; v = agnxtnode(g,v)) + for (e = agfstout(g,v); e; e; = agnxtout(g,e)) { + p = (mydata*) agbindrec(g,e,"mydata",sizeof(mydata),TRUE); + p->x = 27; /* meaningless data access example */ + ((mydata*)(AGDATA(e)))->y = 999; /* another example */ + } + } +} +.P1 +.SH "EXAMPLE GRAPH FILES" +.P0 +digraph G { + a -> b; + c [shape=box]; + a -> c [weight=29,label="some text]; + subgraph anything { + /* the following affects only x,y,z */ + node [shape=circle]; + a; x; y -> z; y -> z; /* multiple edges */ + } +} + +strict graph H { + n0 -- n1 -- n2 -- n0; /* a cycle */ + n0 -- {a b c d}; /* a star */ + n0 -- n3; + n0 -- n3 [weight=1]; /* same edge because graph is strict */ +} +.P1 +.SH "SEE ALSO" +Libcdt(3) + +.SH "BUGS" +It is difficult to change endpoints of edges, delete string attributes or +modify edge keys. The work-around is to create a new object and copy the +contents of an old one (but new object obviously has a different ID, +internal address, and object creation timestamp). + +The API lacks convenient functions to substitute programmer-defined ordering of +nodes and edges but in principle this can be supported. +.SH "AUTHOR" +Stephen North, north@research.att.com, AT&T Research.