cgraph.h

Go to the documentation of this file.

 
/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/
 
#pragma once
 
#include "cdt.h"
#include <inttypes.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
 
#ifdef __cplusplus
extern "C" {
#endif
 
 
#ifdef GVDLL
#ifdef EXPORT_CGRAPH
#define CGRAPH_API __declspec(dllexport)
#else
#define CGRAPH_API __declspec(dllimport)
#endif
#endif
 
#ifndef CGRAPH_API
#define CGRAPH_API /* nothing */
#endif
 
 
/* forward struct type declarations */
typedef uint64_t IDTYPE; 
typedef struct Agtag_s Agtag_t;
typedef struct Agobj_s Agobj_t; 
typedef struct Agraph_s Agraph_t;     
typedef struct Agdesc_s Agdesc_t;     
typedef struct Agdstate_s Agdstate_t; 
typedef struct Agclos_s Agclos_t;     
typedef struct Agnode_s Agnode_t; 
typedef struct Agsubnode_s Agsubnode_t;
typedef struct Agedge_s Agedge_t;         
typedef struct Agedgepair_s Agedgepair_t; 
typedef struct Agiddisc_s Agiddisc_t; 
typedef struct Agiodisc_s Agiodisc_t; 
typedef struct Agdisc_s Agdisc_t;     
typedef struct Agcbdisc_s Agcbdisc_t;   
typedef struct Agcbstack_s Agcbstack_t; 
 
typedef struct Agsym_s Agsym_t;           
typedef struct Agattr_s Agattr_t;         
typedef struct Agdatadict_s Agdatadict_t; 
typedef struct Agrec_s Agrec_t;
 
struct Agrec_s {
  char *name;
  Agrec_t *next; 
                 /* following this would be any programmer-defined data */
};
 
struct Agtag_s {
  unsigned objtype : 2; /* see enum below */
  unsigned mtflock : 1; 
  unsigned attrwf : 1;  /* attrs written (parity, write.c) */
  unsigned seq : (sizeof(unsigned) * 8 - 4); /* sequence no. */
  IDTYPE id;                                 /* client  ID */
};
 
enum { AGRAPH, AGNODE, AGEDGE, AGOUTEDGE = AGEDGE, AGINEDGE };
 
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)
 
 
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 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 */
};
 
struct Agiddisc_s {
  void *(*open)(Agraph_t *g, Agdisc_t *); /* associated with a graph */
  long (*map)(void *state, int objtype, char *str, IDTYPE *id, int createflag);
  long (*alloc)(void *state, int objtype, IDTYPE id);
  void (*free)(void *state, int objtype, IDTYPE id);
  char *(*print)(void *state, int objtype, IDTYPE id);
  void (*close)(void *state);
  void (*idregister)(void *state, int objtype, void *obj);
};
 
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 {
  Agiddisc_t *id;
  Agiodisc_t *io;
};
 
/* default resource disciplines */
 
CGRAPH_API extern Agiddisc_t AgIdDisc;
CGRAPH_API extern Agiodisc_t AgIoDisc;
 
CGRAPH_API extern Agdisc_t AgDefaultDisc;
 
struct Agdstate_s {
  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 {
  Agcbdisc_t *f;     /* methods */
  void *state;       /* closure */
  Agcbstack_t *prev; /* kept in a stack, unlike other disciplines */
};
 
CGRAPH_API void agpushdisc(Agraph_t *g, Agcbdisc_t *disc, void *state);
CGRAPH_API int agpopdisc(Agraph_t *g, Agcbdisc_t *disc);
 
 
struct Agclos_s {
  Agdisc_t disc;    /* resource discipline functions */
  Agdstate_t state; /* resource closures */
  Dict_t *strdict;  /* shared string dict */
  uint64_t seq[3];  /* local object sequence number counter */
  Agcbstack_t *cb;  /* user and system callback function stacks */
  Dict_t *lookup_by_name[3];
  Dict_t *lookup_by_id[3];
};
 
struct graphviz_node_set;
 
struct Agraph_s {
  Agobj_t base;
  Agdesc_t desc;
  Dtlink_t seq_link;
  Dtlink_t id_link;
  Dict_t *n_seq;                  
  struct graphviz_node_set *n_id; 
  Dict_t *e_seq, *e_id;           
  Dict_t *g_seq, *g_id;           
  Agraph_t *parent, *root;        
  Agclos_t *clos;                 
};
 
/* graphs */
CGRAPH_API Agraph_t *agopen(char *name, Agdesc_t desc, Agdisc_t *disc);
CGRAPH_API int agclose(Agraph_t *g);
CGRAPH_API Agraph_t *agread(void *chan, Agdisc_t *disc);
 
CGRAPH_API Agraph_t *agmemread(const char *cp);
 
CGRAPH_API Agraph_t *agmemconcat(Agraph_t *g, const char *cp);
CGRAPH_API void agreadline(int);
 
CGRAPH_API void agsetfile(const char *);
 
CGRAPH_API Agraph_t *agconcat(Agraph_t *g, void *chan, Agdisc_t *disc);
CGRAPH_API int agwrite(Agraph_t *g, void *chan);
CGRAPH_API int agisdirected(Agraph_t *g);
CGRAPH_API int agisundirected(Agraph_t *g);
CGRAPH_API int agisstrict(Agraph_t *g);
CGRAPH_API int agissimple(Agraph_t *g);
 
CGRAPH_API Agnode_t *agnode(Agraph_t *g, char *name, int createflag);
CGRAPH_API Agnode_t *agidnode(Agraph_t *g, IDTYPE id, int createflag);
CGRAPH_API Agnode_t *agsubnode(Agraph_t *g, Agnode_t *n, int createflag);
CGRAPH_API Agnode_t *agfstnode(Agraph_t *g);
CGRAPH_API Agnode_t *agnxtnode(Agraph_t *g, Agnode_t *n);
CGRAPH_API Agnode_t *aglstnode(Agraph_t *g);
CGRAPH_API Agnode_t *agprvnode(Agraph_t *g, Agnode_t *n);
 
CGRAPH_API Agsubnode_t *agsubrep(Agraph_t *g, Agnode_t *n);
CGRAPH_API int agnodebefore(Agnode_t *u, Agnode_t *v); /* we have no shame */
CGRAPH_API int agdelnode(Agraph_t *g, Agnode_t *arg_n);
CGRAPH_API int agrelabel_node(Agnode_t *n, char *newname);
 
CGRAPH_API Agedge_t *agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name,
                            int createflag);
