Daniel@0: .de P0
Daniel@0: .nf
Daniel@0: \f5
Daniel@0: ..
Daniel@0: .de P1
Daniel@0: \fP
Daniel@0: .fi
Daniel@0: ..
Daniel@0: .de Ss
Daniel@0: .fl
Daniel@0: .ne 2
Daniel@0: .SS "\\$1"
Daniel@0: ..
Daniel@0: .TH LIBCGRAPH 3 "30 JULY 2007"
Daniel@0: .SH "NAME"
Daniel@0: \fBlibcgraph\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: .P0
Daniel@0: #include <graphviz/cgraph.h>
Daniel@0: .P1
Daniel@0: .SS "TYPES"
Daniel@0: .P0
Daniel@0: Agraph_t;
Daniel@0: Agnode_t;
Daniel@0: Agedge_t;
Daniel@0: Agdesc_t;
Daniel@0: Agdisc_t;
Daniel@0: Agsym_t;
Daniel@0: .P1
Daniel@0: .SS "GRAPHS"
Daniel@0: .P0
Daniel@0: Agraph_t        *agopen(char *name, Agdesc_t kind, Agdisc_t *disc);
Daniel@0: int             agclose(Agraph_t *g);
Daniel@0: Agraph_t        *agread(void *channel, Agdisc_t *);
Daniel@0: void			agreadline(int line_no);
Daniel@0: void			agsetfile(char *file_name);
Daniel@0: Agraph_t		*agconcat(Agraph_t *g, void *channel, Agdisc_t *disc)
Daniel@0: int             agwrite(Agraph_t *g, void *channel);
Daniel@0: int				agnnodes(Agraph_t *g),agnedges(Agraph_t *g);
Daniel@0: int				agisdirected(Agraph_t * g),agisundirected(Agraph_t * g),agisstrict(Agraph_t * g), agissimple(Agraph_t * g); 
Daniel@0: .SS "SUBGRAPHS"
Daniel@0: .P0
Daniel@0: Agraph_t        *agsubg(Agraph_t *g, char *name, int createflag);
Daniel@0: Agraph_t		*agidsubg(Agraph_t * g, unsigned long id, int cflag);
Daniel@0: Agraph_t        *agfstsubg(Agraph_t *g), agnxtsubg(Agraph_t *);
Daniel@0: Agraph_t        *agparent(Agraph_t *g);
Daniel@0: int				agdelsubg(Agraph_t * g, Agraph_t * sub);	/* same as agclose() */
Daniel@0: .P1
Daniel@0: .SS "NODES"
Daniel@0: .P0
Daniel@0: Agnode_t        *agnode(Agraph_t *g, char *name, int createflag);
Daniel@0: Agnode_t        *agidnode(Agraph_t *g, ulong id, int createflag);
Daniel@0: Agnode_t        *agsubnode(Agraph_t *g, Agnode_t *n, int createflag);
Daniel@0: Agnode_t        *agfstnode(Agraph_t *g);
Daniel@0: Agnode_t        *agnxtnode(Agraph_t *g, Agnode_t *n);
Daniel@0: Agnode_t        *agprvnode(Agraph_t *g, Agnode_t *n);
Daniel@0: Agnode_t        *aglstnode(Agraph_t *g);
Daniel@0: int             agdelnode(Agraph_t *g, Agnode_t *n);
Daniel@0: int				agdegree(Agnode_t *n, int use_inedges, int use_outedges);
Daniel@0: .P1
Daniel@0: .SS "EDGES"
Daniel@0: .P0
Daniel@0: Agedge_t        *agedge(Agraph_t* g, Agnode_t *t, Agnode_t *h, char *name, int createflag);
Daniel@0: Agedge_t		*agidedge(Agraph_t * g, Agnode_t * t, Agnode_t * h, unsigned long id, int createflag);
Daniel@0: Agedge_t        *agsubedge(Agraph_t *g, Agedge_t *e, int createflag);
Daniel@0: Agnode_t        *aghead(Agedge_t *e), *agtail(Agedge_t *e);
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: int             agdeledge(Agraph_t *g, Agedge_t *e);
Daniel@0: .SS "STRING ATTRIBUTES"
Daniel@0: .P0
Daniel@0: Agsym_t			*agattr(Agraph_t *g, int kind, char *name, char *value);
Daniel@0: Agsym_t			*agattrsym(void *obj, char *name);
Daniel@0: Agsym_t			*agnxtattr(Agraph_t *g, int kind, Agsym_t *attr);
Daniel@0: char			*agget(void *obj, char *name);
Daniel@0: char			*agxget(void *obj, Agsym_t *sym);
Daniel@0: int				agset(void *obj, char *name, char *value);
Daniel@0: int				agxset(void *obj, Agsym_t *sym, char *value);
Daniel@0: int				agsafeset(void *obj, char *name, char *value, char *def);
Daniel@0: .P1
Daniel@0: .SS "RECORDS"
Daniel@0: .P0
Daniel@0: void		*agbindrec(void *obj, char *name, unsigned int size, move_to_front);
Daniel@0: Agrec_t     *aggetrec(void *obj, char *name, int move_to_front);
Daniel@0: int         agdelrec(Agraph_t *g, void *obj, char *name);
Daniel@0: int			agcopyattr(void *, void *);
Daniel@0: void		aginit(Agraph_t * g, int kind, char *rec_name, int rec_size, int move_to_front);
Daniel@0: void		agclean(Agraph_t * g, int kind, char *rec_name);
Daniel@0: .P1
Daniel@0: .SS "CALLBACKS"
Daniel@0: .P0
Daniel@0: Agcbdisc_t    *agpopdisc(Agraph_t *g);
Daniel@0: void        agpushdisc(Agraph_t *g, Agcbdisc_t *disc);
Daniel@0: void        agmethod(Agraph_t *g, void *obj, Agcbdisc_t *disc, int initflag);
Daniel@0: .P1
Daniel@0: .SS "MEMORY"
Daniel@0: .P0
Daniel@0: void		*agalloc(Agraph_t *g, size_t request);
Daniel@0: void		*agrealloc(Agraph_t *g, void *ptr, size_t oldsize, size_t newsize);
Daniel@0: void		agfree(Agraph_t *g, void *ptr);
Daniel@0: .P1
Daniel@0: .SS "STRINGS"
Daniel@0: .P0
Daniel@0: char		*agstrdup(Agraph_t *, char *);
Daniel@0: char		*agstrdup_html(Agraph_t *, char *);
Daniel@0: int		aghtmlstr(char *);
Daniel@0: char		*agstrbind(Agraph_t * g, char *);
Daniel@0: int		strfree(Agraph_t *, char *);
Daniel@0: char		*agcanonStr(char *);
Daniel@0: char		*agstrcanon(char *, char *);
Daniel@0: .P1
Daniel@0: .SS "GENERIC OBJECTS"
Daniel@0: .P0
Daniel@0: Agraph_t	*agraphof(void*);
Daniel@0: Agraph_t	*agroot(void*);
Daniel@0: int			agcontains(Agraph_t*, void*);
Daniel@0: char		*agnameof(void*);
Daniel@0: void		agdelete(Agraph_t *g, void *obj);
Daniel@0: int 		agobjkind(void *obj);
Daniel@0: Agrec_t		*AGDATA(void *obj);
Daniel@0: ulong		AGID(void *obj);
Daniel@0: int			AGTYPE(void *obj);
Daniel@0: .P1
Daniel@0: .SH "DESCRIPTION"
Daniel@0: Libcgraph supports graph programming by maintaining graphs in memory
Daniel@0: and reading and writing graph files.
Daniel@0: Graphs are composed of nodes, edges, and nested subgraphs.
Daniel@0: These graph objects may be attributed with string name-value pairs
Daniel@0: and programmer-defined records (see Attributes).
Daniel@0: .PP
Daniel@0: All of Libcgraph's global symbols have the prefix \fBag\fR (case varying).
Daniel@0: .SH "GRAPH AND SUBGRAPHS"
Daniel@0: .PP
Daniel@0: A ``main'' or ``root'' graph defines a namespace for a collection of
Daniel@0: graph objects (subgraphs, nodes, edges) and their attributes.
Daniel@0: Objects may be named by unique strings or by 32-bit IDs.
Daniel@0: .PP
Daniel@0: \fBagopen\fP creates a new graph with the given name and kind.
Daniel@0: (Graph kinds are \fBAgdirected\fP, \fBAgundirected\fP,
Daniel@0: \fBAgstrictdirected\fP, and \fBAgstrictundirected\fP.
Daniel@0: A strict graph cannot have multi-edges or self-arcs.)
Daniel@0: \fBagclose\fP deletes a graph, freeing its associated storage.
Daniel@0: \fBagread\fP, \fBagwrite\fP, and \fBagconcat\fP perform file I/O 
Daniel@0: using the graph file language described below. \fBagread\fP
Daniel@0: constructs a new graph while \fBagconcat\fP merges the file
Daniel@0: contents with a pre-existing graph.  Though I/O methods may
Daniel@0: be overridden, the default is that the channel argument is
Daniel@0: a stdio FILE pointer. \fBagsetfile\fP and \fBagreadline\fP
Daniel@0: are helper functions that simply set the current file name
Daniel@0: and input line number for subsequent error reporting.
Daniel@0: .PP
Daniel@0: \fBagsubg\fP finds or creates
Daniel@0: a subgraph by name.  A new subgraph is is initially empty and
Daniel@0: is of the same kind as its parent.  Nested subgraph trees may be created. 
Daniel@0: A subgraph's name is only interpreted relative to its parent.
Daniel@0: A program can scan subgraphs under a given graph
Daniel@0: using \fBagfstsubg\fP and \fRagnxtsubg\fP.  A subgraph is
Daniel@0: deleted with \fBagdelsubg\fP (or \fBagclose\fP).
Daniel@0: .PP
Daniel@0: By default, nodes are stored in ordered sets for efficient random
Daniel@0: access to insert, find, and delete nodes.
Daniel@0: The edges of a node are also stored in ordered sets.
Daniel@0: The sets are maintained internally as splay tree dictionaries
Daniel@0: using Phong Vo's cdt library.
Daniel@0: .PP
Daniel@0: \fBagnnodes\fP, \fBagnedges\fP, and \fBagdegree\fP return the
Daniel@0: sizes of node and edge sets of a graph.  The \fBagdegree\fP returns
Daniel@0: the size of the edge set of a nodes, and takes flags
Daniel@0: to select in-edges, out-edges, or both.
Daniel@0: .PP
Daniel@0: An \fBAgdisc_t\fP defines callbacks to be invoked by libcgraph when
Daniel@0: initializing, modifying, or finalizing graph objects.  (Casual users can ignore 
Daniel@0: the following.) Disciplines are kept on a stack.  Libcgraph automatically
Daniel@0: calls the methods on the stack, top-down.  Callbacks are installed
Daniel@0: with \fBagpushdisc\fP, uninstalled with \fBagpopdisc\fP, and 
Daniel@0: can be held pending or released via \fBagcallbacks\fP.
Daniel@0: .PP
Daniel@0: (Casual users may ignore the following.
Daniel@0: When Libcgraph is compiled with Vmalloc (which is not the default),
Daniel@0: each graph has its own heap.
Daniel@0: Programmers may allocate application-dependent data within the
Daniel@0: same heap as the rest of the graph.  The advantage is that
Daniel@0: a graph can be deleted by atomically freeing its entire heap
Daniel@0: without scanning each individual node and edge.
Daniel@0: .SH "NODES"
Daniel@0: A node is created by giving a unique string name or
Daniel@0: programmer defined 32-bit ID, and is represented by a
Daniel@0: unique internal object. (Node equality can checked
Daniel@0: by pointer comparison.)
Daniel@0: .PP
Daniel@0: \fBagnode\fP searches in a graph or subgraph for a node
Daniel@0: with the given name, and returns it if found.
Daniel@0: If not found, if \fBcreateflag\fP is boolean true
Daniel@0: a new node is created and returned, otherwise a nil
Daniel@0: pointer is returned.
Daniel@0: \fBagidnode\fP allows a programmer to specify the node
Daniel@0: by a unique 32-bit ID.
Daniel@0: \fBagsubnode\fP performs a similar operation on
Daniel@0: an existing node and a subgraph.
Daniel@0: .Pp
Daniel@0: \fBagfstnode\fP and \fBagnxtnode\fP scan node lists.
Daniel@0: \fBagprvnode\fP and \fPaglstnode\fP are symmetric but scan backward.
Daniel@0: The default sequence is order of creation (object timestamp.)
Daniel@0: \fBagdelnode\fP removes a node from a graph or subgraph.
Daniel@0: .SH "EDGES"
Daniel@0: .PP
Daniel@0: An abstract edge has two endpoint nodes called tail and head
Daniel@0: where the all outedges of the same node have it as the tail
Daniel@0: value and similarly all inedges have it as the head.
Daniel@0: In an undirected graph, head and tail are interchangable.
Daniel@0: If a graph has multi-edges between the same pair of nodes,
Daniel@0: the edge's string name behaves as a secondary key.
Daniel@0: .Pp
Daniel@0: \fBagedge\fP searches in a graph of subgraph for an
Daniel@0: edge between the given endpoints (with an optional
Daniel@0: multi-edge selector name) and returns it if found.
Daniel@0: Otherwise, if \fBcreateflag\fP is boolean true,
Daniel@0: a new edge is created and returned: otherwise
Daniel@0: a nil pointer is returned.  If the \fBname\fP 
Daniel@0: is NULL, then an anonymous internal
Daniel@0: value is generated. \fBagidedge\fP allows a programmer
Daniel@0: to create an edge by giving its unique 32-bit ID.
Daniel@0: \fBagfstin\fP, \fBagnxtint\fP, \fBagfstout\fP, and 
Daniel@0: \fBagnxtout\fP visit directed in- and out- edge lists,
Daniel@0: and ordinarily apply only in directed graphs.
Daniel@0: \fBagfstedge\fP and \fBagnxtedge\fP visit all edges
Daniel@0: incident to a node.  \fBagtail\fP and \fBaghead\fP
Daniel@0: get the endpoint of an edge.
Daniel@0: .SH "INTERNAL ATTRIBUTES"
Daniel@0: Programmer-defined values may be dynamically
Daniel@0: attached to graphs, subgraphs, nodes, and edges.
Daniel@0: Such values are either uninterpreted binary records
Daniel@0: (for implementing efficient algorithms)
Daniel@0: or character string data (for I/O).
Daniel@0: .SH "STRING ATTRIBUTES"
Daniel@0: String attributes are handled automatically in reading
Daniel@0: and writing graph files. 
Daniel@0: A string attribute is identified by name and by
Daniel@0: an internal symbol table entry (\fBAgsym_t\fP) created by Libcgraph.
Daniel@0: Attributes of nodes, edges, and graphs (with their subgraphs)
Daniel@0: have separate namespaces.  The contents of an \fBAgsym_t\fP
Daniel@0: is listed below, followed by primitives to operate on string
Daniel@0: attributes.
Daniel@0: .P0
Daniel@0: typedef struct Agsym_s {        /* symbol in one of the above dictionaries */
Daniel@0:     Dtlink_t        link;
Daniel@0:     char            *name;      /* attribute's name */
Daniel@0:     char            *defval;    /* its default value for initialization */
Daniel@0:     int             id;         /* its index in attr[] */
Daniel@0:     unsigned char	kind;		/* referent object type */
Daniel@0:     unsigned char	fixed;		/* immutable value */
Daniel@0: } Agsym_t;
Daniel@0: .P1
Daniel@0: .PP
Daniel@0: \fBagattr\fP creates or looks up attributes.
Daniel@0: \fBkind\fP may be \fBAGRAPH\fP, \fBAGNODE\fP, or \fBAGEDGE\fP.
Daniel@0: If \fBvalue\fP is \fB(char*)0)\fP, the request is to search
Daniel@0: for an existing attribute of the given kind and name.
Daniel@0: Otherwise, if the attribute already exists, its default
Daniel@0: for creating new objects is set to the given value;
Daniel@0: if it does not exist, a new attribute is created with the
Daniel@0: given default, and the default is applied to all pre-existing
Daniel@0: objects of the given kind. If \fBg\fP is NIL, the default is
Daniel@0: set for all graphs created subsequently.
Daniel@0: \fBagattrsym\fP is a helper function
Daniel@0: that looks up an attribute for a graph object given as an argument.
Daniel@0: \fBagnxtattr\fP permits traversing the list of attributes of
Daniel@0: a given type.  If \fBNIL\fP is passed as an argument it gets
Daniel@0: the first attribute, otherwise it returns the next one in
Daniel@0: succession or returns \fBNIL\fP at the end of the list.
Daniel@0: \fBagget\fP and \fPagset\fP allow fetching and updating a
Daniel@0: string attribute for an object taking the attribute name as
Daniel@0: an argument. \fBagxget\fP and \fBagxset\fP do this but with
Daniel@0: an attribute symbol table entry as an argument (to avoid
Daniel@0: the cost of the string lookup).  \fBagsafeset\fP is a
Daniel@0: convenience function that ensures the given attribute is
Daniel@0: declared before setting it locally on an object.
Daniel@0: 
Daniel@0: .SH "STRINGS"
Daniel@0: Libcgraph performs its own storage management of strings as 
Daniel@0: reference-counted strings.
Daniel@0: The caller does not need to dynamically allocate storage.
Daniel@0: .PP
Daniel@0: \fBagstrdup\fP returns a pointer to a reference-counted copy of
Daniel@0: the argument string, creating one if necessary. \fBagstrbind\fP
Daniel@0: returns a pointer to a reference-counted string if it exists, or NULL if not.
Daniel@0: All uses of cgraph strings need to be freed using \fBagstrfree\fP
Daniel@0: in order to correctly maintain the reference count.
Daniel@0: .PP
Daniel@0: \fBagcanonStr\fP returns a pointer to a version of the input string
Daniel@0: canonicalized for output for later re-parsing. This includes quoting
Daniel@0: special characters and keywords. It uses its own internal buffer, so
Daniel@0: the value will be lost on the next call to \fBagcanonStr\fP.
Daniel@0: \fBagstrcanon\fP is an unsafe version of \fBagcanonStr\fP, in which
Daniel@0: the application passes in a buffer as the second argument. Note that
Daniel@0: the buffer may not be used; if the input string is in canonical form,
Daniel@0: the function will just return a pointer to it.
Daniel@0: .PP
Daniel@0: The cgraph parser handles HTML-like strings. These should be 
Daniel@0: indistinguishable from other strings for most purposes. To create
Daniel@0: an HTML-like string, use \fBagstrdup_html\fP. The \fBaghtmlstr\fP
Daniel@0: function can be used to query if a string is an ordinary string or
Daniel@0: an HTML-like string.
Daniel@0: .SH "RECORDS"
Daniel@0: Uninterpreted records may be attached to graphs, subgraphs, nodes,
Daniel@0: and edges for efficient operations on values such as marks, weights,
Daniel@0: counts, and pointers needed by algorithms.  Application programmers
Daniel@0: define the fields of these records, but they must be declared with
Daniel@0: a common header as shown below.
Daniel@0: .P0
Daniel@0: typedef struct Agrec_s {
Daniel@0:     Agrec_t		header;
Daniel@0:     /* programmer-defined fields follow */
Daniel@0: } Agrec_t;
Daniel@0: .P1
Daniel@0: Records are created and managed by Libcgraph. A programmer must
Daniel@0: explicitly attach them to the objects in a graph, either to
Daniel@0: individual objects one at a time via \fBagbindrec\fP, or to
Daniel@0: all the objects of the same class in a graph via \fBaginit\fP.
Daniel@0: The \fBname\fP argument a record distinguishes various types of records,
Daniel@0: and is programmer defined (Libcgraph reserves the prefix \fB_ag\fR).
Daniel@0: If size is 0, the call to \fBagbindrec\fP is simply a lookup.
Daniel@0: \fBagdelrec\fP is the deletes records one at a time.
Daniel@0: \fBagclean\fP does the same for all objects of the same
Daniel@0: class in an entire graph. 
Daniel@0: 
Daniel@0: Internally, records are maintained in circular linked lists
Daniel@0: attached to graph objects.
Daniel@0: To allow referencing application-dependent data without function
Daniel@0: calls or search, Libcgraph allows setting and locking the list
Daniel@0: pointer of a graph, node, or edge on a particular record.
Daniel@0: This pointer can be obtained with the macro \fBAGDATA(obj)\fP.
Daniel@0: A cast, generally within a macro or inline function,
Daniel@0: is usually applied to convert the list pointer to
Daniel@0: an appropriate programmer-defined type.
Daniel@0: 
Daniel@0: To control the setting of this pointer,
Daniel@0: the \fBmove_to_front\fP flag may be \fBAG_MTF_FALSE\fP,
Daniel@0: \fBAG_MTF_SOFT\fP, or \fBAG_MTF_HARD\fP accordingly.
Daniel@0: The \fBAG_MTF_SOFT\fP field is only a hint that decreases
Daniel@0: overhead in subsequent calls of \fBaggetrec\fP;
Daniel@0: \fBAG_MTF_HARD\fP guarantees that a lock was obtained.
Daniel@0: To release locks, use \fBAG_MTF_SOFT\fP or \fBAG_MTF_FALSE\fP.
Daniel@0: Use of this feature implies cooperation or at least isolation
Daniel@0: from other functions also using the move-to-front convention.
Daniel@0: 
Daniel@0: .SH "DISCIPLINES"
Daniel@0: (The following is not intended for casual users.)
Daniel@0: Programmer-defined disciplines customize certain resources-
Daniel@0: ID namespace, memory, and I/O - needed by Libcgraph.
Daniel@0: A discipline struct (or NIL) is passed at graph creation time.
Daniel@0: .P0
Daniel@0: struct Agdisc_s {			/* user's discipline */
Daniel@0: 	Agmemdisc_t			*mem;
Daniel@0: 	Agiddisc_t			*id;
Daniel@0: 	Agiodisc_t			*io;
Daniel@0: } ;
Daniel@0: .P1
Daniel@0: A default discipline is supplied when NIL is given for
Daniel@0: any of these fields.
Daniel@0: 
Daniel@0: An ID allocator discipline allows a client to control assignment
Daniel@0: of IDs (uninterpreted 32-bit values) to objects, and possibly how
Daniel@0: they are mapped to and from strings.
Daniel@0: 
Daniel@0: .P0
Daniel@0: struct Agiddisc_s {		/* object ID allocator */
Daniel@0: 	void	*(*open)(Agraph_t *g);	/* associated with a graph */
Daniel@0: 	int		(*map)(void *state, int objtype, char *str, ulong *id, int createflag);
Daniel@0: 	int		(*alloc)(void *state, int objtype, ulong id);
Daniel@0: 	void	(*free)(void *state, int objtype, ulong id);
Daniel@0: 	char	*(*print)(void *state, int objtype, ulong id);
Daniel@0: 	void	(*close)(void *state);
Daniel@0: } ;
Daniel@0: .P1
Daniel@0: 
Daniel@0: \f5open\fP permits the ID discipline to initialize any data
Daniel@0: structures that maintains per individual graph.
Daniel@0: Its return value is then passed as the first argument to
Daniel@0: all subsequent ID manager calls.
Daniel@0: 
Daniel@0: \f5alloc\fP informs the ID manager that Libcgraph is attempting
Daniel@0: to create an object with a specific ID that was given by a client.
Daniel@0: The ID manager should return TRUE (nonzero) if the ID can be
Daniel@0: allocated, or FALSE (which aborts the operation).
Daniel@0: 
Daniel@0: \f5free\fP is called to inform the ID manager that the
Daniel@0: object labeled with the given ID is about to go out of existence.
Daniel@0: 
Daniel@0: \f5map\fP is called to create or look-up IDs by string name
Daniel@0: (if supported by the ID manager).  Returning TRUE (nonzero)
Daniel@0: in all cases means that the request succeeded (with a valid
Daniel@0: ID stored through \f5result\fP.  There are four cases:
Daniel@0: .PP
Daniel@0: \f5name != NULL\fP and \f5createflag == 1\fP:
Daniel@0: This requests mapping a string (e.g. a name in a graph file) into a new ID.
Daniel@0: If the ID manager can comply, then it stores the result and returns TRUE.
Daniel@0: It is then also responsible for being able to \f5print\fP the ID again
Daniel@0: as a string.  Otherwise the ID manager may return FALSE but it must
Daniel@0: implement the following (at least for graph file reading and writing to work):
Daniel@0: .PP
Daniel@0: \f5name == NULL\fP and \f5createflag == 1\fP:
Daniel@0: The ID manager creates a unique new ID of its own choosing. 
Daniel@0: Although it may return FALSE if it does not support anonymous objects,
Daniel@0: but this is strongly discouraged (to support "local names" in graph files.)
Daniel@0: .PP
Daniel@0: \f5name != NULL\fP and \f5createflag == 0\fP:
Daniel@0: This is a namespace probe.  If the name was previously mapped into
Daniel@0: an allocated ID by the ID manager, then the manager must return this ID.
Daniel@0: Otherwise, the ID manager may either return FALSE, or may store
Daniel@0: any unallocated ID into result. (This is convenient, for example,
Daniel@0: if names are known to be digit strings that are directly converted into 32 bit values.)
Daniel@0: .PP
Daniel@0: \f5name == NULL\fP and \f5createflag == 0\fP: forbidden.
Daniel@0: .PP
Daniel@0: \f5print\fP is allowed to return a pointer to a static buffer;
Daniel@0: a caller must copy its value if needed past subsequent calls.
Daniel@0: \f5NULL\fP should be returned by ID managers that do not map names.
Daniel@0: .PP
Daniel@0: The \f5map\fP and \f5alloc\fP calls do not pass a pointer to the
Daniel@0: newly allocated object.  If a client needs to install object
Daniel@0: pointers in a handle table, it can obtain them via 
Daniel@0: new object callbacks.
Daniel@0: .P0
Daniel@0: struct Agiodisc_s {
Daniel@0: 	int		(*fread)(void *chan, char *buf, int bufsize);
Daniel@0: 	int		(*putstr)(void *chan, char *str);
Daniel@0: 	int		(*flush)(void *chan);	/* sync */
Daniel@0: 	/* error messages? */
Daniel@0: } ;
Daniel@0: 
Daniel@0: struct Agmemdisc_s {	/* memory allocator */
Daniel@0: 	void	*(*open)(void);		/* independent of other resources */
Daniel@0: 	void	*(*alloc)(void *state, size_t req);
Daniel@0: 	void	*(*resize)(void *state, void *ptr, size_t old, size_t req);
Daniel@0: 	void	(*free)(void *state, void *ptr);
Daniel@0: 	void	(*close)(void *state);
Daniel@0: } ;
Daniel@0: .P1
Daniel@0: 
Daniel@0: .SH "EXAMPLE PROGRAM"
Daniel@0: .P0
Daniel@0: #include <graphviz/cgraph.h>
Daniel@0: typedef struct mydata_s {Agrec_t hdr; int x,y,z;} mydata;
Daniel@0: 
Daniel@0: main(int argc, char **argv)
Daniel@0: {
Daniel@0:     Agraph_t    *g;
Daniel@0:     Agnode_t    *v;
Daniel@0:     Agedge_t    *e;
Daniel@0:     Agsym_t     *attr;
Daniel@0:     Dict_t      *d
Daniel@0:     int         cnt;
Daniel@0:     mydata      *p;
Daniel@0: 
Daniel@0:     if (g = agread(stdin,NIL(Agdisc_t*))) {
Daniel@0: 		cnt = 0; attr = 0;
Daniel@0: 		while (attr = agnxtattr(g, AGNODE, attr)) cnt++;
Daniel@0: 		printf("The graph %s has %d attributes\n",agnameof(g),cnt);
Daniel@0: 
Daniel@0: 		/* make the graph have a node color attribute, default is blue */
Daniel@0:         attr = agattr(g,AGNODE,"color","blue");
Daniel@0: 
Daniel@0:         /* create a new graph of the same kind as g */
Daniel@0:         h = agopen("tmp",g->desc);
Daniel@0: 
Daniel@0:         /* this is a way of counting all the edges of the graph */
Daniel@0:         cnt = 0;
Daniel@0:         for (v = agfstnode(g); v; v = agnxtnode(g,v))
Daniel@0:             for (e = agfstout(g,v); e; e = agnxtout(g,e))
Daniel@0:                 cnt++;
Daniel@0: 
Daniel@0:         /* attach records to edges */
Daniel@0:         for (v = agfstnode(g); v; v = agnxtnode(g,v))
Daniel@0:             for (e = agfstout(g,v); e; e; = agnxtout(g,e)) {
Daniel@0:                 p = (mydata*) agbindrec(g,e,"mydata",sizeof(mydata),TRUE);
Daniel@0:                 p->x = 27;  /* meaningless data access example */
Daniel@0: 				((mydata*)(AGDATA(e)))->y = 999; /* another example */
Daniel@0:         }
Daniel@0:     }
Daniel@0: }
Daniel@0: .P1
Daniel@0: .SH "EXAMPLE GRAPH FILES"
Daniel@0: .P0
Daniel@0: digraph G {
Daniel@0:     a -> b;
Daniel@0:     c [shape=box];
Daniel@0:     a -> c [weight=29,label="some text];
Daniel@0:     subgraph anything {
Daniel@0:         /* the following affects only x,y,z */
Daniel@0:         node [shape=circle];
Daniel@0:         a; x; y -> z; y -> z;  /* multiple edges */
Daniel@0:     }
Daniel@0: }
Daniel@0: 
Daniel@0: strict graph H {
Daniel@0:     n0 -- n1 -- n2 -- n0;  /* a cycle */
Daniel@0:     n0 -- {a b c d};       /* a star */
Daniel@0:     n0 -- n3;
Daniel@0:     n0 -- n3 [weight=1];   /* same edge because graph is strict */
Daniel@0: }
Daniel@0: .P1
Daniel@0: .SH "SEE ALSO"
Daniel@0: Libcdt(3)
Daniel@0: 
Daniel@0: .SH "BUGS"
Daniel@0: It is difficult to change endpoints of edges, delete string attributes or
Daniel@0: modify edge keys.  The work-around is to create a new object and copy the
Daniel@0: contents of an old one (but new object obviously has a different ID,
Daniel@0: internal address, and object creation timestamp).
Daniel@0: 
Daniel@0: The API lacks convenient functions to substitute programmer-defined ordering of
Daniel@0: nodes and edges but in principle this can be supported.
Daniel@0: .SH "AUTHOR"
Daniel@0: Stephen North, north@research.att.com, AT&T Research.