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
17const char AgraphVersion[] = PACKAGE_VERSION;
18
19/*
20 * this code sets up the resource management discipline
21 * and returns a new main graph struct.
22 */
23static 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 */
44Agraph_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 */
69Agraph_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 */
93int 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
157uint64_t agnextseq(Agraph_t * g, int objtype)
158{
159 return ++(g->clos->seq[objtype]);
160}
161
162int agnnodes(Agraph_t * g)
163{
164 return dtsize(g->n_id);
165}
166
167int 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
177int agnsubg(Agraph_t * g)
178{
179 return dtsize(g->g_dict);
180}
181
182int agisdirected(Agraph_t * g)
183{
184 return g->desc.directed;
185}
186
187int agisundirected(Agraph_t * g)
188{
189 return NOT(agisdirected(g));
190}
191
192int agisstrict(Agraph_t * g)
193{
194 return g->desc.strict;
195}
196
197int agissimple(Agraph_t * g)
198{
199 return (g->desc.strict && g->desc.no_loop);
200}
201
202static 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
211int 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
229int 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
242int 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
252int 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
262Dtdisc_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 */
276Agdesc_t Agdirected = { 1, 0, 0, 1 };
277Agdesc_t Agstrictdirected = { 1, 1, 0, 1 };
278Agdesc_t Agundirected = { 0, 0, 0, 1 };
279Agdesc_t Agstrictundirected = { 0, 1, 0, 1 };
280
281Agdisc_t AgDefaultDisc = { &AgMemDisc, &AgIdDisc, &AgIoDisc };
282
283
284#include <stdio.h>
285void scndump(Agraph_t *g, char *file)
286{
287 FILE * f = fopen(file,"w");
288 if (f) {agwrite(g,f); fclose(f);}
289}
290