Man Linux: Main Page and Category List


       libgraph - abstract graph library



       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.    and   map
       between   subgraphs  and  meta‐nodes.   The  nodes  and  edges  of  the
       meta‐graph may be traversed by the usual libgraph  functions  for  this


       1.  Define types , , and  (usually in a header file) before including .

       2. Call  before any other libgraph functions.  (This is  a  macro  that
       calls    to   define  the  sizes  of  Agraphinfo_t,  Agnodeinfo_t,  and

       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.


       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  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 (, , etc.) to set defaults.

        reads a file and returns a new graph if one was  successfully  parsed,
       otherwise  returns  NULL if  or a syntax error was encountered.  Errors
       are reported on stderr and a count is returned from agerrors()


       , ,  are generic  functions  for  nodes,  edges,  and  graphs.    is  a
       predicate that tests if an object belongs to the given graph.   inserts
       an object in a graph and  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.


         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.   () return the first
       (next) element in the node set of a graph, respectively, or NULL.    ()
       return  the  last  (previous)  element  in  the  node  set  of a graph,
       respectively, or NULL.


        creates a new edge with the attributes of  g->proto->e  including  its
       key  if  not  empty.    finds the first (u,v) edge in .   () return the
       first (next) element in the edge set of a graph, respectively, or NULL.
       , , , refer to in‐ or out‐edge sets.  The idiomatic usage in a directed
       graph is:

       An edge is uniquely identified by its endpoints and its  attribute  (if
       there  are  multiple  edges).   If  the   of    is empty, new edges are
       assigned an internal value.  Edges also have  and  values.  These  have
       special  syntax  in  the  graph  file  language  but  are not otherwise


       , , and  make new  attributes.    should  be  a  main  graph,  or   for
       declarations  applying  to  all  graphs  subsequently  read or created.
       searches for an existing attribute.

       External attributes are accessed by  and 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  and .  The  flag of an attribute may be set to 0
       to skip it when writing a graph file.

       The  in an attribute dictionary is maintained in order of creation  and
       is NULL terminated.  Here is a program fragment to print node attribute


       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" */


       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.


       Stephen North (, AT&T Bell Laboratories.

                                 01 MARCH 1993                     LIBGRAPH(3)