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