Graphviz 13.0.0~dev.20250123.2027
Loading...
Searching...
No Matches
graph.c
Go to the documentation of this file.
1
6/*************************************************************************
7 * Copyright (c) 2011 AT&T Intellectual Property
8 * All rights reserved. This program and the accompanying materials
9 * are made available under the terms of the Eclipse Public License v1.0
10 * which accompanies this distribution, and is available at
11 * https://www.eclipse.org/legal/epl-v10.html
12 *
13 * Contributors: Details at https://graphviz.org
14 *************************************************************************/
15
16#include <assert.h>
17#include <cgraph/cghdr.h>
18#include <cgraph/node_set.h>
19#include <limits.h>
20#include <stdbool.h>
21#include <stdlib.h>
22#include <util/alloc.h>
23
25
26/*
27 * this code sets up the resource management discipline
28 * and returns a new main graph struct.
29 */
30static Agclos_t *agclos(Agdisc_t * proto)
31{
32 Agclos_t *rv;
33
34 /* establish an allocation arena */
35 rv = gv_calloc(1, sizeof(Agclos_t));
36 rv->disc.id = ((proto && proto->id) ? proto->id : &AgIdDisc);
37 rv->disc.io = ((proto && proto->io) ? proto->io : &AgIoDisc);
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 = gv_calloc(1, 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 g = agopen1(g);
61 agregister(g, AGRAPH, g);
62 return g;
63}
64
65/*
66 * initialize dictionaries, set seq, invoke init method of new graph
67 */
69{
70 Agraph_t *par;
71
73 g->n_id = node_set_new();
77
79
80 par = agparent(g);
81 if (par) {
82 uint64_t seq = agnextseq(par, AGRAPH);
83 assert((seq & SEQ_MASK) == seq && "sequence ID overflow");
84 AGSEQ(g) = seq & SEQ_MASK;
85 dtinsert(par->g_seq, g);
86 dtinsert(par->g_id, g);
87 }
88 if (!par || par->desc.has_attrs)
90 agmethod_init(g, g);
91 return g;
92}
93
94/*
95 * Close a graph or subgraph, freeing its storage.
96 */
98{
99 Agraph_t *subg, *next_subg, *par;
100 Agnode_t *n, *next_n;
101
102 par = agparent(g);
103
104 for (subg = agfstsubg(g); subg; subg = next_subg) {
105 next_subg = agnxtsubg(subg);
106 agclose(subg);
107 }
108
109 for (n = agfstnode(g); n; n = next_n) {
110 next_n = agnxtnode(g, n);
111 agdelnode(g, n);
112 }
113
115 agmethod_delete(g, g);
116
117 assert(node_set_is_empty(g->n_id));
118 node_set_free(&g->n_id);
119 assert(dtsize(g->n_seq) == 0);
120 if (agdtclose(g, g->n_seq)) return FAILURE;
121
122 assert(dtsize(g->e_id) == 0);
123 if (agdtclose(g, g->e_id)) return FAILURE;
124 assert(dtsize(g->e_seq) == 0);
125 if (agdtclose(g, g->e_seq)) return FAILURE;
126
127 assert(dtsize(g->g_seq) == 0);
128 if (agdtclose(g, g->g_seq)) return FAILURE;
129
130 assert(dtsize(g->g_id) == 0);
131 if (agdtclose(g, g->g_id)) 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 free(g);
141 } else {
142 void *clos;
143 while (g->clos->cb)
144 agpopdisc(g, g->clos->cb->f);
145 AGDISC(g, id)->close(AGCLOS(g, id));
146 if (agstrclose(g)) return FAILURE;
147 clos = g->clos;
148 free(g);
149 free(clos);
150 }
151 return SUCCESS;
152}
153
154uint64_t agnextseq(Agraph_t * g, int objtype)
155{
156 return ++(g->clos->seq[objtype]);
157}
158
160{
161 assert(node_set_size(g->n_id) <= INT_MAX);
162 return (int)node_set_size(g->n_id);
163}
164
166{
167 Agnode_t *n;
168 int rv = 0;
169
170 for (n = agfstnode(g); n; n = agnxtnode(g, n))
171 rv += agdegree(g, n, 0, 1); /* must use OUT to get self-arcs */
172 return rv;
173}
174
176{
177 return dtsize(g->g_seq);
178}
179
181{
182 return g->desc.directed;
183}
184
186{
187 return !agisdirected(g);
188}
189
191{
192 return g->desc.strict;
193}
194
196{
197 return (g->desc.strict && g->desc.no_loop);
198}
199
200static int cnt(Dict_t * d, Dtlink_t ** set)
201{
202 int rv;
203 dtrestore(d, *set);
204 rv = dtsize(d);
205 *set = dtextract(d);
206 return rv;
207}
208
209int agcountuniqedges(Agraph_t * g, Agnode_t * n, int want_in, int want_out)
210{
211 Agedge_t *e;
212 Agsubnode_t *sn;
213 int rv = 0;
214
215 sn = agsubrep(g, n);
216 if (want_out) rv = cnt(g->e_seq,&(sn->out_seq));
217 if (want_in) {
218 if (!want_out) rv += cnt(g->e_seq,&(sn->in_seq)); /* cheap */
219 else { /* less cheap */
220 for (e = agfstin(g, n); e; e = agnxtin(g, e))
221 if (e->node != n) rv++; /* don't double count loops */
222 }
223 }
224 return rv;
225}
226
227int agdegree(Agraph_t * g, Agnode_t * n, int want_in, int want_out)
228{
229 Agsubnode_t *sn;
230 int rv = 0;
231
232 sn = agsubrep(g, n);
233 if (sn) {
234 if (want_out) rv += cnt(g->e_seq,&(sn->out_seq));
235 if (want_in) rv += cnt(g->e_seq,&(sn->in_seq));
236 }
237 return rv;
238}
239
240static int agraphseqcmpf(void *arg0, void *arg1) {
241 Agraph_t *sg0 = arg0;
242 Agraph_t *sg1 = arg1;
243 if (AGSEQ(sg0) < AGSEQ(sg1)) {
244 return -1;
245 }
246 if (AGSEQ(sg0) > AGSEQ(sg1)) {
247 return 1;
248 }
249 return 0;
250}
251
252static int agraphidcmpf(void *arg0, void *arg1) {
253 Agraph_t *sg0 = arg0;
254 Agraph_t *sg1 = arg1;
255 if (AGID(sg0) < AGID(sg1)) {
256 return -1;
257 }
258 if (AGID(sg0) > AGID(sg1)) {
259 return 1;
260 }
261 return 0;
262}
263
265 .link = offsetof(Agraph_t, seq_link), // link offset
266 .comparf = agraphseqcmpf,
267};
268
270 .link = offsetof(Agraph_t, id_link), // link offset
271 .comparf = agraphidcmpf,
272};
273
274Agdesc_t Agdirected = {.directed = true, .maingraph = true};
275Agdesc_t Agstrictdirected = {.directed = true, .strict = true, .maingraph = true};
277Agdesc_t Agstrictundirected = {.strict = true, .maingraph = true};
278
280
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
CDT_API Dtlink_t * dtextract(Dt_t *)
Definition dtextract.c:9
CDT_API int dtsize(Dt_t *)
Definition dtsize.c:12
#define dtinsert(d, o)
Definition cdt.h:185
CDT_API Dtmethod_t * Dttree
Definition dttree.c:308
CDT_API int dtrestore(Dt_t *, Dtlink_t *)
Definition dtrestore.c:11
cgraph.h additions
void agfreeid(Agraph_t *g, int objtype, IDTYPE id)
Definition id.c:131
int agstrclose(Agraph_t *g)
Definition refstr.c:322
void aginternalmapclose(Agraph_t *g)
Definition imap.c:196
void agrecclose(Agobj_t *obj)
Definition rec.c:227
Dtdisc_t Ag_subnode_seq_disc
Definition node.c:306
int agmapnametoid(Agraph_t *g, int objtype, char *str, IDTYPE *result, bool createflag)
Definition id.c:102
Dict_t * agdtopen(Dtdisc_t *disc, Dtmethod_t *method)
Definition utils.c:21
Dtdisc_t Ag_subedge_seq_disc
Definition edge.c:411
#define FAILURE
Definition cghdr.h:45
#define AGDISC(g, d)
Definition cghdr.h:48
Dtdisc_t Ag_mainedge_seq_disc
Definition edge.c:406
void agregister(Agraph_t *g, int objtype, void *obj)
Definition id.c:170
#define SUCCESS
Definition cghdr.h:44
#define AGCLOS(g, d)
Definition cghdr.h:49
Dtdisc_t Ag_subedge_id_disc
Definition edge.c:422
Dtdisc_t Ag_mainedge_id_disc
Definition edge.c:417
@ SEQ_MASK
Definition cghdr.h:74
int agdtclose(Agraph_t *g, Dict_t *dict)
Definition utils.c:31
void node_set_free(node_set_t **self)
Definition node.c:552
size_t node_set_size(const node_set_t *self)
Definition node.c:547
node_set_t * node_set_new(void)
Definition node.c:408
void free(void *)
static int agraphidcmpf(void *arg0, void *arg1)
Definition graph.c:252
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:200
static Agclos_t * agclos(Agdisc_t *proto)
Definition graph.c:30
Agraph_t * agopen1(Agraph_t *g)
Definition graph.c:68
Agraph_t * Ag_G_global
Definition graph.c:24
uint64_t agnextseq(Agraph_t *g, int objtype)
Definition graph.c:154
static int agraphseqcmpf(void *arg0, void *arg1)
Definition graph.c:240
Dtdisc_t Ag_subgraph_seq_disc
Definition graph.c:264
Dtdisc_t Ag_subgraph_id_disc
Definition graph.c:269
int agnsubg(Agraph_t *g)
Definition graph.c:175
int agcountuniqedges(Agraph_t *g, Agnode_t *n, int want_in, int want_out)
Definition graph.c:209
int agnedges(Agraph_t *g)
Definition graph.c:165
int agdegree(Agraph_t *g, Agnode_t *n, int want_in, int want_out)
Definition graph.c:227
int agnnodes(Agraph_t *g)
Definition graph.c:159
void agraphattr_init(Agraph_t *g)
Definition attr.c:396
int agraphattr_delete(Agraph_t *g)
Definition attr.c:407
int agpopdisc(Agraph_t *g, Agcbdisc_t *disc)
Definition obj.c:211
void agmethod_delete(Agraph_t *g, void *obj)
Definition obj.c:138
void agmethod_init(Agraph_t *g, void *obj)
Definition obj.c:78
Agdisc_t AgDefaultDisc
Definition graph.c:279
Agiddisc_t AgIdDisc
Definition id.c:91
Agiodisc_t AgIoDisc
Definition io.c:39
Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition edge.c:69
Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition edge.c:55
Agdesc_t Agundirected
undirected
Definition graph.c:276
int agisdirected(Agraph_t *g)
Definition graph.c:180
Agdesc_t Agstrictundirected
strict undirected
Definition graph.c:277
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Definition graph.c:97
int agisstrict(Agraph_t *g)
Definition graph.c:190
int agissimple(Agraph_t *g)
Definition graph.c:195
Agdesc_t Agstrictdirected
strict directed. A strict graph cannot have multi-edges or self-arcs.
Definition graph.c:275
Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *arg_disc)
creates a new graph with the given name and kind
Definition graph.c:44
int agisundirected(Agraph_t *g)
Definition graph.c:185
Agdesc_t Agdirected
directed
Definition graph.c:274
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:47
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:40
int agdelnode(Agraph_t *g, Agnode_t *arg_n)
removes a node from a graph or subgraph.
Definition node.c:190
Agsubnode_t * agsubrep(Agraph_t *g, Agnode_t *n)
Definition edge.c:145
#define AGID(obj)
returns the unique integer ID associated with the object
Definition cgraph.h:221
uint64_t IDTYPE
unique per main graph ID
Definition cgraph.h:73
#define AGTYPE(obj)
returns AGRAPH, AGNODE, or AGEDGE depending on the type of the object
Definition cgraph.h:216
Agraph_t * agroot(void *obj)
Definition obj.c:168
#define AGSEQ(obj)
Definition cgraph.h:225
@ AGRAPH
Definition cgraph.h:207
Agraph_t * agparent(Agraph_t *g)
Definition subg.c:88
Agraph_t * agfstsubg(Agraph_t *g)
Definition subg.c:75
Agraph_t * agnxtsubg(Agraph_t *subg)
Definition subg.c:80
int agdelsubg(Agraph_t *g, Agraph_t *sub)
Definition subg.c:96
unordered set of Agsubnode_t *
static bool node_set_is_empty(const node_set_t *self)
Definition node_set.h:55
Agcbdisc_t * f
Definition cgraph.h:399
shared resources for Agraph_s
Definition cgraph.h:410
Agdisc_t disc
Definition cgraph.h:411
Agdstate_t state
Definition cgraph.h:412
Agcbstack_t * cb
Definition cgraph.h:415
uint64_t seq[3]
Definition cgraph.h:414
graph descriptor
Definition cgraph.h:284
unsigned has_attrs
Definition cgraph.h:290
unsigned maingraph
Definition cgraph.h:288
unsigned no_loop
Definition cgraph.h:287
unsigned strict
Definition cgraph.h:286
unsigned directed
Definition cgraph.h:285
user's discipline
Definition cgraph.h:336
Agiddisc_t * id
Definition cgraph.h:337
Agiodisc_t * io
Definition cgraph.h:338
void * id
Definition cgraph.h:363
Agnode_t * node
Definition cgraph.h:272
void *(* open)(Agraph_t *g, Agdisc_t *)
Definition cgraph.h:317
a generic header of Agraph_s, Agnode_s and Agedge_s
Definition cgraph.h:210
graph or subgraph
Definition cgraph.h:424
struct graphviz_node_set * n_id
the node set indexed by ID
Definition cgraph.h:430
Dict_t * g_seq
Definition cgraph.h:432
Agraph_t * root
subgraphs - ancestors
Definition cgraph.h:433
Dict_t * g_id
subgraphs - descendants
Definition cgraph.h:432
Dict_t * e_seq
Definition cgraph.h:431
Dict_t * n_seq
the node set in sequence
Definition cgraph.h:429
Agclos_t * clos
shared resources
Definition cgraph.h:434
Agdesc_t desc
Definition cgraph.h:426
Dict_t * e_id
holders for edge sets
Definition cgraph.h:431
This is the node struct allocated per graph (or subgraph).
Definition cgraph.h:251
Dtlink_t * out_seq
Definition cgraph.h:256
Dtlink_t * in_seq
Definition cgraph.h:256
Definition cdt.h:100
int link
Definition cdt.h:87