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 */
agclos(Agdisc_t * proto)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 */
agopen(char * name,Agdesc_t desc,Agdisc_t * arg_disc)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 */
agopen1(Agraph_t * g)69 Agraph_t *agopen1(Agraph_t * g)
70 {
71 Agraph_t *par;
72
73 g->n_seq = agdtopen(g, &Ag_subnode_seq_disc, Dttree);
74 g->n_id = agdtopen(g, &Ag_subnode_id_disc, Dttree);
75 g->e_seq = agdtopen(g, g == agroot(g)? &Ag_mainedge_seq_disc : &Ag_subedge_seq_disc, Dttree);
76 g->e_id = agdtopen(g, g == agroot(g)? &Ag_mainedge_id_disc : &Ag_subedge_id_disc, Dttree);
77 g->g_dict = agdtopen(g, &Ag_subgraph_id_disc, Dttree);
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 */
agclose(Agraph_t * g)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
117 aginternalmapclose(g);
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
agnextseq(Agraph_t * g,int objtype)157 uint64_t agnextseq(Agraph_t * g, int objtype)
158 {
159 return ++(g->clos->seq[objtype]);
160 }
161
agnnodes(Agraph_t * g)162 int agnnodes(Agraph_t * g)
163 {
164 return dtsize(g->n_id);
165 }
166
agnedges(Agraph_t * g)167 int agnedges(Agraph_t * g)
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
agnsubg(Agraph_t * g)177 int agnsubg(Agraph_t * g)
178 {
179 return dtsize(g->g_dict);
180 }
181
agisdirected(Agraph_t * g)182 int agisdirected(Agraph_t * g)
183 {
184 return g->desc.directed;
185 }
186
agisundirected(Agraph_t * g)187 int agisundirected(Agraph_t * g)
188 {
189 return NOT(agisdirected(g));
190 }
191
agisstrict(Agraph_t * g)192 int agisstrict(Agraph_t * g)
193 {
194 return g->desc.strict;
195 }
196
agissimple(Agraph_t * g)197 int agissimple(Agraph_t * g)
198 {
199 return (g->desc.strict && g->desc.no_loop);
200 }
201
cnt(Dict_t * d,Dtlink_t ** set)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
agcountuniqedges(Agraph_t * g,Agnode_t * n,int want_in,int want_out)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
agdegree(Agraph_t * g,Agnode_t * n,int want_in,int want_out)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
agraphidcmpf(Dict_t * d,void * arg0,void * arg1,Dtdisc_t * disc)242 static 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
agraphseqcmpf(Dict_t * d,void * arg0,void * arg1,Dtdisc_t * disc)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
262 Dtdisc_t Ag_subgraph_id_disc = {
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
281 Agdisc_t AgDefaultDisc = { &AgMemDisc, &AgIdDisc, &AgIoDisc };
282
283
284 #include <stdio.h>
scndump(Agraph_t * g,char * file)285 void scndump(Agraph_t *g, char *file)
286 {
287 FILE * f = fopen(file,"w");
288 if (f) {agwrite(g,f); fclose(f);}
289 }
290