graph

LIBGRAPH(3)                Library Functions Manual                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);
       Agnode_t    *aglstnode(Agraph_t *g);
       Agnode_t    *agprvnode(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 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
       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‐value pairs)
       dynamically allocated at runtime and accessed through libgraph 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‐graph).  Meta‐nodes correspond to subgraphs, and meta‐
       edges signify containment of one subgraph in 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 a header file) 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,
       Agnodeinfo_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
       catastrophic errors.


GRAPHS
       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;
       A graph kind 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‐arcs or multi‐edges.  attr 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 these dictionaries directly, though
       the edge dictionaries may be re‐ordered to support programmer‐defined
       ordered edges (see dtreorder in cdt(3)).  proto is a stack of templates
       for node and edge initialization.  The attributes of these nodes and
       edges are set in the usual way (agget, agset, etc.) to set defaults.

       agread reads a file and returns a new graph if one was succesfully
       parsed, otherwise returns NULL if EOF or a syntax error was
       encountered.  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
       subgraph 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 an object belongs
       to the given graph.  aginsert inserts an object in a graph and agdelete
       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.


NODES
       typedef struct Agnode_t {
           char                *name;
           Agraph_t            *graph;
           char                **attr;
           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 the node set of a graph,
       respectively, or NULL.  aglstnode (agprvnode) return the last
       (previous) element in the node set of a graph, respectively, or NULL.


EDGES
       typedef struct Agedge_t {
           Agnode_t            *head,*tail;
           char                **attr;
           Agedgeinfo_t        u;
       } Agedge_t;
       agedge creates a new edge with the attributes of g->proto->e including
       its key if not empty.  agfindedge finds the first (u,v) edge in g.
       agfstedge (agnxtedge) return the first (next) element in the edge set
       of a graph, respectively, or NULL.  agfstin, agnxtin, agfstout,
       agnxtout refer to in‐ or out‐edge sets.  The idiomatic usage in 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 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 the graph file 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
       subsequently read 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 to 0 to skip it when writing a graph
       file.

       The list in an attribute dictionary is maintained in 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(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 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" */
       }


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)