CGRAPH_API Agedge_t *agidedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, IDTYPE id,
                              int createflag);
CGRAPH_API Agedge_t *agsubedge(Agraph_t *g, Agedge_t *e, int createflag);
CGRAPH_API Agedge_t *agfstin(Agraph_t *g, Agnode_t *n);
CGRAPH_API Agedge_t *agnxtin(Agraph_t *g, Agedge_t *e);
CGRAPH_API Agedge_t *agfstout(Agraph_t *g, Agnode_t *n);
CGRAPH_API Agedge_t *agnxtout(Agraph_t *g, Agedge_t *e);
CGRAPH_API Agedge_t *agfstedge(Agraph_t *g, Agnode_t *n);
CGRAPH_API Agedge_t *agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n);
CGRAPH_API int agdeledge(Agraph_t *g, Agedge_t *arg_e);
 
 
// Generic object (graphs, nodes and edges) functions
 
CGRAPH_API Agraph_t *agraphof(void *obj);
CGRAPH_API Agraph_t *agroot(void *obj);
 
CGRAPH_API int agcontains(Agraph_t *, void *obj);
 
CGRAPH_API char *agnameof(void *);
 
CGRAPH_API int agdelete(Agraph_t *g, void *obj);
CGRAPH_API int agobjkind(void *obj);
 
CGRAPH_API char *agstrdup(Agraph_t *, const char *);
 
CGRAPH_API char *agstrdup_html(Agraph_t *, const char *);
CGRAPH_API int aghtmlstr(const char *);
CGRAPH_API char *agstrbind(Agraph_t *g, const char *);
 
CGRAPH_API int agstrfree(Agraph_t *, const char *);
CGRAPH_API char *agcanon(char *str, int html);
CGRAPH_API char *agstrcanon(char *, char *);
CGRAPH_API 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;   
  char **str;     
};
 
struct Agsym_s {
  Dtlink_t link;
  char *name;          /* attribute's name */
  char *defval;        /* its default value for initialization */
  int id;              
  unsigned char kind;  /* referent object type */
  unsigned char fixed; /* immutable value */
  unsigned char print; /* always print */
};
 
struct Agdatadict_s { 
  Agrec_t h;          /* installed in list of graph recs */
  struct {
    Dict_t *n, *e, *g;
  } dict;
};
 
CGRAPH_API Agsym_t *agattr(Agraph_t *g, int kind, char *name,
                           const char *value);
CGRAPH_API Agsym_t *agattrsym(void *obj, char *name);
 
CGRAPH_API Agsym_t *agnxtattr(Agraph_t *g, int kind, Agsym_t *attr);
 
CGRAPH_API int agcopyattr(void *oldobj, void *newobj);
CGRAPH_API void *agbindrec(void *obj, const char *name, unsigned int recsize,
                           int move_to_front);
 
CGRAPH_API Agrec_t *aggetrec(void *obj, const char *name, int move_to_front);
 
CGRAPH_API int agdelrec(void *obj, const char *name);
 
CGRAPH_API void aginit(Agraph_t *g, int kind, const char *rec_name,
                       int rec_size, int move_to_front);
