Graphviz 14.0.2~dev.20251008.0253
Loading...
Searching...
No Matches
adjust.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/* adjust.c
12 * Routines for repositioning nodes after initial layout in
13 * order to reduce/remove node overlaps.
14 */
15
16#include <assert.h>
17#include <neatogen/neato.h>
18#include <common/utils.h>
19#include <float.h>
20#include <math.h>
21#include <neatogen/voronoi.h>
22#include <neatogen/info.h>
23#include <neatogen/edges.h>
24#include <neatogen/site.h>
25#include <neatogen/digcola.h>
26#if defined(HAVE_GTS) && defined(SFDP)
27#include <neatogen/overlap.h>
28#endif
29#include <stdbool.h>
30#ifdef IPSEPCOLA
31#include <vpsc/csolve_VPSC.h>
33#endif
34#include <stddef.h>
35#include <util/agxbuf.h>
36#include <util/alloc.h>
37#include <util/debug.h>
38#include <util/gv_ctype.h>
39#include <util/startswith.h>
40#include <util/strcasecmp.h>
41
42#define SEPFACT 0.8 // default esep/sep
43
44static const double incr = 0.05; /* Increase bounding box by adding
45 * incr * dimension around box.
46 */
47
48typedef struct {
51 Point nw, ne, sw, se;
53} state_t;
54
55static void setBoundBox(state_t *st, Point *ll, Point *ur) {
56 pxmin = ll->x;
57 pxmax = ur->x;
58 pymin = ll->y;
59 pymax = ur->y;
60 st->nw.x = st->sw.x = pxmin;
61 st->ne.x = st->se.x = pxmax;
62 st->nw.y = st->ne.y = pymax;
63 st->sw.y = st->se.y = pymin;
64}
65
67static void freeNodes(void)
68{
69 for (size_t i = 0; i < nsites; i++) {
71 }
72 polyFree();
73 if (nodeInfo != NULL) {
74 free(nodeInfo->verts); // Free vertices
75 }
77}
78
79/* Compute extremes of graph, then set up bounding box.
80 * If user supplied a bounding box, use that;
81 * else if "window" is a graph attribute, use that;
82 * otherwise, define bounding box as a percentage expansion of
83 * graph extremes.
84 * In the first two cases, check that graph fits in bounding box.
85 */
86static void chkBoundBox(state_t *st, Agraph_t *graph) {
87 Point ll, ur;
88
89 double x_min = DBL_MAX;
90 double y_min = DBL_MAX;
91 double x_max = -DBL_MAX;
92 double y_max = -DBL_MAX;
93 assert(nsites > 0);
94 for (size_t i = 0; i < nsites; ++i) {
95 Info_t *ip = &nodeInfo[i];
96 Poly *pp = &ip->poly;
97 double x = ip->site.coord.x;
98 double y = ip->site.coord.y;
99 x_min = fmin(x_min, pp->origin.x + x);
100 y_min = fmin(y_min, pp->origin.y + y);
101 x_max = fmax(x_max, pp->corner.x + x);
102 y_max = fmax(y_max, pp->corner.y + y);
103 }
104
105 // create initial bounding box by adding margin × dimension around box
106 // enclosing nodes
107 char *marg = agget(graph, "voro_margin");
108 const double margin = (marg && *marg != '\0') ? atof(marg) : 0.05;
109 double ydelta = margin * (y_max - y_min);
110 double xdelta = margin * (x_max - x_min);
111 ll.x = x_min - xdelta;
112 ll.y = y_min - ydelta;
113 ur.x = x_max + xdelta;
114 ur.y = y_max + ydelta;
115
116 setBoundBox(st, &ll, &ur);
117}
118
121{
122 int (*polyf)(Poly *, Agnode_t *, double, double);
123
124 assert(agnnodes(graph) >= 0);
125 nsites = (size_t)agnnodes(graph);
126 geominit();
127
128 nodeInfo = gv_calloc(nsites, sizeof(Info_t));
129
131
132 expand_t pmargin = sepFactor (graph);
133
134 if (pmargin.doAdd) {
135 polyf = makeAddPoly;
136 /* we need inches for makeAddPoly */
137 pmargin.x = PS2INCH(pmargin.x);
138 pmargin.y = PS2INCH(pmargin.y);
139 }
140
141 else polyf = makePoly;
142 for (size_t i = 0; i < nsites; i++) {
143 Info_t *ip = &nodeInfo[i];
144 ip->site.coord.x = ND_pos(node)[0];
145 ip->site.coord.y = ND_pos(node)[1];
146
147 if (polyf(&ip->poly, node, pmargin.x, pmargin.y)) {
148 free (nodeInfo);
149 nodeInfo = NULL;
150 return 1;
151 }
152
153 ip->site.sitenbr = i;
154 ip->node = node;
155 ip->verts = NULL;
156 ip->n_verts = 0;
158 }
159 return 0;
160}
161
162/* sort sites on y, then x, coord */
163static int scomp(const void *S1, const void *S2)
164{
165 const Site *s1 = *(Site *const *)S1;
166 const Site *s2 = *(Site *const *)S2;
167 if (s1->coord.y < s2->coord.y)
168 return -1;
169 if (s1->coord.y > s2->coord.y)
170 return 1;
171 if (s1->coord.x < s2->coord.x)
172 return -1;
173 if (s1->coord.x > s2->coord.x)
174 return 1;
175 return 0;
176}
177
179static void sortSites(state_t *st) {
180 if (st->sites == NULL) {
181 st->sites = gv_calloc(nsites, sizeof(Site*));
182 st->endSite = st->sites + nsites;
183 }
184
185 for (size_t i = 0; i < nsites; i++) {
186 Info_t *ip = &nodeInfo[i];
187 st->sites[i] = &ip->site;
188 ip->verts = NULL;
189 ip->n_verts = 0;
190 }
191
192 qsort(st->sites, nsites, sizeof(Site *), scomp);
193
194 /* Reset site index for nextOne */
195 st->nextSite = st->sites;
196
197}
198
199static void geomUpdate(state_t *st, int doSort) {
200 if (doSort)
201 sortSites(st);
202
203 /* compute ranges */
204 xmin = DBL_MAX;
205 xmax = -DBL_MAX;
206 assert(nsites > 0);
207 for (size_t i = 0; i < nsites; ++i) {
208 xmin = fmin(xmin, st->sites[i]->coord.x);
209 xmax = fmax(xmax, st->sites[i]->coord.x);
210 }
211 ymin = st->sites[0]->coord.y;
212 ymax = st->sites[nsites - 1]->coord.y;
213
214 deltax = xmax - xmin;
215}
216
217static Site *nextOne(void *state) {
218 state_t *st = state;
219 if (st->nextSite < st->endSite) {
220 return *st->nextSite++;
221 } else
222 return NULL;
223}
224
226static void rmEquality(state_t *st) {
227 sortSites(st);
228
229 for (Site **ip = st->sites; ip < st->endSite; ) {
230 Site **jp = ip + 1;
231 if (jp >= st->endSite ||
232 (*jp)->coord.x != (*ip)->coord.x ||
233 (*jp)->coord.y != (*ip)->coord.y) {
234 ip = jp;
235 continue;
236 }
237
238 /* Find first node kp with position different from ip */
239 int cnt = 2;
240 Site **kp = jp + 1;
241 while (kp < st->endSite &&
242 (*kp)->coord.x == (*ip)->coord.x &&
243 (*kp)->coord.y == (*ip)->coord.y) {
244 cnt++;
245 jp = kp;
246 kp = jp + 1;
247 }
248
249 /* If next node exists and is on the same line */
250 if (kp < st->endSite && (*kp)->coord.y == (*ip)->coord.y) {
251 const double xdel = ((*kp)->coord.x - (*ip)->coord.x) / cnt;
252 int i = 1;
253 for (jp = ip + 1; jp < kp; jp++) {
254 (*jp)->coord.x += i * xdel;
255 i++;
256 }
257 } else { /* nothing is to the right */
258 Info_t *info;
259 for (jp = ip + 1; jp < kp; ip++, jp++) {
260 info = nodeInfo + (*ip)->sitenbr;
261 double xdel = info->poly.corner.x - info->poly.origin.x;
262 info = nodeInfo + (*jp)->sitenbr;
263 xdel += info->poly.corner.x - info->poly.origin.x;
264 (*jp)->coord.x = (*ip)->coord.x + xdel / 2;
265 }
266 }
267 ip = kp;
268 }
269}
270
272static unsigned countOverlap(unsigned iter) {
273 unsigned count = 0;
274
275 for (size_t i = 0; i < nsites; i++)
276 nodeInfo[i].overlaps = false;
277
278 for (size_t i = 0; i < nsites - 1; i++) {
279 Info_t *ip = &nodeInfo[i];
280 for (size_t j = i + 1; j < nsites; j++) {
281 Info_t *jp = &nodeInfo[j];
282 if (polyOverlap(ip->site.coord, &ip->poly, jp->site.coord, &jp->poly)) {
283 count++;
284 ip->overlaps = true;
285 jp->overlaps = true;
286 }
287 }
288 }
289
290 if (Verbose > 1)
291 fprintf(stderr, "overlap [%u] : %u\n", iter, count);
292 return count;
293}
294
295static void increaseBoundBox(state_t *st) {
296 Point ur = {.x = pxmax, .y = pymax};
297 Point ll = {.x = pxmin, .y = pymin};
298
299 const double ydelta = incr * (ur.y - ll.y);
300 const double xdelta = incr * (ur.x - ll.x);
301
302 ur.x += xdelta;
303 ur.y += ydelta;
304 ll.x -= xdelta;
305 ll.y -= ydelta;
306
307 setBoundBox(st, &ll, &ur);
308}
309
311static double areaOf(Point a, Point b, Point c)
312{
313 return fabs(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2;
314}
315
316/* Compute centroid of triangle with vertices a, b, c.
317 * Return coordinates in x and y.
318 */
319static void centroidOf(Point a, Point b, Point c, double *x, double *y)
320{
321 *x = (a.x + b.x + c.x) / 3;
322 *y = (a.y + b.y + c.y) / 3;
323}
324
325/* The new position is the centroid of the voronoi polygon. This is the weighted
326 * sum of the centroids of a triangulation, normalized to the total area.
327 */
328static void newpos(Info_t * ip)
329{
330 const Point anchor = ip->verts[0];
331 double totalArea = 0.0;
332 double cx = 0.0;
333 double cy = 0.0;
334 double x;
335 double y;
336
337 for (size_t i = 1; i + 1 < ip->n_verts; ++i) {
338 const Point p = ip->verts[i];
339 const Point q = ip->verts[i + 1];
340 const double area = areaOf(anchor, p, q);
341 centroidOf(anchor, p, q, &x, &y);
342 cx += area * x;
343 cy += area * y;
344 totalArea += area;
345 }
346
347 ip->site.coord.x = cx / totalArea;
348 ip->site.coord.y = cy / totalArea;
349}
350
351 /* Add corners of clipping window to appropriate sites.
352 * A site gets a corner if it is the closest site to that corner.
353 */
354static void addCorners(const state_t *st) {
355 Info_t *ip = nodeInfo;
356 Info_t *sws = ip;
357 Info_t *nws = ip;
358 Info_t *ses = ip;
359 Info_t *nes = ip;
360 double swd = dist_2(ip->site.coord, st->sw);
361 double nwd = dist_2(ip->site.coord, st->nw);
362 double sed = dist_2(ip->site.coord, st->se);
363 double ned = dist_2(ip->site.coord, st->ne);
364
365 for (size_t i = 1; i < nsites; i++) {
366 ip = &nodeInfo[i];
367 double d = dist_2(ip->site.coord, st->sw);
368 if (d < swd) {
369 swd = d;
370 sws = ip;
371 }
372 d = dist_2(ip->site.coord, st->se);
373 if (d < sed) {
374 sed = d;
375 ses = ip;
376 }
377 d = dist_2(ip->site.coord, st->nw);
378 if (d < nwd) {
379 nwd = d;
380 nws = ip;
381 }
382 d = dist_2(ip->site.coord, st->ne);
383 if (d < ned) {
384 ned = d;
385 nes = ip;
386 }
387 }
388
389 addVertex(&sws->site, st->sw.x, st->sw.y);
390 addVertex(&ses->site, st->se.x, st->se.y);
391 addVertex(&nws->site, st->nw.x, st->nw.y);
392 addVertex(&nes->site, st->ne.x, st->ne.y);
393}
394
395 /* Calculate the new position of a site as the centroid
396 * of its voronoi polygon, if it overlaps other nodes.
397 * The polygons are finite by being clipped to the clipping
398 * window.
399 * We first add the corner of the clipping windows to the
400 * vertex lists of the appropriate sites.
401 *
402 * @param st Algorithm state
403 * @param doAll Move all nodes, regardless of overlap
404 */
405static void newPos(const state_t *st, bool doAll) {
406 addCorners(st);
407 for (size_t i = 0; i < nsites; i++) {
408 Info_t *ip = &nodeInfo[i];
409 if (doAll || ip->overlaps)
410 newpos(ip);
411 }
412}
413
414static int vAdjust(state_t *st) {
415 unsigned iterCnt = 0;
416 unsigned badLevel = 0;
417 unsigned increaseCnt = 0;
418
419 unsigned overlapCnt = countOverlap(iterCnt);
420
421 if (overlapCnt == 0)
422 return 0;
423
424 rmEquality(st);
425 geomUpdate(st, 0);
426 voronoi(nextOne, st);
427 for (bool doAll = false;;) {
428 newPos(st, doAll);
429 iterCnt++;
430
431 const unsigned cnt = countOverlap(iterCnt);
432 if (cnt == 0)
433 break;
434 if (cnt >= overlapCnt)
435 badLevel++;
436 else
437 badLevel = 0;
438 overlapCnt = cnt;
439
440 switch (badLevel) {
441 case 0:
442 doAll = true;
443 break;
444 default:
445 doAll = true;
446 increaseCnt++;
448 break;
449 }
450
451 geomUpdate(st, 1);
452 voronoi(nextOne, st);
453 }
454
455 GV_DEBUG("Number of iterations = %u", iterCnt);
456 GV_DEBUG("Number of increases = %u", increaseCnt);
457
458 return 1;
459}
460
461static void rePos(void) {
462 double f = 1.0 + incr;
463
464 for (size_t i = 0; i < nsites; i++) {
465 Info_t *ip = &nodeInfo[i];
466 ip->site.coord.x *= f;
467 ip->site.coord.y *= f;
468 }
469}
470
471static int sAdjust(state_t *st) {
472 unsigned iterCnt = 0;
473
474 const unsigned overlapCnt = countOverlap(iterCnt);
475
476 if (overlapCnt == 0)
477 return 0;
478
479 rmEquality(st);
480 while (1) {
481 rePos();
482 iterCnt++;
483
484 const unsigned cnt = countOverlap(iterCnt);
485 if (cnt == 0)
486 break;
487 }
488
489 if (Verbose) {
490 fprintf(stderr, "Number of iterations = %u\n", iterCnt);
491 }
492
493 return 1;
494}
495
497static void updateGraph(void)
498{
499 for (size_t i = 0; i < nsites; i++) {
500 Info_t *ip = &nodeInfo[i];
501 ND_pos(ip->node)[0] = ip->site.coord.x;
502 ND_pos(ip->node)[1] = ip->site.coord.y;
503 }
504}
505
506#define ELS "|edgelabel|"
507 /* Return true if node name starts with ELS */
508#define IS_LNODE(n) startswith(agnameof(n), ELS)
509
511double *getSizes(Agraph_t * g, pointf pad, int* n_elabels, int** elabels)
512{
513 double *sizes = gv_calloc(Ndim * agnnodes(g), sizeof(double));
514 int nedge_nodes = 0;
515
516 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
517 if (elabels && IS_LNODE(n)) nedge_nodes++;
518
519 const int i = ND_id(n);
520 sizes[i * Ndim] = ND_width(n) * .5 + pad.x;
521 sizes[i * Ndim + 1] = ND_height(n) * .5 + pad.y;
522 }
523
524 if (elabels && nedge_nodes) {
525 int* elabs = gv_calloc(nedge_nodes, sizeof(int));
526 nedge_nodes = 0;
527 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
528 if (IS_LNODE(n))
529 elabs[nedge_nodes++] = ND_id(n);
530 }
531 *elabels = elabs;
532 *n_elabels = nedge_nodes;
533 }
534
535 return sizes;
536}
537
538/* Assumes g is connected and simple, i.e., we can have a->b and b->a
539 * but not a->b and a->b
540 */
542 if (!g)
543 return NULL;
544 const int nnodes = agnnodes(g);
545 const int nedges = agnedges(g);
546
547 /* Assign node ids */
548 int i = 0;
549 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n))
550 ND_id(n) = i++;
551
552 int *I = gv_calloc(nedges, sizeof(int));
553 int *J = gv_calloc(nedges, sizeof(int));
554 double *val = gv_calloc(nedges, sizeof(double));
555
556 Agsym_t *sym = agfindedgeattr(g, "weight");
557
558 i = 0;
559 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
560 const int row = ND_id(n);
561 for (Agedge_t *e = agfstout(g, n); e; e = agnxtout(g, e)) {
562 I[i] = row;
563 J[i] = ND_id(aghead(e));
564 double v;
565 if (!sym || sscanf(agxget(e, sym), "%lf", &v) != 1)
566 v = 1;
567 val[i] = v;
568 /* edge length */
569 i++;
570 }
571 }
572
574 I, J, val,
576 sizeof(double));
577
578 free(I);
579 free(J);
580 free(val);
581
582 return A;
583}
584
585#if defined(HAVE_GTS) && defined(SFDP)
586static void fdpAdjust(graph_t *g, adjust_data *am) {
587 SparseMatrix A0 = makeMatrix(g);
588 SparseMatrix A = A0;
589 double *pos = gv_calloc(Ndim * agnnodes(g), sizeof(double));
590 expand_t sep = sepFactor(g);
591 pointf pad;
592
593 if (sep.doAdd) {
594 pad.x = PS2INCH(sep.x);
595 pad.y = PS2INCH(sep.y);
596 } else {
597 pad.x = PS2INCH(DFLT_MARGIN);
598 pad.y = PS2INCH(DFLT_MARGIN);
599 }
600 double *sizes = getSizes(g, pad, NULL, NULL);
601
602 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
603 double* npos = pos + Ndim * ND_id(n);
604 for (int i = 0; i < Ndim; i++) {
605 npos[i] = ND_pos(n)[i];
606 }
607 }
608
609 if (!SparseMatrix_is_symmetric(A, false) || A->type != MATRIX_TYPE_REAL) {
611 } else {
613 }
614
615 remove_overlap(Ndim, A, pos, sizes, am->value, am->scaling,
617 mapBool(agget(g, "overlap_shrink"), true));
618
619 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
620 double *npos = pos + Ndim * ND_id(n);
621 for (int i = 0; i < Ndim; i++) {
622 ND_pos(n)[i] = npos[i];
623 }
624 }
625
626 free(sizes);
627 free(pos);
628 if (A != A0)
631}
632#endif
633
634#ifdef IPSEPCOLA
635static int
636vpscAdjust(graph_t* G)
637{
638 enum { dim = 2 };
639 int nnodes = agnnodes(G);
640 ipsep_options opt;
641 pointf *nsize = gv_calloc(nnodes, sizeof(pointf));
642 float* coords[dim];
643 float *f_storage = gv_calloc(dim * nnodes, sizeof(float));
644
645 for (size_t i = 0; i < dim; i++) {
646 coords[i] = f_storage + i * nnodes;
647 }
648
649 size_t j = 0;
650 for (Agnode_t *v = agfstnode(G); v; v = agnxtnode(G, v)) {
651 for (size_t i = 0; i < dim; i++) {
652 coords[i][j] = (float)ND_pos(v)[i];
653 }
654 nsize[j].x = ND_width(v);
655 nsize[j].y = ND_height(v);
656 j++;
657 }
658
659 opt.diredges = 0;
660 opt.edge_gap = 0;
661 opt.noverlap = 2;
662 opt.clusters = (cluster_data){0};
663 expand_t exp_margin = sepFactor (G);
664 /* Multiply by 2 since opt.gap is the gap size, not the margin */
665 if (exp_margin.doAdd) {
666 opt.gap.x = 2.0*PS2INCH(exp_margin.x);
667 opt.gap.y = 2.0*PS2INCH(exp_margin.y);
668 }
669 else {
670 opt.gap.x = opt.gap.y = 2.0*PS2INCH(DFLT_MARGIN);
671 }
672 opt.nsize = nsize;
673
674 removeoverlaps(nnodes, coords, &opt);
675
676 j = 0;
677 for (Agnode_t *v = agfstnode(G); v; v = agnxtnode(G, v)) {
678 for (size_t i = 0; i < dim; i++) {
679 ND_pos(v)[i] = coords[i][j];
680 }
681 j++;
682 }
683
684 free (f_storage);
685 free (nsize);
686 return 0;
687}
688#endif
689
690/* Return true if "normalize" is defined and valid; return angle in phi.
691 * Read angle as degrees, convert to radians.
692 * Guarantee -PI < phi <= PI.
693 */
694static int
695angleSet (graph_t* g, double* phi)
696{
697 char* p;
698 char* a = agget(g, "normalize");
699
700 if (!a || *a == '\0')
701 return 0;
702 double ang = strtod (a, &p);
703 if (p == a) { /* no number */
704 if (mapbool(a))
705 ang = 0.0;
706 else
707 return 0;
708 }
709 while (ang > 180) ang -= 360;
710 while (ang <= -180) ang += 360;
711
712 *phi = RADIANS(ang);
713 return 1;
714}
715
716/* If normalize is set, move first node to origin, then
717 * rotate graph so that the angle of the first edge is given
718 * by the degrees from normalize.
719 * FIX: Generalize to allow rotation determined by graph shape.
720 */
722{
723 double phi;
724 int ret;
725
726 if (!angleSet(g, &phi))
727 return 0;
728
729 node_t *v = agfstnode(g);
730 pointf p = {.x = ND_pos(v)[0], .y = ND_pos(v)[1]};
731 for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
732 ND_pos(v)[0] -= p.x;
733 ND_pos(v)[1] -= p.y;
734 }
735 if (p.x || p.y) ret = 1;
736 else ret = 0;
737
738 edge_t *e = NULL;
739 for (v = agfstnode(g); v; v = agnxtnode(g, v))
740 if ((e = agfstout(g, v)))
741 break;
742 if (e == NULL)
743 return ret;
744
745 /* rotation necessary; pos => ccw */
746 phi -= atan2(ND_pos(aghead(e))[1] - ND_pos(agtail(e))[1],
747 ND_pos(aghead(e))[0] - ND_pos(agtail(e))[0]);
748
749 if (phi) {
750 const pointf orig = {.x = ND_pos(agtail(e))[0],
751 .y = ND_pos(agtail(e))[1]};
752 const double cosv = cos(phi);
753 const double sinv = sin(phi);
754 for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
755 p.x = ND_pos(v)[0] - orig.x;
756 p.y = ND_pos(v)[1] - orig.y;
757 ND_pos(v)[0] = p.x * cosv - p.y * sinv + orig.x;
758 ND_pos(v)[1] = p.x * sinv + p.y * cosv + orig.y;
759 }
760 return 1;
761 }
762 else return ret;
763}
764
765typedef struct {
767 char *attrib;
768 char *print;
769} lookup_t;
770
771/* Translation table from overlap values to algorithms.
772 * adjustMode[0] corresponds to overlap=true
773 * adjustMode[1] corresponds to overlap=false
774 */
775static const lookup_t adjustMode[] = {
776 {AM_NONE, "", "none"},
777#if defined(HAVE_GTS) && defined(SFDP)
778 {AM_PRISM, "prism", "prism"},
779#endif
780 {AM_VOR, "voronoi", "Voronoi"},
781 {AM_NSCALE, "scale", "scaling"},
782 {AM_COMPRESS, "compress", "compress"},
783 {AM_VPSC, "vpsc", "vpsc"},
784 {AM_IPSEP, "ipsep", "ipsep"},
785 {AM_SCALE, "oscale", "old scaling"},
786 {AM_SCALEXY, "scalexy", "x and y scaling"},
787 {AM_ORTHO, "ortho", "orthogonal constraints"},
788 {AM_ORTHO_YX, "ortho_yx", "orthogonal constraints"},
789 {AM_ORTHOXY, "orthoxy", "xy orthogonal constraints"},
790 {AM_ORTHOYX, "orthoyx", "yx orthogonal constraints"},
791 {AM_PORTHO, "portho", "pseudo-orthogonal constraints"},
792 {AM_PORTHO_YX, "portho_yx", "pseudo-orthogonal constraints"},
793 {AM_PORTHOXY, "porthoxy", "xy pseudo-orthogonal constraints"},
794 {AM_PORTHOYX, "porthoyx", "yx pseudo-orthogonal constraints"},
795#if !(defined(HAVE_GTS) && defined(SFDP))
796 {AM_PRISM, "prism", 0},
797#endif
798 {0}
799};
800
802static void setPrismValues(Agraph_t *g, const char *s, adjust_data *dp) {
803 int v;
804
805 if (sscanf (s, "%d", &v) > 0 && v >= 0)
806 dp->value = v;
807 else
808 dp->value = 1000;
809 dp->scaling = late_double(g, agfindgraphattr(g, "overlap_scaling"), -4.0, -1.e10);
810}
811
813static void getAdjustMode(Agraph_t *g, const char *s, adjust_data *dp) {
814 const lookup_t *ap = adjustMode + 1;
815 if (s == NULL || *s == '\0') {
816 dp->mode = adjustMode[0].mode;
817 dp->print = adjustMode[0].print;
818 }
819 else {
820 while (ap->attrib) {
821 bool matches = strcasecmp(s, ap->attrib) == 0;
822 // "prism" takes parameters, so needs to match "prism.*"
823 matches |= ap->mode == AM_PRISM
824 && strncasecmp(s, ap->attrib, strlen(ap->attrib)) == 0;
825 if (matches) {
826 if (ap->print == NULL) {
827 agwarningf("Overlap value \"%s\" unsupported - ignored\n", ap->attrib);
828 ap = &adjustMode[1];
829 }
830 dp->mode = ap->mode;
831 dp->print = ap->print;
832 if (ap->mode == AM_PRISM)
833 setPrismValues(g, s + strlen(ap->attrib), dp);
834 break;
835 }
836 ap++;
837 }
838 if (ap->attrib == NULL ) {
839 bool v = mapbool(s);
840 bool unmappable = v != mapBool(s, true);
841 if (unmappable) {
842 agwarningf("Unrecognized overlap value \"%s\" - using false\n", s);
843 v = false;
844 }
845 if (v) {
846 dp->mode = adjustMode[0].mode;
847 dp->print = adjustMode[0].print;
848 }
849 else {
850 dp->mode = adjustMode[1].mode;
851 dp->print = adjustMode[1].print;
852 }
853 if (dp->mode == AM_PRISM)
854 setPrismValues (g, "", dp);
855 }
856 }
857 if (Verbose) {
858 fprintf(stderr, "overlap: %s value %d scaling %.04f\n", dp->print, dp->value, dp->scaling);
859 }
860}
861
862void graphAdjustMode(graph_t *G, adjust_data *dp, char *dflt) {
863 char* am = agget(G, "overlap");
864 getAdjustMode (G, am ? am : (dflt ? dflt : ""), dp);
865}
866
867#define ISZERO(d) (fabs(d) < 0.000000001)
868
869static int simpleScale (graph_t* g)
870{
871 pointf sc;
872 int i;
873 char* p;
874
875 if ((p = agget(g, "scale"))) {
876 if ((i = sscanf(p, "%lf,%lf", &sc.x, &sc.y))) {
877 if (ISZERO(sc.x)) return 0;
878 if (i == 1) sc.y = sc.x;
879 else if (ISZERO(sc.y)) return 0;
880 if (sc.y == 1 && sc.x == 1) return 0;
881 if (Verbose)
882 fprintf (stderr, "scale = (%.03f,%.03f)\n", sc.x, sc.y);
883 for (node_t *n = agfstnode(g); n; n = agnxtnode(g,n)) {
884 ND_pos(n)[0] *= sc.x;
885 ND_pos(n)[1] *= sc.y;
886 }
887 return 1;
888 }
889 }
890 return 0;
891}
892
893/* Use adjust_data to determine if and how to remove
894 * node overlaps.
895 * Return non-zero if nodes are moved.
896 */
897int
899{
900 int ret;
901
902 if (agnnodes(G) < 2)
903 return 0;
904
905 int nret = normalize (G);
906 nret += simpleScale (G);
907
908 if (am->mode == AM_NONE)
909 return nret;
910
911 if (Verbose)
912 fprintf(stderr, "Adjusting %s using %s\n", agnameof(G), am->print);
913
914 if (am->mode > AM_SCALE) {
915 switch (am->mode) {
916 case AM_NSCALE:
917 ret = scAdjust(G, 1);
918 break;
919 case AM_SCALEXY:
920 ret = scAdjust(G, 0);
921 break;
922 case AM_PORTHO_YX:
923 case AM_PORTHO:
924 case AM_PORTHOXY:
925 case AM_PORTHOYX:
926 case AM_ORTHO_YX:
927 case AM_ORTHO:
928 case AM_ORTHOXY:
929 case AM_ORTHOYX:
930 cAdjust(G, am->mode);
931 ret = 0;
932 break;
933 case AM_COMPRESS:
934 ret = scAdjust(G, -1);
935 break;
936#if defined(HAVE_GTS) && defined(SFDP)
937 case AM_PRISM:
938 fdpAdjust(G, am);
939 ret = 0;
940 break;
941#endif
942#ifdef IPSEPCOLA
943 case AM_IPSEP:
944 return nret; /* handled during layout */
945 break;
946 case AM_VPSC:
947 ret = vpscAdjust(G);
948 break;
949#endif
950 default: /* to silence warnings */
951 if (am->mode != AM_VOR && am->mode != AM_SCALE)
952 agwarningf("Unhandled adjust option %s\n", am->print);
953 ret = 0;
954 break;
955 }
956 return nret+ret;
957 }
958
959 /* create main array */
960 if (makeInfo(G)) {
961 freeNodes();
962 return nret;
963 }
964
965 /* establish and verify bounding box */
966 state_t st = {0};
967 chkBoundBox(&st, G);
968
969 if (am->mode == AM_SCALE)
970 ret = sAdjust(&st);
971 else
972 ret = vAdjust(&st);
973
974 if (ret)
975 updateGraph();
976
977 freeNodes();
978 free(st.sites);
979
980 return ret+nret;
981}
982
984int
986{
987 adjust_data am;
988
989 if (agnnodes(G) < 2)
990 return 0;
991 getAdjustMode(G, flag, &am);
992 return removeOverlapWith (G, &am);
993}
994
995/* Remove node overlap relying on graph's overlap attribute.
996 * Return non-zero if graph has changed.
997 */
999{
1000 return removeOverlapAs(G, agget(G, "overlap"));
1001}
1002
1003/* Convert "sep" attribute into expand_t.
1004 * Input "+x,y" becomes {x,y,true}
1005 * Input "x,y" becomes {1 + x/sepfact,1 + y/sepfact,false}
1006 * Return 1 on success, 0 on failure
1007 */
1008static int parseFactor(char *s, expand_t *pp, double sepfact, double dflt) {
1009 int i;
1010
1011 while (gv_isspace(*s)) s++;
1012 if (*s == '+') {
1013 s++;
1014 pp->doAdd = true;
1015 }
1016 else pp->doAdd = false;
1017
1018 double x, y;
1019 if ((i = sscanf(s, "%lf,%lf", &x, &y))) {
1020 if (i == 1) y = x;
1021 if (pp->doAdd) {
1022 if (sepfact > 1) {
1023 pp->x = fmin(dflt, x / sepfact);
1024 pp->y = fmin(dflt, y / sepfact);
1025 }
1026 else if (sepfact < 1) {
1027 pp->x = fmax(dflt, x / sepfact);
1028 pp->y = fmax(dflt, y / sepfact);
1029 }
1030 else {
1031 pp->x = x;
1032 pp->y = y;
1033 }
1034 }
1035 else {
1036 pp->x = 1.0 + x / sepfact;
1037 pp->y = 1.0 + y / sepfact;
1038 }
1039 return 1;
1040 }
1041 else return 0;
1042}
1043
1046{
1047 expand_t pmargin;
1048 char* marg;
1049
1050 if ((marg = agget(g, "sep")) && parseFactor(marg, &pmargin, 1.0, 0)) {
1051 }
1052 else if ((marg = agget(g, "esep")) && parseFactor(marg, &pmargin, SEPFACT, DFLT_MARGIN)) {
1053 }
1054 else { /* default */
1055 pmargin.x = pmargin.y = DFLT_MARGIN;
1056 pmargin.doAdd = true;
1057 }
1058 if (Verbose)
1059 fprintf (stderr, "Node separation: add=%d (%f,%f)\n",
1060 pmargin.doAdd, pmargin.x, pmargin.y);
1061 return pmargin;
1062}
1063
1064/* This value should be smaller than the sep value used to expand
1065 * nodes during adjustment. If not, when the adjustment pass produces
1066 * a fairly tight layout, the spline code will find that some nodes
1067 * still overlap.
1068 */
1071{
1072 expand_t pmargin;
1073 char* marg;
1074
1075 if ((marg = agget(g, "esep")) && parseFactor(marg, &pmargin, 1.0, 0)) {
1076 }
1077 else if ((marg = agget(g, "sep")) &&
1078 parseFactor(marg, &pmargin, 1.0 / SEPFACT, SEPFACT * DFLT_MARGIN)) {
1079 }
1080 else {
1081 pmargin.x = pmargin.y = SEPFACT*DFLT_MARGIN;
1082 pmargin.doAdd = true;
1083 }
1084 if (Verbose)
1085 fprintf (stderr, "Edge separation: add=%d (%f,%f)\n",
1086 pmargin.doAdd, pmargin.x, pmargin.y);
1087 return pmargin;
1088}
bool SparseMatrix_is_symmetric(SparseMatrix A, bool test_pattern_symmetry_only)
SparseMatrix SparseMatrix_from_coordinate_arrays(int nz, int m, int n, int *irn, int *jcn, void *val0, int type, size_t sz)
void SparseMatrix_delete(SparseMatrix A)
SparseMatrix SparseMatrix_get_real_adjacency_matrix_symmetrized(SparseMatrix A)
SparseMatrix SparseMatrix_remove_diagonal(SparseMatrix A)
@ MATRIX_TYPE_REAL
static unsigned countOverlap(unsigned iter)
Count number of node-node overlaps at iteration iter.
Definition adjust.c:272
static void newpos(Info_t *ip)
Definition adjust.c:328
static int sAdjust(state_t *st)
Definition adjust.c:471
static void sortSites(state_t *st)
Fill array of pointer to sites and sort the sites using scomp.
Definition adjust.c:179
static void newPos(const state_t *st, bool doAll)
Definition adjust.c:405
static void updateGraph(void)
Enter new node positions into the graph.
Definition adjust.c:497
expand_t esepFactor(graph_t *g)
Definition adjust.c:1070
static void centroidOf(Point a, Point b, Point c, double *x, double *y)
Definition adjust.c:319
static void chkBoundBox(state_t *st, Agraph_t *graph)
Definition adjust.c:86
static void freeNodes(void)
Free node resources.
Definition adjust.c:67
SparseMatrix makeMatrix(Agraph_t *g)
Definition adjust.c:541
static void setBoundBox(state_t *st, Point *ll, Point *ur)
Definition adjust.c:55
expand_t sepFactor(graph_t *g)
Definition adjust.c:1045
static void getAdjustMode(Agraph_t *g, const char *s, adjust_data *dp)
Convert string value to internal value of adjustment mode.
Definition adjust.c:813
static const lookup_t adjustMode[]
Definition adjust.c:775
#define IS_LNODE(n)
Definition adjust.c:508
int removeOverlapAs(graph_t *G, char *flag)
Use flag value to determine if and how to remove node overlaps.
Definition adjust.c:985
#define ISZERO(d)
Definition adjust.c:867
double * getSizes(Agraph_t *g, pointf pad, int *n_elabels, int **elabels)
Set up array of half sizes in inches.
Definition adjust.c:511
static int parseFactor(char *s, expand_t *pp, double sepfact, double dflt)
Definition adjust.c:1008
static int scomp(const void *S1, const void *S2)
Definition adjust.c:163
static double areaOf(Point a, Point b, Point c)
Area of triangle whose vertices are a,b,c.
Definition adjust.c:311
static Site * nextOne(void *state)
Definition adjust.c:217
static void rmEquality(state_t *st)
Check for nodes with identical positions and tweak the positions.
Definition adjust.c:226
static int makeInfo(Agraph_t *graph)
For each node in the graph, create a Info data structure.
Definition adjust.c:120
static void rePos(void)
Definition adjust.c:461
#define SEPFACT
Definition adjust.c:42
static int vAdjust(state_t *st)
Definition adjust.c:414
static void geomUpdate(state_t *st, int doSort)
Definition adjust.c:199
int adjustNodes(graph_t *G)
Definition adjust.c:998
int normalize(graph_t *g)
Definition adjust.c:721
static void increaseBoundBox(state_t *st)
Definition adjust.c:295
static const double incr
Definition adjust.c:44
static void addCorners(const state_t *st)
Definition adjust.c:354
static int angleSet(graph_t *g, double *phi)
Definition adjust.c:695
static int simpleScale(graph_t *g)
Definition adjust.c:869
static void setPrismValues(Agraph_t *g, const char *s, adjust_data *dp)
Initialize and set prism values.
Definition adjust.c:802
void graphAdjustMode(graph_t *G, adjust_data *dp, char *dflt)
Definition adjust.c:862
int removeOverlapWith(graph_t *G, adjust_data *am)
Definition adjust.c:898
PRIVATE int scAdjust(graph_t *, int)
Definition constraint.c:783
PRIVATE int cAdjust(graph_t *, int)
Definition constraint.c:552
#define DFLT_MARGIN
Definition adjust.h:23
adjust_mode
Definition adjust.h:25
@ AM_PORTHOYX
Definition adjust.h:29
@ AM_NONE
Definition adjust.h:26
@ AM_VPSC
Definition adjust.h:30
@ AM_PORTHO
Definition adjust.h:29
@ AM_ORTHO_YX
Definition adjust.h:28
@ AM_ORTHO
Definition adjust.h:28
@ AM_PORTHO_YX
Definition adjust.h:29
@ AM_NSCALE
Definition adjust.h:27
@ AM_SCALE
Definition adjust.h:27
@ AM_SCALEXY
Definition adjust.h:27
@ AM_IPSEP
Definition adjust.h:30
@ AM_ORTHOYX
Definition adjust.h:28
@ AM_PRISM
Definition adjust.h:30
@ AM_VOR
Definition adjust.h:26
@ AM_ORTHOXY
Definition adjust.h:28
@ AM_PORTHOXY
Definition adjust.h:29
@ AM_COMPRESS
Definition adjust.h:29
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define RADIANS(deg)
Definition arith.h:49
static bool doAll
induce subgraphs
Definition ccomps.c:67
bool mapbool(const char *p)
Definition utils.c:339
double late_double(void *obj, attrsym_t *attr, double defaultValue, double minimum)
Definition utils.c:51
bool mapBool(const char *p, bool defaultValue)
Definition utils.c:323
static int overlaps(nitem *p, int cnt)
Definition constraint.c:476
helpers for verbose/debug printing
#define GV_DEBUG(...)
Definition debug.h:39
double pymin
Definition edges.c:19
double pymax
Definition edges.c:19
double pxmin
Definition edges.c:19
double pxmax
Definition edges.c:19
#define A(n, t)
Definition expr.h:76
#define I
Definition expr.h:71
#define G
Definition gdefs.h:7
#define PS2INCH(a_points)
Definition geom.h:64
size_t nsites
Definition geometry.c:18
double deltax
Definition geometry.c:16
double xmax
Definition geometry.c:15
void geominit(void)
Definition geometry.c:21
double ymin
Definition geometry.c:15
double xmin
Definition geometry.c:15
double dist_2(Point pp, Point qp)
distance squared between two points
Definition geometry.c:29
double ymax
Definition geometry.c:15
unsigned short Ndim
Definition globals.h:62
static bool Verbose
Definition gml2gv.c:24
void free(void *)
node NULL
Definition grammar.y:181
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:196
int agnedges(Agraph_t *g)
Definition graph.c:161
int agnnodes(Agraph_t *g)
Definition graph.c:155
char * agget(void *obj, char *name)
Definition attr.c:448
char * agxget(void *obj, Agsym_t *sym)
Definition attr.c:458
#define agfindedgeattr(g, a)
Definition types.h:617
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
#define agtail(e)
Definition cgraph.h:977
#define aghead(e)
Definition cgraph.h:978
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
void agwarningf(const char *fmt,...)
Definition agerror.c:173
#define agfindgraphattr(g, a)
Definition types.h:613
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_height(n)
Definition types.h:498
#define ND_width(n)
Definition types.h:536
#define ND_pos(n)
Definition types.h:520
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
Agraph_t * graph(char *name)
Definition gv.cpp:30
replacements for ctype.h functions
static bool gv_isspace(int c)
Definition gv_ctype.h:55
rows row
Definition htmlparse.y:320
Info_t * nodeInfo
array of node info
Definition info.c:17
void addVertex(Site *s, double x, double y)
insert vertex into sorted list
Definition info.c:101
#define ND_id(n)
Definition mm2gv.c:40
static const int dim
NEATOPROCS_API void s1(graph_t *, node_t *)
Definition stuff.c:663
void remove_overlap(int dim, SparseMatrix A, double *x, double *label_sizes, int ntry, double initial_scaling, int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, bool do_shrinking)
Definition overlap.c:586
@ ELSCHEME_NONE
Definition overlap.h:30
int polyOverlap(Point p, Poly *pp, Point q, Poly *qp)
Definition poly.c:437
void breakPoly(Poly *pp)
Definition poly.c:43
void polyFree(void)
Definition poly.c:32
int makePoly(Poly *pp, Agnode_t *n, double xmargin, double ymargin)
Definition poly.c:217
int makeAddPoly(Poly *pp, Agnode_t *n, double xmargin, double ymargin)
Definition poly.c:127
static int nedges
total no. of edges used in routing
Definition routespl.c:32
int fdpAdjust(graph_t *g)
platform abstraction for case-insensitive string functions
graph or subgraph
Definition cgraph.h:424
string attribute descriptor symbol in Agattr_s.dict
Definition cgraph.h:640
info concerning site
Definition info.h:25
size_t n_verts
number of elements in verts
Definition info.h:31
Point * verts
sorted list of vertices of voronoi polygon
Definition info.h:30
bool overlaps
true if node overlaps other nodes
Definition info.h:28
Poly poly
polygon at node
Definition info.h:29
Agnode_t * node
libgraph node
Definition info.h:26
Site site
site used by voronoi code
Definition info.h:27
double x
Definition geometry.h:24
double y
Definition geometry.h:24
Definition poly.h:21
Point corner
Definition poly.h:23
Point origin
Definition poly.h:22
Definition site.h:23
Point coord
Definition site.h:24
size_t sitenbr
Definition site.h:25
int value
Definition adjust.h:36
double scaling
Definition adjust.h:37
char * print
Definition adjust.h:35
adjust_mode mode
Definition adjust.h:34
double x
Definition adjust.h:41
double y
Definition adjust.h:41
bool doAdd
Definition adjust.h:42
char * attrib
Definition adjust.c:767
char * print
Definition adjust.c:768
adjust_mode mode
Definition adjust.c:766
double x
Definition geom.h:29
double y
Definition geom.h:29
information the ID allocator needs to do its job
Definition id.c:27
Site ** sites
array of pointers to sites; used in qsort
Definition adjust.c:49
Point sw
Definition adjust.c:51
Site ** nextSite
Definition adjust.c:52
Point nw
Definition adjust.c:51
Site ** endSite
sentinel on sites array
Definition adjust.c:50
Point ne
Definition adjust.c:51
Point se
corners of clipping window
Definition adjust.c:51
Definition grammar.c:90
void voronoi(Site *(*nextsite)(void *context), void *context)
Definition voronoi.c:19