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#include "config.h"
16
17#include "neato.h"
18#include "adjust.h"
19
20/* For precision, scale up before algorithms, then scale down */
21#define SCALE 10
22#define SCALE2 (SCALE/2)
23
24typedef struct nitem {
25 Dtlink_t link;
26 int val;
27 point pos; /* position for sorting */
28 node_t *np; /* base node */
29 node_t *cnode; /* corresponding node in constraint graph */
30 node_t *vnode; /* corresponding node in neighbor graph */
31 box bb;
32} nitem;
33
34typedef int (*distfn) (box *, box *);
35typedef int (*intersectfn) (nitem *, nitem *);
36
37static int cmpitem(Dt_t * d, int *p1, int *p2, Dtdisc_t * disc)
38{
39 NOTUSED(d);
40 NOTUSED(disc);
41
42 return (*p1 - *p2);
43}
44
45static Dtdisc_t constr = {
46 offsetof(nitem, val),
47 sizeof(int),
48 offsetof(nitem, link),
49 NIL(Dtmake_f),
50 NIL(Dtfree_f),
51 (Dtcompar_f) cmpitem,
52 NIL(Dthash_f),
53 NIL(Dtmemory_f),
54 NIL(Dtevent_f)
55};
56
57static int distY(box * b1, box * b2)
58{
59 return ((b1->UR.y - b1->LL.y) + (b2->UR.y - b2->LL.y)) / 2;
60}
61
62static int distX(box * b1, box * b2)
63{
64 return ((b1->UR.x - b1->LL.x) + (b2->UR.x - b2->LL.x)) / 2;
65}
66
67/* intersectX0:
68 * Return true if boxes could overlap if shifted in y but don't,
69 * or if actually overlap and an y move is smallest to remove overlap.
70 * Otherwise (no x overlap or a x move is smaller), return false.
71 * Assume q pos to above of p pos.
72 */
73static int intersectX0(nitem * p, nitem * q)
74{
75 int xdelta, ydelta;
76 int v = ((p->bb.LL.x <= q->bb.UR.x) && (q->bb.LL.x <= p->bb.UR.x));
77 if (v == 0) /* no x overlap */
78 return 0;
79 if (p->bb.UR.y < q->bb.LL.y) /* but boxes don't really overlap */
80 return 1;
81 ydelta = distY(&p->bb,&q->bb) - (q->pos.y - p->pos.y);
82 if (q->pos.x >= p->pos.x)
83 xdelta = distX(&p->bb,&q->bb) - (q->pos.x - p->pos.x);
84 else
85 xdelta = distX(&p->bb,&q->bb) - (p->pos.x - q->pos.x);
86 return (ydelta <= xdelta);
87}
88
89/* intersectY0:
90 * Return true if boxes could overlap if shifted in x but don't,
91 * or if actually overlap and an x move is smallest to remove overlap.
92 * Otherwise (no y overlap or a y move is smaller), return false.
93 * Assume q pos to right of p pos.
94 */
95static int intersectY0(nitem * p, nitem * q)
96{
97 int xdelta, ydelta;
98 int v = ((p->bb.LL.y <= q->bb.UR.y) && (q->bb.LL.y <= p->bb.UR.y));
99 if (v == 0) /* no y overlap */
100 return 0;
101 if (p->bb.UR.x < q->bb.LL.x) /* but boxes don't really overlap */
102 return 1;
103 xdelta = distX(&p->bb,&q->bb) - (q->pos.x - p->pos.x);
104 if (q->pos.y >= p->pos.y)
105 ydelta = distY(&p->bb,&q->bb) - (q->pos.y - p->pos.y);
106 else
107 ydelta = distY(&p->bb,&q->bb) - (p->pos.y - q->pos.y);
108 return (xdelta <= ydelta);
109}
110
111static int intersectY(nitem * p, nitem * q)
112{
113 return ((p->bb.LL.y <= q->bb.UR.y) && (q->bb.LL.y <= p->bb.UR.y));
114}
115
116static int intersectX(nitem * p, nitem * q)
117{
118 return ((p->bb.LL.x <= q->bb.UR.x) && (q->bb.LL.x <= p->bb.UR.x));
119}
120
121/* mapGraphs:
122 */
123static void mapGraphs(graph_t * g, graph_t * cg, distfn dist)
124{
125 node_t *n;
126 edge_t *e;
127 edge_t *ce;
128 node_t *t;
129 node_t *h;
130 nitem *tp;
131 nitem *hp;
132 int delta;
133
134 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
135 tp = (nitem *) ND_alg(n);
136 t = tp->cnode;
137 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
138 hp = (nitem *) ND_alg(aghead(e));
139 delta = dist(&tp->bb, &hp->bb);
140 h = hp->cnode;
141 ce = agedge(cg, t, h, NULL, 1);
142 agbindrec(ce, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE);
143 ED_weight(ce) = 1;
144 if (ED_minlen(ce) < delta) {
145 if (ED_minlen(ce) == 0.0) {
146 elist_append(ce, ND_out(t));
147 elist_append(ce, ND_in(h));
148 }
149 ED_minlen(ce) = delta;
150 }
151 }
152 }
153}
154
155#if DEBUG > 1
156static int
157indegree (graph_t * g, node_t *n)
158{
159 edge_t *e;
160 int cnt = 0;
161 for (e = agfstin(g,n); e; e = agnxtin(g,e)) cnt++;
162 return cnt;
163}
164
165static int
166outdegree (graph_t * g, node_t *n)
167{
168 edge_t *e;
169 int cnt = 0;
170 for (e = agfstout(g,n); e; e = agnxtout(g,e)) cnt++;
171 return cnt;
172}
173
174static void
175validate(graph_t * g)
176{
177 node_t *n;
178 edge_t *e;
179 int i, cnt;
180
181 cnt = 0;
182 for (n = GD_nlist(g);n; n = ND_next(n)) {
183 assert(outdegree(g,n) == ND_out(n).size);
184 for (i = 0; (e = ND_out(n).list[i]); i++) {
185 assert(agtail(e) == n);
186 assert( e == agfindedge(g, n, aghead(e)));
187 }
188 assert(indegree(g,n) == ND_in(n).size);
189 for (i = 0; (e = ND_in(n).list[i]); i++) {
190 assert(aghead(e) == n);
191 assert( e == agfindedge(g, agtail(e), n));
192 }
193 cnt++;
194 }
195
196 assert (agnnodes(g) == cnt);
197}
198#endif
199
200#ifdef OLD
201static node_t *newNode(graph_t * g)
202{
203 static int id = 0;
204 char buf[100];
205
206 sprintf(buf, "n%d", id++);
207 return agnode(g, buf);
208}
209#endif
210
211/* mkNConstraintG:
212 * Similar to mkConstraintG, except it doesn't enforce orthogonal
213 * ordering. If there is overlap, as defined by intersect, the
214 * nodes will kept/pushed apart in the current order. If not, no
215 * constraint is enforced. If a constraint edge is added, and it
216 * corresponds to a real edge, we increase the weight in an attempt
217 * to keep the resulting shift short.
218 */
219static graph_t *mkNConstraintG(graph_t * g, Dt_t * list,
220 intersectfn intersect, distfn dist)
221{
222 nitem *p;
223 nitem *nxp;
224 node_t *n;
225 edge_t *e;
226 node_t *lastn = NULL;
227 graph_t *cg = agopen("cg", Agstrictdirected, NIL(Agdisc_t *));
228 agbindrec(cg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); // graph custom data
229
230 for (p = (nitem *) dtflatten(list); p;
231 p = (nitem *) dtlink(list, (Dtlink_t *) p)) {
232 n = agnode(cg, agnameof(p->np), 1); /* FIX */
233 agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); //node custom data
234 ND_alg(n) = p;
235 p->cnode = n;
236 alloc_elist(0, ND_in(n));
237 alloc_elist(0, ND_out(n));
238 if (lastn) {
239 ND_next(lastn) = n;
240 lastn = n;
241 } else {
242 lastn = GD_nlist(cg) = n;
243 }
244 }
245 for (p = (nitem *) dtflatten(list); p;
246 p = (nitem *) dtlink(list, (Dtlink_t *) p)) {
247 for (nxp = (nitem *) dtlink(link, (Dtlink_t *) p); nxp;
248 nxp = (nitem *) dtlink(list, (Dtlink_t *) nxp)) {
249 e = NULL;
250 if (intersect(p, nxp)) {
251 double delta = dist(&p->bb, &nxp->bb);
252 e = agedge(cg, p->cnode, nxp->cnode, NULL, 1);
253 agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); // edge custom data
254 assert (delta <= 0xFFFF);
255 ED_minlen(e) = delta;
256 ED_weight(e) = 1;
257 }
258 if (e && agfindedge(g,p->np, nxp->np)) {
259 ED_weight(e) = 100;
260 }
261#if 0
262 if (agfindedge(g,p->np, nxp->np)) {
263 if (e == NULL)
264 e = agedge(cg, p->cnode, nxp->cnode);
265 ED_weight(e) = 100;
266 /* If minlen < SCALE, the nodes can't conflict or there's
267 * an overlap but it will be removed in the orthogonal pass.
268 * So we just keep the node's basically where they are.
269 */
270 if (SCALE > ED_minlen(e))
271 ED_minlen(e) = SCALE;
272 }
273#endif
274 }
275 }
276
277 for (p = (nitem *) dtflatten(list); p;
278 p = (nitem *) dtlink(list, (Dtlink_t *) p)) {
279 n = p->cnode;
280 for (e = agfstout(cg,n); e; e = agnxtout(cg,e)) {
281 elist_append(e, ND_out(n));
282 elist_append(e, ND_in(aghead(e)));
283 }
284 }
285
286 /* We could remove redundant constraints here. However, the cost of doing
287 * this may be a good deal more than the time saved in network simplex.
288 * Also, if the graph is changed, the ND_in and ND_out data has to be
289 * updated.
290 */
291 return cg;
292}
293/* mkConstraintG:
294 */
295static graph_t *mkConstraintG(graph_t * g, Dt_t * list,
296 intersectfn intersect, distfn dist)
297{
298 nitem *p;
299 nitem *nxt = NULL;
300 nitem *nxp;
301 graph_t *vg;
302 node_t *prev = NULL;
303 node_t *root = NULL;
304 node_t *n = NULL;
305 edge_t *e;
306 int lcnt, cnt;
307 int oldval = -INT_MAX;
308#ifdef OLD
309 double root_val;
310#endif
311 node_t *lastn = NULL;
312 graph_t *cg = agopen("cg", Agstrictdirected, NIL(Agdisc_t *));
313 agbindrec(cg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); // graph custom data
314
315 /* count distinct nodes */
316 cnt = 0;
317 for (p = (nitem *) dtflatten(list); p;
318 p = (nitem *) dtlink(list, (Dtlink_t *) p)) {
319 if (oldval != p->val) {
320 oldval = p->val;
321 cnt++;
322 }
323 }
324
325 /* construct basic chain to enforce left to right order */
326 oldval = -INT_MAX;
327 lcnt = 0;
328 for (p = (nitem *) dtflatten(list); p;
329 p = (nitem *) dtlink(list, (Dtlink_t *) p)) {
330 if (oldval != p->val) {
331 oldval = p->val;
332 /* n = newNode (cg); */
333 n = agnode(cg, agnameof(p->np), 1); /* FIX */
334 agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); //node custom data
335 ND_alg(n) = p;
336 if (root) {
337 ND_next(lastn) = n;
338 lastn = n;
339 } else {
340 root = n;
341#ifdef OLD
342 root_val = p->val;
343#endif
344 lastn = GD_nlist(cg) = n;
345 }
346 alloc_elist(lcnt, ND_in(n));
347 if (prev) {
348 if (prev == root)
349 alloc_elist(2 * (cnt - 1), ND_out(prev));
350 else
351 alloc_elist(cnt - lcnt - 1, ND_out(prev));
352 e = agedge(cg, prev, n, NULL, 1);
353 agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); // edge custom data
354 ED_minlen(e) = SCALE;
355 ED_weight(e) = 1;
356 elist_append(e, ND_out(prev));
357 elist_append(e, ND_in(n));
358 }
359 lcnt++;
360 prev = n;
361 }
362 p->cnode = n;
363 }
364 alloc_elist(0, ND_out(prev));
365
366 /* add immediate right neighbor constraints
367 * Construct visibility graph, then perform transitive reduction.
368 * Remaining outedges are immediate right neighbors.
369 * FIX: Incremental algorithm to construct trans. reduction?
370 */
371 vg = agopen("vg", Agstrictdirected, NIL(Agdisc_t *));
372 for (p = (nitem *) dtflatten(list); p;
373 p = (nitem *) dtlink(list, (Dtlink_t *) p)) {
374 n = agnode(vg, agnameof(p->np), 1); /* FIX */
375 agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); //node custom data
376 p->vnode = n;
377 ND_alg(n) = p;
378 }
379 oldval = -INT_MAX;
380 for (p = (nitem *) dtflatten(list); p;
381 p = (nitem *) dtlink(list, (Dtlink_t *) p)) {
382 if (oldval != p->val) { /* new pos: reset nxt */
383 oldval = p->val;
384 for (nxt = (nitem *) dtlink(link, (Dtlink_t *) p); nxt;
385 nxt = (nitem *) dtlink(list, (Dtlink_t *) nxt)) {
386 if (nxt->val != oldval)
387 break;
388 }
389 if (!nxt)
390 break;
391 }
392 for (nxp = nxt; nxp;
393 nxp = (nitem *) dtlink(list, (Dtlink_t *) nxp)) {
394 if (intersect(p, nxp))
395 agedge(vg, p->vnode, nxp->vnode, NULL, 1);
396 }
397 }
398
399 /* Remove redundant constraints here. However, the cost of doing this
400 * may be a good deal more than the time saved in network simplex. Also,
401 * if the graph is changed, the ND_in and ND_out data has to be updated.
402 */
403 mapGraphs(vg, cg, dist);
404 agclose(vg);
405
406 /* add dummy constraints for absolute values and initial positions */
407#ifdef OLD
408 for (n = agfstnode(cg); n; n = agnxtnode(cg, n)) {
409 node_t *vn; /* slack node for absolute value */
410 node_t *an; /* node representing original position */
411
412 p = (nitem *) ND_alg(n);
413 if ((n == root) || (!p))
414 continue;
415 vn = newNode(cg);
416 ND_next(lastn) = vn;
417 lastn = vn;
418 alloc_elist(0, ND_out(vn));
419 alloc_elist(2, ND_in(vn));
420 an = newNode(cg);
421 ND_next(lastn) = an;
422 lastn = an;
423 alloc_elist(1, ND_in(an));
424 alloc_elist(1, ND_out(an));
425
426 e = agedge(cg, root, an, 1);
427 ED_minlen(e) = p->val - root_val;
428 elist_append(e, ND_out(root));
429 elist_append(e, ND_in(an));
430
431 e = agedge(cg, an, vn, 1);
432 elist_append(e, ND_out(an));
433 elist_append(e, ND_in(vn));
434
435 e = agedge(cg, n, vn, 1);
436 elist_append(e, ND_out(n));
437 elist_append(e, ND_in(vn));
438 }
439#endif /* OLD */
440
441 return cg;
442}
443
444static void closeGraph(graph_t * cg)
445{
446 node_t *n;
447 for (n = agfstnode(cg); n; n = agnxtnode(cg, n)) {
448 free_list(ND_in(n));
449 free_list(ND_out(n));
450 }
451 agclose(cg);
452}
453
454/* constrainX:
455 * Create the X constrains and solve. We use a linear objective function
456 * (absolute values rather than squares), so we can reuse network simplex.
457 * The constraints are encoded as a dag with edges having a minimum length.
458 */
459static void constrainX(graph_t* g, nitem* nlist, int nnodes, intersectfn ifn,
460 int ortho)
461{
462 Dt_t *list = dtopen(&constr, Dtobag);
463 nitem *p = nlist;
464 graph_t *cg;
465 int i;
466
467 for (i = 0; i < nnodes; i++) {
468 p->val = p->pos.x;
469 dtinsert(list, p);
470 p++;
471 }
472 if (ortho)
473 cg = mkConstraintG(g, list, ifn, distX);
474 else
475 cg = mkNConstraintG(g, list, ifn, distX);
476 rank(cg, 2, INT_MAX);
477
478 p = nlist;
479 for (i = 0; i < nnodes; i++) {
480 int newpos, oldpos, delta;
481 oldpos = p->pos.x;
482 newpos = ND_rank(p->cnode);
483 delta = newpos - oldpos;
484 p->pos.x = newpos;
485 p->bb.LL.x += delta;
486 p->bb.UR.x += delta;
487 p++;
488 }
489
490 closeGraph(cg);
491 dtclose(list);
492}
493
494/* constrainY:
495 * See constrainX.
496 */
497static void constrainY(graph_t* g, nitem* nlist, int nnodes, intersectfn ifn,
498 int ortho)
499{
500 Dt_t *list = dtopen(&constr, Dtobag);
501 nitem *p = nlist;
502 graph_t *cg;
503 int i;
504
505 for (i = 0; i < nnodes; i++) {
506 p->val = p->pos.y;
507 dtinsert(list, p);
508 p++;
509 }
510 if (ortho)
511 cg = mkConstraintG(g, list, ifn, distY);
512 else
513 cg = mkNConstraintG(g, list, ifn, distY);
514 rank(cg, 2, INT_MAX);
515#ifdef DEBUG
516 {
517 Agsym_t *mlsym = agattr(cg, AGEDGE, "minlen", "");
518 Agsym_t *rksym = agattr(cg, AGNODE, "rank", "");
519 char buf[100];
520 node_t *n;
521 edge_t *e;
522 for (n = agfstnode(cg); n; n = agnxtnode(cg, n)) {
523 sprintf(buf, "%d", ND_rank(n));
524 agxset(n, rksym, buf);
525 for (e = agfstedge(cg, n); e; e = agnxtedge(cg, e, n)) {
526 sprintf(buf, "%d", ED_minlen(e));
527 agxset(e, mlsym, buf);
528 }
529 }
530 }
531#endif
532
533 p = nlist;
534 for (i = 0; i < nnodes; i++) {
535 int newpos, oldpos, delta;
536 oldpos = p->pos.y;
537 newpos = ND_rank(p->cnode);
538 delta = newpos - oldpos;
539 p->pos.y = newpos;
540 p->bb.LL.y += delta;
541 p->bb.UR.y += delta;
542 p++;
543 }
544
545 closeGraph(cg);
546 dtclose(list);
547}
548
549#define overlap(pb,qb) \
550 ((pb.LL.x <= qb.UR.x) && (qb.LL.x <= pb.UR.x) && \
551 (pb.LL.y <= qb.UR.y) && (qb.LL.y <= pb.UR.y))
552
553/* overlaps:
554 */
555static int overlaps(nitem * p, int cnt)
556{
557 int i, j;
558 nitem *pi = p;
559 nitem *pj;
560
561 for (i = 0; i < cnt - 1; i++) {
562 pj = pi + 1;
563 for (j = i + 1; j < cnt; j++) {
564 if (overlap(pi->bb, pj->bb))
565 return 1;
566 pj++;
567 }
568 pi++;
569 }
570 return 0;
571}
572
573/* initItem:
574 */
575static void initItem(node_t * n, nitem * p, expand_t margin)
576{
577 int x = POINTS(SCALE * ND_pos(n)[0]);
578 int y = POINTS(SCALE * ND_pos(n)[1]);
579 int w2, h2;
580 box b;
581
582 if (margin.doAdd) {
583 w2 = SCALE * (POINTS(ND_width(n)/2.0) + margin.x);
584 h2 = SCALE * (POINTS(ND_height(n)/2.0) + margin.y);
585 }
586 else {
587 w2 = POINTS(margin.x * SCALE2 * ND_width(n));
588 h2 = POINTS(margin.y * SCALE2 * ND_height(n));
589 }
590
591 b.LL.x = x - w2;
592 b.LL.y = y - h2;
593 b.UR.x = x + w2;
594 b.UR.y = y + h2;
595
596 p->pos.x = x;
597 p->pos.y = y;
598 p->np = n;
599 p->bb = b;
600}
601
602/* cAdjust:
603 * Use optimization to remove overlaps.
604 * Modifications;
605 * - do y;x then x;y and use the better one
606 * - for all overlaps (or if overlap with leftmost nodes), add a constraint;
607 * constraint could move both x and y away, or the smallest, or some
608 * mixture.
609 * - follow by a scale down using actual shapes
610 * We use an optimization based on Marriott, Stuckey, Tam and He,
611 * "Removing Node Overlapping in Graph Layout Using Constrained Optimization",
612 * Constraints,8(2):143--172, 2003.
613 * We solve 2 constraint problem, one in X, one in Y. In each dimension,
614 * we require relative positions to remain the same. That is, if two nodes
615 * have the same x originally, they have the same x at the end, and if one
616 * node is to the left of another, it remains to the left. In addition, if
617 * two nodes could overlap by moving their X coordinates, we insert a constraint * to keep the two nodes sufficiently apart. Similarly, for Y.
618 *
619 * mode = AM_ORTHOXY => first X, then Y
620 * mode = AM_ORTHOYX => first Y, then X
621 * mode = AM_ORTHO => first X, then Y
622 * mode = AM_ORTHO_YX => first Y, then X
623 * In the last 2 cases, relax the constraints as follows: during the X pass,
624 * if two nodes actually intersect and a smaller move in the Y direction
625 * will remove the overlap, we don't force the nodes apart in the X direction,
626 * but leave it for the Y pass to remove any remaining overlaps. Without this,
627 * the X pass will remove all overlaps, and the Y pass only compresses in the
628 * Y direction, causing a skewing of the aspect ratio.
629 *
630 * mode = AM_ORTHOXY => first X, then Y
631 * mode = AM_ORTHOYX => first Y, then X
632 * mode = AM_ORTHO => first X, then Y
633 * mode = AM_ORTHO_YX => first Y, then X
634 */
635int cAdjust(graph_t * g, int mode)
636{
637 expand_t margin;
638 int ret, i, nnodes = agnnodes(g);
639 nitem *nlist = N_GNEW(nnodes, nitem);
640 nitem *p = nlist;
641 node_t *n;
642
643 margin = sepFactor (g);
644
645 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
646 initItem(n, p, margin);
647 p++;
648 }
649
650 if (overlaps(nlist, nnodes)) {
651 point pt;
652
653 switch ((adjust_mode)mode) {
654 case AM_ORTHOXY:
655 constrainX(g, nlist, nnodes, intersectY, 1);
656 constrainY(g, nlist, nnodes, intersectX, 1);
657 break;
658 case AM_ORTHOYX:
659 constrainY(g, nlist, nnodes, intersectX, 1);
660 constrainX(g, nlist, nnodes, intersectY, 1);
661 break;
662 case AM_ORTHO :
663 constrainX(g, nlist, nnodes, intersectY0, 1);
664 constrainY(g, nlist, nnodes, intersectX, 1);
665 case AM_ORTHO_YX :
666 constrainY(g, nlist, nnodes, intersectX0, 1);
667 constrainX(g, nlist, nnodes, intersectY, 1);
668 case AM_PORTHOXY:
669 constrainX(g, nlist, nnodes, intersectY, 0);
670 constrainY(g, nlist, nnodes, intersectX, 0);
671 break;
672 case AM_PORTHOYX:
673 constrainY(g, nlist, nnodes, intersectX, 0);
674 constrainX(g, nlist, nnodes, intersectY, 0);
675 break;
676 case AM_PORTHO_YX :
677 constrainY(g, nlist, nnodes, intersectX0, 0);
678 constrainX(g, nlist, nnodes, intersectY, 0);
679 break;
680 case AM_PORTHO :
681 default :
682 constrainX(g, nlist, nnodes, intersectY0, 0);
683 constrainY(g, nlist, nnodes, intersectX, 0);
684 break;
685 }
686 p = nlist;
687 for (i = 0; i < nnodes; i++) {
688 n = p->np;
689 pt = p->pos;
690 ND_pos(n)[0] = PS2INCH(pt.x) / SCALE;
691 ND_pos(n)[1] = PS2INCH(pt.y) / SCALE;
692 p++;
693 }
694 ret = 1;
695 }
696 else ret = 0;
697 free(nlist);
698 return ret;
699}
700
701typedef struct {
702 pointf pos; /* position for sorting */
703 boxf bb;
704 double wd2;
705 double ht2;
706 node_t *np;
707} info;
708
709typedef int (*sortfn_t) (const void *, const void *);
710
711static int sortf(pointf * p, pointf * q)
712{
713 if (p->x < q->x)
714 return -1;
715 else if (p->x > q->x)
716 return 1;
717 else if (p->y < q->y)
718 return -1;
719 else if (p->y > q->y)
720 return 1;
721 else
722 return 0;
723}
724
725static double compress(info * nl, int nn)
726{
727 info *p = nl;
728 info *q;
729 int i, j;
730 double s, sc = 0;
731 pointf pt;
732
733 for (i = 0; i < nn; i++) {
734 q = p + 1;
735 for (j = i + 1; j < nn; j++) {
736 if (overlap(p->bb, q->bb))
737 return 0;
738 if (p->pos.x == q->pos.x)
739 pt.x = HUGE_VAL;
740 else {
741 pt.x = (p->wd2 + q->wd2) / fabs(p->pos.x - q->pos.x);
742 }
743 if (p->pos.y == q->pos.y)
744 pt.y = HUGE_VAL;
745 else {
746 pt.y = (p->ht2 + q->ht2) / fabs(p->pos.y - q->pos.y);
747 }
748 if (pt.y < pt.x)
749 s = pt.y;
750 else
751 s = pt.x;
752 if (s > sc)
753 sc = s;
754 q++;
755 }
756 p++;
757 }
758 return sc;
759}
760
761static pointf *mkOverlapSet(info * nl, int nn, int *cntp)
762{
763 info *p = nl;
764 info *q;
765 int sz = nn;
766 pointf *S = N_GNEW(sz + 1, pointf);
767 int i, j;
768 int cnt = 0;
769
770 for (i = 0; i < nn; i++) {
771 q = p + 1;
772 for (j = i + 1; j < nn; j++) {
773 if (overlap(p->bb, q->bb)) {
774 pointf pt;
775 if (cnt == sz) {
776 sz += nn;
777 S = RALLOC(sz + 1, S, pointf);
778 }
779 if (p->pos.x == q->pos.x)
780 pt.x = HUGE_VAL;
781 else {
782 pt.x = (p->wd2 + q->wd2) / fabs(p->pos.x - q->pos.x);
783 if (pt.x < 1)
784 pt.x = 1;
785 }
786 if (p->pos.y == q->pos.y)
787 pt.y = HUGE_VAL;
788 else {
789 pt.y = (p->ht2 + q->ht2) / fabs(p->pos.y - q->pos.y);
790 if (pt.y < 1)
791 pt.y = 1;
792 }
793 S[++cnt] = pt;
794 }
795 q++;
796 }
797 p++;
798 }
799
800 S = RALLOC(cnt + 1, S, pointf);
801 *cntp = cnt;
802 return S;
803}
804
805static pointf computeScaleXY(pointf * aarr, int m)
806{
807 pointf *barr;
808 double cost, bestcost;
809 int k, best = 0;
810 pointf scale;
811
812 aarr[0].x = 1;
813 aarr[0].y = HUGE_VAL;
814 qsort(aarr + 1, m, sizeof(pointf), (sortfn_t) sortf);
815
816 barr = N_GNEW(m + 1, pointf);
817 barr[m].x = aarr[m].x;
818 barr[m].y = 1;
819 for (k = m - 1; k >= 0; k--) {
820 barr[k].x = aarr[k].x;
821 barr[k].y = MAX(aarr[k + 1].y, barr[k + 1].y);
822 }
823
824 bestcost = HUGE_VAL;
825 for (k = 0; k <= m; k++) {
826 cost = barr[k].x * barr[k].y;
827 if (cost < bestcost) {
828 bestcost = cost;
829 best = k;
830 }
831 }
832 assert(bestcost < HUGE_VAL);
833 scale.x = barr[best].x;
834 scale.y = barr[best].y;
835
836 return scale;
837}
838
839/* computeScale:
840 * For each (x,y) in aarr, scale has to be bigger than the smallest one.
841 * So, the scale is the max min.
842 */
843static double computeScale(pointf * aarr, int m)
844{
845 int i;
846 double sc = 0;
847 double v;
848 pointf p;
849
850 aarr++;
851 for (i = 1; i <= m; i++) {
852 p = *aarr++;
853 v = MIN(p.x, p.y);
854 if (v > sc)
855 sc = v;
856 }
857 return sc;
858}
859
860/* scAdjust:
861 * Scale the layout.
862 * equal > 0 => scale uniformly in x and y to remove overlaps
863 * equal = 0 => scale separately in x and y to remove overlaps
864 * equal < 0 => scale down uniformly in x and y to remove excess space
865 * The last assumes there are no overlaps at present.
866 * Based on Marriott, Stuckey, Tam and He,
867 * "Removing Node Overlapping in Graph Layout Using Constrained Optimization",
868 * Constraints,8(2):143--172, 2003.
869 */
870int scAdjust(graph_t * g, int equal)
871{
872 int nnodes = agnnodes(g);
873 info *nlist = N_GNEW(nnodes, info);
874 info *p = nlist;
875 node_t *n;
876 pointf s;
877 int i;
878 expand_t margin;
879 pointf *aarr;
880 int m;
881
882 margin = sepFactor (g);
883 if (margin.doAdd) {
884 /* we use inches below */
885 margin.x = PS2INCH(margin.x);
886 margin.y = PS2INCH(margin.y);
887 }
888
889 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
890 double w2, h2;
891 if (margin.doAdd) {
892 w2 = (ND_width(n) / 2.0) + margin.x;
893 h2 = (ND_height(n) / 2.0) + margin.y;
894 }
895 else {
896 w2 = margin.x * ND_width(n) / 2.0;
897 h2 = margin.y * ND_height(n) / 2.0;
898 }
899 p->pos.x = ND_pos(n)[0];
900 p->pos.y = ND_pos(n)[1];
901 p->bb.LL.x = p->pos.x - w2;
902 p->bb.LL.y = p->pos.y - h2;
903 p->bb.UR.x = p->pos.x + w2;
904 p->bb.UR.y = p->pos.y + h2;
905 p->wd2 = w2;
906 p->ht2 = h2;
907 p->np = n;
908 p++;
909 }
910
911 if (equal < 0) {
912 s.x = s.y = compress(nlist, nnodes);
913 if (s.x == 0) { /* overlaps exist */
914 free(nlist);
915 return 0;
916 }
917 if (Verbose) fprintf(stderr, "compress %g \n", s.x);
918 } else {
919 aarr = mkOverlapSet(nlist, nnodes, &m);
920
921 if (m == 0) { /* no overlaps */
922 free(aarr);
923 free(nlist);
924 return 0;
925 }
926
927 if (equal) {
928 s.x = s.y = computeScale(aarr, m);
929 } else {
930 s = computeScaleXY(aarr, m);
931 }
932 free(aarr);
933 if (Verbose) fprintf(stderr, "scale by %g,%g \n", s.x, s.y);
934 }
935
936 p = nlist;
937 for (i = 0; i < nnodes; i++) {
938 ND_pos(p->np)[0] = s.x * p->pos.x;
939 ND_pos(p->np)[1] = s.y * p->pos.y;
940 p++;
941 }
942
943 free(nlist);
944 return 1;
945}
946