comparison toolboxes/graph_visualisation/include/graphviz/cgraph.h @ 0:e9a9cd732c1e tip

first hg version after svn

+/* $Id: cgraph.h,v 1.16 2009/07/10 21:10:32 erg Exp $ $Revision: 1.16 $ */
+/* vim:set shiftwidth=4 ts=8: */
+
+/**********************************************************
+*      This software is part of the graphviz package      *
+*                http://www.graphviz.org/                 *
+*                                                         *
+*            Copyright (c) 1994-2004 AT&T Corp.           *
+*                and is licensed under the                *
+*            Common Public License, Version 1.0           *
+*                      by AT&T Corp.                      *
+*                                                         *
+*        Information and Software Systems Research        *
+*              AT&T Research, Florham Park NJ             *
+**********************************************************/
+
+#ifndef ATT_GRAPH_H
+#define ATT_GRAPH_H
+
+#include		"cdt.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#ifndef FALSE
+#define FALSE (0)
+#endif
+#ifndef TRUE
+#define TRUE (!FALSE)
+#endif
+#ifndef NOT
+#define	NOT(x)			(!(x))
+#endif
+#ifndef NIL
+#define NIL(type)		((type)0)
+#endif
+#define NILgraph		NIL(Agraph_t*)
+#define NILnode			NIL(Agnode_t*)
+#define NILedge			NIL(Agedge_t*)
+#define NILsym			NIL(Agsym_t*)
+
+/* forward struct type declarations */
+typedef struct Agtag_s Agtag_t;
+typedef struct Agobj_s Agobj_t;	/* generic object header */
+typedef struct Agraph_s Agraph_t;	/* graph, subgraph (or hyperedge) */
+typedef struct Agnode_s Agnode_t;	/* node (atom) */
+typedef struct Agedge_s Agedge_t;	/* node pair */
+typedef struct Agdesc_s Agdesc_t;	/* graph descriptor */
+typedef struct Agmemdisc_s Agmemdisc_t;	/* memory allocator */
+typedef struct Agiddisc_s Agiddisc_t;	/* object ID allocator */
+typedef struct Agiodisc_s Agiodisc_t;	/* IO services */
+typedef struct Agdisc_s Agdisc_t;	/* union of client discipline methods */
+typedef struct Agdstate_s Agdstate_t;	/* client state (closures) */
+typedef struct Agsym_s Agsym_t;	/* string attribute descriptors */
+typedef struct Agattr_s Agattr_t;	/* string attribute container */
+typedef struct Agcbdisc_s Agcbdisc_t;	/* client event callbacks */
+typedef struct Agcbstack_s Agcbstack_t;	/* enclosing state for cbdisc */
+typedef struct Agclos_s Agclos_t;	/* common fields for graph/subgs */
+typedef struct Agrec_s Agrec_t;	/* generic runtime record */
+typedef struct Agdatadict_s Agdatadict_t;	/* set of dictionaries per graph */
+typedef struct Agedgepair_s Agedgepair_t;	/* the edge object */
+typedef struct Agsubnode_s Agsubnode_t;
+
+/* Header of a user record.  These records are attached by client programs
+dynamically at runtime.  A unique string ID must be given to each record
+attached to the same object.  Cgraph has functions to create, search for,
+and delete these records.   The records are maintained in a circular list,
+with obj->data pointing somewhere in the list.  The search function has
+an option to lock this pointer on a given record.  The application must
+be written so only one such lock is outstanding at a time. */
+
+struct Agrec_s {
+    char *name;
+    Agrec_t *next;
+    /* following this would be any programmer-defined data */
+};
+
+/* Object tag for graphs, nodes, and edges.  While there may be several structs
+for a given node or edges, there is only one unique ID (per main graph).  */
+struct Agtag_s {
+    unsigned objtype:2;		/* see literal tags below */
+    unsigned mtflock:1;		/* move-to-front lock, see above */
+    unsigned attrwf:1;		/* attrs written (parity, write.c) */
+    unsigned seq:(sizeof(unsigned) * 8 - 4);	/* sequence no. */
+    unsigned long id;		/* client  ID */
+};
+
+	/* object tags */
+#define AGRAPH				0	/* can't exceed 2 bits. see Agtag_t. */
+#define AGNODE				1
+#define AGOUTEDGE			2
+#define AGINEDGE			3	/* (1 << 1) indicates an edge tag.   */
+#define AGEDGE 				AGOUTEDGE	/* synonym in object kind args */
+
+	/* a generic graph/node/edge header */
+struct Agobj_s {
+    Agtag_t tag;
+    Agrec_t *data;
+};
+
+#define AGTAG(obj)		(((Agobj_t*)(obj))->tag)
+#define AGTYPE(obj)		(AGTAG(obj).objtype)
+#define AGID(obj)		(AGTAG(obj).id)
+#define AGSEQ(obj)		(AGTAG(obj).seq)
+#define AGATTRWF(obj)		(AGTAG(obj).attrwf)
+#define AGDATA(obj)		(((Agobj_t*)(obj))->data)
+
+/* This is the node struct allocated per graph (or subgraph).  It resides
+in the n_dict of the graph.  The node set is maintained by libdict, but
+transparently to libgraph callers.  Every node may be given an optional
+string name at its time of creation, or it is permissible to pass NIL(char*)
+for the name. */
+
+struct Agsubnode_s {		/* the node-per-graph-or-subgraph record */
+    Dtlink_t seq_link;		/* must be first */
+    Dtlink_t id_link;
+    Agnode_t *node;		/* the object */
+    Dtlink_t *in_id, *out_id;	/* by node/ID for random access */
+    Dtlink_t *in_seq, *out_seq;	/* by node/sequence for serial access */
+};
+
+struct Agnode_s {
+    Agobj_t base;
+    Agraph_t *root;
+    Agsubnode_t mainsub;	/* embedded for main graph */
+};
+
+struct Agedge_s {
+    Agobj_t base;
+    Dtlink_t id_link;		/* main graph only */
+    Dtlink_t seq_link;
+    Agnode_t *node;		/* the endpoint node */
+};
+
+struct Agedgepair_s {
+    Agedge_t out, in;
+};
+
+struct Agdesc_s {		/* graph descriptor */
+    unsigned directed:1;	/* if edges are asymmetric */
+    unsigned strict:1;		/* if multi-edges forbidden */
+    unsigned no_loop:1;		/* if no loops */
+    unsigned maingraph:1;	/* if this is the top level graph */
+    unsigned flatlock:1;	/* if sets are flattened into lists in cdt */
+    unsigned no_write:1;	/* if a temporary subgraph */
+    unsigned has_attrs:1;	/* if string attr tables should be initialized */
+    unsigned has_cmpnd:1;	/* if may contain collapsed nodes */
+};
+
+/* disciplines for external resources needed by libgraph */
+
+struct Agmemdisc_s {		/* memory allocator */
+    void *(*open) (void);	/* independent of other resources */
+    void *(*alloc) (void *state, size_t req);
+    void *(*resize) (void *state, void *ptr, size_t old, size_t req);
+    void (*free) (void *state, void *ptr);
+    void (*close) (void *state);
+};
+
+struct Agiddisc_s {		/* object ID allocator */
+    void *(*open) (Agraph_t * g);	/* associated with a graph */
+    long (*map) (void *state, int objtype, char *str, unsigned long *id,
+		 int createflag);
+    long (*alloc) (void *state, int objtype, unsigned long id);
+    void (*free) (void *state, int objtype, unsigned long id);
+    char *(*print) (void *state, int objtype, unsigned long id);
+    void (*close) (void *state);
+};
+
+struct Agiodisc_s {
+    int (*afread) (void *chan, char *buf, int bufsize);
+    int (*putstr) (void *chan, const char *str);
+    int (*flush) (void *chan);	/* sync */
+    /* error messages? */
+};
+
+struct Agdisc_s {		/* user's discipline */
+    Agmemdisc_t *mem;
+    Agiddisc_t *id;
+    Agiodisc_t *io;
+};
+
+	/* default resource disciplines */
+#if !defined(_BLD_cgraph) && defined(GVDLL)
+#define extern  __declspec(dllimport)
+#endif
+
+/*visual studio*/
+#ifdef WIN32_DLL
+#ifndef CGRAPH_EXPORTS
+#define extern __declspec(dllimport)
+#endif
+#endif
+/*end visual studio*/
+
+extern Agmemdisc_t AgMemDisc;
+extern Agiddisc_t AgIdDisc;
+extern Agiodisc_t AgIoDisc;
+
+extern Agdisc_t AgDefaultDisc;
+#undef extern
+
+struct Agdstate_s {
+    void *mem;
+    void *id;
+    /* IO must be initialized and finalized outside Cgraph,
+     * and channels (FILES) are passed as void* arguments. */
+};
+
+typedef void (*agobjfn_t) (Agraph_t * g, Agobj_t * obj, void *arg);
+typedef void (*agobjupdfn_t) (Agraph_t * g, Agobj_t * obj, void *arg,
+			      Agsym_t * sym);
+
+struct Agcbdisc_s {
+    struct {
+	agobjfn_t ins;
+	agobjupdfn_t mod;
+	agobjfn_t del;
+    } graph, node, edge;
+};
+
+struct Agcbstack_s {		/* object event callbacks */
+    Agcbdisc_t *f;		/* methods */
+    void *state;		/* closure */
+    Agcbstack_t *prev;		/* kept in a stack, unlike other disciplines */
+};
+
+struct Agclos_s {
+    Agdisc_t disc;		/* resource discipline functions */
+    Agdstate_t state;		/* resource closures */
+    Dict_t *strdict;		/* shared string dict */
+    unsigned long seq[3];	/* local object sequence number counter */
+    Agcbstack_t *cb;		/* user and system callback function stacks */
+    unsigned char callbacks_enabled;	/* issue user callbacks or hold them? */
+    Dict_t *lookup_by_name[3];
+    Dict_t *lookup_by_id[3];
+};
+
+struct Agraph_s {
+    Agobj_t base;
+    Agdesc_t desc;
+    Dtlink_t link;
+    Dict_t *n_seq;		/* the node set in sequence */
+    Dict_t *n_id;		/* the node set indexed by ID */
+    Dict_t *e_seq, *e_id;	/* holders for edge sets */
+    Dict_t *g_dict;		/* subgraphs - descendants */
+    Agraph_t *parent, *root;	/* subgraphs - ancestors */
+    Agclos_t *clos;		/* shared resources */
+};
+
+
+#if _PACKAGE_ast
+/* fine control of object callbacks */
+#   if defined(_BLD_cgraph) && defined(__EXPORT__)
+#	define extern  __EXPORT__
+#   endif
+#   if !defined(_BLD_cgraph) && defined(__IMPORT__)
+#	define extern  __IMPORT__
+#   endif
+#endif
+
+extern void agpushdisc(Agraph_t * g, Agcbdisc_t * disc, void *state);
+extern int agpopdisc(Agraph_t * g, Agcbdisc_t * disc);
+extern int agcallbacks(Agraph_t * g, int flag);	/* return prev value */
+
+/* graphs */
+extern Agraph_t *agopen(char *name, Agdesc_t desc, Agdisc_t * disc);
+extern int agclose(Agraph_t * g);
+extern Agraph_t *agread(void *chan, Agdisc_t * disc);
+extern void agreadline(int);
+extern void agsetfile(char *);
+extern Agraph_t *agconcat(Agraph_t * g, void *chan, Agdisc_t * disc);
+extern int agwrite(Agraph_t * g, void *chan);
+extern int agisdirected(Agraph_t * g);
+extern int agisundirected(Agraph_t * g);
+extern int agisstrict(Agraph_t * g);
+extern int agissimple(Agraph_t * g);
+
+/* nodes */
+extern Agnode_t *agnode(Agraph_t * g, char *name, int createflag);
+extern Agnode_t *agidnode(Agraph_t * g, unsigned long id, int createflag);
+extern Agnode_t *agsubnode(Agraph_t * g, Agnode_t * n, int createflag);
+extern Agnode_t *agfstnode(Agraph_t * g);
+extern Agnode_t *agnxtnode(Agraph_t * g, Agnode_t * n);
+extern Agnode_t *aglstnode(Agraph_t * g);
+extern Agnode_t *agprvnode(Agraph_t * g, Agnode_t * n);
+
+extern Agsubnode_t *agsubrep(Agraph_t * g, Agnode_t * n);
+
+/* edges */
+extern Agedge_t *agedge(Agraph_t * g, Agnode_t * t, Agnode_t * h,
+			char *name, int createflag);
+extern Agedge_t *agidedge(Agraph_t * g, Agnode_t * t, Agnode_t * h,
+			  unsigned long id, int createflag);
+extern Agedge_t *agsubedge(Agraph_t * g, Agedge_t * e, int createflag);
+extern Agedge_t *agfstin(Agraph_t * g, Agnode_t * n);
+extern Agedge_t *agnxtin(Agraph_t * g, Agedge_t * e);
+extern Agedge_t *agfstout(Agraph_t * g, Agnode_t * n);
+extern Agedge_t *agnxtout(Agraph_t * g, Agedge_t * e);
+extern Agedge_t *agfstedge(Agraph_t * g, Agnode_t * n);
+extern Agedge_t *agnxtedge(Agraph_t * g, Agedge_t * e, Agnode_t * n);
+
+/* generic */
+extern Agraph_t *agraphof(void* obj);
+extern Agraph_t *agroot(void* obj);
+extern int agcontains(Agraph_t *, void *);
+extern char *agnameof(void *);
+extern int agrelabel(void *obj, char *name);	/* scary */
+extern int agrelabel_node(Agnode_t * n, char *newname);
+extern int agdelete(Agraph_t * g, void *obj);
+extern long agdelsubg(Agraph_t * g, Agraph_t * sub);	/* could be agclose */
+extern int agdelnode(Agraph_t * g, Agnode_t * arg_n);
+extern int agdeledge(Agraph_t * g, Agedge_t * arg_e);
+extern int agobjkind(void *);
+
+/* strings */
+extern char *agstrdup(Agraph_t *, char *);
+extern char *agstrdup_html(Agraph_t *, char *);
+extern int aghtmlstr(char *);
+extern char *agstrbind(Agraph_t * g, char *);
+extern int agstrfree(Agraph_t *, char *);
+extern char *agstrcanon(char *, char *);
+char *agcanonStr(char *str);  /* manages its own buf */
+
+/* definitions for dynamic string attributes */
+struct Agattr_s {		/* dynamic string attributes */
+    Agrec_t h;			/* common data header */
+    Dict_t *dict;		/* shared dict to interpret attr field */
+    char **str;			/* the attribute string values */
+};
+
+struct Agsym_s {		/* symbol in one of the above dictionaries */
+    Dtlink_t link;
+    char *name;			/* attribute's name */
+    char *defval;		/* its default value for initialization */
+    int id;			/* its index in attr[] */
+    unsigned char kind;		/* referent object type */
+    unsigned char fixed;	/* immutable value */
+};
+
+struct Agdatadict_s {		/* set of dictionaries per graph */
+    Agrec_t h;			/* installed in list of graph recs */
+    struct {
+	Dict_t *n, *e, *g;
+    } dict;
+};
+
+extern Agsym_t *agattr(Agraph_t * g, int kind, char *name, char *value);
+extern Agsym_t *agattrsym(void *obj, char *name);
+extern Agsym_t *agnxtattr(Agraph_t * g, int kind, Agsym_t * attr);
+extern int      agcopyattr(void *oldobj, void *newobj);
+
+extern void *agbindrec(void *obj, char *name, unsigned int size,
+		       int move_to_front);
+extern Agrec_t *aggetrec(void *obj, char *name, int move_to_front);
+extern int agdelrec(void *obj, char *name);
+extern void aginit(Agraph_t * g, int kind, char *rec_name, int rec_size,
+		   int move_to_front);
+extern void agclean(Agraph_t * g, int kind, char *rec_name);
+
+extern char *agget(void *obj, char *name);
+extern char *agxget(void *obj, Agsym_t * sym);
+extern int agset(void *obj, char *name, char *value);
+extern int agxset(void *obj, Agsym_t * sym, char *value);
+extern int agsafeset(void* obj, char* name, char* value, char* def);
+
+/* defintions for subgraphs */
+extern Agraph_t *agsubg(Agraph_t * g, char *name, int cflag);	/* constructor */
+extern Agraph_t *agidsubg(Agraph_t * g, unsigned long id, int cflag);	/* constructor */
+extern Agraph_t *agfstsubg(Agraph_t * g), *agnxtsubg(Agraph_t * subg);
+extern Agraph_t *agparent(Agraph_t * g);
+
+/* set cardinality */
+extern int agnnodes(Agraph_t * g), agnedges(Agraph_t * g);
+extern int agdegree(Agraph_t * g, Agnode_t * n, int in, int out);
+extern int agcountuniqedges(Agraph_t * g, Agnode_t * n, int in, int out);
+
+/* memory */
+extern void *agalloc(Agraph_t * g, size_t size);
+extern void *agrealloc(Agraph_t * g, void *ptr, size_t oldsize,
+		       size_t size);
+extern void agfree(Agraph_t * g, void *ptr);
+extern struct _vmalloc_s *agheap(Agraph_t * g);
+
+/* an engineering compromise is a joy forever */
+extern void aginternalmapclearlocalnames(Agraph_t * g);
+
+#define agnew(g,t)		((t*)agalloc(g,sizeof(t)))
+#define agnnew(g,n,t)	((t*)agalloc(g,(n)*sizeof(t)))
+
+/* error handling */
+typedef enum { AGWARN, AGERR, AGMAX, AGPREV } agerrlevel_t;
+extern agerrlevel_t agerrno;
+extern void agseterr(agerrlevel_t);
+extern char *aglasterr(void);
+extern int agerr(agerrlevel_t level, char *fmt, ...);
+extern void agerrorf(char *fmt, ...);
+extern void agwarningf(char *fmt, ...);
+extern int agerrors(void);
+
+/* data access macros */
+/* this assumes that e[0] is out and e[1] is inedge, see edgepair in edge.c  */
+#define AGIN2OUT(e)		((e)-1)
+#define AGOUT2IN(e)		((e)+1)
+#define AGOPP(e)		((AGTYPE(e)==AGINEDGE)?AGIN2OUT(e):AGOUT2IN(e))
+#define AGMKOUT(e)		(AGTYPE(e) == AGOUTEDGE? (e): AGIN2OUT(e))
+#define AGMKIN(e)		(AGTYPE(e) == AGINEDGE?  (e): AGOUT2IN(e))
+#define AGTAIL(e)		(AGMKIN(e)->node)
+#define AGHEAD(e)		(AGMKOUT(e)->node)
+#define agtail(e)		AGTAIL(e)
+#define aghead(e)		AGHEAD(e)
+#define agopp(e)		AGOPP(e)
+
+#define TAILPORT_ID		"tailport"
+#define HEADPORT_ID		"headport"
+
+#if _PACKAGE_ast
+#   if !defined(_BLD_cgraph) && defined(__IMPORT__)
+#	define extern  __IMPORT__
+#   endif
+#endif
+#if !defined(_BLD_cgraph) && defined(GVDLL)
+#define extern  __declspec(dllimport)
+#endif
+
+extern Agdesc_t Agdirected, Agstrictdirected, Agundirected,
+    Agstrictundirected;
+
+#undef extern
+
+/* fast graphs */
+void agflatten(Agraph_t * g, int flag);
+typedef Agsubnode_t	Agnoderef_t;
+typedef Dtlink_t	Agedgeref_t;
+
+#define AGHEADPOINTER(g)	((Agnoderef_t*)(g->n_seq->data->hh._head))
+#define AGRIGHTPOINTER(rep)  	((Agnoderef_t*)((rep)->seq_link.right?((void*)((rep)->seq_link.right) - offsetof(Agsubnode_t,seq_link)):0))
+#define AGLEFTPOINTER(rep)  	((Agnoderef_t*)((rep)->seq_link.hl._left?((void*)((rep)->seq_link.hl._left) - offsetof(Agsubnode_t,seq_link)):0))
+
+#define FIRSTNREF(g)	(agflatten(g,1), AGHEADPOINTER(g))
+
+#define NEXTNREF(g,rep)  	(AGRIGHTPOINTER(rep) == AGHEADPOINTER(g)?0:AGRIGHTPOINTER(rep))
+
+#define PREVNREF(g,rep)  	(((rep)==AGHEADPOINTER(g))?0:(AGLEFTPOINTER(rep)))
+
+#define LASTNREF(g)		(agflatten(g,1), AGHEADPOINTER(g)?AGLEFTPOINTER(AGHEADPOINTER(g)):0)
+#define NODEOF(rep)		((rep)->node)
+
+#define FIRSTOUTREF(g,sn)	(agflatten(g,1), (sn)->out_seq)
+#define LASTOUTREF(g,sn)	(agflatten(g,1), (Agedgeref_t*)dtlast(sn->out_seq))
+#define FIRSTINREF(g,sn)	(agflatten(g,1), (sn)->in_seq)
+#define NEXTEREF(g,rep)  	((rep)->right)
+#define PREVEREF(g,rep)  	((rep)->hl._left)
+/* this is expedient but a bit slimey because it "knows" that dict entries of both nodes
+and edges are embedded in main graph objects but allocated separately in subgraphs */
+#define AGSNMAIN(sn)        ((sn)==(&((sn)->node->mainsub)))
+#define EDGEOF(sn,rep)		(AGSNMAIN(sn)?((Agedge_t*)((unsigned char*)(rep) - offsetof(Agedge_t,seq_link))) : ((Dthold_t*)(rep))->obj)
+
+#undef extern
+#if _PACKAGE_ast
+_END_EXTERNS_
+#endif
+#ifdef __cplusplus
+}
+#endif
+#endif