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 "render.h"
16#include "xlabels.h"
17
18static int Rankdir;
19static boolean Flip;
20static pointf Offset;
21
22static void place_flip_graph_label(graph_t * g);
23
24#define M1 \
25"/pathbox {\n\
26 /Y exch %.5g sub def\n\
27 /X exch %.5g sub def\n\
28 /y exch %.5g sub def\n\
29 /x exch %.5g sub def\n\
30 newpath x y moveto\n\
31 X y lineto\n\
32 X Y lineto\n\
33 x Y lineto\n\
34 closepath stroke\n \
35} def\n\
36/dbgstart { gsave %.5g %.5g translate } def\n\
37/arrowlength 10 def\n\
38/arrowwidth arrowlength 2 div def\n\
39/arrowhead {\n\
40 gsave\n\
41 rotate\n\
42 currentpoint\n\
43 newpath\n\
44 moveto\n\
45 arrowlength arrowwidth 2 div rlineto\n\
46 0 arrowwidth neg rlineto\n\
47 closepath fill\n\
48 grestore\n\
49} bind def\n\
50/makearrow {\n\
51 currentpoint exch pop sub exch currentpoint pop sub atan\n\
52 arrowhead\n\
53} bind def\n\
54/point {\
55 newpath\
56 2 0 360 arc fill\
57} def\
58/makevec {\n\
59 /Y exch def\n\
60 /X exch def\n\
61 /y exch def\n\
62 /x exch def\n\
63 newpath x y moveto\n\
64 X Y lineto stroke\n\
65 X Y moveto\n\
66 x y makearrow\n\
67} def\n"
68
69#define M2 \
70"/pathbox {\n\
71 /X exch neg %.5g sub def\n\
72 /Y exch %.5g sub def\n\
73 /x exch neg %.5g sub def\n\
74 /y exch %.5g sub def\n\
75 newpath x y moveto\n\
76 X y lineto\n\
77 X Y lineto\n\
78 x Y lineto\n\
79 closepath stroke\n\
80} def\n"
81
82static pointf map_point(pointf p)
83{
84 p = ccwrotatepf(p, Rankdir * 90);
85 p.x -= Offset.x;
86 p.y -= Offset.y;
87 return p;
88}
89
90static void map_edge(edge_t * e)
91{
92 int j, k;
93 bezier bz;
94
95 if (ED_spl(e) == NULL) {
96 if ((Concentrate == FALSE) && (ED_edge_type(e) != IGNORED))
97 agerr(AGERR, "lost %s %s edge\n", agnameof(agtail(e)),
98 agnameof(aghead(e)));
99 return;
100 }
101 for (j = 0; j < ED_spl(e)->size; j++) {
102 bz = ED_spl(e)->list[j];
103 for (k = 0; k < bz.size; k++)
104 bz.list[k] = map_point(bz.list[k]);
105 if (bz.sflag)
106 ED_spl(e)->list[j].sp = map_point(ED_spl(e)->list[j].sp);
107 if (bz.eflag)
108 ED_spl(e)->list[j].ep = map_point(ED_spl(e)->list[j].ep);
109 }
110 if (ED_label(e))
111 ED_label(e)->pos = map_point(ED_label(e)->pos);
112 if (ED_xlabel(e))
113 ED_xlabel(e)->pos = map_point(ED_xlabel(e)->pos);
114 /* vladimir */
115 if (ED_head_label(e))
116 ED_head_label(e)->pos = map_point(ED_head_label(e)->pos);
117 if (ED_tail_label(e))
118 ED_tail_label(e)->pos = map_point(ED_tail_label(e)->pos);
119}
120
121void translate_bb(graph_t * g, int rankdir)
122{
123 int c;
124 boxf bb, new_bb;
125
126 bb = GD_bb(g);
127 if (rankdir == RANKDIR_LR || rankdir == RANKDIR_BT) {
128 new_bb.LL = map_point(pointfof(bb.LL.x, bb.UR.y));
129 new_bb.UR = map_point(pointfof(bb.UR.x, bb.LL.y));
130 } else {
131 new_bb.LL = map_point(pointfof(bb.LL.x, bb.LL.y));
132 new_bb.UR = map_point(pointfof(bb.UR.x, bb.UR.y));
133 }
134 GD_bb(g) = new_bb;
135 if (GD_label(g)) {
136 GD_label(g)->pos = map_point(GD_label(g)->pos);
137 }
138 for (c = 1; c <= GD_n_cluster(g); c++)
139 translate_bb(GD_clust(g)[c], rankdir);
140}
141
142/* translate_drawing:
143 * Translate and/or rotate nodes, spline points, and bbox info if
144 * necessary. Also, if Rankdir (!= RANKDIR_BT), reset ND_lw, ND_rw,
145 * and ND_ht to correct value.
146 */
147static void translate_drawing(graph_t * g)
148{
149 node_t *v;
150 edge_t *e;
151 int shift = (Offset.x || Offset.y);
152
153 if (!shift && !Rankdir)
154 return;
155 for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
156 if (Rankdir)
157 gv_nodesize(v, FALSE);
158 ND_coord(v) = map_point(ND_coord(v));
159 if (ND_xlabel(v))
160 ND_xlabel(v)->pos = map_point(ND_xlabel(v)->pos);
161 if (State == GVSPLINES)
162 for (e = agfstout(g, v); e; e = agnxtout(g, e))
163 map_edge(e);
164 }
165 translate_bb(g, GD_rankdir(g));
166}
167
168/* place_root_label:
169 * Set position of root graph label.
170 * Note that at this point, after translate_drawing, a
171 * flipped drawing has been transposed, so we don't have
172 * to worry about switching x and y.
173 */
174static void place_root_label(graph_t * g, pointf d)
175{
176 pointf p;
177
178 if (GD_label_pos(g) & LABEL_AT_RIGHT) {
179 p.x = GD_bb(g).UR.x - d.x / 2;
180 } else if (GD_label_pos(g) & LABEL_AT_LEFT) {
181 p.x = GD_bb(g).LL.x + d.x / 2;
182 } else {
183 p.x = (GD_bb(g).LL.x + GD_bb(g).UR.x) / 2;
184 }
185
186 if (GD_label_pos(g) & LABEL_AT_TOP) {
187 p.y = GD_bb(g).UR.y - d.y / 2;
188 } else {
189 p.y = GD_bb(g).LL.y + d.y / 2;
190 }
191
192 GD_label(g)->pos = p;
193 GD_label(g)->set = TRUE;
194}
195
196/* centerPt:
197 * Calculate the center point of the xlabel. The returned positions for
198 * xlabels always correspond to the lower left corner.
199 */
200static pointf
201centerPt (xlabel_t* xlp) {
202 pointf p;
203
204 p = xlp->pos;
205 p.x += (xlp->sz.x)/2.0;
206 p.y += (xlp->sz.y)/2.0;
207
208 return p;
209}
210
211static int
212printData (object_t* objs, int n_objs, xlabel_t* lbls, int n_lbls,
213 label_params_t* params) {
214 int i;
215 xlabel_t* xp;
216 fprintf (stderr, "%d objs %d xlabels force=%d bb=(%.02f,%.02f) (%.02f,%.02f)\n",
217 n_objs, n_lbls, params->force, params->bb.LL.x, params->bb.LL.y,
218 params->bb.UR.x, params->bb.UR.y);
219 if (Verbose < 2) return 0;
220 fprintf(stderr, "objects\n");
221 for (i = 0; i < n_objs; i++) {
222 xp = objs->lbl;
223 fprintf (stderr, " [%d] (%.02f,%.02f) (%.02f,%.02f) %p \"%s\"\n",
224 i, objs->pos.x,objs->pos.y,objs->sz.x,objs->sz.y, objs->lbl,
225 (xp?((textlabel_t*)(xp->lbl))->text:""));
226 objs++;
227 }
228 fprintf(stderr, "xlabels\n");
229 for (i = 0; i < n_lbls; i++) {
230 fprintf (stderr, " [%d] %p set %d (%.02f,%.02f) (%.02f,%.02f) %s\n",
231 i, lbls, lbls->set, lbls->pos.x,lbls->pos.y, lbls->sz.x,lbls->sz.y, ((textlabel_t*)lbls->lbl)->text);
232 lbls++;
233 }
234 return 0;
235}
236
237static pointf
238edgeTailpoint (Agedge_t* e)
239{
240 splines *spl;
241 bezier *bez;
242
243 if ((spl = getsplinepoints(e)) == NULL) {
244 pointf p;
245 p.x = p.y = 0;
246 return p;
247 }
248 bez = &spl->list[0];
249 if (bez->sflag) {
250 return bez->sp;
251 } else {
252 return bez->list[0];
253 }
254}
255
256static pointf
257edgeHeadpoint (Agedge_t* e)
258{
259 splines *spl;
260 bezier *bez;
261
262 if ((spl = getsplinepoints(e)) == NULL) {
263 pointf p;
264 p.x = p.y = 0;
265 return p;
266 }
267 bez = &spl->list[spl->size - 1];
268 if (bez->eflag) {
269 return bez->ep;
270 } else {
271 return bez->list[bez->size - 1];
272 }
273}
274
275/* adjustBB:
276 */
277static boxf
278adjustBB (object_t* objp, boxf bb)
279{
280 pointf ur;
281
282 /* Adjust bounding box */
283 bb.LL.x = MIN(bb.LL.x, objp->pos.x);
284 bb.LL.y = MIN(bb.LL.y, objp->pos.y);
285 ur.x = objp->pos.x + objp->sz.x;
286 ur.y = objp->pos.y + objp->sz.y;
287 bb.UR.x = MAX(bb.UR.x, ur.x);
288 bb.UR.y = MAX(bb.UR.y, ur.y);
289
290 return bb;
291}
292
293/* addXLabel:
294 * Set up xlabel_t object and connect with related object.
295 * If initObj is set, initialize the object.
296 */
297static void
298addXLabel (textlabel_t* lp, object_t* objp, xlabel_t* xlp, int initObj, pointf pos)
299{
300 if (initObj) {
301 objp->sz.x = 0;
302 objp->sz.y = 0;
303 objp->pos = pos;
304 }
305
306 if (Flip) {
307 xlp->sz.x = lp->dimen.y;
308 xlp->sz.y = lp->dimen.x;
309 }
310 else {
311 xlp->sz = lp->dimen;
312 }
313 xlp->lbl = lp;
314 xlp->set = 0;
315 objp->lbl = xlp;
316}
317
318/* addLabelObj:
319 * Set up obstacle object based on set external label.
320 * This includes dot edge labels.
321 * Use label information to determine size and position of object.
322 * Then adjust given bounding box bb to include label and return new bb.
323 */
324static boxf
325addLabelObj (textlabel_t* lp, object_t* objp, boxf bb)
326{
327 if (Flip) {
328 objp->sz.x = lp->dimen.y;
329 objp->sz.y = lp->dimen.x;
330 }
331 else {
332 objp->sz.x = lp->dimen.x;
333 objp->sz.y = lp->dimen.y;
334 }
335 objp->pos = lp->pos;
336 objp->pos.x -= (objp->sz.x) / 2.0;
337 objp->pos.y -= (objp->sz.y) / 2.0;
338
339 return adjustBB(objp, bb);
340}
341
342/* addNodeOjb:
343 * Set up obstacle object based on a node.
344 * Use node information to determine size and position of object.
345 * Then adjust given bounding box bb to include label and return new bb.
346 */
347static boxf
348addNodeObj (node_t* np, object_t* objp, boxf bb)
349{
350 if (Flip) {
351 objp->sz.x = INCH2PS(ND_height(np));
352 objp->sz.y = INCH2PS(ND_width(np));
353 }
354 else {
355 objp->sz.x = INCH2PS(ND_width(np));
356 objp->sz.y = INCH2PS(ND_height(np));
357 }
358 objp->pos = ND_coord(np);
359 objp->pos.x -= (objp->sz.x) / 2.0;
360 objp->pos.y -= (objp->sz.y) / 2.0;
361
362 return adjustBB(objp, bb);
363}
364
365typedef struct {
366 boxf bb;
367 object_t* objp;
368} cinfo_t;
369
370static cinfo_t
371addClusterObj (Agraph_t* g, cinfo_t info)
372{
373 int c;
374
375 for (c = 1; c <= GD_n_cluster(g); c++)
376 info = addClusterObj (GD_clust(g)[c], info);
377 if ((g != agroot(g)) && (GD_label(g)) && GD_label(g)->set) {
378 object_t* objp = info.objp;
379 info.bb = addLabelObj (GD_label(g), objp, info.bb);
380 info.objp++;
381 }
382
383 return info;
384}
385
386static int
387countClusterLabels (Agraph_t* g)
388{
389 int c, i = 0;
390 if ((g != agroot(g)) && (GD_label(g)) && GD_label(g)->set)
391 i++;
392 for (c = 1; c <= GD_n_cluster(g); c++)
393 i += countClusterLabels (GD_clust(g)[c]);
394 return i;
395}
396
397/* addXLabels:
398 * Position xlabels and any unpositioned edge labels using
399 * a map placement algorithm to avoid overlap.
400 *
401 * TODO: interaction with spline=ortho
402 */
403 /* True if edges geometries were computed and this edge has a geometry */
404#define HAVE_EDGE(ep) ((et != ET_NONE) && (ED_spl(ep) != NULL))
405
406static void addXLabels(Agraph_t * gp)
407{
408 Agnode_t *np;
409 Agedge_t *ep;
410 int cnt, i, n_objs, n_lbls;
411 int n_nlbls = 0; /* # of unset node xlabels */
412 int n_elbls = 0; /* # of unset edge labels or xlabels */
413 int n_set_lbls = 0; /* # of set xlabels and edge labels */
414 int n_clbls = 0; /* # of set cluster labels */
415 boxf bb;
416 pointf ur;
417 textlabel_t* lp;
418 label_params_t params;
419 object_t* objs;
420 xlabel_t* lbls;
421 object_t* objp;
422 xlabel_t* xlp;
423 Agsym_t* force;
424 int et = EDGE_TYPE(gp);
425
426 if (!(GD_has_labels(gp) & NODE_XLABEL) &&
427 !(GD_has_labels(gp) & EDGE_XLABEL) &&
428 !(GD_has_labels(gp) & TAIL_LABEL) &&
429 !(GD_has_labels(gp) & HEAD_LABEL) &&
430 (!(GD_has_labels(gp) & EDGE_LABEL) || EdgeLabelsDone))
431 return;
432
433 for (np = agfstnode(gp); np; np = agnxtnode(gp, np)) {
434 if (ND_xlabel(np)) {
435 if (ND_xlabel(np)->set)
436 n_set_lbls++;
437 else
438 n_nlbls++;
439 }
440 for (ep = agfstout(gp, np); ep; ep = agnxtout(gp, ep)) {
441 if (ED_xlabel(ep)) {
442 if (ED_xlabel(ep)->set)
443 n_set_lbls++;
444 else if (HAVE_EDGE(ep))
445 n_elbls++;
446 }
447 if (ED_head_label(ep)) {
448 if (ED_head_label(ep)->set)
449 n_set_lbls++;
450 else if (HAVE_EDGE(ep))
451 n_elbls++;
452 }
453 if (ED_tail_label(ep)) {
454 if (ED_tail_label(ep)->set)
455 n_set_lbls++;
456 else if (HAVE_EDGE(ep))
457 n_elbls++;
458 }
459 if (ED_label(ep)) {
460 if (ED_label(ep)->set)
461 n_set_lbls++;
462 else if (HAVE_EDGE(ep))
463 n_elbls++;
464 }
465 }
466 }
467 if (GD_has_labels(gp) & GRAPH_LABEL)
468 n_clbls = countClusterLabels (gp);
469
470 /* A label for each unpositioned external label */
471 n_lbls = n_nlbls + n_elbls;
472 if (n_lbls == 0) return;
473
474 /* An object for each node, each positioned external label, any cluster label,
475 * and all unset edge labels and xlabels.
476 */
477 n_objs = agnnodes(gp) + n_set_lbls + n_clbls + n_elbls;
478 objp = objs = N_NEW(n_objs, object_t);
479 xlp = lbls = N_NEW(n_lbls, xlabel_t);
480 bb.LL = pointfof(INT_MAX, INT_MAX);
481 bb.UR = pointfof(-INT_MAX, -INT_MAX);
482
483 for (np = agfstnode(gp); np; np = agnxtnode(gp, np)) {
484
485 bb = addNodeObj (np, objp, bb);
486 if ((lp = ND_xlabel(np))) {
487 if (lp->set) {
488 objp++;
489 bb = addLabelObj (lp, objp, bb);
490 }
491 else {
492 addXLabel (lp, objp, xlp, 0, ur);
493 xlp++;
494 }
495 }
496 objp++;
497 for (ep = agfstout(gp, np); ep; ep = agnxtout(gp, ep)) {
498 if ((lp = ED_label(ep))) {
499 if (lp->set) {
500 bb = addLabelObj (lp, objp, bb);
501 }
502 else if (HAVE_EDGE(ep)) {
503 addXLabel (lp, objp, xlp, 1, edgeMidpoint(gp, ep));
504 xlp++;
505 }
506 else {
507 agerr(AGWARN, "no position for edge with label %s\n",
508 ED_label(ep)->text);
509 continue;
510 }
511 objp++;
512 }
513 if ((lp = ED_tail_label(ep))) {
514 if (lp->set) {
515 bb = addLabelObj (lp, objp, bb);
516 }
517 else if (HAVE_EDGE(ep)) {
518 addXLabel (lp, objp, xlp, 1, edgeTailpoint(ep));
519 xlp++;
520 }
521 else {
522 agerr(AGWARN, "no position for edge with tail label %s\n",
523 ED_tail_label(ep)->text);
524 continue;
525 }
526 objp++;
527 }
528 if ((lp = ED_head_label(ep))) {
529 if (lp->set) {
530 bb = addLabelObj (lp, objp, bb);
531 }
532 else if (HAVE_EDGE(ep)) {
533 addXLabel (lp, objp, xlp, 1, edgeHeadpoint(ep));
534 xlp++;
535 }
536 else {
537 agerr(AGWARN, "no position for edge with head label %s\n",
538 ED_head_label(ep)->text);
539 continue;
540 }
541 objp++;
542 }
543 if ((lp = ED_xlabel(ep))) {
544 if (lp->set) {
545 bb = addLabelObj (lp, objp, bb);
546 }
547 else if (HAVE_EDGE(ep)) {
548 addXLabel (lp, objp, xlp, 1, edgeMidpoint(gp, ep));
549 xlp++;
550 }
551 else {
552 agerr(AGWARN, "no position for edge with xlabel %s\n",
553 ED_xlabel(ep)->text);
554 continue;
555 }
556 objp++;
557 }
558 }
559 }
560 if (n_clbls) {
561 cinfo_t info;
562 info.bb = bb;
563 info.objp = objp;
564 info = addClusterObj (gp, info);
565 bb = info.bb;
566 }
567
568 force = agfindgraphattr(gp, "forcelabels");
569
570 params.force = late_bool(gp, force, TRUE);
571 params.bb = bb;
572 placeLabels(objs, n_objs, lbls, n_lbls, &params);
573 if (Verbose)
574 printData(objs, n_objs, lbls, n_lbls, &params);
575
576 xlp = lbls;
577 cnt = 0;
578 for (i = 0; i < n_lbls; i++) {
579 if (xlp->set) {
580 cnt++;
581 lp = (textlabel_t *) (xlp->lbl);
582 lp->set = 1;
583 lp->pos = centerPt(xlp);
584 updateBB (gp, lp);
585 }
586 xlp++;
587 }
588 if (Verbose)
589 fprintf (stderr, "%d out of %d labels positioned.\n", cnt, n_lbls);
590 else if (cnt != n_lbls)
591 agerr(AGWARN, "%d out of %d exterior labels positioned.\n", cnt, n_lbls);
592 free(objs);
593 free(lbls);
594}
595
596/* gv_postprocess:
597 * Set graph and cluster label positions.
598 * Add space for root graph label and translate graph accordingly.
599 * Set final nodesize using ns.
600 * Assumes the boxes of all clusters have been computed.
601 * When done, the bounding box of g has LL at origin.
602 */
603void gv_postprocess(Agraph_t * g, int allowTranslation)
604{
605 double diff;
606 pointf dimen = { 0., 0. };
607
608
609 Rankdir = GD_rankdir(g);
610 Flip = GD_flip(g);
611 /* Handle cluster labels */
612 if (Flip)
613 place_flip_graph_label(g);
614 else
615 place_graph_label(g);
616
617 /* Everything has been placed except the root graph label, if any.
618 * The graph positions have not yet been rotated back if necessary.
619 */
620 addXLabels(g);
621
622 /* Add space for graph label if necessary */
623 if (GD_label(g) && !GD_label(g)->set) {
624 dimen = GD_label(g)->dimen;
625 PAD(dimen);
626 if (Flip) {
627 if (GD_label_pos(g) & LABEL_AT_TOP) {
628 GD_bb(g).UR.x += dimen.y;
629 } else {
630 GD_bb(g).LL.x -= dimen.y;
631 }
632
633 if (dimen.x > (GD_bb(g).UR.y - GD_bb(g).LL.y)) {
634 diff = dimen.x - (GD_bb(g).UR.y - GD_bb(g).LL.y);
635 diff = diff / 2.;
636 GD_bb(g).LL.y -= diff;
637 GD_bb(g).UR.y += diff;
638 }
639 } else {
640 if (GD_label_pos(g) & LABEL_AT_TOP) {
641 if (Rankdir == RANKDIR_TB)
642 GD_bb(g).UR.y += dimen.y;
643 else
644 GD_bb(g).LL.y -= dimen.y;
645 } else {
646 if (Rankdir == RANKDIR_TB)
647 GD_bb(g).LL.y -= dimen.y;
648 else
649 GD_bb(g).UR.y += dimen.y;
650 }
651
652 if (dimen.x > (GD_bb(g).UR.x - GD_bb(g).LL.x)) {
653 diff = dimen.x - (GD_bb(g).UR.x - GD_bb(g).LL.x);
654 diff = diff / 2.;
655 GD_bb(g).LL.x -= diff;
656 GD_bb(g).UR.x += diff;
657 }
658 }
659 }
660 if (allowTranslation) {
661 switch (Rankdir) {
662 case RANKDIR_TB:
663 Offset = GD_bb(g).LL;
664 break;
665 case RANKDIR_LR:
666 Offset = pointfof(-GD_bb(g).UR.y, GD_bb(g).LL.x);
667 break;
668 case RANKDIR_BT:
669 Offset = pointfof(GD_bb(g).LL.x, -GD_bb(g).UR.y);
670 break;
671 case RANKDIR_RL:
672 Offset = pointfof(GD_bb(g).LL.y, GD_bb(g).LL.x);
673 break;
674 }
675 translate_drawing(g);
676 }
677 if (GD_label(g) && !GD_label(g)->set)
678 place_root_label(g, dimen);
679
680 if (Show_boxes) {
681 char buf[BUFSIZ];
682 if (Flip)
683 sprintf(buf, M2, Offset.x, Offset.y, Offset.x, Offset.y);
684 else
685 sprintf(buf, M1, Offset.y, Offset.x, Offset.y, Offset.x,
686 -Offset.x, -Offset.y);
687 Show_boxes[0] = strdup(buf);
688 }
689}
690
691/* dotneato_postprocess:
692 */
693void dotneato_postprocess(Agraph_t * g)
694{
695 gv_postprocess(g, 1);
696}
697
698/* place_flip_graph_label:
699 * Put cluster labels recursively in the flip case.
700 */
701static void place_flip_graph_label(graph_t * g)
702{
703 int c;
704 pointf p, d;
705
706 if ((g != agroot(g)) && (GD_label(g)) && !GD_label(g)->set) {
707 if (GD_label_pos(g) & LABEL_AT_TOP) {
708 d = GD_border(g)[RIGHT_IX];
709 p.x = GD_bb(g).UR.x - d.x / 2;
710 } else {
711 d = GD_border(g)[LEFT_IX];
712 p.x = GD_bb(g).LL.x + d.x / 2;
713 }
714
715 if (GD_label_pos(g) & LABEL_AT_RIGHT) {
716 p.y = GD_bb(g).LL.y + d.y / 2;
717 } else if (GD_label_pos(g) & LABEL_AT_LEFT) {
718 p.y = GD_bb(g).UR.y - d.y / 2;
719 } else {
720 p.y = (GD_bb(g).LL.y + GD_bb(g).UR.y) / 2;
721 }
722 GD_label(g)->pos = p;
723 GD_label(g)->set = TRUE;
724 }
725
726 for (c = 1; c <= GD_n_cluster(g); c++)
727 place_flip_graph_label(GD_clust(g)[c]);
728}
729
730/* place_graph_label:
731 * Put cluster labels recursively in the non-flip case.
732 * The adjustments to the bounding boxes should no longer
733 * be necessary, since we now guarantee the label fits in
734 * the cluster.
735 */
736void place_graph_label(graph_t * g)
737{
738 int c;
739 pointf p, d;
740
741 if ((g != agroot(g)) && (GD_label(g)) && !GD_label(g)->set) {
742 if (GD_label_pos(g) & LABEL_AT_TOP) {
743 d = GD_border(g)[TOP_IX];
744 p.y = GD_bb(g).UR.y - d.y / 2;
745 } else {
746 d = GD_border(g)[BOTTOM_IX];
747 p.y = GD_bb(g).LL.y + d.y / 2;
748 }
749
750 if (GD_label_pos(g) & LABEL_AT_RIGHT) {
751 p.x = GD_bb(g).UR.x - d.x / 2;
752 } else if (GD_label_pos(g) & LABEL_AT_LEFT) {
753 p.x = GD_bb(g).LL.x + d.x / 2;
754 } else {
755 p.x = (GD_bb(g).LL.x + GD_bb(g).UR.x) / 2;
756 }
757 GD_label(g)->pos = p;
758 GD_label(g)->set = TRUE;
759 }
760
761 for (c = 1; c <= GD_n_cluster(g); c++)
762 place_graph_label(GD_clust(g)[c]);
763}
764