Graphviz  2.39.20141220.0545
clusteredges.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 
15 /* clusteredges.c:
16  * Written by Emden R. Gansner
17  *
18  * Code for handling spline edges around clusters.
19  */
20 
21 /* uses PRIVATE interface */
22 #define FDP_PRIVATE 1
23 
24 #ifdef HAVE_CONFIG_H
25 #include <config.h>
26 #endif
27 
28 #include <clusteredges.h>
29 #include <fdp.h>
30 #include <neatoprocs.h>
31 #include "vispath.h"
32 
33 typedef struct {
34  int cnt;
35  int sz;
37 } objlist;
38 
39 /* addObj:
40  * Add an object to the list. The array is increased if necessary.
41  */
42 #define INIT_SZ 100
43 
44 #ifdef DEBUG
45 static void dumpObj(Ppoly_t * p)
46 {
47  int j;
48  Ppoint_t pt;
49  for (j = 0; j < p->pn; j++) {
50  pt = p->ps[j];
51  fprintf(stderr, " %.5g %.5g", pt.x, pt.y);
52  }
53  fputs("\n", stderr);
54 }
55 
56 static void dumpObjlist(objlist * l)
57 {
58  int i;
59  for (i = 0; i < l->cnt; i++) {
60  dumpObj(l->obs[i]);
61  }
62 }
63 #endif
64 
65 static void addObj(objlist * l, Ppoly_t * obj)
66 {
67  if (l->sz == l->cnt) {
68  if (l->obs) {
69  l->sz *= 2;
70  l->obs = RALLOC(l->sz, l->obs, Ppoly_t *);
71  } else {
72  l->obs = N_GNEW(INIT_SZ, Ppoly_t *);
73  l->sz = INIT_SZ;
74  }
75  }
76  l->obs[l->cnt++] = obj;
77 }
78 
79 /* freeObjlist:
80  * Release memory.
81  */
82 static void freeObjlist(objlist * l)
83 {
84  if (l) {
85  free(l->obs);
86  free(l);
87  }
88 }
89 
90 /* resetObjlist:
91  * Reset objlist so it can be reused, using
92  * the same memory.
93  */
94 static void resetObjlist(objlist * l)
95 {
96  l->cnt = 0;
97 }
98 
99 /* makeClustObs:
100  * Create an obstacle corresponding to a cluster's bbox.
101  */
102 static Ppoly_t *makeClustObs(graph_t * g, expand_t* pm)
103 {
104  Ppoly_t *obs = NEW(Ppoly_t);
105  boxf bb;
106  boxf newbb;
107  Ppoint_t ctr;
108 
109  bb = GD_bb(g);
110  obs->pn = 4;
111  obs->ps = N_NEW(4, Ppoint_t);
112 
113  ctr.x = (bb.UR.x + bb.LL.x) / 2.0;
114  ctr.y = (bb.UR.y + bb.LL.y) / 2.0;
115 
116  if (pm->doAdd) {
117  newbb.UR.x = bb.UR.x + pm->x;
118  newbb.UR.y = bb.UR.y + pm->y;
119  newbb.LL.x = bb.LL.x - pm->x;
120  newbb.LL.y = bb.LL.y - pm->y;
121  }
122  else {
123  double deltax = pm->x - 1.0;
124  double deltay = pm->y - 1.0;
125  newbb.UR.x = pm->x * bb.UR.x - deltax * ctr.x;
126  newbb.UR.y = pm->y * bb.UR.y - deltay * ctr.y;
127  newbb.LL.x = pm->x * bb.LL.x - deltax * ctr.x;
128  newbb.LL.y = pm->y * bb.LL.y - deltay * ctr.y;
129  }
130 
131  /* CW order */
132  obs->ps[0].x = newbb.LL.x;
133  obs->ps[0].y = newbb.LL.y;
134  obs->ps[1].x = newbb.LL.x;
135  obs->ps[1].y = newbb.UR.y;
136  obs->ps[2].x = newbb.UR.x;
137  obs->ps[2].y = newbb.UR.y;
138  obs->ps[3].x = newbb.UR.x;
139  obs->ps[3].y = newbb.LL.y;
140 
141  return obs;
142 }
143 
144 /* addGraphObjs:
145  * Add all top-level clusters and nodes with g as their smallest
146  * containing graph to the list l.
147  * Don't add any objects equal to tex or hex.
148  * Return the list.
149  */
150 static void
151 addGraphObjs(objlist * l, graph_t * g, void *tex, void *hex, expand_t* pm)
152 {
153  node_t *n;
154  graph_t *sg;
155  int i;
156 
157  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
158  if ((PARENT(n) == g) && (n != tex) && (n != hex)
159  && !IS_CLUST_NODE(n)) {
160  addObj(l, makeObstacle(n, pm, FALSE));
161  }
162  }
163  for (i = 1; i <= GD_n_cluster(g); i++) {
164  sg = GD_clust(g)[i];
165  if ((sg != tex) && (sg != hex)) {
166  addObj(l, makeClustObs(sg, pm));
167  }
168  }
169 }
170 
171 /* raiseLevel:
172  * Add barrier objects for node n, in graph *gp of level maxlvl, up to
173  * level minlvl.
174  * Assume maxlvl > minlvl.
175  * Return appended list, plus pass back last cluster processed in gp.
176  */
177 static void
178 raiseLevel(objlist * l, int maxlvl, void *ex, int minlvl, graph_t ** gp,
179  expand_t* pm)
180 {
181  graph_t *g = *gp;
182  int i;
183 
184  for (i = maxlvl; i > minlvl; i--) {
185  addGraphObjs(l, g, ex, NULL, pm);
186  ex = g;
187  g = GPARENT(g);
188  }
189  *gp = (graph_t *) ex;
190 }
191 
192 /* objectList:
193  * Create array of all objects (nodes and clusters) to be avoided
194  * when routing edge e. Make sure it never adds the endpoints of the
195  * edge, or any graph containing the endpoints.
196  * Return the list.
197  * Assume e is not a loop.
198  */
199 static objlist *objectList(edge_t * ep, expand_t* pm)
200 {
201  node_t *h = aghead(ep);
202  node_t *t = agtail(ep);
203  graph_t *hg = PARENT(h);
204  graph_t *tg = PARENT(t);
205  int hlevel;
206  int tlevel;
207  void *hex; /* Objects to be excluded from list */
208  void *tex;
209  objlist *list = NEW(objlist);
210 
211  /* If either endpoint is a cluster node, we move up one level */
212  if (IS_CLUST_NODE(h)) {
213  hex = hg;
214  hg = GPARENT(hg);
215  } else
216  hex = h;
217  if (IS_CLUST_NODE(t)) {
218  tex = tg;
219  tg = GPARENT(tg);
220  } else
221  tex = t;
222 
223  hlevel = LEVEL(hg);
224  tlevel = LEVEL(tg);
225  if (hlevel > tlevel) {
226  raiseLevel(list, hlevel, hex, tlevel, &hg, pm);
227  hex = hg;
228  hg = GPARENT(hg);
229  } else if (tlevel > hlevel) {
230  raiseLevel(list, tlevel, tex, hlevel, &tg, pm);
231  tex = tg;
232  tg = GPARENT(tg);
233  }
234 
235  /* hg and tg always have the same level */
236  while (hg != tg) {
237  addGraphObjs(list, hg, NULL, hex, pm);
238  addGraphObjs(list, tg, tex, NULL, pm);
239  hex = hg;
240  hg = GPARENT(hg);
241  tex = tg;
242  tg = GPARENT(tg);
243  }
244  addGraphObjs(list, tg, tex, hex, pm);
245 
246  return list;
247 }
248 
249 /* compoundEdges:
250  * Construct edges as splines, avoiding clusters when required.
251  * We still don't implement spline multiedges, so we just copy
252  * one spline to all the other edges.
253  * Returns 0 on success. Failure indicates the obstacle configuration
254  * for some edge had overlaps.
255  */
256 int compoundEdges(graph_t * g, expand_t* pm, int edgetype)
257 {
258  node_t *n;
259  node_t *head;
260  edge_t *e;
261  edge_t *e0;
262  objlist *objl = NULL;
263  path *P = NULL;
264  vconfig_t *vconfig;
265  int rv = 0;
266 
267  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
268  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
269  head = aghead(e);
270  if ((n == head) && ED_count(e)) { /* self arc */
271  if (!P) {
272  P = NEW(path);
273  P->boxes = N_NEW(agnnodes(g) + 20 * 2 * 9, boxf);
274  }
275  makeSelfArcs(P, e, GD_nodesep(g));
276  } else if (ED_count(e)) {
277  objl = objectList(e, pm);
278  if (Plegal_arrangement(objl->obs, objl->cnt)) {
279  vconfig = Pobsopen(objl->obs, objl->cnt);
280  if (!vconfig) {
281  agerr(AGWARN, "compoundEdges: could not construct obstacles - falling back to straight line edges\n");
282  rv = 1;
283  continue;
284  }
285  }
286  else {
287  if (Verbose)
288  fprintf(stderr,
289  "nodes touch - falling back to straight line edges\n");
290  rv = 1;
291  continue;
292  }
293 
294  /* For efficiency, it should be possible to copy the spline
295  * from the first edge to the rest. However, one has to deal
296  * with change in direction, different arrowheads, labels, etc.
297  */
298  for (e0 = e; e0; e0 = ED_to_virt(e0)) {
299  ED_path(e0) =
300  getPath(e0, vconfig, 0, objl->obs, objl->cnt);
301  makeSpline(g, e0, objl->obs, objl->cnt, FALSE);
302  }
303  resetObjlist(objl);
304  }
305  }
306  }
307  freeObjlist(objl);
308  if (P) {
309  free(P->boxes);
310  free(P);
311  }
312  return rv;
313 }
boolean doAdd
Definition: adjust.h:45
Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:494
#define RALLOC(size, ptr, type)
Definition: memory.h:42
void makeSpline(graph_t *, edge_t *, Ppoly_t **, int, boolean)
Definition: neatosplines.c:499
Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:502
#define N_NEW(n, t)
Definition: memory.h:36
int pn
Definition: pathgeom.h:36
double deltax
Definition: geometry.c:21
#define head
Definition: dthdr.h:26
#define GD_n_cluster(g)
Definition: types.h:376
char * hex[16]
Definition: colorutil.c:51
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
double x
Definition: pathgeom.h:27
int agnnodes(Agraph_t *g)
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:142
int compoundEdges(graph_t *g, expand_t *pm, int edgetype)
Definition: clusteredges.c:256
#define PARENT(n)
Definition: circular.h:89
boxf * boxes
Definition: types.h:104
Definition: cgraph.h:389
double deltay
Definition: geometry.c:21
Ppolyline_t getPath(edge_t *, vconfig_t *, int, Ppoly_t **, int)
Definition: neatosplines.c:444
void free()
int i
Definition: gvdevice.c:448
double y
Definition: geom.h:30
vconfig_t * Pobsopen(Ppoly_t **obs, int n_obs)
Definition: cvt.c:62
#define ED_count(e)
Definition: types.h:538
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
float y
Definition: adjust.h:44
#define INIT_SZ
Definition: clusteredges.c:42
Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define GD_clust(g)
Definition: types.h:344
Ppoint_t * ps
Definition: pathgeom.h:35
#define ED_to_virt(e)
Definition: types.h:556
#define NULL
Definition: logic.h:50
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
double x
Definition: geom.h:30
EXTERN unsigned char Verbose
Definition: globals.h:73
Ppoly_t * makeObstacle(node_t *n, expand_t *, boolean)
Definition: neatosplines.c:269
pointf LL
Definition: geom.h:37
Definition: types.h:101
#define ED_path(e)
Definition: types.h:550
#define IS_CLUST_NODE(n)
Definition: macros.h:30
Ppoly_t ** obs
Definition: clusteredges.c:36
#define GD_bb(g)
Definition: types.h:337
Definition: pathgeom.h:26
#define GD_nodesep(g)
Definition: types.h:382
double y
Definition: pathgeom.h:27
void makeSelfArcs(path *P, edge_t *e, int stepx)
Definition: neatosplines.c:228
float x
Definition: adjust.h:44
Definition: vis.h:38
pointf UR
Definition: geom.h:37
Definition: geom.h:37
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define FALSE
Definition: cgraph.h:24
#define NEW(t)
Definition: memory.h:35