Graphviz  2.41.20170921.2350
cmpnd.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 #include <cghdr.h>
15 
16 /*
17  * provides "compound nodes" on top of base Libgraph.
18  * a compound node behaves as both an ordinary node and a subgraph.
19  * there are additional primitives to "hide" and "expose" its contents.
20  *
21  * you could think of these as hypergraphs, but there is an assymetry
22  * in the operations we have chosen. i.e. nodes "own" their edges,
23  * but nodes and interior edges are "owned by" the hyperedges.
24  * also the subgraphs are nested, etc. the bottom line is that graphs
25  * and hypergraphs are just sets, everything else here is convenience
26  * and maintaining consistency.
27  *
28  * this package adds a primitive "agsplice" to move endpoints of edges.
29  * this could be useful in other situations.
30  */
31 
32 static char Descriptor_id[] = "AG_cmpnd";
33 
34 typedef struct Agcmpnode_s {
37  int collapsed;
38 } Agcmpnode_t;
39 
40 typedef struct Agcmpgraph_s {
42  Agnode_t *node; /* its associated node */
44 } Agcmpgraph_t;
45 
46 typedef struct save_e_s {
48 } save_e_t;
49 
50 typedef struct save_stack_s {
52  int stacksize;
53 } save_stack_t;
54 
55 typedef struct Agcmpedge_s {
57  save_stack_t stack[2]; /* IN and OUT save stacks */
58 } Agcmpedge_t;
59 #define IN_STACK 0
60 #define OUT_STACK 1
61 
62 static save_stack_t *save_stack_of(Agedge_t * e,
63  Agnode_t * node_being_saved)
64 {
65  int i;
66  Agcmpedge_t *edgerec;
67  edgerec =
68  (Agcmpedge_t *) agbindrec(e, Descriptor_id, sizeof(*edgerec),
69  FALSE);
70  if (node_being_saved == AGHEAD(e))
71  i = IN_STACK;
72  else
73  i = OUT_STACK;
74  return &(edgerec->stack[i]);
75 }
76 
77 static void stackpush(save_stack_t * stk, Agnode_t * from, Agnode_t * to)
78 {
79  int i, osize, nsize;
80 
81  osize = (stk->stacksize) * sizeof(stk->mem);
82  i = stk->stacksize++;
83  nsize = (stk->stacksize) * sizeof(stk->mem);
84  stk->mem = agrealloc(agraphof(from), stk->mem, osize, nsize);
85  stk->mem[i].from = from;
86  stk->mem[i].to = to;
87 }
88 
89 static save_e_t stacktop(save_stack_t * stk)
90 {
91  save_e_t rv;
92  if (stk->stacksize > 0)
93  rv = stk->mem[stk->stacksize - 1];
94  else
95  rv.from = rv.to = NILnode;
96  return rv;
97 }
98 
99 /* note: doesn't give back mem, but stackpush() eventually does */
100 static save_e_t stackpop(save_stack_t * stk)
101 {
102  save_e_t rv;
103  rv = stacktop(stk);
104  if (stk->stacksize > 0)
105  stk->stacksize--;
106  return rv;
107 }
108 
109 typedef struct Agsplice_arg_s {
113 
114 /* perform a splice operation on an individual edge */
115 static void splice(Agobj_t * obj, void *arg)
116 {
117  Agraph_t *g;
118  Agedge_t *e, *opp;
119  Agnode_t *target, *t, *h;
120  Agedge_t **dict_of_del, **dict_of_ins, **dict_of_relabel;
121  Agsplice_arg_t *spl;
122 
123  e = (Agedge_t *) obj;
124  g = agraphof(e);
125  t = AGTAIL(e);
126  h = AGHEAD(e);
127  opp = AGOPP(e);
128  spl = arg;
129  target = spl->target;
130 
131  /* set e to variant side, opp to invariant */
132  if ((e->node == h) != spl->head_side) {
133  Agedge_t *t = e;
134  e = opp;
135  opp = t;
136  }
137 
138  if (spl->head_side) {
139  dict_of_relabel = &(t->out);
140  dict_of_del = &(h->in);
141  dict_of_ins = &(target->in);
142  } else {
143  dict_of_relabel = &(h->in);
144  dict_of_del = &(t->out);
145  dict_of_ins = &(target->out);
146  }
147 
148  agdeledgeimage(g, dict_of_del, opp);
149  agdeledgeimage(g, dict_of_relabel, e);
150  e->node = target;
151  aginsedgeimage(g, dict_of_ins, opp);
152  aginsedgeimage(g, dict_of_relabel, e);
153 }
154 
155 int agsplice(Agedge_t * e, Agnode_t * target)
156 {
157  Agnode_t *t, *h;
158  Agraph_t *g, *root;
159  Agsplice_arg_t splice_arg;
160 
161 
162  if ((e == NILedge) || (e->node == target))
163  return FAILURE;
164  g = agraphof(e);
165  t = AGTAIL(e);
166  h = AGHEAD(e);
167  splice_arg.head_side = (e->node == h);
168  splice_arg.target = target;
169  root = agroot(g);
170  agapply(root, (Agobj_t *) e, splice, &splice_arg, TRUE);
171  return SUCCESS;
172 }
173 
174 Agnode_t *agcmpnode(Agraph_t * g, char *name)
175 {
176  Agnode_t *n;
177  Agraph_t *subg;
178  n = agnode(g, name, TRUE);
179  subg = agsubg(g, name);
180  if (n && g && agassociate(n, subg))
181  return n;
182  else
183  return NILnode;
184 }
185 
187 {
188  Agcmpnode_t *noderec;
189  Agcmpgraph_t *graphrec;
190 
191  if (agsubnode(sub, n, FALSE))
192  return FAILURE; /* avoid cycles */
193  noderec = agbindrec(n, Descriptor_id, sizeof(*noderec), FALSE);
194  graphrec = agbindrec(sub, Descriptor_id, sizeof(*graphrec), FALSE);
195  if (noderec->subg || graphrec->node)
196  return FAILURE;
197  noderec->subg = sub;
198  graphrec->node = n;
199  return SUCCESS;
200 }
201 
202 /* a utility function for aghide */
203 static void delete_outside_subg(Agraph_t * g, Agnode_t * node,
204  Agraph_t * subg)
205 {
206  Agraph_t *s, **subglist;
207  Agnode_t *n;
208  Agcmpgraph_t *graphrec;
209  Dict_t *d;
210 
211  if ((g != subg) && (n = agsubnode(g, (Agnode_t *) node, FALSE))) {
212  dtdelete(g->n_dict, n);
213 
214  graphrec = agbindrec(g, Descriptor_id, sizeof(*graphrec), FALSE);
215  if ((d = graphrec->hidden_node_set) == NIL(Dict_t *)) {
216  /* use name disc. to permit search for hidden node by name */
217  d = graphrec->hidden_node_set
218  = agdtopen(g, &Ag_node_name_disc, Dttree);
219  }
220  dtinsert(d, n);
221 
222  subglist = agsubglist(g);
223  while ((s = *subglist++))
224  delete_outside_subg(s, node, subg);
225  }
226 }
227 
228 /*
229  * when we hide a compound node (make it opaque)
230  * 1. hide its nodes (option)
231  * 2. hide the associated subgraph (option)
232  * 3. remap edges to internal nodes (option)
233  */
234 int aghide(Agnode_t * cmpnode)
235 {
236  Agcmpnode_t *noderec;
237  Agraph_t *g, *subg, *root;
238  Agnode_t *n, *nn, *rootn;
239  Agedge_t *e, *opp, *f;
240 
241  g = agraphof(cmpnode);
242  /* skip operation if node is not compound, or hidden */
243  if (agcmpgraph_of(cmpnode) == NILgraph)
244  return FAILURE;
245  noderec = (Agcmpnode_t *) aggetrec(cmpnode, Descriptor_id, FALSE);
246 
247  subg = noderec->subg;
248  root = agroot(g);
249 
250  /* make sure caller hasn't put a node "inside itself" */
251  if ((n = agsubnode(subg, cmpnode, FALSE)))
252  agdelnode(n);
253 
254  /* remap edges by splicing and saving previous endpt */
255  for (n = agfstnode(subg); n; n = agnxtnode(n)) {
256  rootn = agsubnode(root, n, FALSE);
257  for (e = agfstedge(rootn); e; e = f) {
258  f = agnxtedge(e, rootn);
259  if (agsubedge(subg, e, FALSE))
260  continue; /* an internal edge */
261  opp = AGOPP(e);
262  stackpush(save_stack_of(e, rootn), rootn, cmpnode);
263  agsplice(opp, cmpnode);
264  }
265  }
266 
267  /* hide nodes by deleting from the parent set. what if they also
268  belong to a sibling subg? weird. possible bug. */
269  for (n = agfstnode(subg); n; n = nn) {
270  nn = agnxtnode(n);
271  delete_outside_subg(root, n, subg);
272  }
273 
274  /* hide subgraph is easy */
275  agdelsubg(agparent(subg), subg);
276 
277  noderec->collapsed = TRUE;
278  g->desc.has_cmpnd = TRUE;
279  return SUCCESS;
280 }
281 
282 /* utility function for agexpose */
283 static void insert_outside_subg(Agraph_t * g, Agnode_t * node,
284  Agraph_t * subg)
285 {
286  Agraph_t *s, **subglist;
287  Agnode_t *n;
288  Agcmpgraph_t *graphrec;
289 
290  if ((g != subg)
291  && ((n = agsubnode(g, (Agnode_t *) node, FALSE)) == NILnode)) {
292  graphrec = (Agcmpgraph_t *) aggetrec(g, Descriptor_id, FALSE);
293  if (graphrec
294  &&
295  ((n = (Agnode_t *) dtsearch(graphrec->hidden_node_set, node))))
296  dtinsert(g->n_dict, n);
297 
298  subglist = agsubglist(g);
299  while ((s = *subglist++))
300  delete_outside_subg(s, node, subg);
301  }
302 }
303 
304 int agexpose(Agnode_t * cmpnode)
305 {
306  Agcmpnode_t *noderec;
307  Agcmpedge_t *edgerec;
308  Agraph_t *g, *subg, *root;
309  Agnode_t *n, *rootcmp;
310  Agedge_t *e, *f;
311  save_stack_t *stk;
312  save_e_t sav;
313  int i;
314 
315  g = agraphof(cmpnode);
316 
317  /* skip if this is not a collapsed subgraph */
318  noderec = (Agcmpnode_t *) aggetrec(cmpnode, Descriptor_id, FALSE);
319  if ((noderec == NIL(Agcmpnode_t *) || NOT(noderec->collapsed)))
320  return FAILURE;
321 
322  /* undo aghide (above) in reverse order. first, expose subgraph */
323  subg = noderec->subg;
324  agsubgrec_insert(agsubgrec(agparent(subg)), subg);
325 
326  /* re-insert nodes */
327  for (n = agfstnode(subg); n; n = agnxtnode(n))
328  insert_outside_subg(g, n, subg);
329 
330  /* re-splice the affected edges */
331  root = agroot(g);
332  rootcmp = agsubnode(root, cmpnode, FALSE);
333  for (e = agfstedge(rootcmp); e; e = f) {
334  f = agnxtedge(e, rootcmp);
335  if ((edgerec = (Agcmpedge_t *) aggetrec(e, Descriptor_id, FALSE))) {
336  /* anything interesting on either stack? */
337  for (i = 0; i < 2; i++) {
338  stk = &(edgerec->stack[i]);
339  sav = stacktop(stk);
340  if (sav.to && (AGID(sav.to) == AGID(cmpnode))) {
341  if (e->node != sav.to)
342  e = AGOPP(e);
343  agsplice(e, sav.from);
344  stackpop(stk);
345  continue;
346  }
347  }
348  }
349  }
350  noderec->collapsed = FALSE;
351  return SUCCESS;
352 }
353 
355 {
356  Agcmpnode_t *noderec;
357  noderec = (Agcmpnode_t *) aggetrec(n, Descriptor_id, FALSE);
358  if (noderec && NOT(noderec->collapsed))
359  return noderec->subg;
360  else
361  return NILgraph;
362 }
363 
365 {
366  Agcmpgraph_t *graphrec;
367  graphrec = (Agcmpgraph_t *) aggetrec(g, Descriptor_id, FALSE);
368  if (graphrec)
369  return graphrec->node;
370  else
371  return NILnode;
372 }
373 
374 Agnode_t *agfindhidden(Agraph_t * g, char *name)
375 {
376  Agcmpgraph_t *graphrec;
377  Agnode_t key;
378 
379  graphrec = (Agcmpgraph_t *) aggetrec(g, Descriptor_id, FALSE);
380  if (graphrec) {
381  key.name = name;
382  return (Agnode_t *) dtsearch(graphrec->hidden_node_set, &key);
383  } else
384  return NILnode;
385 }
#define AGOPP(e)
Definition: cgraph.h:403
CGRAPH_API Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition: node.c:142
save_e_t * mem
Definition: cmpnd.c:51
struct save_e_s save_e_t
#define SUCCESS
Definition: cghdr.h:62
CGRAPH_API int agdelnode(Agraph_t *g, Agnode_t *arg_n)
Definition: node.c:192
Agdesc_t desc
Definition: cgraph.h:241
save_stack_t stack[2]
Definition: cmpnd.c:57
#define AGID(obj)
Definition: cgraph.h:114
int collapsed
Definition: cmpnd.c:37
Agraph_t * agcmpgraph_of(Agnode_t *n)
Definition: cmpnd.c:354
#define dtdelete(d, o)
Definition: cdt.h:264
CGRAPH_API long agdelsubg(Agraph_t *g, Agraph_t *sub)
Definition: subg.c:93
Agnode_t * target
Definition: cmpnd.c:111
struct save_stack_s save_stack_t
int aghide(Agnode_t *cmpnode)
Definition: cmpnd.c:234
Definition: cmpnd.c:46
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
Agnode_t * agcmpnode_of(Agraph_t *g)
Definition: cmpnd.c:364
int agexpose(Agnode_t *cmpnode)
Definition: cmpnd.c:304
CGRAPH_API Agraph_t * agroot(void *obj)
Definition: obj.c:169
#define OUT_STACK
Definition: cmpnd.c:60
int head_side
Definition: cmpnd.c:110
int stacksize
Definition: cmpnd.c:52
CGRAPH_API Agraph_t * agraphof(void *obj)
Definition: obj.c:185
Agnode_t * agcmpnode(Agraph_t *g, char *name)
Definition: cmpnd.c:174
struct Agsplice_arg_s Agsplice_arg_t
Agnode_t * agfindhidden(Agraph_t *g, char *name)
Definition: cmpnd.c:374
CGRAPH_API void * agrealloc(Agraph_t *g, void *ptr, size_t oldsize, size_t size)
Definition: mem.c:72
CGRAPH_API Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition: subg.c:52
#define NILnode
Definition: cghdr.h:57
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
Agnode_t * node
Definition: cmpnd.c:42
#define NIL(t)
Definition: dthdr.h:13
Agnode_t * node
Definition: cgraph.h:143
#define dtsearch(d, o)
Definition: cdt.h:260
#define NILgraph
Definition: cghdr.h:56
#define FAILURE
Definition: cghdr.h:63
#define AGTAIL(e)
Definition: cgraph.h:406
CGRAPH_API Agraph_t * agparent(Agraph_t *g)
Definition: subg.c:85
void agdeledgeimage(Agraph_t *g, Agedge_t *edge, void *ignored)
Definition: edge.c:327
Agrec_t hdr
Definition: cmpnd.c:56
CGRAPH_API Agedge_t * agsubedge(Agraph_t *g, Agedge_t *e, int createflag)
Definition: edge.c:378
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
CGRAPH_API Agrec_t * aggetrec(void *obj, char *name, int move_to_front)
Definition: rec.c:34
Definition: grammar.c:79
Definition: cgraph.h:83
int agsplice(Agedge_t *e, Agnode_t *target)
Definition: cmpnd.c:155
#define dtinsert(d, o)
Definition: cdt.h:262
#define sub(h, i)
Definition: closest.c:75
Dict_t * agdtopen(Agraph_t *g, Dtdisc_t *disc, Dtmethod_t *method)
Definition: utils.c:53
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
Dict_t * hidden_node_set
Definition: cmpnd.c:43
CDT_API Dtmethod_t * Dttree
Definition: cdt.h:176
#define NOT(x)
Definition: cgraph.h:41
#define NILedge
Definition: cghdr.h:58
struct Agcmpnode_s Agcmpnode_t
Agnode_t * node(Agraph_t *g, char *name)
Definition: gv.cpp:103
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
Definition: cdt.h:99
#define IN_STACK
Definition: cmpnd.c:59
Agrec_t hdr
Definition: cmpnd.c:35
Agnode_t * from
Definition: cmpnd.c:47
int agassociate(Agnode_t *n, Agraph_t *sub)
Definition: cmpnd.c:186
struct Agcmpgraph_s Agcmpgraph_t
struct Agcmpedge_s Agcmpedge_t
Agrec_t hdr
Definition: cmpnd.c:41
Agraph_t * subg
Definition: cmpnd.c:36
#define AGHEAD(e)
Definition: cgraph.h:407
int agapply(Agraph_t *g, Agobj_t *obj, agobjfn_t fn, void *arg, int preorder)
Definition: apply.c:61
#define FALSE
Definition: cgraph.h:35
CGRAPH_API Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition: node.c:254
unsigned has_cmpnd
Definition: cgraph.h:158
Agnode_t * to
Definition: cmpnd.c:47
#define TRUE
Definition: cgraph.h:38