NAME
libcgraph - abstract graph library
SYNOPSIS
TYPES
GRAPHS
SUBGRAPHS
NODES
EDGES
STRING ATTRIBUTES
RECORDS
CALLBACKS
MEMORY
STRINGS
GENERIC OBJECTS
DESCRIPTION
Libcgraph supports graph programming by maintaining graphs in memory
and reading and writing graph files. Graphs are composed of nodes,
edges, and nested subgraphs. These graph objects may be attributed
with string name-value pairs and programmer-defined records (see
Attributes).
All of Libcgraph’s global symbols have the prefix ag (case varying).
GRAPH AND SUBGRAPHS
A ‘‘main’’ or ‘‘root’’ graph defines a namespace for a collection of
graph objects (subgraphs, nodes, edges) and their attributes. Objects
may be named by unique strings or by 32-bit IDs.
agopen creates a new graph with the given name and kind. (Graph kinds
are Agdirected, Agundirected, Agstrictdirected, and Agstrictundirected.
A strict graph cannot have multi-edges or self-arcs.) agclose deletes
a graph, freeing its associated storage. agread, agwrite, and agconcat
perform file I/O using the graph file language described below. agread
constructs a new graph while agconcat merges the file contents with a
pre-existing graph. Though I/O methods may be overridden, the default
is that the channel argument is a stdio FILE pointer. agsetfile and
agreadline are helper functions that simply set the current file name
and input line number for subsequent error reporting.
agsubg finds or creates a subgraph by name. A new subgraph is is
initially empty and is of the same kind as its parent. Nested subgraph
trees may be created. A subgraph’s name is only interpreted relative
to its parent. A program can scan subgraphs under a given graph using
agfstsubg and agnxtsubg. A subgraph is deleted with agdelsubg (or
agclose).
By default, nodes are stored in ordered sets for efficient random
access to insert, find, and delete nodes. The edges of a node are also
stored in ordered sets. The sets are maintained internally as splay
tree dictionaries using Phong Vo’s cdt library.
agnnodes, agnedges, and agdegree return the sizes of node and edge sets
of a graph. The agdegree returns the size of the edge set of a nodes,
and takes flags to select in-edges, out-edges, or both.
An Agdisc_t defines callbacks to be invoked by libcgraph when
initializing, modifying, or finalizing graph objects. (Casual users
can ignore the following.) Disciplines are kept on a stack. Libcgraph
automatically calls the methods on the stack, top-down. Callbacks are
installed with agpushdisc, uninstalled with agpopdisc, and can be held
pending or released via agcallbacks.
(Casual users may ignore the following. When Libcgraph is compiled
with Vmalloc (which is not the default), each graph has its own heap.
Programmers may allocate application-dependent data within the same
heap as the rest of the graph. The advantage is that a graph can be
deleted by atomically freeing its entire heap without scanning each
individual node and edge.
NODES
A node is created by giving a unique string name or programmer defined
32-bit ID, and is represented by a unique internal object. (Node
equality can checked by pointer comparison.)
agnode searches in a graph or subgraph for a node with the given name,
and returns it if found. If not found, if createflag is boolean true a
new node is created and returned, otherwise a nil pointer is returned.
agidnode allows a programmer to specify the node by a unique 32-bit ID.
agsubnode performs a similar operation on an existing node and a
subgraph.
agfstnode and agnxtnode scan node lists. agprvnode and aglstnode are
symmetric but scan backward. The default sequence is order of creation
(object timestamp.) agdelnode removes a node from a graph or subgraph.
EDGES
An abstract edge has two endpoint nodes called tail and head where the
all outedges of the same node have it as the tail value and similarly
all inedges have it as the head. In an undirected graph, head and tail
are interchangeable. If a graph has multi-edges between the same pair
of nodes, the edge’s string name behaves as a secondary key.
agedge searches in a graph of subgraph for an edge between the given
endpoints (with an optional multi-edge selector name) and returns it if
found. Otherwise, if createflag is boolean true, a new edge is created
and returned: otherwise a nil pointer is returned. If the name is
NULL, then an anonymous internal value is generated. agidedge allows a
programmer to create an edge by giving its unique 32-bit ID. agfstin,
agnxtint, agfstout, and agnxtout visit directed in- and out- edge
lists, and ordinarily apply only in directed graphs. agfstedge and
agnxtedge visit all edges incident to a node. agtail and aghead get
the endpoint of an edge.
INTERNAL ATTRIBUTES
Programmer-defined values may be dynamically attached to graphs,
subgraphs, nodes, and edges. Such values are either uninterpreted
binary records (for implementing efficient algorithms) or character
string data (for I/O).
STRING ATTRIBUTES
String attributes are handled automatically in reading and writing
graph files. A string attribute is identified by name and by an
internal symbol table entry (Agsym_t) created by Libcgraph. Attributes
of nodes, edges, and graphs (with their subgraphs) have separate
namespaces. The contents of an Agsym_t is listed below, followed by
primitives to operate on string attributes.
agattr creates or looks up attributes. kind may be AGRAPH, AGNODE, or
AGEDGE. If value is (char*)0), the request is to search for an
existing attribute of the given kind and name. Otherwise, if the
attribute already exists, its default for creating new objects is set
to the given value; if it does not exist, a new attribute is created
with the given default, and the default is applied to all pre-existing
objects of the given kind. If g is NIL, the default is set for all
graphs created subsequently. agattrsym is a helper function that looks
up an attribute for a graph object given as an argument. agnxtattr
permits traversing the list of attributes of a given type. If NIL is
passed as an argument it gets the first attribute, otherwise it returns
the next one in succession or returns NIL at the end of the list.
agget and agset allow fetching and updating a string attribute for an
object taking the attribute name as an argument. agxget and agxset do
this but with an attribute symbol table entry as an argument (to avoid
the cost of the string lookup). agsafeset is a convenience function
that ensures the given attribute is declared before setting it locally
on an object.
STRINGS
Libcgraph performs its own storage management of strings as reference-
counted strings. The caller does not need to dynamically allocate
storage.
agstrdup returns a pointer to a reference-counted copy of the argument
string, creating one if necessary. agstrbind returns a pointer to a
reference-counted string if it exists, or NULL if not. All uses of
cgraph strings need to be freed using agstrfree in order to correctly
maintain the reference count.
agcanonStr returns a pointer to a version of the input string
canonicalized for output for later re-parsing. This includes quoting
special characters and keywords. It uses its own internal buffer, so
the value will be lost on the next call to agcanonStr. agstrcanon is
an unsafe version of agcanonStr, in which the application passes in a
buffer as the second argument. Note that the buffer may not be used; if
the input string is in canonical form, the function will just return a
pointer to it.
The cgraph parser handles HTML-like strings. These should be
indistinguishable from other strings for most purposes. To create an
HTML-like string, use agstrdup_html. The aghtmlstr function can be used
to query if a string is an ordinary string or an HTML-like string.
RECORDS
Uninterpreted records may be attached to graphs, subgraphs, nodes, and
edges for efficient operations on values such as marks, weights,
counts, and pointers needed by algorithms. Application programmers
define the fields of these records, but they must be declared with a
common header as shown below.
Records are created and managed by Libcgraph. A programmer must
explicitly attach them to the objects in a graph, either to individual
objects one at a time via agbindrec, or to all the objects of the same
class in a graph via aginit. (Note that for graphs, aginit is applied
recursively to the graph and its subgraphs if rec_size is negative (of
the actual rec_size.)) The name argument a record distinguishes
various types of records, and is programmer defined (Libcgraph reserves
the prefix _ag). If size is 0, the call to agbindrec is simply a
lookup. agdelrec is the deletes records one at a time. agclean does
the same for all objects of the same class in an entire graph.
Internally, records are maintained in circular linked lists attached to
graph objects. To allow referencing application-dependent data without
function calls or search, Libcgraph allows setting and locking the list
pointer of a graph, node, or edge on a particular record. This pointer
can be obtained with the macro AGDATA(obj). A cast, generally within a
macro or inline function, is usually applied to convert the list
pointer to an appropriate programmer-defined type.
To control the setting of this pointer, the move_to_front flag may be
AG_MTF_FALSE, AG_MTF_SOFT, or AG_MTF_HARD accordingly. The AG_MTF_SOFT
field is only a hint that decreases overhead in subsequent calls of
aggetrec; AG_MTF_HARD guarantees that a lock was obtained. To release
locks, use AG_MTF_SOFT or AG_MTF_FALSE. Use of this feature implies
cooperation or at least isolation from other functions also using the
move-to-front convention.
DISCIPLINES
(The following is not intended for casual users.) Programmer-defined
disciplines customize certain resources- ID namespace, memory, and I/O
- needed by Libcgraph. A discipline struct (or NIL) is passed at graph
creation time.
A default discipline is supplied when NIL is given for any of these
fields.
An ID allocator discipline allows a client to control assignment of IDs
(uninterpreted 32-bit values) to objects, and possibly how they are
mapped to and from strings.
permits the ID discipline to initialize any data structures that
maintains per individual graph. Its return value is then passed as the
first argument to all subsequent ID manager calls.
informs the ID manager that Libcgraph is attempting to create an
object with a specific ID that was given by a client. The ID manager
should return TRUE (nonzero) if the ID can be allocated, or FALSE
(which aborts the operation).
is called to inform the ID manager that the object labeled with the
given ID is about to go out of existence.
is called to create or look-up IDs by string name (if supported by the
ID manager). Returning TRUE (nonzero) in all cases means that the
request succeeded (with a valid ID stored through . There are four
cases:
and : This requests mapping a string (e.g. a name in a graph file)
into a new ID. If the ID manager can comply, then it stores the result
and returns TRUE. It is then also responsible for being able to the
ID again as a string. Otherwise the ID manager may return FALSE but it
must implement the following (at least for graph file reading and
writing to work):
and : The ID manager creates a unique new ID of its own choosing.
Although it may return FALSE if it does not support anonymous objects,
but this is strongly discouraged (to support "local names" in graph
files.)
and : This is a namespace probe. If the name was previously
mapped into an allocated ID by the ID manager, then the manager must
return this ID. Otherwise, the ID manager may either return FALSE, or
may store any unallocated ID into result. (This is convenient, for
example, if names are known to be digit strings that are directly
converted into 32 bit values.)
and : forbidden.
is allowed to return a pointer to a static buffer; a caller must copy
its value if needed past subsequent calls. should be returned by ID
managers that do not map names.
The and calls do not pass a pointer to the newly allocated object.
If a client needs to install object pointers in a handle table, it can
obtain them via new object callbacks.
EXAMPLE PROGRAM
EXAMPLE GRAPH FILES
SEE ALSO
Libcdt(3)
BUGS
It is difficult to change endpoints of edges, delete string attributes
or modify edge keys. The work-around is to create a new object and
copy the contents of an old one (but new object obviously has a
different ID, internal address, and object creation timestamp).
The API lacks convenient functions to substitute programmer-defined
ordering of nodes and edges but in principle this can be supported.
AUTHOR
Stephen North, north@research.att.com, AT&T Research.
30 JULY 2007 LIBCGRAPH(3)