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