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