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
32typedef struct {
33 int cnt;
34 int sz;
35 Ppoly_t **obs;
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
44static 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
55static 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
64static 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 */
81static 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 */
93static void resetObjlist(objlist * l)
94{
95 l->cnt = 0;
96}
97
98/* makeClustObs:
99 * Create an obstacle corresponding to a cluster's bbox.
100 */
101static 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 */
149static void
150addGraphObjs(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 */
176static void
177raiseLevel(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 */
198static 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 */
255int 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}
320