NAME
libgraph - abstract graph library
SYNOPSIS
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. 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
purpose.
USE
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
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
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()
ALL OBJECTS
, , 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.
NODES
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.
EDGES
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
interpreted.
ATTRIBUTES
, , 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
names:
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)