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/* adjust.c
15 * Routines for repositioning nodes after initial layout in
16 * order to reduce/remove node overlaps.
17 */
18
19#include "neato.h"
20#include "agxbuf.h"
21#include "utils.h"
22#include "ctype.h"
23#include "voronoi.h"
24#include "info.h"
25#include "edges.h"
26#include "site.h"
27#include "heap.h"
28#include "hedges.h"
29#include "digcola.h"
30#if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
31#include "overlap.h"
32#endif
33#ifdef IPSEPCOLA
34#include "csolve_VPSC.h"
35#include "quad_prog_vpsc.h"
36#endif
37
38#define SEPFACT 0.8 /* default esep/sep */
39
40static double margin = 0.05; /* Create initial bounding box by adding
41 * margin * dimension around box enclosing
42 * nodes.
43 */
44static double incr = 0.05; /* Increase bounding box by adding
45 * incr * dimension around box.
46 */
47static int iterations = -1; /* Number of iterations */
48static int useIter = 0; /* Use specified number of iterations */
49
50static int doAll = 0; /* Move all nodes, regardless of overlap */
51static Site **sites; /* Array of pointers to sites; used in qsort */
52static Site **endSite; /* Sentinel on sites array */
53static Point nw, ne, sw, se; /* Corners of clipping window */
54
55static Site **nextSite;
56
57static void setBoundBox(Point * ll, Point * ur)
58{
59 pxmin = ll->x;
60 pxmax = ur->x;
61 pymin = ll->y;
62 pymax = ur->y;
63 nw.x = sw.x = pxmin;
64 ne.x = se.x = pxmax;
65 nw.y = ne.y = pymax;
66 sw.y = se.y = pymin;
67}
68
69 /* freeNodes:
70 * Free node resources.
71 */
72static void freeNodes(void)
73{
74 int i;
75 Info_t *ip = nodeInfo;
76
77 for (i = 0; i < nsites; i++) {
78 breakPoly(&ip->poly);
79 ip++;
80 }
81 polyFree();
82 infoinit(); /* Free vertices */
83 free(nodeInfo);
84}
85
86/* chkBoundBox:
87 * Compute extremes of graph, then set up bounding box.
88 * If user supplied a bounding box, use that;
89 * else if "window" is a graph attribute, use that;
90 * otherwise, define bounding box as a percentage expansion of
91 * graph extremes.
92 * In the first two cases, check that graph fits in bounding box.
93 */
94static void chkBoundBox(Agraph_t * graph)
95{
96 char *marg;
97 Point ll, ur;
98 int i;
99 double x, y;
100 double xmin, xmax, ymin, ymax;
101 double xmn, xmx, ymn, ymx;
102 double ydelta, xdelta;
103 Info_t *ip;
104 Poly *pp;
105 /* int cnt; */
106
107 ip = nodeInfo;
108 pp = &ip->poly;
109 x = ip->site.coord.x;
110 y = ip->site.coord.y;
111 xmin = pp->origin.x + x;
112 ymin = pp->origin.y + y;
113 xmax = pp->corner.x + x;
114 ymax = pp->corner.y + y;
115 for (i = 1; i < nsites; i++) {
116 ip++;
117 pp = &ip->poly;
118 x = ip->site.coord.x;
119 y = ip->site.coord.y;
120 xmn = pp->origin.x + x;
121 ymn = pp->origin.y + y;
122 xmx = pp->corner.x + x;
123 ymx = pp->corner.y + y;
124 if (xmn < xmin)
125 xmin = xmn;
126 if (ymn < ymin)
127 ymin = ymn;
128 if (xmx > xmax)
129 xmax = xmx;
130 if (ymx > ymax)
131 ymax = ymx;
132 }
133
134 marg = agget(graph, "voro_margin");
135 if (marg && (*marg != '\0')) {
136 margin = atof(marg);
137 }
138 ydelta = margin * (ymax - ymin);
139 xdelta = margin * (xmax - xmin);
140 ll.x = xmin - xdelta;
141 ll.y = ymin - ydelta;
142 ur.x = xmax + xdelta;
143 ur.y = ymax + ydelta;
144
145 setBoundBox(&ll, &ur);
146}
147
148 /* makeInfo:
149 * For each node in the graph, create a Info data structure
150 */
151static int makeInfo(Agraph_t * graph)
152{
153 Agnode_t *node;
154 int i;
155 Info_t *ip;
156 expand_t pmargin;
157 int (*polyf)(Poly *, Agnode_t *, float, float);
158
159 nsites = agnnodes(graph);
160 geominit();
161
162 nodeInfo = N_GNEW(nsites, Info_t);
163
164 node = agfstnode(graph);
165 ip = nodeInfo;
166
167 pmargin = sepFactor (graph);
168
169 if (pmargin.doAdd) {
170 polyf = makeAddPoly;
171 /* we need inches for makeAddPoly */
172 pmargin.x = PS2INCH(pmargin.x);
173 pmargin.y = PS2INCH(pmargin.y);
174 }
175
176 else polyf = makePoly;
177 for (i = 0; i < nsites; i++) {
178 ip->site.coord.x = ND_pos(node)[0];
179 ip->site.coord.y = ND_pos(node)[1];
180
181 if (polyf(&ip->poly, node, pmargin.x, pmargin.y)) {
182 free (nodeInfo);
183 nodeInfo = NULL;
184 return 1;
185 }
186
187 ip->site.sitenbr = i;
188 ip->site.refcnt = 1;
189 ip->node = node;
190 ip->verts = NULL;
191 node = agnxtnode(graph, node);
192 ip++;
193 }
194 return 0;
195}
196
197/* sort sites on y, then x, coord */
198static int scomp(const void *S1, const void *S2)
199{
200 Site *s1, *s2;
201
202 s1 = *(Site **) S1;
203 s2 = *(Site **) S2;
204 if (s1->coord.y < s2->coord.y)
205 return (-1);
206 if (s1->coord.y > s2->coord.y)
207 return (1);
208 if (s1->coord.x < s2->coord.x)
209 return (-1);
210 if (s1->coord.x > s2->coord.x)
211 return (1);
212 return (0);
213}
214
215 /* sortSites:
216 * Fill array of pointer to sites and sort the sites using scomp
217 */
218static void sortSites(void)
219{
220 int i;
221 Site **sp;
222 Info_t *ip;
223
224 if (sites == 0) {
225 sites = N_GNEW(nsites, Site *);
226 endSite = sites + nsites;
227 }
228
229 sp = sites;
230 ip = nodeInfo;
231 infoinit();
232 for (i = 0; i < nsites; i++) {
233 *sp++ = &(ip->site);
234 ip->verts = NULL;
235 ip->site.refcnt = 1;
236 ip++;
237 }
238
239 qsort(sites, nsites, sizeof(Site *), scomp);
240
241 /* Reset site index for nextOne */
242 nextSite = sites;
243
244}
245
246static void geomUpdate(int doSort)
247{
248 int i;
249
250 if (doSort)
251 sortSites();
252
253 /* compute ranges */
254 xmin = sites[0]->coord.x;
255 xmax = sites[0]->coord.x;
256 for (i = 1; i < nsites; i++) {
257 if (sites[i]->coord.x < xmin)
258 xmin = sites[i]->coord.x;
259 if (sites[i]->coord.x > xmax)
260 xmax = sites[i]->coord.x;
261 }
262 ymin = sites[0]->coord.y;
263 ymax = sites[nsites - 1]->coord.y;
264
265 deltay = ymax - ymin;
266 deltax = xmax - xmin;
267}
268
269static Site *nextOne(void)
270{
271 Site *s;
272
273 if (nextSite < endSite) {
274 s = *nextSite++;
275 return (s);
276 } else
277 return ((Site *) NULL);
278}
279
280/* rmEquality:
281 * Check for nodes with identical positions and tweak
282 * the positions.
283 */
284static void rmEquality(void)
285{
286 int i, cnt;
287 Site **ip;
288 Site **jp;
289 Site **kp;
290 double xdel;
291
292 sortSites();
293 ip = sites;
294
295 while (ip < endSite) {
296 jp = ip + 1;
297 if ((jp >= endSite) ||
298 ((*jp)->coord.x != (*ip)->coord.x) ||
299 ((*jp)->coord.y != (*ip)->coord.y)) {
300 ip = jp;
301 continue;
302 }
303
304 /* Find first node kp with position different from ip */
305 cnt = 2;
306 kp = jp + 1;
307 while ((kp < endSite) &&
308 ((*kp)->coord.x == (*ip)->coord.x) &&
309 ((*kp)->coord.y == (*ip)->coord.y)) {
310 cnt++;
311 jp = kp;
312 kp = jp + 1;
313 }
314
315 /* If next node exists and is on the same line */
316 if ((kp < endSite) && ((*kp)->coord.y == (*ip)->coord.y)) {
317 xdel = ((*kp)->coord.x - (*ip)->coord.x) / cnt;
318 i = 1;
319 for (jp = ip + 1; jp < kp; jp++) {
320 (*jp)->coord.x += i * xdel;
321 i++;
322 }
323 } else { /* nothing is to the right */
324 Info_t *info;
325 for (jp = ip + 1; jp < kp; ip++, jp++) {
326 info = nodeInfo + (*ip)->sitenbr;
327 xdel = info->poly.corner.x - info->poly.origin.x;
328 info = nodeInfo + (*jp)->sitenbr;
329 xdel += info->poly.corner.x - info->poly.origin.x;
330 (*jp)->coord.x = (*ip)->coord.x + xdel / 2;
331 }
332 }
333 ip = kp;
334 }
335}
336
337/* countOverlap:
338 * Count number of node-node overlaps at iteration iter.
339 */
340static int countOverlap(int iter)
341{
342 int count = 0;
343 int i, j;
344 Info_t *ip = nodeInfo;
345 Info_t *jp;
346
347 for (i = 0; i < nsites; i++)
348 nodeInfo[i].overlaps = 0;
349
350 for (i = 0; i < nsites - 1; i++) {
351 jp = ip + 1;
352 for (j = i + 1; j < nsites; j++) {
353 if (polyOverlap
354 (ip->site.coord, &ip->poly, jp->site.coord, &jp->poly)) {
355 count++;
356 ip->overlaps = 1;
357 jp->overlaps = 1;
358 }
359 jp++;
360 }
361 ip++;
362 }
363
364 if (Verbose > 1)
365 fprintf(stderr, "overlap [%d] : %d\n", iter, count);
366 return count;
367}
368
369static void increaseBoundBox(void)
370{
371 double ydelta, xdelta;
372 Point ll, ur;
373
374 ur.x = pxmax;
375 ur.y = pymax;
376 ll.x = pxmin;
377 ll.y = pymin;
378
379 ydelta = incr * (ur.y - ll.y);
380 xdelta = incr * (ur.x - ll.x);
381
382 ur.x += xdelta;
383 ur.y += ydelta;
384 ll.x -= xdelta;
385 ll.y -= ydelta;
386
387 setBoundBox(&ll, &ur);
388}
389
390 /* areaOf:
391 * Area of triangle whose vertices are a,b,c
392 */
393static double areaOf(Point a, Point b, Point c)
394{
395 double area;
396
397 area =
398 (double) (fabs
399 (a.x * (b.y - c.y) + b.x * (c.y - a.y) +
400 c.x * (a.y - b.y)) / 2);
401 return area;
402}
403
404 /* centroidOf:
405 * Compute centroid of triangle with vertices a, b, c.
406 * Return coordinates in x and y.
407 */
408static void centroidOf(Point a, Point b, Point c, double *x, double *y)
409{
410 *x = (a.x + b.x + c.x) / 3;
411 *y = (a.y + b.y + c.y) / 3;
412}
413
414 /* newpos;
415 * The new position is the centroid of the
416 * voronoi polygon. This is the weighted sum of the
417 * centroids of a triangulation, normalized to the
418 * total area.
419 */
420static void newpos(Info_t * ip)
421{
422 PtItem *anchor = ip->verts;
423 PtItem *p, *q;
424 double totalArea = 0.0;
425 double cx = 0.0;
426 double cy = 0.0;
427 double x;
428 double y;
429 double area;
430
431 p = anchor->next;
432 q = p->next;
433 while (q != NULL) {
434 area = areaOf(anchor->p, p->p, q->p);
435 centroidOf(anchor->p, p->p, q->p, &x, &y);
436 cx = cx + area * x;
437 cy = cy + area * y;
438 totalArea = totalArea + area;
439 p = q;
440 q = q->next;
441 }
442
443 ip->site.coord.x = cx / totalArea;
444 ip->site.coord.y = cy / totalArea;
445}
446
447 /* addCorners:
448 * Add corners of clipping window to appropriate sites.
449 * A site gets a corner if it is the closest site to that corner.
450 */
451static void addCorners(void)
452{
453 Info_t *ip = nodeInfo;
454 Info_t *sws = ip;
455 Info_t *nws = ip;
456 Info_t *ses = ip;
457 Info_t *nes = ip;
458 double swd = dist_2(&ip->site.coord, &sw);
459 double nwd = dist_2(&ip->site.coord, &nw);
460 double sed = dist_2(&ip->site.coord, &se);
461 double ned = dist_2(&ip->site.coord, &ne);
462 double d;
463 int i;
464
465 ip++;
466 for (i = 1; i < nsites; i++) {
467 d = dist_2(&ip->site.coord, &sw);
468 if (d < swd) {
469 swd = d;
470 sws = ip;
471 }
472 d = dist_2(&ip->site.coord, &se);
473 if (d < sed) {
474 sed = d;
475 ses = ip;
476 }
477 d = dist_2(&ip->site.coord, &nw);
478 if (d < nwd) {
479 nwd = d;
480 nws = ip;
481 }
482 d = dist_2(&ip->site.coord, &ne);
483 if (d < ned) {
484 ned = d;
485 nes = ip;
486 }
487 ip++;
488 }
489
490 addVertex(&sws->site, sw.x, sw.y);
491 addVertex(&ses->site, se.x, se.y);
492 addVertex(&nws->site, nw.x, nw.y);
493 addVertex(&nes->site, ne.x, ne.y);
494}
495
496 /* newPos:
497 * Calculate the new position of a site as the centroid
498 * of its voronoi polygon, if it overlaps other nodes.
499 * The polygons are finite by being clipped to the clipping
500 * window.
501 * We first add the corner of the clipping windows to the
502 * vertex lists of the appropriate sites.
503 */
504static void newPos(void)
505{
506 int i;
507 Info_t *ip = nodeInfo;
508
509 addCorners();
510 for (i = 0; i < nsites; i++) {
511 if (doAll || ip->overlaps)
512 newpos(ip);
513 ip++;
514 }
515}
516
517/* cleanup:
518 * Cleanup voronoi memory.
519 * Note that PQcleanup and ELcleanup rely on the number
520 * of sites, so should at least be reset every time we use vAdjust.
521 * This could be optimized, over multiple components or
522 * even multiple graphs, but probably not worth it.
523 */
524static void cleanup(void)
525{
526 PQcleanup();
527 ELcleanup();
528 siteinit(); /* free memory */
529 edgeinit(); /* free memory */
530}
531
532static int vAdjust(void)
533{
534 int iterCnt = 0;
535 int overlapCnt = 0;
536 int badLevel = 0;
537 int increaseCnt = 0;
538 int cnt;
539
540 if (!useIter || (iterations > 0))
541 overlapCnt = countOverlap(iterCnt);
542
543 if ((overlapCnt == 0) || (iterations == 0))
544 return 0;
545
546 rmEquality();
547 geomUpdate(0);
548 voronoi(0, nextOne);
549 while (1) {
550 newPos();
551 iterCnt++;
552
553 if (useIter && (iterCnt == iterations))
554 break;
555 cnt = countOverlap(iterCnt);
556 if (cnt == 0)
557 break;
558 if (cnt >= overlapCnt)
559 badLevel++;
560 else
561 badLevel = 0;
562 overlapCnt = cnt;
563
564 switch (badLevel) {
565 case 0:
566 doAll = 1;
567 break;
568/*
569 case 1:
570 doAll = 1;
571 break;
572*/
573 default:
574 doAll = 1;
575 increaseCnt++;
576 increaseBoundBox();
577 break;
578 }
579
580 geomUpdate(1);
581 voronoi(0, nextOne);
582 }
583
584 if (Verbose) {
585 fprintf(stderr, "Number of iterations = %d\n", iterCnt);
586 fprintf(stderr, "Number of increases = %d\n", increaseCnt);
587 }
588
589 cleanup();
590 return 1;
591}
592
593static double rePos(Point c)
594{
595 int i;
596 Info_t *ip = nodeInfo;
597 double f = 1.0 + incr;
598
599 for (i = 0; i < nsites; i++) {
600 /* ip->site.coord.x = f*(ip->site.coord.x - c.x) + c.x; */
601 /* ip->site.coord.y = f*(ip->site.coord.y - c.y) + c.y; */
602 ip->site.coord.x = f * ip->site.coord.x;
603 ip->site.coord.y = f * ip->site.coord.y;
604 ip++;
605 }
606 return f;
607}
608
609static int sAdjust(void)
610{
611 int iterCnt = 0;
612 int overlapCnt = 0;
613 int cnt;
614 Point center;
615 /* double sc; */
616
617 if (!useIter || (iterations > 0))
618 overlapCnt = countOverlap(iterCnt);
619
620 if ((overlapCnt == 0) || (iterations == 0))
621 return 0;
622
623 rmEquality();
624 center.x = (pxmin + pxmax) / 2.0;
625 center.y = (pymin + pymax) / 2.0;
626 while (1) {
627 /* sc = */ rePos(center);
628 iterCnt++;
629
630 if (useIter && (iterCnt == iterations))
631 break;
632 cnt = countOverlap(iterCnt);
633 if (cnt == 0)
634 break;
635 }
636
637 if (Verbose) {
638 fprintf(stderr, "Number of iterations = %d\n", iterCnt);
639 }
640
641 return 1;
642}
643
644 /* updateGraph:
645 * Enter new node positions into the graph
646 */
647static void updateGraph(Agraph_t * graph)
648{
649 /* Agnode_t* node; */
650 int i;
651 Info_t *ip;
652 /* char pos[100]; */
653
654 ip = nodeInfo;
655 for (i = 0; i < nsites; i++) {
656 ND_pos(ip->node)[0] = ip->site.coord.x;
657 ND_pos(ip->node)[1] = ip->site.coord.y;
658 ip++;
659 }
660}
661
662#define ELS "|edgelabel|"
663#define ELSN (sizeof(ELS)-1)
664 /* Return true if node name starts with ELS */
665#define IS_LNODE(n) (!strncmp(agnameof(n),ELS,ELSN))
666
667/* getSizes:
668 * Set up array of half sizes in inches.
669 */
670double *getSizes(Agraph_t * g, pointf pad, int* n_elabels, int** elabels)
671{
672 Agnode_t *n;
673 real *sizes = N_GNEW(Ndim * agnnodes(g), real);
674 int i, nedge_nodes = 0;
675 int* elabs;
676
677 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
678 if (elabels && IS_LNODE(n)) nedge_nodes++;
679
680 i = ND_id(n);
681 sizes[i * Ndim] = ND_width(n) * .5 + pad.x;
682 sizes[i * Ndim + 1] = ND_height(n) * .5 + pad.y;
683 }
684
685 if (elabels && nedge_nodes) {
686 elabs = N_GNEW(nedge_nodes, int);
687 nedge_nodes = 0;
688 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
689 if (IS_LNODE(n))
690 elabs[nedge_nodes++] = ND_id(n);
691 }
692 *elabels = elabs;
693 *n_elabels = nedge_nodes;
694 }
695
696 return sizes;
697}
698
699/* makeMatrix:
700 * Assumes g is connected and simple, i.e., we can have a->b and b->a
701 * but not a->b and a->b
702 */
703SparseMatrix makeMatrix(Agraph_t* g, int dim, SparseMatrix *D)
704{
705 SparseMatrix A = 0;
706 Agnode_t *n;
707 Agedge_t *e;
708 Agsym_t *sym;
709 int nnodes;
710 int nedges;
711 int i, row;
712 int *I;
713 int *J;
714 real *val;
715 real v;
716 int type = MATRIX_TYPE_REAL;
717 Agsym_t* symD = NULL;
718 real* valD = NULL;
719
720 if (!g)
721 return NULL;
722 nnodes = agnnodes(g);
723 nedges = agnedges(g);
724
725 /* Assign node ids */
726 i = 0;
727 for (n = agfstnode(g); n; n = agnxtnode(g, n))
728 ND_id(n) = i++;
729
730 I = N_GNEW(nedges, int);
731 J = N_GNEW(nedges, int);
732 val = N_GNEW(nedges, real);
733
734 sym = agfindedgeattr(g, "weight");
735 if (D) {
736 symD = agfindedgeattr(g, "len");
737 valD = N_NEW(nedges, real);
738 }
739
740 i = 0;
741 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
742 row = ND_id(n);
743 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
744 I[i] = row;
745 J[i] = ND_id(aghead(e));
746 if (!sym || (sscanf(agxget(e, sym), "%lf", &v) != 1))
747 v = 1;
748 val[i] = v;
749 /* edge length */
750 if (symD) {
751 if (sscanf (agxget (e, symD), "%lf", &v) != 1) v = 1;
752 valD[i] = v;
753 }
754 i++;
755 }
756 }
757
758 A = SparseMatrix_from_coordinate_arrays(nedges, nnodes, nnodes, I, J,
759 val, type, sizeof(real));
760
761 if (D) *D = SparseMatrix_from_coordinate_arrays(nedges, nnodes, nnodes, I, J, valD, type, sizeof(real));
762
763 free(I);
764 free(J);
765 free(val);
766 if (valD) free (valD);
767
768 return A;
769}
770
771#if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
772static int
773fdpAdjust (graph_t* g, adjust_data* am)
774{
775 SparseMatrix A0 = makeMatrix(g, Ndim, NULL);
776 SparseMatrix A = A0;
777 real *sizes;
778 real *pos = N_NEW(Ndim * agnnodes(g), real);
779 Agnode_t *n;
780 int flag, i;
781 expand_t sep = sepFactor(g);
782 pointf pad;
783
784 if (sep.doAdd) {
785 pad.x = PS2INCH(sep.x);
786 pad.y = PS2INCH(sep.y);
787 } else {
788 pad.x = PS2INCH(DFLT_MARGIN);
789 pad.y = PS2INCH(DFLT_MARGIN);
790 }
791 sizes = getSizes(g, pad, NULL, NULL);
792
793 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
794 real* npos = pos + (Ndim * ND_id(n));
795 for (i = 0; i < Ndim; i++) {
796 npos[i] = ND_pos(n)[i];
797 }
798 }
799
800 if (!SparseMatrix_is_symmetric(A, FALSE)
801 || A->type != MATRIX_TYPE_REAL) {
802 A = SparseMatrix_get_real_adjacency_matrix_symmetrized(A);
803 } else {
804 A = SparseMatrix_remove_diagonal(A);
805 }
806
807 remove_overlap(Ndim, A, pos, sizes, am->value, am->scaling,
808 ELSCHEME_NONE, 0, NULL, NULL, mapBool (agget(g, "overlap_shrink"), TRUE), &flag);
809
810 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
811 real *npos = pos + (Ndim * ND_id(n));
812 for (i = 0; i < Ndim; i++) {
813 ND_pos(n)[i] = npos[i];
814 }
815 }
816
817 free(sizes);
818 free(pos);
819 if (A != A0)
820 SparseMatrix_delete(A);
821 SparseMatrix_delete (A0);
822
823 return flag;
824}
825#endif
826
827#ifdef IPSEPCOLA
828static int
829vpscAdjust(graph_t* G)
830{
831 int dim = 2;
832 int nnodes = agnnodes(G);
833 ipsep_options opt;
834 pointf* nsize = N_GNEW(nnodes, pointf);
835 float** coords = N_GNEW(dim, float*);
836 float* f_storage = N_GNEW(dim * nnodes, float);
837 int i, j;
838 Agnode_t* v;
839 expand_t margin;
840
841 for (i = 0; i < dim; i++) {
842 coords[i] = f_storage + i * nnodes;
843 }
844
845 j = 0;
846 for (v = agfstnode(G); v; v = agnxtnode(G, v)) {
847 for (i = 0; i < dim; i++) {
848 coords[i][j] = (float) (ND_pos(v)[i]);
849 }
850 nsize[j].x = ND_width(v);
851 nsize[j].y = ND_height(v);
852 j++;
853 }
854
855 opt.diredges = 0;
856 opt.edge_gap = 0;
857 opt.noverlap = 2;
858 opt.clusters = NEW(cluster_data);
859 margin = sepFactor (G);
860 /* Multiply by 2 since opt.gap is the gap size, not the margin */
861 if (margin.doAdd) {
862 opt.gap.x = 2.0*PS2INCH(margin.x);
863 opt.gap.y = 2.0*PS2INCH(margin.y);
864 }
865 else {
866 opt.gap.x = opt.gap.y = 2.0*PS2INCH(DFLT_MARGIN);
867 }
868 opt.nsize = nsize;
869
870 removeoverlaps(nnodes, coords, &opt);
871
872 j = 0;
873 for (v = agfstnode(G); v; v = agnxtnode(G, v)) {
874 for (i = 0; i < dim; i++) {
875 ND_pos(v)[i] = coords[i][j];
876 }
877 j++;
878 }
879
880 free (opt.clusters);
881 free (f_storage);
882 free (coords);
883 free (nsize);
884 return 0;
885}
886#endif
887
888/* angleSet:
889 * Return true if "normalize" is defined and valid; return angle in phi.
890 * Read angle as degrees, convert to radians.
891 * Guarantee -PI < phi <= PI.
892 */
893static int
894angleSet (graph_t* g, double* phi)
895{
896 double ang;
897 char* p;
898 char* a = agget(g, "normalize");
899
900 if (!a || (*a == '\0'))
901 return 0;
902 ang = strtod (a, &p);
903 if (p == a) { /* no number */
904 if (mapbool(a))
905 ang = 0.0;
906 else
907 return 0;
908 }
909 while (ang > 180) ang -= 360;
910 while (ang <= -180) ang += 360;
911
912 *phi = RADIANS(ang);
913 return 1;
914}
915
916/* normalize:
917 * If normalize is set, move first node to origin, then
918 * rotate graph so that the angle of the first edge is given
919 * by the degrees from normalize.
920 * FIX: Generalize to allow rotation determined by graph shape.
921 */
922int normalize(graph_t * g)
923{
924 node_t *v;
925 edge_t *e;
926 double phi;
927 double cosv, sinv;
928 pointf p, orig;
929 int ret;
930
931 if (!angleSet(g, &phi))
932 return 0;
933
934 v = agfstnode(g);
935 p.x = ND_pos(v)[0];
936 p.y = ND_pos(v)[1];
937 for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
938 ND_pos(v)[0] -= p.x;
939 ND_pos(v)[1] -= p.y;
940 }
941 if (p.x || p.y) ret = 1;
942 else ret = 0;
943
944 e = NULL;
945 for (v = agfstnode(g); v; v = agnxtnode(g, v))
946 if ((e = agfstout(g, v)))
947 break;
948 if (e == NULL)
949 return ret;
950
951 /* rotation necessary; pos => ccw */
952 phi -= atan2(ND_pos(aghead(e))[1] - ND_pos(agtail(e))[1],
953 ND_pos(aghead(e))[0] - ND_pos(agtail(e))[0]);
954
955 if (phi) {
956 orig.x = ND_pos(agtail(e))[0];
957 orig.y = ND_pos(agtail(e))[1];
958 cosv = cos(phi);
959 sinv = sin(phi);
960 for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
961 p.x = ND_pos(v)[0] - orig.x;
962 p.y = ND_pos(v)[1] - orig.y;
963 ND_pos(v)[0] = p.x * cosv - p.y * sinv + orig.x;
964 ND_pos(v)[1] = p.x * sinv + p.y * cosv + orig.y;
965 }
966 return 1;
967 }
968 else return ret;
969}
970
971typedef struct {
972 adjust_mode mode;
973 char *attrib;
974 int len;
975 char *print;
976} lookup_t;
977
978#define STRLEN(s) ((sizeof(s)-1)/sizeof(char))
979#define ITEM(i,s,v) {i, s, STRLEN(s), v}
980
981/* Translation table from overlap values to algorithms.
982 * adjustMode[0] corresponds to overlap=true
983 * adjustMode[1] corresponds to overlap=false
984 */
985static lookup_t adjustMode[] = {
986 ITEM(AM_NONE, "", "none"),
987#if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
988 ITEM(AM_PRISM, "prism", "prism"),
989#endif
990 ITEM(AM_VOR, "voronoi", "Voronoi"),
991 ITEM(AM_NSCALE, "scale", "scaling"),
992 ITEM(AM_COMPRESS, "compress", "compress"),
993 ITEM(AM_VPSC, "vpsc", "vpsc"),
994 ITEM(AM_IPSEP, "ipsep", "ipsep"),
995 ITEM(AM_SCALE, "oscale", "old scaling"),
996 ITEM(AM_SCALEXY, "scalexy", "x and y scaling"),
997 ITEM(AM_ORTHO, "ortho", "orthogonal constraints"),
998 ITEM(AM_ORTHO_YX, "ortho_yx", "orthogonal constraints"),
999 ITEM(AM_ORTHOXY, "orthoxy", "xy orthogonal constraints"),
1000 ITEM(AM_ORTHOYX, "orthoyx", "yx orthogonal constraints"),
1001 ITEM(AM_PORTHO, "portho", "pseudo-orthogonal constraints"),
1002 ITEM(AM_PORTHO_YX, "portho_yx", "pseudo-orthogonal constraints"),
1003 ITEM(AM_PORTHOXY, "porthoxy", "xy pseudo-orthogonal constraints"),
1004 ITEM(AM_PORTHOYX, "porthoyx", "yx pseudo-orthogonal constraints"),
1005#if !((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
1006 ITEM(AM_PRISM, "prism", 0),
1007#endif
1008 {AM_NONE, 0, 0, 0}
1009};
1010
1011
1012/* setPrismValues:
1013 * Initialize and set prism values
1014 */
1015static void
1016setPrismValues (Agraph_t* g, char* s, adjust_data* dp)
1017{
1018 int v;
1019
1020 if ((sscanf (s, "%d", &v) > 0) && (v >= 0))
1021 dp->value = v;
1022 else
1023 dp->value = 1000;
1024 dp->scaling = late_double(g, agfindgraphattr(g, "overlap_scaling"), -4.0, -1.e10);
1025}
1026
1027/* getAdjustMode:
1028 * Convert string value to internal value of adjustment mode.
1029 * If s is NULL or empty, return NONE.
1030 */
1031static adjust_data *getAdjustMode(Agraph_t* g, char *s, adjust_data* dp)
1032{
1033 lookup_t *ap = adjustMode + 1;
1034 if ((s == NULL) || (*s == '\0')) {
1035 dp->mode = adjustMode[0].mode;
1036 dp->print = adjustMode[0].print;
1037 }
1038 else {
1039 while (ap->attrib) {
1040 if (!strncasecmp(s, ap->attrib, ap->len)) {
1041 if (ap->print == NULL) {
1042 agerr (AGWARN, "Overlap value \"%s\" unsupported - ignored\n", ap->attrib);
1043 ap = &adjustMode[1];
1044 }
1045 dp->mode = ap->mode;
1046 dp->print = ap->print;
1047 if (ap->mode == AM_PRISM)
1048 setPrismValues (g, s + ap->len, dp);
1049 break;
1050 }
1051 ap++;
1052 }
1053 if (ap->attrib == NULL ) {
1054 int v = mapBool(s,'?');
1055 if (v == '?') {
1056 agerr (AGWARN, "Unrecognized overlap value \"%s\" - using false\n", s);
1057 v = FALSE;
1058 }
1059 if (v) {
1060 dp->mode = adjustMode[0].mode;
1061 dp->print = adjustMode[0].print;
1062 }
1063 else {
1064 dp->mode = adjustMode[1].mode;
1065 dp->print = adjustMode[1].print;
1066 }
1067 if (dp->mode == AM_PRISM)
1068 setPrismValues (g, "", dp);
1069 }
1070 }
1071 if (Verbose) {
1072 fprintf(stderr, "overlap: %s value %d scaling %.04f\n", dp->print, dp->value, dp->scaling);
1073 }
1074 return dp;
1075}
1076
1077adjust_data *graphAdjustMode(graph_t *G, adjust_data* dp, char* dflt)
1078{
1079 char* am = agget(G, "overlap");
1080 return (getAdjustMode (G, am ? am : (dflt ? dflt : ""), dp));
1081}
1082
1083#define ISZERO(d) ((fabs(d) < 0.000000001))
1084
1085/* simpleScaling:
1086 */
1087static int simpleScale (graph_t* g)
1088{
1089 pointf sc;
1090 node_t* n;
1091 int i;
1092 char* p;
1093
1094 if ((p = agget(g, "scale"))) {
1095 if ((i = sscanf(p, "%lf,%lf", &sc.x, &sc.y))) {
1096 if (ISZERO(sc.x)) return 0;
1097 if (i == 1) sc.y = sc.x;
1098 else if (ISZERO(sc.y)) return 0;
1099 if ((sc.y == 1) && (sc.x == 1)) return 0;
1100 if (Verbose)
1101 fprintf (stderr, "scale = (%.03f,%.03f)\n", sc.x, sc.y);
1102 for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
1103 ND_pos(n)[0] *= sc.x;
1104 ND_pos(n)[1] *= sc.y;
1105 }
1106 return 1;
1107 }
1108 }
1109 return 0;
1110}
1111
1112/* removeOverlapWith:
1113 * Use adjust_data to determine if and how to remove
1114 * node overlaps.
1115 * Return non-zero if nodes are moved.
1116 */
1117int
1118removeOverlapWith (graph_t * G, adjust_data* am)
1119{
1120 int ret, nret;
1121
1122 if (agnnodes(G) < 2)
1123 return 0;
1124
1125 nret = normalize (G);
1126 nret += simpleScale (G);
1127
1128 if (am->mode == AM_NONE)
1129 return nret;
1130
1131 if (Verbose)
1132 fprintf(stderr, "Adjusting %s using %s\n", agnameof(G), am->print);
1133
1134 if (am->mode > AM_SCALE) {
1135/* start_timer(); */
1136 switch (am->mode) {
1137 case AM_NSCALE:
1138 ret = scAdjust(G, 1);
1139 break;
1140 case AM_SCALEXY:
1141 ret = scAdjust(G, 0);
1142 break;
1143 case AM_PUSH:
1144 /* scanAdjust (G, 1); */
1145 ret = 0;
1146 break;
1147 case AM_PUSHPULL:
1148 /* scanAdjust (G, 0); */
1149 ret = 0;
1150 break;
1151 case AM_PORTHO_YX:
1152 case AM_PORTHO:
1153 case AM_PORTHOXY:
1154 case AM_PORTHOYX:
1155 case AM_ORTHO_YX:
1156 case AM_ORTHO:
1157 case AM_ORTHOXY:
1158 case AM_ORTHOYX:
1159 cAdjust(G, am->mode);
1160 ret = 0;
1161 break;
1162 case AM_COMPRESS:
1163 ret = scAdjust(G, -1);
1164 break;
1165#if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
1166 case AM_PRISM:
1167 ret = fdpAdjust(G, am);
1168 break;
1169#endif
1170#ifdef IPSEPCOLA
1171 case AM_IPSEP:
1172 return nret; /* handled during layout */
1173 break;
1174 case AM_VPSC:
1175 ret = vpscAdjust(G);
1176 break;
1177#endif
1178 default: /* to silence warnings */
1179 if ((am->mode != AM_VOR) && (am->mode != AM_SCALE))
1180 agerr(AGWARN, "Unhandled adjust option %s\n", am->print);
1181 ret = 0;
1182 break;
1183 }
1184/* fprintf (stderr, "%s %.4f sec\n", am->print, elapsed_sec()); */
1185 return nret+ret;
1186 }
1187
1188 /* create main array */
1189/* start_timer(); */
1190 if (makeInfo(G)) {
1191 freeNodes();
1192 free(sites);
1193 sites = 0;
1194 return nret;
1195 }
1196
1197 /* establish and verify bounding box */
1198 chkBoundBox(G);
1199
1200 if (am->mode == AM_SCALE)
1201 ret = sAdjust();
1202 else
1203 ret = vAdjust();
1204
1205 if (ret)
1206 updateGraph(G);
1207
1208 freeNodes();
1209 free(sites);
1210 sites = 0;
1211/* fprintf (stderr, "%s %.4f sec\n", am->print, elapsed_sec()); */
1212
1213 return ret+nret;
1214}
1215
1216/* removeOverlapAs:
1217 * Use flag value to determine if and how to remove
1218 * node overlaps.
1219 */
1220int
1221removeOverlapAs(graph_t * G, char* flag)
1222{
1223 adjust_data am;
1224
1225 if (agnnodes(G) < 2)
1226 return 0;
1227 getAdjustMode(G, flag, &am);
1228 return removeOverlapWith (G, &am);
1229}
1230
1231/* adjustNodes:
1232 * Remove node overlap relying on graph's overlap attribute.
1233 * Return non-zero if graph has changed.
1234 */
1235int adjustNodes(graph_t * G)
1236{
1237 return (removeOverlapAs(G, agget(G, "overlap")));
1238}
1239
1240/* parseFactor:
1241 * Convert "sep" attribute into expand_t.
1242 * Input "+x,y" becomes {x,y,true}
1243 * Input "x,y" becomes {1 + x/sepfact,1 + y/sepfact,false}
1244 * Return 1 on success, 0 on failure
1245 */
1246static int
1247parseFactor (char* s, expand_t* pp, float sepfact, float dflt)
1248{
1249 int i;
1250 float x, y;
1251
1252 while (isspace(*s)) s++;
1253 if (*s == '+') {
1254 s++;
1255 pp->doAdd = 1;
1256 }
1257 else pp->doAdd = 0;
1258
1259 if ((i = sscanf(s, "%f,%f", &x, &y))) {
1260 if (i == 1) y = x;
1261 if (pp->doAdd) {
1262 if (sepfact > 1) {
1263 pp->x = MIN(dflt,x/sepfact);
1264 pp->y = MIN(dflt,y/sepfact);
1265 }
1266 else if (sepfact < 1) {
1267 pp->x = MAX(dflt,x/sepfact);
1268 pp->y = MAX(dflt,y/sepfact);
1269 }
1270 else {
1271 pp->x = x;
1272 pp->y = y;
1273 }
1274 }
1275 else {
1276 pp->x = 1.0 + x/sepfact;
1277 pp->y = 1.0 + y/sepfact;
1278 }
1279 return 1;
1280 }
1281 else return 0;
1282}
1283
1284/* sepFactor:
1285 */
1286expand_t
1287sepFactor(graph_t* g)
1288{
1289 expand_t pmargin;
1290 char* marg;
1291
1292 if ((marg = agget(g, "sep")) && parseFactor(marg, &pmargin, 1.0, 0)) {
1293 }
1294 else if ((marg = agget(g, "esep")) && parseFactor(marg, &pmargin, SEPFACT, DFLT_MARGIN)) {
1295 }
1296 else { /* default */
1297 pmargin.x = pmargin.y = DFLT_MARGIN;
1298 pmargin.doAdd = 1;
1299 }
1300 if (Verbose)
1301 fprintf (stderr, "Node separation: add=%d (%f,%f)\n",
1302 pmargin.doAdd, pmargin.x, pmargin.y);
1303 return pmargin;
1304}
1305
1306/* esepFactor:
1307 * This value should be smaller than the sep value used to expand
1308 * nodes during adjustment. If not, when the adjustment pass produces
1309 * a fairly tight layout, the spline code will find that some nodes
1310 * still overlap.
1311 */
1312expand_t
1313esepFactor(graph_t* g)
1314{
1315 expand_t pmargin;
1316 char* marg;
1317
1318 if ((marg = agget(g, "esep")) && parseFactor(marg, &pmargin, 1.0, 0)) {
1319 }
1320 else if ((marg = agget(g, "sep")) && parseFactor(marg, &pmargin, 1.0/SEPFACT, SEPFACT*DFLT_MARGIN)) {
1321 }
1322 else {
1323 pmargin.x = pmargin.y = SEPFACT*DFLT_MARGIN;
1324 pmargin.doAdd = 1;
1325 }
1326 if (Verbose)
1327 fprintf (stderr, "Edge separation: add=%d (%f,%f)\n",
1328 pmargin.doAdd, pmargin.x, pmargin.y);
1329 return pmargin;
1330}
1331