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/*
16 * position(g): set ND_coord(n) (x and y) for all nodes n of g, using GD_rank(g).
17 * (the graph may be modified by merging certain edges with a common endpoint.)
18 * the coordinates are computed by constructing and ranking an auxiliary graph.
19 * then leaf nodes are inserted in the fast graph. cluster boundary nodes are
20 * created and correctly separated.
21 */
22
23#include "dot.h"
24#include "aspect.h"
25
26static int nsiter2(graph_t * g);
27static void create_aux_edges(graph_t * g);
28static void remove_aux_edges(graph_t * g);
29static void set_xcoords(graph_t * g);
30static void set_ycoords(graph_t * g);
31static void set_aspect(graph_t * g, aspect_t* );
32static void expand_leaves(graph_t * g);
33static void make_lrvn(graph_t * g);
34static void contain_nodes(graph_t * g);
35static boolean idealsize(graph_t * g, double);
36
37#if DEBUG > 1
38static void
39dumpNS (graph_t * g)
40{
41 node_t* n = GD_nlist(g);
42 elist el;
43 edge_t* e;
44 int i;
45
46 while (n) {
47 el = ND_out(n);
48 for (i = 0; i < el.size; i++) {
49 e = el.list[i];
50 fprintf (stderr, "%s(%x) -> ", agnameof(agtail(e)),agtail(e));
51 fprintf (stderr, "%s(%x) : %d\n", agnameof(aghead(e)), aghead(e),
52 ED_minlen(e));
53 }
54 n = ND_next(n);
55 }
56}
57#endif
58
59static double
60largeMinlen (double l)
61{
62 agerr (AGERR, "Edge length %f larger than maximum %u allowed.\nCheck for overwide node(s).\n", l, USHRT_MAX);
63 return (double)USHRT_MAX;
64}
65
66/* connectGraph:
67 * When source and/or sink nodes are defined, it is possible that
68 * after the auxiliary edges are added, the graph may still have 2 or
69 * 3 components. To fix this, we put trivial constraints connecting the
70 * first items of each rank.
71 */
72static void
73connectGraph (graph_t* g)
74{
75 int i, j, r, found;
76 node_t* tp;
77 node_t* hp;
78 node_t* sn;
79 edge_t* e;
80 rank_t* rp;
81
82 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
83 rp = GD_rank(g)+r;
84 found =FALSE;
85 tp = NULL;
86 for (i = 0; i < rp->n; i++) {
87 tp = rp->v[i];
88 if (ND_save_out(tp).list) {
89 for (j = 0; (e = ND_save_out(tp).list[j]); j++) {
90 if ((ND_rank(aghead(e)) > r) || (ND_rank(agtail(e)) > r)) {
91 found = TRUE;
92 break;
93 }
94 }
95 if (found) break;
96 }
97 if (ND_save_in(tp).list) {
98 for (j = 0; (e = ND_save_in(tp).list[j]); j++) {
99 if ((ND_rank(agtail(e)) > r) || (ND_rank(aghead(e)) > r)) {
100 found = TRUE;
101 break;
102 }
103 }
104 if (found) break;
105 }
106 }
107 if (found || !tp) continue;
108 tp = rp->v[0];
109 if (r < GD_maxrank(g)) hp = (rp+1)->v[0];
110 else hp = (rp-1)->v[0];
111 assert (hp);
112 sn = virtual_node(g);
113 ND_node_type(sn) = SLACKNODE;
114 make_aux_edge(sn, tp, 0, 0);
115 make_aux_edge(sn, hp, 0, 0);
116 ND_rank(sn) = MIN(ND_rank(tp), ND_rank(hp));
117 }
118}
119
120void dot_position(graph_t * g, aspect_t* asp)
121{
122 if (GD_nlist(g) == NULL)
123 return; /* ignore empty graph */
124 mark_lowclusters(g); /* we could remove from splines.c now */
125 set_ycoords(g);
126 if (Concentrate)
127 dot_concentrate(g);
128 expand_leaves(g);
129 if (flat_edges(g))
130 set_ycoords(g);
131 create_aux_edges(g);
132 if (rank(g, 2, nsiter2(g))) { /* LR balance == 2 */
133 connectGraph (g);
134 const int rank_result = rank(g, 2, nsiter2(g));
135 assert(rank_result == 0);
136 }
137 set_xcoords(g);
138 set_aspect(g, asp);
139 remove_aux_edges(g); /* must come after set_aspect since we now
140 * use GD_ln and GD_rn for bbox width.
141 */
142}
143
144static int nsiter2(graph_t * g)
145{
146 int maxiter = INT_MAX;
147 char *s;
148
149 if ((s = agget(g, "nslimit")))
150 maxiter = atof(s) * agnnodes(g);
151 return maxiter;
152}
153
154static int go(node_t * u, node_t * v)
155{
156 int i;
157 edge_t *e;
158
159 if (u == v)
160 return TRUE;
161 for (i = 0; (e = ND_out(u).list[i]); i++) {
162 if (go(aghead(e), v))
163 return TRUE;
164 }
165 return FALSE;
166}
167
168static int canreach(node_t * u, node_t * v)
169{
170 return go(u, v);
171}
172
173edge_t *make_aux_edge(node_t * u, node_t * v, double len, int wt)
174{
175 edge_t *e;
176
177 Agedgepair_t* e2 = NEW(Agedgepair_t);
178 AGTYPE(&(e2->in)) = AGINEDGE;
179 AGTYPE(&(e2->out)) = AGOUTEDGE;
180 e2->out.base.data = (Agrec_t*)NEW(Agedgeinfo_t);
181 e = &(e2->out);
182
183 agtail(e) = u;
184 aghead(e) = v;
185 if (len > USHRT_MAX)
186 len = largeMinlen (len);
187 ED_minlen(e) = ROUND(len);
188 ED_weight(e) = wt;
189 fast_edge(e);
190 return e;
191}
192
193static void allocate_aux_edges(graph_t * g)
194{
195 int i, j, n_in;
196 node_t *n;
197
198 /* allocate space for aux edge lists */
199 for (n = GD_nlist(g); n; n = ND_next(n)) {
200 ND_save_in(n) = ND_in(n);
201 ND_save_out(n) = ND_out(n);
202 for (i = 0; ND_out(n).list[i]; i++);
203 for (j = 0; ND_in(n).list[j]; j++);
204 n_in = i + j;
205 alloc_elist(n_in + 3, ND_in(n));
206 alloc_elist(3, ND_out(n));
207 }
208}
209
210/* make_LR_constraints:
211 */
212static void
213make_LR_constraints(graph_t * g)
214{
215 int i, j, k;
216 int sw; /* self width */
217 int m0, m1;
218 double width;
219 int sep[2];
220 int nodesep; /* separation between nodes on same rank */
221 edge_t *e, *e0, *e1, *ff;
222 node_t *u, *v, *t0, *h0;
223 rank_t *rank = GD_rank(g);
224
225 /* Use smaller separation on odd ranks if g has edge labels */
226 if (GD_has_labels(g->root) & EDGE_LABEL) {
227 sep[0] = GD_nodesep(g);
228 sep[1] = 5;
229 }
230 else {
231 sep[1] = sep[0] = GD_nodesep(g);
232 }
233 /* make edges to constrain left-to-right ordering */
234 for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
235 double last;
236 last = ND_rank(rank[i].v[0]) = 0;
237 nodesep = sep[i & 1];
238 for (j = 0; j < rank[i].n; j++) {
239 u = rank[i].v[j];
240 ND_mval(u) = ND_rw(u); /* keep it somewhere safe */
241 if (ND_other(u).size > 0) { /* compute self size */
242 /* FIX: dot assumes all self-edges go to the right. This
243 * is no longer true, though makeSelfEdge still attempts to
244 * put as many as reasonable on the right. The dot code
245 * should be modified to allow a box reflecting the placement
246 * of all self-edges, and use that to reposition the nodes.
247 * Note that this would not only affect left and right
248 * positioning but may also affect interrank spacing.
249 */
250 sw = 0;
251 for (k = 0; (e = ND_other(u).list[k]); k++) {
252 if (agtail(e) == aghead(e)) {
253 sw += selfRightSpace (e);
254 }
255 }
256 ND_rw(u) += sw; /* increment to include self edges */
257 }
258 v = rank[i].v[j + 1];
259 if (v) {
260 width = ND_rw(u) + ND_lw(v) + nodesep;
261 e0 = make_aux_edge(u, v, width, 0);
262 last = (ND_rank(v) = last + width);
263 }
264
265 /* constraints from labels of flat edges on previous rank */
266 if ((e = (edge_t*)ND_alg(u))) {
267 e0 = ND_save_out(u).list[0];
268 e1 = ND_save_out(u).list[1];
269 if (ND_order(aghead(e0)) > ND_order(aghead(e1))) {
270 ff = e0;
271 e0 = e1;
272 e1 = ff;
273 }
274 m0 = (ED_minlen(e) * GD_nodesep(g)) / 2;
275 m1 = m0 + ND_rw(aghead(e0)) + ND_lw(agtail(e0));
276 /* these guards are needed because the flat edges
277 * work very poorly with cluster layout */
278 if (canreach(agtail(e0), aghead(e0)) == FALSE)
279 make_aux_edge(aghead(e0), agtail(e0), m1,
280 ED_weight(e));
281 m1 = m0 + ND_rw(agtail(e1)) + ND_lw(aghead(e1));
282 if (canreach(aghead(e1), agtail(e1)) == FALSE)
283 make_aux_edge(agtail(e1), aghead(e1), m1,
284 ED_weight(e));
285 }
286
287 /* position flat edge endpoints */
288 for (k = 0; k < ND_flat_out(u).size; k++) {
289 e = ND_flat_out(u).list[k];
290 if (ND_order(agtail(e)) < ND_order(aghead(e))) {
291 t0 = agtail(e);
292 h0 = aghead(e);
293 } else {
294 t0 = aghead(e);
295 h0 = agtail(e);
296 }
297
298 width = ND_rw(t0) + ND_lw(h0);
299 m0 = ED_minlen(e) * GD_nodesep(g) + width;
300
301 if ((e0 = find_fast_edge(t0, h0))) {
302 /* flat edge between adjacent neighbors
303 * ED_dist contains the largest label width.
304 */
305 m0 = MAX(m0, width + GD_nodesep(g) + ROUND(ED_dist(e)));
306 if (m0 > USHRT_MAX)
307 m0 = largeMinlen (m0);
308 ED_minlen(e0) = MAX(ED_minlen(e0), m0);
309 ED_weight(e0) = MAX(ED_weight(e0), ED_weight(e));
310 }
311 else if (!ED_label(e)) {
312 /* unlabeled flat edge between non-neighbors
313 * ED_minlen(e) is max of ED_minlen of all equivalent
314 * edges.
315 */
316 make_aux_edge(t0, h0, m0, ED_weight(e));
317 }
318 /* labeled flat edges between non-neighbors have already
319 * been constrained by the label above.
320 */
321 }
322 }
323 }
324}
325
326/* make_edge_pairs: make virtual edge pairs corresponding to input edges */
327static void make_edge_pairs(graph_t * g)
328{
329 int i, m0, m1;
330 node_t *n, *sn;
331 edge_t *e;
332
333 for (n = GD_nlist(g); n; n = ND_next(n)) {
334 if (ND_save_out(n).list)
335 for (i = 0; (e = ND_save_out(n).list[i]); i++) {
336 sn = virtual_node(g);
337 ND_node_type(sn) = SLACKNODE;
338 m0 = (ED_head_port(e).p.x - ED_tail_port(e).p.x);
339 if (m0 > 0)
340 m1 = 0;
341 else {
342 m1 = -m0;
343 m0 = 0;
344 }
345#ifdef NOTDEF
346/* was trying to improve LR balance */
347 if ((ND_save_out(n).size % 2 == 0)
348 && (i == ND_save_out(n).size / 2 - 1)) {
349 node_t *u = ND_save_out(n).list[i]->head;
350 node_t *v = ND_save_out(n).list[i + 1]->head;
351 double width = ND_rw(u) + ND_lw(v) + GD_nodesep(g);
352 m0 = width / 2 - 1;
353 }
354#endif
355 make_aux_edge(sn, agtail(e), m0 + 1, ED_weight(e));
356 make_aux_edge(sn, aghead(e), m1 + 1, ED_weight(e));
357 ND_rank(sn) =
358 MIN(ND_rank(agtail(e)) - m0 - 1,
359 ND_rank(aghead(e)) - m1 - 1);
360 }
361 }
362}
363
364static void contain_clustnodes(graph_t * g)
365{
366 int c;
367 edge_t *e;
368
369 if (g != dot_root(g)) {
370 contain_nodes(g);
371 if ((e = find_fast_edge(GD_ln(g),GD_rn(g)))) /* maybe from lrvn()?*/
372 ED_weight(e) += 128;
373 else
374 make_aux_edge(GD_ln(g), GD_rn(g), 1, 128); /* clust compaction edge */
375 }
376 for (c = 1; c <= GD_n_cluster(g); c++)
377 contain_clustnodes(GD_clust(g)[c]);
378}
379
380static int vnode_not_related_to(graph_t * g, node_t * v)
381{
382 edge_t *e;
383
384 if (ND_node_type(v) != VIRTUAL)
385 return FALSE;
386 for (e = ND_save_out(v).list[0]; ED_to_orig(e); e = ED_to_orig(e));
387 if (agcontains(g, agtail(e)))
388 return FALSE;
389 if (agcontains(g, aghead(e)))
390 return FALSE;
391 return TRUE;
392}
393
394/* keepout_othernodes:
395 * Guarantee nodes outside the cluster g are placed outside of it.
396 * This is done by adding constraints to make sure such nodes have
397 * a gap of margin from the left or right bounding box node ln or rn.
398 *
399 * We could probably reduce some of these constraints by checking if
400 * the node is in a cluster, since elsewhere we make constrain a
401 * separate between clusters. Also, we should be able to skip the
402 * first loop if g is the root graph.
403 */
404static void keepout_othernodes(graph_t * g)
405{
406 int i, c, r, margin;
407 node_t *u, *v;
408
409 margin = late_int (g, G_margin, CL_OFFSET, 0);
410 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
411 if (GD_rank(g)[r].n == 0)
412 continue;
413 v = GD_rank(g)[r].v[0];
414 if (v == NULL)
415 continue;
416 for (i = ND_order(v) - 1; i >= 0; i--) {
417 u = GD_rank(dot_root(g))[r].v[i];
418 /* can't use "is_a_vnode_of" because elists are swapped */
419 if ((ND_node_type(u) == NORMAL) || vnode_not_related_to(g, u)) {
420 make_aux_edge(u, GD_ln(g), margin + ND_rw(u), 0);
421 break;
422 }
423 }
424 for (i = ND_order(v) + GD_rank(g)[r].n; i < GD_rank(dot_root(g))[r].n;
425 i++) {
426 u = GD_rank(dot_root(g))[r].v[i];
427 if ((ND_node_type(u) == NORMAL) || vnode_not_related_to(g, u)) {
428 make_aux_edge(GD_rn(g), u, margin + ND_lw(u), 0);
429 break;
430 }
431 }
432 }
433
434 for (c = 1; c <= GD_n_cluster(g); c++)
435 keepout_othernodes(GD_clust(g)[c]);
436}
437
438/* contain_subclust:
439 * Make sure boxes of subclusters of g are offset from the
440 * box of g. This is done by a constraint between the left and
441 * right bounding box nodes ln and rn of g and a subcluster.
442 * The gap needs to include any left or right labels.
443 */
444static void contain_subclust(graph_t * g)
445{
446 int margin, c;
447 graph_t *subg;
448
449 margin = late_int (g, G_margin, CL_OFFSET, 0);
450 make_lrvn(g);
451 for (c = 1; c <= GD_n_cluster(g); c++) {
452 subg = GD_clust(g)[c];
453 make_lrvn(subg);
454 make_aux_edge(GD_ln(g), GD_ln(subg),
455 margin + GD_border(g)[LEFT_IX].x, 0);
456 make_aux_edge(GD_rn(subg), GD_rn(g),
457 margin + GD_border(g)[RIGHT_IX].x, 0);
458 contain_subclust(subg);
459 }
460}
461
462/* separate_subclust:
463 * Guarantee space between subcluster of g.
464 * This is done by adding a constraint between the right bbox node rn
465 * of the left cluster and the left bbox node ln of the right cluster.
466 * This is only done if the two clusters overlap in some rank.
467 */
468static void separate_subclust(graph_t * g)
469{
470 int i, j, margin;
471 graph_t *low, *high;
472 graph_t *left, *right;
473
474 margin = late_int (g, G_margin, CL_OFFSET, 0);
475 for (i = 1; i <= GD_n_cluster(g); i++)
476 make_lrvn(GD_clust(g)[i]);
477 for (i = 1; i <= GD_n_cluster(g); i++) {
478 for (j = i + 1; j <= GD_n_cluster(g); j++) {
479 low = GD_clust(g)[i];
480 high = GD_clust(g)[j];
481 if (GD_minrank(low) > GD_minrank(high)) {
482 graph_t *temp = low;
483 low = high;
484 high = temp;
485 }
486 if (GD_maxrank(low) < GD_minrank(high))
487 continue;
488 if (ND_order(GD_rank(low)[GD_minrank(high)].v[0])
489 < ND_order(GD_rank(high)[GD_minrank(high)].v[0])) {
490 left = low;
491 right = high;
492 } else {
493 left = high;
494 right = low;
495 }
496 make_aux_edge(GD_rn(left), GD_ln(right), margin, 0);
497 }
498 separate_subclust(GD_clust(g)[i]);
499 }
500}
501
502/* pos_clusters: create constraints for:
503 * node containment in clusters,
504 * cluster containment in clusters,
505 * separation of sibling clusters.
506 */
507static void pos_clusters(graph_t * g)
508{
509 if (GD_n_cluster(g) > 0) {
510 contain_clustnodes(g);
511 keepout_othernodes(g);
512 contain_subclust(g);
513 separate_subclust(g);
514 }
515}
516
517static void compress_graph(graph_t * g)
518{
519 double x;
520 pointf p;
521
522 if (GD_drawing(g)->ratio_kind != R_COMPRESS)
523 return;
524 p = GD_drawing(g)->size;
525 if (p.x * p.y <= 1)
526 return;
527 contain_nodes(g);
528 if (GD_flip(g) == FALSE)
529 x = p.x;
530 else
531 x = p.y;
532
533 /* Guard against huge size attribute since max. edge length is USHRT_MAX
534 * A warning might be called for. Also, one could check that the graph
535 * already fits GD_drawing(g)->size and return immediately.
536 */
537 x = MIN(x,USHRT_MAX);
538 make_aux_edge(GD_ln(g), GD_rn(g), x, 1000);
539}
540
541static void create_aux_edges(graph_t * g)
542{
543 allocate_aux_edges(g);
544 make_LR_constraints(g);
545 make_edge_pairs(g);
546 pos_clusters(g);
547 compress_graph(g);
548}
549
550static void remove_aux_edges(graph_t * g)
551{
552 int i;
553 node_t *n, *nnext, *nprev;
554 edge_t *e;
555
556 for (n = GD_nlist(g); n; n = ND_next(n)) {
557 for (i = 0; (e = ND_out(n).list[i]); i++) {
558 free(e->base.data);
559 free(e);
560 }
561 free_list(ND_out(n));
562 free_list(ND_in(n));
563 ND_out(n) = ND_save_out(n);
564 ND_in(n) = ND_save_in(n);
565 }
566 /* cannot be merged with previous loop */
567 nprev = NULL;
568 for (n = GD_nlist(g); n; n = nnext) {
569 nnext = ND_next(n);
570 if (ND_node_type(n) == SLACKNODE) {
571 if (nprev)
572 ND_next(nprev) = nnext;
573 else
574 GD_nlist(g) = nnext;
575 free(n->base.data);
576 free(n);
577 } else
578 nprev = n;
579 }
580 ND_prev(GD_nlist(g)) = NULL;
581}
582
583/* set_xcoords:
584 * Set x coords of nodes.
585 */
586static void
587set_xcoords(graph_t * g)
588{
589 int i, j;
590 node_t *v;
591 rank_t *rank = GD_rank(g);
592
593 for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
594 for (j = 0; j < rank[i].n; j++) {
595 v = rank[i].v[j];
596 ND_coord(v).x = ND_rank(v);
597 ND_rank(v) = i;
598 }
599 }
600}
601
602/* adjustSimple:
603 * Expand cluster height by delta, adding half to top
604 * and half to bottom. If the bottom expansion exceeds the
605 * ht1 of the rank, shift the ranks in the cluster up.
606 * If the top expansion, including any shift from the bottom
607 * expansion, exceeds to ht2 of the rank, shift the ranks above
608 * the cluster up.
609 *
610 * FIX: There can be excess space between ranks. Not sure where this is
611 * coming from but it could be cleaned up.
612 */
613static void adjustSimple(graph_t * g, int delta, int margin_total)
614{
615 int r, bottom, deltop, delbottom;
616 graph_t *root = dot_root(g);
617 rank_t *rank = GD_rank(root);
618 int maxr = GD_maxrank(g);
619 int minr = GD_minrank(g);
620
621 bottom = (delta+1) / 2;
622 delbottom = GD_ht1(g) + bottom - (rank[maxr].ht1 - margin_total);
623 if (delbottom > 0) {
624 for (r = maxr; r >= minr; r--) {
625 if (rank[r].n > 0)
626 ND_coord(rank[r].v[0]).y += delbottom;
627 }
628 deltop = GD_ht2(g) + (delta-bottom) + delbottom - (rank[minr].ht2 - margin_total);
629 }
630 else
631 deltop = GD_ht2(g) + (delta-bottom) - (rank[minr].ht2 - margin_total);
632 if (deltop > 0) {
633 for (r = minr-1; r >= GD_minrank(root); r--) {
634 if (rank[r].n > 0)
635 ND_coord(rank[r].v[0]).y += deltop;
636 }
637 }
638 GD_ht2(g) += (delta - bottom);
639 GD_ht1(g) += bottom;
640}
641
642/* adjustRanks:
643 * Recursively adjust ranks to take into account
644 * wide cluster labels when rankdir=LR.
645 * We divide the extra space between the top and bottom.
646 * Adjust the ht1 and ht2 values in the process.
647 */
648static void adjustRanks(graph_t * g, int margin_total)
649{
650 double lht; /* label height */
651 double rht; /* height between top and bottom ranks */
652 int maxr, minr, margin;
653 int c;
654 double delta, ht1, ht2;
655
656 rank_t *rank = GD_rank(dot_root(g));
657 if (g == dot_root(g))
658 margin = 0;
659 else
660 margin = late_int (g, G_margin, CL_OFFSET, 0);
661
662 ht1 = GD_ht1(g);
663 ht2 = GD_ht2(g);
664
665 for (c = 1; c <= GD_n_cluster(g); c++) {
666 graph_t *subg = GD_clust(g)[c];
667 adjustRanks(subg, margin+margin_total);
668 if (GD_maxrank(subg) == GD_maxrank(g))
669 ht1 = MAX(ht1, GD_ht1(subg) + margin);
670 if (GD_minrank(subg) == GD_minrank(g))
671 ht2 = MAX(ht2, GD_ht2(subg) + margin);
672 }
673
674 GD_ht1(g) = ht1;
675 GD_ht2(g) = ht2;
676
677 if ((g != dot_root(g)) && GD_label(g)) {
678 lht = MAX(GD_border(g)[LEFT_IX].y, GD_border(g)[RIGHT_IX].y);
679 maxr = GD_maxrank(g);
680 minr = GD_minrank(g);
681 rht = ND_coord(rank[minr].v[0]).y - ND_coord(rank[maxr].v[0]).y;
682 delta = lht - (rht + ht1 + ht2);
683 if (delta > 0) {
684 adjustSimple(g, delta, margin_total);
685 }
686 }
687
688 /* update the global ranks */
689 if (g != dot_root(g)) {
690 rank[GD_minrank(g)].ht2 = MAX(rank[GD_minrank(g)].ht2, GD_ht2(g));
691 rank[GD_maxrank(g)].ht1 = MAX(rank[GD_maxrank(g)].ht1, GD_ht1(g));
692 }
693}
694
695/* clust_ht:
696 * recursively compute cluster ht requirements. assumes GD_ht1(subg) and ht2
697 * are computed from primitive nodes only. updates ht1 and ht2 to reflect
698 * cluster nesting and labels. also maintains global rank ht1 and ht2.
699 * Return true if some cluster has a label.
700 */
701static int clust_ht(Agraph_t * g)
702{
703 int c;
704 double ht1, ht2;
705 graph_t *subg;
706 rank_t *rank = GD_rank(dot_root(g));
707 int margin, haveClustLabel = 0;
708
709 if (g == dot_root(g))
710 margin = CL_OFFSET;
711 else
712 margin = late_int (g, G_margin, CL_OFFSET, 0);
713
714 ht1 = GD_ht1(g);
715 ht2 = GD_ht2(g);
716
717 /* account for sub-clusters */
718 for (c = 1; c <= GD_n_cluster(g); c++) {
719 subg = GD_clust(g)[c];
720 haveClustLabel |= clust_ht(subg);
721 if (GD_maxrank(subg) == GD_maxrank(g))
722 ht1 = MAX(ht1, GD_ht1(subg) + margin);
723 if (GD_minrank(subg) == GD_minrank(g))
724 ht2 = MAX(ht2, GD_ht2(subg) + margin);
725 }
726
727 /* account for a possible cluster label in clusters */
728 /* room for root graph label is handled in dotneato_postprocess */
729 if ((g != dot_root(g)) && GD_label(g)) {
730 haveClustLabel = 1;
731 if (!GD_flip(agroot(g))) {
732 ht1 += GD_border(g)[BOTTOM_IX].y;
733 ht2 += GD_border(g)[TOP_IX].y;
734 }
735 }
736 GD_ht1(g) = ht1;
737 GD_ht2(g) = ht2;
738
739 /* update the global ranks */
740 if (g != dot_root(g)) {
741 rank[GD_minrank(g)].ht2 = MAX(rank[GD_minrank(g)].ht2, ht2);
742 rank[GD_maxrank(g)].ht1 = MAX(rank[GD_maxrank(g)].ht1, ht1);
743 }
744
745 return haveClustLabel;
746}
747
748/* set y coordinates of nodes, a rank at a time */
749static void set_ycoords(graph_t * g)
750{
751 int i, j, r;
752 double ht2, maxht, delta, d0, d1;
753 node_t *n;
754 edge_t *e;
755 rank_t *rank = GD_rank(g);
756 graph_t *clust;
757 int lbl;
758
759 ht2 = maxht = 0;
760
761 /* scan ranks for tallest nodes. */
762 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
763 for (i = 0; i < rank[r].n; i++) {
764 n = rank[r].v[i];
765
766 /* assumes symmetry, ht1 = ht2 */
767 ht2 = ND_ht(n) / 2;
768
769
770 /* have to look for high self-edge labels, too */
771 if (ND_other(n).list)
772 for (j = 0; (e = ND_other(n).list[j]); j++) {
773 if (agtail(e) == aghead(e)) {
774 if (ED_label(e))
775 ht2 = MAX(ht2, ED_label(e)->dimen.y / 2);
776 }
777 }
778
779 /* update global rank ht */
780 if (rank[r].pht2 < ht2)
781 rank[r].pht2 = rank[r].ht2 = ht2;
782 if (rank[r].pht1 < ht2)
783 rank[r].pht1 = rank[r].ht1 = ht2;
784
785 /* update nearest enclosing cluster rank ht */
786 if ((clust = ND_clust(n))) {
787 int yoff = (clust == g ? 0 : late_int (clust, G_margin, CL_OFFSET, 0));
788 if (ND_rank(n) == GD_minrank(clust))
789 GD_ht2(clust) = MAX(GD_ht2(clust), ht2 + yoff);
790 if (ND_rank(n) == GD_maxrank(clust))
791 GD_ht1(clust) = MAX(GD_ht1(clust), ht2 + yoff);
792 }
793 }
794 }
795
796 /* scan sub-clusters */
797 lbl = clust_ht(g);
798
799 /* make the initial assignment of ycoords to leftmost nodes by ranks */
800 maxht = 0;
801 r = GD_maxrank(g);
802 (ND_coord(rank[r].v[0])).y = rank[r].ht1;
803 while (--r >= GD_minrank(g)) {
804 d0 = rank[r + 1].pht2 + rank[r].pht1 + GD_ranksep(g); /* prim node sep */
805 d1 = rank[r + 1].ht2 + rank[r].ht1 + CL_OFFSET; /* cluster sep */
806 delta = MAX(d0, d1);
807 if (rank[r].n > 0) /* this may reflect some problem */
808 (ND_coord(rank[r].v[0])).y = (ND_coord(rank[r + 1].v[0])).y + delta;
809#ifdef DEBUG
810 else
811 fprintf(stderr, "dot set_ycoords: rank %d is empty\n",
812 rank[r].n);
813#endif
814 maxht = MAX(maxht, delta);
815 }
816
817 /* If there are cluster labels and the drawing is rotated, we need special processing to
818 * allocate enough room. We use adjustRanks for this, and then recompute the maxht if
819 * the ranks are to be equally spaced. This seems simpler and appears to work better than
820 * handling equal spacing as a special case.
821 */
822 if (lbl && GD_flip(g)) {
823 adjustRanks(g, 0);
824 if (GD_exact_ranksep(g)) { /* recompute maxht */
825 maxht = 0;
826 r = GD_maxrank(g);
827 d0 = (ND_coord(rank[r].v[0])).y;
828 while (--r >= GD_minrank(g)) {
829 d1 = (ND_coord(rank[r].v[0])).y;
830 delta = d1 - d0;
831 maxht = MAX(maxht, delta);
832 d0 = d1;
833 }
834 }
835 }
836
837 /* re-assign if ranks are equally spaced */
838 if (GD_exact_ranksep(g)) {
839 for (r = GD_maxrank(g) - 1; r >= GD_minrank(g); r--)
840 if (rank[r].n > 0) /* this may reflect the same problem :-() */
841 (ND_coord(rank[r].v[0])).y=
842 (ND_coord(rank[r + 1].v[0])).y + maxht;
843 }
844
845 /* copy ycoord assignment from leftmost nodes to others */
846 for (n = GD_nlist(g); n; n = ND_next(n))
847 ND_coord(n).y = (ND_coord(rank[ND_rank(n)].v[0])).y;
848}
849
850/* dot_compute_bb:
851 * Compute bounding box of g.
852 * The x limits of clusters are given by the x positions of ln and rn.
853 * This information is stored in the rank field, since it was calculated
854 * using network simplex.
855 * For the root graph, we don't enforce all the constraints on lr and
856 * rn, so we traverse the nodes and subclusters.
857 */
858static void dot_compute_bb(graph_t * g, graph_t * root)
859{
860 int r, c;
861 double x, offset;
862 node_t *v;
863 pointf LL, UR;
864
865 if (g == dot_root(g)) {
866 LL.x = (double)(INT_MAX);
867 UR.x = (double)(-INT_MAX);
868 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
869 int rnkn = GD_rank(g)[r].n;
870 if (rnkn == 0)
871 continue;
872 if ((v = GD_rank(g)[r].v[0]) == NULL)
873 continue;
874 for (c = 1; (ND_node_type(v) != NORMAL) && c < rnkn; c++)
875 v = GD_rank(g)[r].v[c];
876 if (ND_node_type(v) == NORMAL) {
877 x = ND_coord(v).x - ND_lw(v);
878 LL.x = MIN(LL.x, x);
879 }
880 else continue;
881 /* At this point, we know the rank contains a NORMAL node */
882 v = GD_rank(g)[r].v[rnkn - 1];
883 for (c = rnkn-2; ND_node_type(v) != NORMAL; c--)
884 v = GD_rank(g)[r].v[c];
885 x = ND_coord(v).x + ND_rw(v);
886 UR.x = MAX(UR.x, x);
887 }
888 offset = CL_OFFSET;
889 for (c = 1; c <= GD_n_cluster(g); c++) {
890 x = (double)(GD_bb(GD_clust(g)[c]).LL.x - offset);
891 LL.x = MIN(LL.x, x);
892 x = (double)(GD_bb(GD_clust(g)[c]).UR.x + offset);
893 UR.x = MAX(UR.x, x);
894 }
895 } else {
896 LL.x = (double)(ND_rank(GD_ln(g)));
897 UR.x = (double)(ND_rank(GD_rn(g)));
898 }
899 LL.y = ND_coord(GD_rank(root)[GD_maxrank(g)].v[0]).y - GD_ht1(g);
900 UR.y = ND_coord(GD_rank(root)[GD_minrank(g)].v[0]).y + GD_ht2(g);
901 GD_bb(g).LL = LL;
902 GD_bb(g).UR = UR;
903}
904
905static void rec_bb(graph_t * g, graph_t * root)
906{
907 int c;
908 for (c = 1; c <= GD_n_cluster(g); c++)
909 rec_bb(GD_clust(g)[c], root);
910 dot_compute_bb(g, root);
911}
912
913/* scale_bb:
914 * Recursively rescale all bounding boxes using scale factors
915 * xf and yf. We assume all the bboxes have been computed.
916 */
917static void scale_bb(graph_t * g, graph_t * root, double xf, double yf)
918{
919 int c;
920
921 for (c = 1; c <= GD_n_cluster(g); c++)
922 scale_bb(GD_clust(g)[c], root, xf, yf);
923 GD_bb(g).LL.x *= xf;
924 GD_bb(g).LL.y *= yf;
925 GD_bb(g).UR.x *= xf;
926 GD_bb(g).UR.y *= yf;
927}
928
929/* adjustAspectRatio:
930 */
931static void adjustAspectRatio (graph_t* g, aspect_t* asp)
932{
933 double AR = (GD_bb(g).UR.x - GD_bb(g).LL.x)/(GD_bb(g).UR.y - GD_bb(g).LL.y);
934 if (Verbose) {
935 fprintf(stderr, "AR=%0.4lf\t Area= %0.4lf\t", AR, (double)(GD_bb(g).UR.x - GD_bb(g).LL.x)*(GD_bb(g).UR.y - GD_bb(g).LL.y)/10000.0);
936 fprintf(stderr, "Dummy=%d\n", countDummyNodes(g));
937 }
938 if (AR > 1.1*asp->targetAR) {
939 asp->nextIter = (int)(asp->targetAR * (double)(asp->curIterations - asp->prevIterations)/(AR));
940 }
941 else if (AR <= 0.8 * asp->targetAR) {
942 asp->nextIter = -1;
943 if (Verbose)
944 fprintf(stderr, "Going to apply another expansion.\n");
945 }
946 else {
947 asp->nextIter = 0;
948 }
949 if (Verbose)
950 fprintf(stderr, "next#iter=%d\n", asp->nextIter);
951}
952
953/* set_aspect:
954 * Set bounding boxes and, if ratio is set, rescale graph.
955 * Note that if some dimension shrinks, there may be problems
956 * with labels.
957 */
958static void set_aspect(graph_t * g, aspect_t* asp)
959{
960 double xf = 0.0, yf = 0.0, actual, desired;
961 node_t *n;
962 boolean scale_it, filled;
963 point sz;
964
965 rec_bb(g, g);
966 if ((GD_maxrank(g) > 0) && (GD_drawing(g)->ratio_kind)) {
967 sz.x = GD_bb(g).UR.x - GD_bb(g).LL.x;
968 sz.y = GD_bb(g).UR.y - GD_bb(g).LL.y; /* normalize */
969 if (GD_flip(g)) {
970 int t = sz.x;
971 sz.x = sz.y;
972 sz.y = t;
973 }
974 scale_it = TRUE;
975 if (GD_drawing(g)->ratio_kind == R_AUTO)
976 filled = idealsize(g, .5);
977 else
978 filled = (GD_drawing(g)->ratio_kind == R_FILL);
979 if (filled) {
980 /* fill is weird because both X and Y can stretch */
981 if (GD_drawing(g)->size.x <= 0)
982 scale_it = FALSE;
983 else {
984 xf = (double) GD_drawing(g)->size.x / (double) sz.x;
985 yf = (double) GD_drawing(g)->size.y / (double) sz.y;
986 if ((xf < 1.0) || (yf < 1.0)) {
987 if (xf < yf) {
988 yf = yf / xf;
989 xf = 1.0;
990 } else {
991 xf = xf / yf;
992 yf = 1.0;
993 }
994 }
995 }
996 } else if (GD_drawing(g)->ratio_kind == R_EXPAND) {
997 if (GD_drawing(g)->size.x <= 0)
998 scale_it = FALSE;
999 else {
1000 xf = (double) GD_drawing(g)->size.x /
1001 (double) GD_bb(g).UR.x;
1002 yf = (double) GD_drawing(g)->size.y /
1003 (double) GD_bb(g).UR.y;
1004 if ((xf > 1.0) && (yf > 1.0)) {
1005 double scale = MIN(xf, yf);
1006 xf = yf = scale;
1007 } else
1008 scale_it = FALSE;
1009 }
1010 } else if (GD_drawing(g)->ratio_kind == R_VALUE) {
1011 desired = GD_drawing(g)->ratio;
1012 actual = ((double) sz.y) / ((double) sz.x);
1013 if (actual < desired) {
1014 yf = desired / actual;
1015 xf = 1.0;
1016 } else {
1017 xf = actual / desired;
1018 yf = 1.0;
1019 }
1020 } else
1021 scale_it = FALSE;
1022 if (scale_it) {
1023 if (GD_flip(g)) {
1024 double t = xf;
1025 xf = yf;
1026 yf = t;
1027 }
1028 for (n = GD_nlist(g); n; n = ND_next(n)) {
1029 ND_coord(n).x = ROUND(ND_coord(n).x * xf);
1030 ND_coord(n).y = ROUND(ND_coord(n).y * yf);
1031 }
1032 scale_bb(g, g, xf, yf);
1033 }
1034 }
1035
1036 if (asp) adjustAspectRatio (g, asp);
1037}
1038
1039static point resize_leaf(node_t * leaf, point lbound)
1040{
1041 gv_nodesize(leaf, GD_flip(agraphof(leaf)));
1042 ND_coord(leaf).y = lbound.y;
1043 ND_coord(leaf).x = lbound.x + ND_lw(leaf);
1044 lbound.x = lbound.x + ND_lw(leaf) + ND_rw(leaf) + GD_nodesep(agraphof(leaf));
1045 return lbound;
1046}
1047
1048static point place_leaf(graph_t* ing, node_t * leaf, point lbound, int order)
1049{
1050 node_t *leader;
1051 graph_t *g = dot_root(ing);
1052
1053 leader = UF_find(leaf);
1054 if (leaf != leader)
1055 fast_nodeapp(leader, leaf);
1056 ND_order(leaf) = order;
1057 ND_rank(leaf) = ND_rank(leader);
1058 GD_rank(g)[ND_rank(leaf)].v[ND_order(leaf)] = leaf;
1059 return resize_leaf(leaf, lbound);
1060}
1061
1062/* make space for the leaf nodes of each rank */
1063static void make_leafslots(graph_t * g)
1064{
1065 int i, j, r;
1066 node_t *v;
1067
1068 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1069 j = 0;
1070 for (i = 0; i < GD_rank(g)[r].n; i++) {
1071 v = GD_rank(g)[r].v[i];
1072 ND_order(v) = j;
1073 if (ND_ranktype(v) == LEAFSET)
1074 j = j + ND_UF_size(v);
1075 else
1076 j++;
1077 }
1078 if (j <= GD_rank(g)[r].n)
1079 continue;
1080 GD_rank(g)[r].v = ALLOC(j + 1, GD_rank(g)[r].v, node_t *);
1081 for (i = GD_rank(g)[r].n - 1; i >= 0; i--) {
1082 v = GD_rank(g)[r].v[i];
1083 GD_rank(g)[r].v[ND_order(v)] = v;
1084 }
1085 GD_rank(g)[r].n = j;
1086 GD_rank(g)[r].v[j] = NULL;
1087 }
1088}
1089
1090static void do_leaves(graph_t * g, node_t * leader)
1091{
1092 int j;
1093 point lbound;
1094 node_t *n;
1095 edge_t *e;
1096
1097 if (ND_UF_size(leader) <= 1)
1098 return;
1099 lbound.x = ND_coord(leader).x - ND_lw(leader);
1100 lbound.y = ND_coord(leader).y;
1101 lbound = resize_leaf(leader, lbound);
1102 if (ND_out(leader).size > 0) { /* in-edge leaves */
1103 n = aghead(ND_out(leader).list[0]);
1104 j = ND_order(leader) + 1;
1105 for (e = agfstin(g, n); e; e = agnxtin(g, e)) {
1106 edge_t *e1 = AGMKOUT(e);
1107 if ((agtail(e1) != leader) && (UF_find(agtail(e1)) == leader)) {
1108 lbound = place_leaf(g, agtail(e1), lbound, j++);
1109 unmerge_oneway(e1);
1110 elist_append(e1, ND_in(aghead(e1)));
1111 }
1112 }
1113 } else { /* out edge leaves */
1114 n = agtail(ND_in(leader).list[0]);
1115 j = ND_order(leader) + 1;
1116 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1117 if ((aghead(e) != leader) && (UF_find(aghead(e)) == leader)) {
1118 lbound = place_leaf(g, aghead(e), lbound, j++);
1119 unmerge_oneway(e);
1120 elist_append(e, ND_out(agtail(e)));
1121 }
1122 }
1123 }
1124}
1125
1126int ports_eq(edge_t * e, edge_t * f)
1127{
1128 return ((ED_head_port(e).defined == ED_head_port(f).defined)
1129 && (((ED_head_port(e).p.x == ED_head_port(f).p.x) &&
1130 (ED_head_port(e).p.y == ED_head_port(f).p.y))
1131 || (ED_head_port(e).defined == FALSE))
1132 && (((ED_tail_port(e).p.x == ED_tail_port(f).p.x) &&
1133 (ED_tail_port(e).p.y == ED_tail_port(f).p.y))
1134 || (ED_tail_port(e).defined == FALSE))
1135 );
1136}
1137
1138static void expand_leaves(graph_t * g)
1139{
1140 int i, d;
1141 node_t *n;
1142 edge_t *e, *f;
1143
1144 make_leafslots(g);
1145 for (n = GD_nlist(g); n; n = ND_next(n)) {
1146 if (ND_inleaf(n))
1147 do_leaves(g, ND_inleaf(n));
1148 if (ND_outleaf(n))
1149 do_leaves(g, ND_outleaf(n));
1150 if (ND_other(n).list)
1151 for (i = 0; (e = ND_other(n).list[i]); i++) {
1152 if ((d = ND_rank(aghead(e)) - ND_rank(aghead(e))) == 0)
1153 continue;
1154 f = ED_to_orig(e);
1155 if (ports_eq(e, f) == FALSE) {
1156 zapinlist(&(ND_other(n)), e);
1157 if (d == 1)
1158 fast_edge(e);
1159 /*else unitize(e); ### */
1160 i--;
1161 }
1162 }
1163 }
1164}
1165
1166/* make_lrvn:
1167 * Add left and right slacknodes to a cluster which
1168 * are used in the LP to constrain nodes not in g but
1169 * sharing its ranks to be to the left or right of g
1170 * by a specified amount.
1171 * The slacknodes ln and rn give the x position of the
1172 * left and right side of the cluster's bounding box. In
1173 * particular, any cluster labels on the left or right side
1174 * are inside.
1175 * If a cluster has a label, and we have rankdir!=LR, we make
1176 * sure the cluster is wide enough for the label. Note that
1177 * if the label is wider than the cluster, the nodes in the
1178 * cluster may not be centered.
1179 */
1180static void make_lrvn(graph_t * g)
1181{
1182 node_t *ln, *rn;
1183
1184 if (GD_ln(g))
1185 return;
1186 ln = virtual_node(dot_root(g));
1187 ND_node_type(ln) = SLACKNODE;
1188 rn = virtual_node(dot_root(g));
1189 ND_node_type(rn) = SLACKNODE;
1190
1191 if (GD_label(g) && (g != dot_root(g)) && !GD_flip(agroot(g))) {
1192 int w = MAX(GD_border(g)[BOTTOM_IX].x, GD_border(g)[TOP_IX].x);
1193 make_aux_edge(ln, rn, w, 0);
1194 }
1195
1196 GD_ln(g) = ln;
1197 GD_rn(g) = rn;
1198}
1199
1200/* contain_nodes:
1201 * make left and right bounding box virtual nodes ln and rn
1202 * constrain interior nodes
1203 */
1204static void contain_nodes(graph_t * g)
1205{
1206 int margin, r;
1207 node_t *ln, *rn, *v;
1208
1209 margin = late_int (g, G_margin, CL_OFFSET, 0);
1210 make_lrvn(g);
1211 ln = GD_ln(g);
1212 rn = GD_rn(g);
1213 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1214 if (GD_rank(g)[r].n == 0)
1215 continue;
1216 v = GD_rank(g)[r].v[0];
1217 if (v == NULL) {
1218 agerr(AGERR, "contain_nodes clust %s rank %d missing node\n",
1219 agnameof(g), r);
1220 continue;
1221 }
1222 make_aux_edge(ln, v,
1223 ND_lw(v) + margin + GD_border(g)[LEFT_IX].x, 0);
1224 v = GD_rank(g)[r].v[GD_rank(g)[r].n - 1];
1225 make_aux_edge(v, rn,
1226 ND_rw(v) + margin + GD_border(g)[RIGHT_IX].x, 0);
1227 }
1228}
1229
1230/* idealsize:
1231 * set g->drawing->size to a reasonable default.
1232 * returns a boolean to indicate if drawing is to
1233 * be scaled and filled */
1234static boolean idealsize(graph_t * g, double minallowed)
1235{
1236 double xf, yf, f, R;
1237 pointf b, relpage, margin;
1238
1239 /* try for one page */
1240 relpage = GD_drawing(g)->page;
1241 if (relpage.x < 0.001 || relpage.y < 0.001)
1242 return FALSE; /* no page was specified */
1243 margin = GD_drawing(g)->margin;
1244 relpage = sub_pointf(relpage, margin);
1245 relpage = sub_pointf(relpage, margin);
1246 b.x = GD_bb(g).UR.x;
1247 b.y = GD_bb(g).UR.y;
1248 xf = relpage.x / b.x;
1249 yf = relpage.y / b.y;
1250 if ((xf >= 1.0) && (yf >= 1.0))
1251 return FALSE; /* fits on one page */
1252
1253 f = MIN(xf, yf);
1254 xf = yf = MAX(f, minallowed);
1255
1256 R = ceil((xf * b.x) / relpage.x);
1257 xf = ((R * relpage.x) / b.x);
1258 R = ceil((yf * b.y) / relpage.y);
1259 yf = ((R * relpage.y) / b.y);
1260 GD_drawing(g)->size.x = b.x * xf;
1261 GD_drawing(g)->size.y = b.y * yf;
1262 return TRUE;
1263}
1264