CGRAPH_API void agclean(Agraph_t *g, int kind, char *rec_name);
 
 
CGRAPH_API char *agget(void *obj, char *name);
CGRAPH_API char *agxget(void *obj, Agsym_t *sym);
CGRAPH_API int agset(void *obj, char *name, const char *value);
CGRAPH_API int agxset(void *obj, Agsym_t *sym, const char *value);
CGRAPH_API int agsafeset(void *obj, char *name, const char *value,
                         const char *def);
 
 
CGRAPH_API Agraph_t *agsubg(Agraph_t *g, char *name,
                            int cflag); /* constructor */
CGRAPH_API Agraph_t *agidsubg(Agraph_t *g, IDTYPE id,
                              int cflag); /* constructor */
CGRAPH_API Agraph_t *agfstsubg(Agraph_t *g);
CGRAPH_API Agraph_t *agnxtsubg(Agraph_t *subg);
CGRAPH_API Agraph_t *agparent(Agraph_t *g);
CGRAPH_API int agdelsubg(Agraph_t *g, Agraph_t *sub); /* could be agclose */
 
CGRAPH_API int agnnodes(Agraph_t *g);
CGRAPH_API int agnedges(Agraph_t *g);
CGRAPH_API int agnsubg(Agraph_t *g);
CGRAPH_API int agdegree(Agraph_t *g, Agnode_t *n, int in, int out);
CGRAPH_API int agcountuniqedges(Agraph_t *g, Agnode_t *n, int in, int out);
 
CGRAPH_API void *agalloc(Agraph_t *g, size_t size);
CGRAPH_API void *agrealloc(Agraph_t *g, void *ptr, size_t oldsize, size_t size);
CGRAPH_API void agfree(Agraph_t *g, void *ptr);
 
/* an engineering compromise is a joy forever */
CGRAPH_API 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)))
 
 
/* support for extra API misuse warnings if available */
#ifdef __GNUC__
#define PRINTF_LIKE(index, first) __attribute__((format(printf, index, first)))
#else
#define PRINTF_LIKE(index, first) /* nothing */
#endif
 
 
typedef enum { AGWARN, AGERR, AGMAX, AGPREV } agerrlevel_t;
typedef int (*agusererrf)(char *);
CGRAPH_API agerrlevel_t agseterr(agerrlevel_t);
CGRAPH_API char *aglasterr(void);
CGRAPH_API int agerr(agerrlevel_t level, const char *fmt, ...)
    PRINTF_LIKE(2, 3);
CGRAPH_API void agerrorf(const char *fmt, ...) PRINTF_LIKE(1, 2);
CGRAPH_API void agwarningf(const char *fmt, ...) PRINTF_LIKE(1, 2);
CGRAPH_API int agerrors(void);
CGRAPH_API int agreseterrors(void);
CGRAPH_API agusererrf agseterrf(agusererrf);
 
#undef PRINTF_LIKE
 
/* data access macros */
/* this assumes that e[0] is out and e[1] is inedge, see @ref Agedgepair_s  */
#define AGIN2OUT(inedge) ((inedge) - 1) 
#define AGOUT2IN(outedge)                                                      \
  ((outedge) + 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 AGEQEDGE(e, f) (AGMKOUT(e) == AGMKOUT(f))
/* These macros are also exposed as functions, so they can be linked against. */
#define agtail(e) AGTAIL(e)
#define aghead(e) AGHEAD(e)
#define agopp(e)                                                               \
  AGOPP(e) 
#define ageqedge(e, f) AGEQEDGE(e, f) 
 
#define TAILPORT_ID "tailport"
#define HEADPORT_ID "headport"
 
CGRAPH_API extern Agdesc_t Agdirected; 
CGRAPH_API extern Agdesc_t Agstrictdirected;
CGRAPH_API extern Agdesc_t Agundirected;       
CGRAPH_API extern Agdesc_t Agstrictundirected; 
 
/* 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)
 
 
typedef struct {
  FILE *outFile;
  bool doWrite;
  bool Verbose;
} graphviz_acyclic_options_t;
 
CGRAPH_API bool graphviz_acyclic(Agraph_t *g,
                                 const graphviz_acyclic_options_t *opts,
                                 size_t *num_rev);
 
typedef struct {
  bool Verbose;
  bool PrintRemovedEdges;
  FILE *out; 
  FILE *err; 
} graphviz_tred_options_t;
 
CGRAPH_API void graphviz_tred(Agraph_t *g, const graphviz_tred_options_t *opts);
 
typedef struct {
  bool Do_fans;
  int MaxMinlen;
  int ChainLimit;
} graphviz_unflatten_options_t;
 
CGRAPH_API void graphviz_unflatten(Agraph_t *g,
                                   const graphviz_unflatten_options_t *opts);
 
CGRAPH_API size_t graphviz_node_induce(Agraph_t *g, Agraph_t *edgeset);
 
#ifdef __cplusplus
}
#endif