Graphviz  2.41.20170921.2350
graph.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 #define EXTERN
15 #include <cghdr.h>
16 
17 const char AgraphVersion[] = PACKAGE_VERSION;
18 
19 /*
20  * this code sets up the resource management discipline
21  * and returns a new main graph struct.
22  */
23 static Agclos_t *agclos(Agdisc_t * proto)
24 {
25  Agmemdisc_t *memdisc;
26  void *memclosure;
27  Agclos_t *rv;
28 
29  /* establish an allocation arena */
30  memdisc = ((proto && proto->mem) ? proto->mem : &AgMemDisc);
31  memclosure = memdisc->open(proto);
32  rv = memdisc->alloc(memclosure, sizeof(Agclos_t));
33  rv->disc.mem = memdisc;
34  rv->state.mem = memclosure;
35  rv->disc.id = ((proto && proto->id) ? proto->id : &AgIdDisc);
36  rv->disc.io = ((proto && proto->io) ? proto->io : &AgIoDisc);
37  rv->callbacks_enabled = TRUE;
38  return rv;
39 }
40 
41 /*
42  * Open a new main graph with the given descriptor (directed, strict, etc.)
43  */
44 Agraph_t *agopen(char *name, Agdesc_t desc, Agdisc_t * arg_disc)
45 {
46  Agraph_t *g;
47  Agclos_t *clos;
48  IDTYPE gid;
49 
50  clos = agclos(arg_disc);
51  g = clos->disc.mem->alloc(clos->state.mem, sizeof(Agraph_t));
52  AGTYPE(g) = AGRAPH;
53  g->clos = clos;
54  g->desc = desc;
55  g->desc.maingraph = TRUE;
56  g->root = g;
57  g->clos->state.id = g->clos->disc.id->open(g, arg_disc);
58  if (agmapnametoid(g, AGRAPH, name, &gid, TRUE))
59  AGID(g) = gid;
60  /* else AGID(g) = 0 because we have no alternatives */
61  g = agopen1(g);
62  agregister(g, AGRAPH, g);
63  return g;
64 }
65 
66 /*
67  * initialize dictionaries, set seq, invoke init method of new graph
68  */
70 {
71  Agraph_t *par;
72 
78 
79  par = agparent(g);
80  if (par) {
81  AGSEQ(g) = agnextseq(par, AGRAPH);
82  dtinsert(par->g_dict, g);
83  } /* else AGSEQ=0 */
84  if (!par || par->desc.has_attrs)
85  agraphattr_init(g);
86  agmethod_init(g, g);
87  return g;
88 }
89 
90 /*
91  * Close a graph or subgraph, freeing its storage.
92  */
93 int agclose(Agraph_t * g)
94 {
95  Agraph_t *subg, *next_subg, *par;
96  Agnode_t *n, *next_n;
97 
98  par = agparent(g);
99  if ((par == NILgraph) && (AGDISC(g, mem)->close)) {
100  /* free entire heap */
101  agmethod_delete(g, g); /* invoke user callbacks */
102  agfreeid(g, AGRAPH, AGID(g));
103  AGDISC(g, mem)->close(AGCLOS(g, mem)); /* whoosh */
104  return SUCCESS;
105  }
106 
107  for (subg = agfstsubg(g); subg; subg = next_subg) {
108  next_subg = agnxtsubg(subg);
109  agclose(subg);
110  }
111 
112  for (n = agfstnode(g); n; n = next_n) {
113  next_n = agnxtnode(g, n);
114  agdelnode(g, n);
115  }
116 
118  agmethod_delete(g, g);
119 
120  assert(dtsize(g->n_id) == 0);
121  if (agdtclose(g, g->n_id)) return FAILURE;
122  assert(dtsize(g->n_seq) == 0);
123  if (agdtclose(g, g->n_seq)) return FAILURE;
124 
125  assert(dtsize(g->e_id) == 0);
126  if (agdtclose(g, g->e_id)) return FAILURE;
127  assert(dtsize(g->e_seq) == 0);
128  if (agdtclose(g, g->e_seq)) return FAILURE;
129 
130  assert(dtsize(g->g_dict) == 0);
131  if (agdtclose(g, g->g_dict)) return FAILURE;
132 
133  if (g->desc.has_attrs)
134  if (agraphattr_delete(g)) return FAILURE;
135  agrecclose((Agobj_t *) g);
136  agfreeid(g, AGRAPH, AGID(g));
137 
138  if (par) {
139  agdelsubg(par, g);
140  agfree(par, g);
141  } else {
142  Agmemdisc_t *memdisc;
143  void *memclos, *clos;
144  while (g->clos->cb)
145  agpopdisc(g, g->clos->cb->f);
146  AGDISC(g, id)->close(AGCLOS(g, id));
147  if (agstrclose(g)) return FAILURE;
148  memdisc = AGDISC(g, mem);
149  memclos = AGCLOS(g, mem);
150  clos = g->clos;
151  (memdisc->free) (memclos, g);
152  (memdisc->free) (memclos, clos);
153  }
154  return SUCCESS;
155 }
156 
157 uint64_t agnextseq(Agraph_t * g, int objtype)
158 {
159  return ++(g->clos->seq[objtype]);
160 }
161 
163 {
164  return dtsize(g->n_id);
165 }
166 
168 {
169  Agnode_t *n;
170  int rv = 0;
171 
172  for (n = agfstnode(g); n; n = agnxtnode(g, n))
173  rv += agdegree(g, n, FALSE, TRUE); /* must use OUT to get self-arcs */
174  return rv;
175 }
176 
178 {
179  return dtsize(g->g_dict);
180 }
181 
183 {
184  return g->desc.directed;
185 }
186 
188 {
189  return NOT(agisdirected(g));
190 }
191 
193 {
194  return g->desc.strict;
195 }
196 
198 {
199  return (g->desc.strict && g->desc.no_loop);
200 }
201 
202 static int cnt(Dict_t * d, Dtlink_t ** set)
203 {
204  int rv;
205  dtrestore(d, *set);
206  rv = dtsize(d);
207  *set = dtextract(d);
208  return rv;
209 }
210 
211 int agcountuniqedges(Agraph_t * g, Agnode_t * n, int want_in, int want_out)
212 {
213  Agedge_t *e;
214  Agsubnode_t *sn;
215  int rv = 0;
216 
217  sn = agsubrep(g, n);
218  if (want_out) rv = cnt(g->e_seq,&(sn->out_seq));
219  if (want_in) {
220  if (!want_out) rv += cnt(g->e_seq,&(sn->in_seq)); /* cheap */
221  else { /* less cheap */
222  for (e = agfstin(g, n); e; e = agnxtin(g, e))
223  if (e->node != n) rv++; /* don't double count loops */
224  }
225  }
226  return rv;
227 }
228 
229 int agdegree(Agraph_t * g, Agnode_t * n, int want_in, int want_out)
230 {
231  Agsubnode_t *sn;
232  int rv = 0;
233 
234  sn = agsubrep(g, n);
235  if (sn) {
236  if (want_out) rv += cnt(g->e_seq,&(sn->out_seq));
237  if (want_in) rv += cnt(g->e_seq,&(sn->in_seq));
238  }
239  return rv;
240 }
241 
242 int agraphidcmpf(Dict_t * d, void *arg0, void *arg1, Dtdisc_t * disc)
243 {
244  ptrdiff_t v;
245  Agraph_t *sg0, *sg1;
246  sg0 = (Agraph_t *) arg0;
247  sg1 = (Agraph_t *) arg1;
248  v = (AGID(sg0) - AGID(sg1));
249  return ((v==0)?0:(v<0?-1:1));
250 }
251 
252 int agraphseqcmpf(Dict_t * d, void *arg0, void *arg1, Dtdisc_t * disc)
253 {
254  long v;
255  Agraph_t *sg0, *sg1;
256  sg0 = (Agraph_t *) arg0;
257  sg1 = (Agraph_t *) arg1;
258  v = (AGSEQ(sg0) - AGSEQ(sg1));
259  return ((v==0)?0:(v<0?-1:1));
260 }
261 
263  0, /* pass object ptr */
264  0, /* size (ignored) */
265  offsetof(Agraph_t, link), /* link offset */
266  NIL(Dtmake_f),
267  NIL(Dtfree_f),
268  agraphidcmpf,
269  NIL(Dthash_f),
270  agdictobjmem,
271  NIL(Dtevent_f)
272 };
273 
274 
275 /* directed, strict, no_loops, maingraph */
276 Agdesc_t Agdirected = { 1, 0, 0, 1 };
277 Agdesc_t Agstrictdirected = { 1, 1, 0, 1 };
278 Agdesc_t Agundirected = { 0, 0, 0, 1 };
279 Agdesc_t Agstrictundirected = { 0, 1, 0, 1 };
280 
282 
283 
284 #include <stdio.h>
285 void scndump(Agraph_t *g, char *file)
286 {
287  FILE * f = fopen(file,"w");
288  if (f) {agwrite(g,f); fclose(f);}
289 }
unsigned int(* Dthash_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:41
#define AGSEQ(obj)
Definition: cgraph.h:115
CGRAPH_API Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
Definition: graph.c:44
Agiddisc_t * id
Definition: cgraph.h:191
void agraphattr_init(Agraph_t *g)
Definition: attr.c:357
void *(* Dtmake_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:38
CGRAPH_API int agdegree(Agraph_t *g, Agnode_t *n, int in, int out)
Definition: graph.c:229
#define SUCCESS
Definition: cghdr.h:62
int agdtclose(Agraph_t *g, Dict_t *dict)
Definition: utils.c:79
Dtdisc_t Ag_mainedge_seq_disc
Definition: edge.c:447
CGRAPH_API Agmemdisc_t AgMemDisc
Definition: cgraph.h:197
CGRAPH_API Agiodisc_t AgIoDisc
Definition: cgraph.h:199
CGRAPH_API int agdelnode(Agraph_t *g, Agnode_t *arg_n)
Definition: node.c:192
void agrecclose(Agobj_t *obj)
Definition: rec.c:263
Dtdisc_t Ag_subgraph_id_disc
Definition: graph.c:262
Agdesc_t desc
Definition: cgraph.h:241
void * id
Definition: cgraph.h:205
int agmapnametoid(Agraph_t *g, int objtype, char *str, IDTYPE *result, int allocflag)
Definition: id.c:96
Dtdisc_t Ag_subedge_id_disc
Definition: edge.c:484
CDT_API Dtlink_t * dtextract(Dt_t *)
Agraph_t * agopen1(Agraph_t *g)
Definition: graph.c:69
void agregister(Agraph_t *g, int objtype, void *obj)
Definition: id.c:169
CGRAPH_API Agdesc_t Agstrictundirected
Definition: cgraph.h:421
CGRAPH_API Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition: edge.c:56
#define AGID(obj)
Definition: cgraph.h:114
Dict_t * n_seq
Definition: cgraph.h:243
#define assert(x)
Definition: cghdr.h:47
CGRAPH_API int agisdirected(Agraph_t *g)
Definition: graph.c:182
CGRAPH_API long agdelsubg(Agraph_t *g, Agraph_t *sub)
Definition: subg.c:93
CGRAPH_API int agisundirected(Agraph_t *g)
Definition: graph.c:187
Definition: cdt.h:80
Dtdisc_t Ag_subnode_seq_disc
Definition: node.c:326
int agstrclose(Agraph_t *g)
Definition: refstr.c:69
#define AGCLOS(g, d)
Definition: cghdr.h:67
CGRAPH_API int agwrite(Agraph_t *g, void *chan)
Definition: write.c:678
Dtdisc_t Ag_subnode_id_disc
Definition: node.c:314
unsigned char callbacks_enabled
Definition: cgraph.h:234
CGRAPH_API Agraph_t * agfstsubg(Agraph_t *g)
Definition: subg.c:72
CGRAPH_API Agraph_t * agroot(void *obj)
Definition: obj.c:169
int agraphidcmpf(Dict_t *d, void *arg0, void *arg1, Dtdisc_t *disc)
Definition: graph.c:242
uint64_t agnextseq(Agraph_t *g, int objtype)
Definition: graph.c:157
Dtdisc_t Ag_mainedge_id_disc
Definition: edge.c:472
Dtlink_t * out_seq
Definition: cgraph.h:130
CGRAPH_API Agdesc_t Agundirected
Definition: cgraph.h:420
CGRAPH_API Agiddisc_t AgIdDisc
Definition: cgraph.h:198
CGRAPH_API void agfree(Agraph_t *g, void *ptr)
Definition: mem.c:89
Agcbdisc_t * f
Definition: cgraph.h:223
#define AGTYPE(obj)
Definition: cgraph.h:113
void scndump(Agraph_t *g, char *file)
Definition: graph.c:285
Agmemdisc_t * mem
Definition: cgraph.h:190
CGRAPH_API Agraph_t * agnxtsubg(Agraph_t *subg)
Definition: subg.c:77
CGRAPH_API Agdesc_t Agstrictdirected
Definition: cgraph.h:419
#define AGDISC(g, d)
Definition: cghdr.h:66
CGRAPH_API Agdesc_t Agdirected
Definition: cgraph.h:418
Agdisc_t disc
Definition: cgraph.h:229
uint64_t IDTYPE
Definition: cgraph.h:51
Dict_t * n_id
Definition: cgraph.h:244
void * mem
Definition: cgraph.h:204
CGRAPH_API int agcountuniqedges(Agraph_t *g, Agnode_t *n, int in, int out)
Definition: graph.c:211
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
unsigned has_attrs
Definition: cgraph.h:157
#define NIL(t)
Definition: dthdr.h:13
Agnode_t * node
Definition: cgraph.h:143
CGRAPH_API int agisstrict(Agraph_t *g)
Definition: graph.c:192
const char AgraphVersion[]
Definition: graph.c:17
#define NILgraph
Definition: cghdr.h:56
#define FAILURE
Definition: cghdr.h:63
uint64_t seq[3]
Definition: cgraph.h:232
CGRAPH_API int agclose(Agraph_t *g)
Definition: graph.c:93
CGRAPH_API Agraph_t * agparent(Agraph_t *g)
Definition: subg.c:85
void *(* open)(Agraph_t *g, Agdisc_t *)
Definition: cgraph.h:172
int agraphseqcmpf(Dict_t *d, void *arg0, void *arg1, Dtdisc_t *disc)
Definition: graph.c:252
void(* free)(void *state, void *ptr)
Definition: cgraph.h:167
void aginternalmapclose(Agraph_t *g)
Definition: imap.c:214
void agmethod_delete(Agraph_t *g, void *obj)
Definition: obj.c:138
void agfreeid(Agraph_t *g, int objtype, IDTYPE id)
Definition: id.c:131
CDT_API int dtsize(Dt_t *)
Definition: dtsize.c:12
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
Dtdisc_t Ag_subedge_seq_disc
Definition: edge.c:459
void agmethod_init(Agraph_t *g, void *obj)
Definition: obj.c:76
CGRAPH_API Agsubnode_t * agsubrep(Agraph_t *g, Agnode_t *n)
Definition: edge.c:157
#define dtinsert(d, o)
Definition: cdt.h:262
unsigned no_loop
Definition: cgraph.h:153
Dict_t * agdtopen(Agraph_t *g, Dtdisc_t *disc, Dtmethod_t *method)
Definition: utils.c:53
CDT_API Dtmethod_t * Dttree
Definition: cdt.h:176
void *(* open)(Agdisc_t *)
Definition: cgraph.h:164
CGRAPH_API int agpopdisc(Agraph_t *g, Agcbdisc_t *disc)
Definition: obj.c:213
CGRAPH_API int agnsubg(Agraph_t *g)
Definition: graph.c:177
#define NOT(x)
Definition: cgraph.h:41
CDT_API int dtrestore(Dt_t *, Dtlink_t *)
unsigned maingraph
Definition: cgraph.h:154
Dict_t * g_dict
Definition: cgraph.h:246
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
Dtlink_t * in_seq
Definition: cgraph.h:130
Dict_t * e_id
Definition: cgraph.h:245
Agiodisc_t * io
Definition: cgraph.h:192
unsigned strict
Definition: cgraph.h:152
void *(* alloc)(void *state, size_t req)
Definition: cgraph.h:165
Agcbstack_t * cb
Definition: cgraph.h:233
CGRAPH_API int agissimple(Agraph_t *g)
Definition: graph.c:197
void * agdictobjmem(Dict_t *dict, void *p, size_t size, Dtdisc_t *disc)
Definition: utils.c:19
int(* Dtevent_f)(Dt_t *, int, void *, Dtdisc_t *)
Definition: cdt.h:42
void(* Dtfree_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:39
CGRAPH_API Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition: edge.c:70
Definition: cdt.h:99
Dict_t * e_seq
Definition: cgraph.h:245
CGRAPH_API int agnedges(Agraph_t *g)
Definition: graph.c:167
Agdstate_t state
Definition: cgraph.h:230
CGRAPH_API Agdisc_t AgDefaultDisc
Definition: cgraph.h:201
Agraph_t * root
Definition: cgraph.h:247
Agclos_t * clos
Definition: cgraph.h:248
unsigned directed
Definition: cgraph.h:151
#define FALSE
Definition: cgraph.h:35
int agraphattr_delete(Agraph_t *g)
Definition: attr.c:370
#define AGRAPH
Definition: cgraph.h:100
#define TRUE
Definition: cgraph.h:38