Seth Woolley's Man Viewer

graph(3) - libgraph - abstract graph library - man 3 graph

([section] manual, -k keyword, -K [section] search, -f whatis)
man plain no title

LIBGRAPH(3)                                                        LIBGRAPH(3)



NAME
       libgraph - abstract graph library

SYNOPSIS
       #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);
       int         agcontains(Agraph_t *g, void *obj);
       int         aginsert(Agraph_t *g, void *obj);
       int         agdelete(Agraph_t *g, void *obj);

       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);

       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);

       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);

       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);

DESCRIPTION
       libgraph  maintains directed and undirected attributed graphs in(1,8) 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 libgraph 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(1,8)
       the  graph, node and edge structs defined at compile time.  These allow
       efficient representation and direct access(2,5) to  values  such  as  marks,
       weights,   and   pointers   for  writing  graph  algorithms.   External
       attributes, on the other hand, are character strings (name-value pairs)
       dynamically  allocated  at runtime and accessed through libgraph calls.
       External attributes are used in(1,8) graph file(1,n) I/O; internal attributes are
       not.   Conversion  between  internal  and  external  attributes must be
       explicitly programmed.

       The subgraphs in(1,8) a main graph are represented by an auxiliary  directed
       graph  (a  meta-graph).   Meta-nodes correspond to subgraphs, and meta-
       edges signify containment of one subgraph in(1,8) another.   agmetanode  and
       agusergraph  map between subgraphs and meta-nodes.  The nodes and edges
       of the meta-graph may be traversed by the usual libgraph functions  for
       this purpose.


USE
       1.  Define  types Agraphinfo_t, Agnodeinfo_t, and Agedgeinfo_t (usually
       in(1,8) a header file(1,n)) before including <graphviz/graph.h>.

       2. Call aginit() before any other libgraph functions.  (This is a macro
       that  calls  aginitlib()  to  define the sizes of Agraphinfo_t, Agnode-
       info_t, and Agedgeinfo_t.)

       3. Compile with -lgraph -lcdt.

       Except for the u fields, libgraph data structures  must  be  considered
       read-only.  Corrupting their contents by direct updates can cause cata-
       strophic errors.


GRAPHS
       typedef struct Agraph_t {
           char                 kind;
           char                *name;
           Agraph_t             *root;
           char                **attr(1,5);
           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;
       A graph kind is one of: AGRAPH, AGRAPHSTRICT, AGDIGRAPH, or  AGDIGRAPH-
       STRICT.   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-arcs or multi-edges.  attr(1,5) is the array of external attribute
       values.  univ points to values shared by all subgraphs of a main graph.
       nodes,  inedges,  and outedges are sets maintained by cdt(3).  Normally
       you don't access(2,5) these dictionaries directly, though the  edge  dictio-
       naries  may  be  re-ordered to support programmer-defined ordered edges
       (see dtreorder in(1,8) cdt(3)).  proto is a stack of templates for node  and
       edge  initialization.   The attributes of these nodes and edges are set(7,n,1 builtins)
       in(1,8) the usual way (agget, agset, etc.) to set(7,n,1 builtins) defaults.

       agread reads a file(1,n) and returns a new  graph  if(3,n)  one  was  succesfully
       parsed,  otherwise  returns  NULL  if(3,n) EOF or a syntax error(8,n) was encoun-
       tered.  Errors are reported on stderr and  a  count  is  returned  from
       agerrors().   write_graph  prints a graph on a file.  agopen and agsubg
       create new empty graph and subgraphs.  agfindsubg searches for  a  sub-
       graph by name, returning NULL when the search fails.


ALL OBJECTS
       agcontains,  aginsert, agdelete are generic functions for nodes, edges,
       and graphs.  gcontains is a predicate that tests if(3,n) an  object  belongs
       to the given graph.  aginsert inserts an object in(1,8) a graph and agdelete
       undoes this operation.  A node or edge is destroyed  (and  its  storage
       freed)  at the time(1,2,n) it is deleted from the main graph.  Likewise a sub-
       graph is destroyed when it is deleted from its last parent or when  its
       last parent is deleted.


NODES
       typedef struct Agnode_t {
           char                *name;
           Agraph_t            *graph;
           char                **attr(1,5);
           Agnodeinfo_t        u;
       } Agnode_t;

       agnode  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.  agfstnode
       (agnxtnode) return the first (next) element in(1,8) the node set(7,n,1 builtins) of a graph,
       respectively, or NULL.


EDGES
       typedef struct Agedge_t {
           Agnode_t            *head,*tail;
           char                **attr(1,5);
           Agedgeinfo_t        u;
       } Agedge_t;
       agedge  creates a new edge with the attributes of g->proto->e including
       its key if(3,n) not empty.  agfindedge finds the  first  (u,v)  edge  in(1,8)  g.
       agfstedge  (agnxtedge)  return the first (next) element in(1,8) the edge set(7,n,1 builtins)
       of  a  graph,  respectively,  or  NULL.   agfstin,  agnxtin,  agfstout,
       agnxtout  refer  to  in-  or  out-edge  sets.  The idiomatic usage in(1,8) a
       directed graph is:

           for (e = agfstout(g,n); e; e = agnextout(g,e)) your_fun(e);

       An edge is uniquely identified by its endpoints and its  key  attribute
       (if(3,n) there are multiple edges).  If the key of g->proto->e is empty, new
       edges are assigned an internal value.  Edges  also  have  tailport  and
       headport  values.  These have special syntax in(1,8) the graph file(1,n) language
       but are not otherwise interpreted.


ATTRIBUTES
       typedef struct attrsym_t {
           char                *name,*value;
           int                 index;
           unsigned char       printed;
       } attrsym_t;
       typedef struct attrdict_t  {
           char                *name;
           Dict_t              *dict;
           attrsym_t           **list;
       } attrdict_t;
       agraphattr, agnodeattr, and agedgeattr make new attributes.   g  should
       be a main graph, or NULL for declarations applying to all graphs subse-
       quently  read(2,n,1 builtins)  or  created.   agfindattr  searches  for   an   existing
       attribute.

       External  attributes  are  accessed  by  agget  and  agset 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 agxget and agxset.  The  printed
       flag  of  an  attribute may be set(7,n,1 builtins) to 0 to skip it when writing a graph
       file.

       The list in(1,8) an attribute dictionary is maintained in(1,8) order of  creation
       and  is  NULL  terminated.   Here  is  a program fragment to print node
       attribute names:
           attrsym_t *aptr;
           for (i = 0; aptr = g->univ->nodedict->list[i]; i++) puts(3,n)(aptr->name);

EXAMPLE GRAPH FILES
       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(7,n,1 builtins) various node attributes */
           node [color=blue];      /* set(7,n,1 builtins) default attributes */
           b -- c [weight=25];     /* set(7,n,1 builtins) edge attributes */
           subgraph sink_nodes {a b c};    /* make a subgraph */
       }

       digraph G {
           bb="8.5,11";            /* sets a graph attribute */
           a -> b;                 /* makes a directed edge */
           chip12.pin1 -> chip28.pin3; /* uses named(5,8) node "ports" */
       }


SEE ALSO
       dot(1), neato(1), libdict(3)
       S. C. North and K. P. Vo, "Dictionary and Graph Libraries'' 1993 Winter
       USENIX Conference Proceedings, pp. 1-11.


AUTHOR
       Stephen North (north@ulysses.att.com), AT&T Bell Laboratories.



                                 01 MARCH 1993                     LIBGRAPH(3)

References for this manual (incoming links)