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