Graphviz 13.0.0~dev.20250424.1043
Loading...
Searching...
No Matches
utils.c
Go to the documentation of this file.
1
3/*************************************************************************
4 * Copyright (c) 2011 AT&T Intellectual Property
5 * All rights reserved. This program and the accompanying materials
6 * are made available under the terms of the Eclipse Public License v1.0
7 * which accompanies this distribution, and is available at
8 * https://www.eclipse.org/legal/epl-v10.html
9 *
10 * Contributors: Details at https://graphviz.org
11 *************************************************************************/
12
13#include <common/render.h>
14#include <common/geomprocs.h>
15#include <common/htmltable.h>
16#include <common/entities.h>
17#include <limits.h>
18#include <math.h>
19#include <gvc/gvc.h>
20#include <stdatomic.h>
21#include <stddef.h>
22#include <stdbool.h>
23#include <stdint.h>
24#include <unistd.h>
25#include <util/agxbuf.h>
26#include <util/alloc.h>
27#include <util/gv_ctype.h>
28#include <util/gv_math.h>
29#include <util/startswith.h>
30#include <util/strcasecmp.h>
31#include <util/streq.h>
32#include <util/strview.h>
33#include <util/tokenize.h>
34
35int late_int(void *obj, attrsym_t *attr, int defaultValue, int minimum) {
36 if (attr == NULL)
37 return defaultValue;
38 char *p = ag_xget(obj, attr);
39 if (!p || p[0] == '\0')
40 return defaultValue;
41 char *endp;
42 long rv = strtol(p, &endp, 10);
43 if (p == endp || rv > INT_MAX)
44 return defaultValue; /* invalid int format */
45 if (rv < minimum)
46 return minimum;
47 return (int)rv;
48}
49
50double late_double(void *obj, attrsym_t *attr, double defaultValue,
51 double minimum) {
52 if (!attr || !obj)
53 return defaultValue;
54 char *p = ag_xget(obj, attr);
55 if (!p || p[0] == '\0')
56 return defaultValue;
57 char *endp;
58 double rv = strtod(p, &endp);
59 if (p == endp)
60 return defaultValue; /* invalid double format */
61 if (rv < minimum)
62 return minimum;
63 return rv;
64}
65
74 if (PSinputscale > 0) return PSinputscale; /* command line flag prevails */
75 double d = late_double(g, agfindgraphattr(g, "inputscale"), -1, 0);
76 if (is_exactly_zero(d)) return POINTS_PER_INCH;
77 return d;
78}
79
80char *late_string(void *obj, attrsym_t *attr, char *defaultValue) {
81 if (!attr || !obj)
82 return defaultValue;
83 return agxget(obj, attr);
84}
85
86char *late_nnstring(void *obj, attrsym_t *attr, char *defaultValue) {
87 char *rv = late_string(obj, attr, defaultValue);
88 if (!rv || (rv[0] == '\0'))
89 return defaultValue;
90 return rv;
91}
92
93bool late_bool(void *obj, attrsym_t *attr, bool defaultValue) {
94 if (attr == NULL)
95 return defaultValue;
96
97 return mapbool(agxget(obj, attr));
98}
99
101{
102 while (ND_UF_parent(n) && ND_UF_parent(n) != n) {
105 n = ND_UF_parent(n);
106 }
107 return n;
108}
109
111{
112 if (u == v)
113 return u;
114 if (ND_UF_parent(u) == NULL) {
115 ND_UF_parent(u) = u;
116 ND_UF_size(u) = 1;
117 } else
118 u = UF_find(u);
119 if (ND_UF_parent(v) == NULL) {
120 ND_UF_parent(v) = v;
121 ND_UF_size(v) = 1;
122 } else
123 v = UF_find(v);
124 /* if we have two copies of the same node, their union is just that node */
125 if (u == v)
126 return u;
127 if (ND_id(u) > ND_id(v)) {
128 ND_UF_parent(u) = v;
129 ND_UF_size(v) += ND_UF_size(u);
130 } else {
131 ND_UF_parent(v) = u;
132 ND_UF_size(u) += ND_UF_size(v);
133 v = u;
134 }
135 return v;
136}
137
139{
140 ND_UF_size(u) = 1;
141 ND_UF_parent(u) = NULL;
142 ND_ranktype(u) = NORMAL;
143}
144
146{
147 assert(u == UF_find(u));
148 ND_UF_parent(u) = v;
149 ND_UF_size(v) += ND_UF_size(u);
150}
151
153{
154 pointf r;
155
156 r.x = POINTS_PER_INCH * ND_pos(n)[0];
157 r.y = POINTS_PER_INCH * ND_pos(n)[1];
158 return r;
159}
160
161/* from Glassner's Graphics Gems */
162#define W_DEGREE 5
163
164/*
165 * Evaluate a Bezier curve at a particular parameter value
166 * Fill in control points for resulting sub-curves if "Left" and
167 * "Right" are non-null.
168 *
169 */
170pointf Bezier(pointf *V, double t, pointf *Left, pointf *Right) {
171 const int degree = 3;
172 int i, j; /* Index variables */
173 pointf Vtemp[W_DEGREE + 1][W_DEGREE + 1];
174
175 /* Copy control points */
176 for (j = 0; j <= degree; j++) {
177 Vtemp[0][j] = V[j];
178 }
179
180 /* Triangle computation */
181 for (i = 1; i <= degree; i++) {
182 for (j = 0; j <= degree - i; j++) {
183 Vtemp[i][j].x =
184 (1.0 - t) * Vtemp[i - 1][j].x + t * Vtemp[i - 1][j + 1].x;
185 Vtemp[i][j].y =
186 (1.0 - t) * Vtemp[i - 1][j].y + t * Vtemp[i - 1][j + 1].y;
187 }
188 }
189
190 if (Left != NULL)
191 for (j = 0; j <= degree; j++)
192 Left[j] = Vtemp[j][0];
193 if (Right != NULL)
194 for (j = 0; j <= degree; j++)
195 Right[j] = Vtemp[degree - j][j];
196
197 return Vtemp[degree][0];
198}
199
200#ifdef DEBUG
201edge_t *debug_getedge(graph_t * g, char *s0, char *s1)
202{
203 node_t *n0, *n1;
204 n0 = agfindnode(g, s0);
205 n1 = agfindnode(g, s1);
206 if (n0 && n1)
207 return agfindedge(g, n0, n1);
208 return NULL;
209}
210Agraphinfo_t* GD_info(graph_t * g) { return ((Agraphinfo_t*)AGDATA(g));}
211Agnodeinfo_t* ND_info(node_t * n) { return ((Agnodeinfo_t*)AGDATA(n));}
212#endif
213
214/* safefile:
215 * Check to make sure it is okay to read in files.
216 * It returns NULL if the filename is trivial.
217 *
218 * If the application has set the SERVER_NAME environment variable,
219 * this indicates it is web-active.
220 *
221 * If filename contains multiple components, the user is
222 * warned, once, that everything to the left is ignored.
223 *
224 * For non-server applications, we use the path list in Gvimagepath to
225 * resolve relative pathnames.
226 *
227 * N.B. safefile uses a fixed buffer, so functions using it should use the
228 * value immediately or make a copy.
229 */
230#ifdef _WIN32
231#define PATHSEP ";"
232#else
233#define PATHSEP ":"
234#endif
235
236static strview_t *mkDirlist(const char *list) {
237 size_t cnt = 0;
238 strview_t *dirs = gv_calloc(1, sizeof(strview_t));
239
240 for (tok_t t = tok(list, PATHSEP); !tok_end(&t); tok_next(&t)) {
241 strview_t dir = tok_get(&t);
242 dirs = gv_recalloc(dirs, cnt + 1, cnt + 2, sizeof(strview_t));
243 dirs[cnt++] = dir;
244 }
245 return dirs;
246}
247
248static char *findPath(const strview_t *dirs, const char *str) {
249 static agxbuf safefilename;
250
251 for (const strview_t *dp = dirs; dp != NULL && dp->data != NULL; dp++) {
252 agxbprint(&safefilename, "%.*s%s%s", (int)dp->size, dp->data, DIRSEP, str);
253 char *filename = agxbuse(&safefilename);
254 if (access(filename, R_OK) == 0)
255 return filename;
256 }
257 return NULL;
258}
259
260const char *safefile(const char *filename)
261{
262 static bool onetime = true;
263 static char *pathlist = NULL;
264 static strview_t *dirs;
265
266 if (!filename || !filename[0])
267 return NULL;
268
269 if (HTTPServerEnVar) { /* If used as a server */
270 if (onetime) {
272 "file loading is disabled because the environment contains SERVER_NAME=\"%s\"\n",
274 onetime = false;
275 }
276 return NULL;
277 }
278
279 if (Gvfilepath != NULL) {
280 if (pathlist == NULL) {
281 free(dirs);
282 pathlist = Gvfilepath;
283 dirs = mkDirlist(pathlist);
284 }
285
286 const char *str = filename;
287 for (const char *sep = "/\\:"; *sep != '\0'; ++sep) {
288 const char *p = strrchr(str, *sep);
289 if (p != NULL) {
290 str = ++p;
291 }
292 }
293
294 return findPath(dirs, str);
295 }
296
297 if (pathlist != Gvimagepath) {
298 free (dirs);
299 dirs = NULL;
300 pathlist = Gvimagepath;
301 if (pathlist && *pathlist)
302 dirs = mkDirlist(pathlist);
303 }
304
305 if (*filename == DIRSEP[0] || !dirs)
306 return filename;
307
308 return findPath(dirs, filename);
309}
310
311int maptoken(char *p, char **name, int *val) {
312 char *q;
313
314 int i = 0;
315 for (; (q = name[i]) != 0; i++)
316 if (p && streq(p, q))
317 break;
318 return val[i];
319}
320
321bool mapBool(const char *p, bool defaultValue) {
322 if (!p || *p == '\0')
323 return defaultValue;
324 if (!strcasecmp(p, "false"))
325 return false;
326 if (!strcasecmp(p, "no"))
327 return false;
328 if (!strcasecmp(p, "true"))
329 return true;
330 if (!strcasecmp(p, "yes"))
331 return true;
332 if (gv_isdigit(*p))
333 return atoi(p) != 0;
334 return defaultValue;
335}
336
337bool mapbool(const char *p)
338{
339 return mapBool(p, false);
340}
341
343{
344 double bestdist2, d2, dlow2, dhigh2; /* squares of distances */
345 double low, high, t;
346 pointf c[4], pt2;
347 bezier bz;
348
349 size_t besti = SIZE_MAX;
350 size_t bestj = SIZE_MAX;
351 bestdist2 = 1e+38;
352 for (size_t i = 0; i < spl->size; i++) {
353 bz = spl->list[i];
354 for (size_t j = 0; j < bz.size; j++) {
355 pointf b;
356
357 b.x = bz.list[j].x;
358 b.y = bz.list[j].y;
359 d2 = DIST2(b, pt);
360 if (bestj == SIZE_MAX || d2 < bestdist2) {
361 besti = i;
362 bestj = j;
363 bestdist2 = d2;
364 }
365 }
366 }
367
368 bz = spl->list[besti];
369 /* Pick best Bezier. If bestj is the last point in the B-spline, decrement.
370 * Then set j to be the first point in the corresponding Bezier by dividing
371 * then multiplying be 3. Thus, 0,1,2 => 0; 3,4,5 => 3, etc.
372 */
373 if (bestj == bz.size-1)
374 bestj--;
375 const size_t j = 3 * (bestj / 3);
376 for (size_t k = 0; k < 4; k++) {
377 c[k].x = bz.list[j + k].x;
378 c[k].y = bz.list[j + k].y;
379 }
380 low = 0.0;
381 high = 1.0;
382 dlow2 = DIST2(c[0], pt);
383 dhigh2 = DIST2(c[3], pt);
384 do {
385 t = (low + high) / 2.0;
386 pt2 = Bezier(c, t, NULL, NULL);
387 if (fabs(dlow2 - dhigh2) < 1.0)
388 break;
389 if (fabs(high - low) < .00001)
390 break;
391 if (dlow2 < dhigh2) {
392 high = t;
393 dhigh2 = DIST2(pt2, pt);
394 } else {
395 low = t;
396 dlow2 = DIST2(pt2, pt);
397 }
398 } while (1);
399 return pt2;
400}
401
402static int Tflag;
403void gvToggle(int s)
404{
405 (void)s;
406 Tflag = !Tflag;
407#if !defined(_WIN32)
408 signal(SIGUSR1, gvToggle);
409#endif
410}
411
412int test_toggle(void)
413{
414 return Tflag;
415}
416
417struct fontinfo {
418 double fontsize;
419 char *fontname;
421};
422
424{
425 struct fontinfo fi;
426 char *str;
427 ND_width(n) =
429 ND_height(n) =
431 ND_shape(n) =
433 str = agxget(n, N_label);
437 ND_label(n) = make_label(n, str,
439 fi.fontsize, fi.fontname, fi.fontcolor);
440 if (N_xlabel && (str = agxget(n, N_xlabel)) && str[0]) {
442 fi.fontsize, fi.fontname, fi.fontcolor);
444 }
445
446 {
447 const int showboxes = imin(late_int(n, N_showboxes, 0, 0), UCHAR_MAX);
448 ND_showboxes(n) = (unsigned char)showboxes;
449 }
450 ND_shape(n)->fns->initfn(n);
451}
452
459
460static void
462 struct fontinfo *lfi)
463{
464 if (!fi->fontname) initFontEdgeAttr(e, fi);
468}
469
471static bool
473{
474 char *str;
475 bool rv = false;
476
477 if (sym) { /* mapbool isn't a good fit, because we want "" to mean true */
478 str = agxget(e,sym);
479 if (str && str[0]) rv = !mapbool(str);
480 else rv = false;
481 }
482 return rv;
483}
484
485static port
486chkPort (port (*pf)(node_t*, char*, char*), node_t* n, char* s)
487{
488 port pt;
489 char* cp=NULL;
490 if(s)
491 cp= strchr(s,':');
492 if (cp) {
493 *cp = '\0';
494 pt = pf(n, s, cp+1);
495 *cp = ':';
496 pt.name = cp+1;
497 }
498 else {
499 pt = pf(n, s, NULL);
500 pt.name = s;
501 }
502 return pt;
503}
504
505/* return true if edge has label */
507 char *str;
508 struct fontinfo fi;
509 struct fontinfo lfi;
510 graph_t *sg = agraphof(agtail(e));
511
512 fi.fontname = NULL;
513 lfi.fontname = NULL;
514 if (E_label && (str = agxget(e, E_label)) && str[0]) {
515 initFontEdgeAttr(e, &fi);
517 fi.fontsize, fi.fontname, fi.fontcolor);
520 }
521
522 if (E_xlabel && (str = agxget(e, E_xlabel)) && str[0]) {
523 if (!fi.fontname)
524 initFontEdgeAttr(e, &fi);
526 fi.fontsize, fi.fontname, fi.fontcolor);
528 }
529
530 if (E_headlabel && (str = agxget(e, E_headlabel)) && str[0]) {
531 initFontLabelEdgeAttr(e, &fi, &lfi);
533 lfi.fontsize, lfi.fontname, lfi.fontcolor);
535 }
536 if (E_taillabel && (str = agxget(e, E_taillabel)) && str[0]) {
537 if (!lfi.fontname)
538 initFontLabelEdgeAttr(e, &fi, &lfi);
540 lfi.fontsize, lfi.fontname, lfi.fontcolor);
542 }
543
544 /* We still accept ports beginning with colons but this is deprecated
545 * That is, we allow tailport = ":abc" as well as the preferred
546 * tailport = "abc".
547 */
548 str = agget(e, TAIL_ID);
549 /* libgraph always defines tailport/headport; libcgraph doesn't */
550 if (!str) str = "";
551 if (str && str[0])
552 ND_has_port(agtail(e)) = true;
553 ED_tail_port(e) = chkPort (ND_shape(agtail(e))->fns->portfn, agtail(e), str);
554 if (noClip(e, E_tailclip))
555 ED_tail_port(e).clip = false;
556 str = agget(e, HEAD_ID);
557 /* libgraph always defines tailport/headport; libcgraph doesn't */
558 if (!str) str = "";
559 if (str && str[0])
560 ND_has_port(aghead(e)) = true;
561 ED_head_port(e) = chkPort(ND_shape(aghead(e))->fns->portfn, aghead(e), str);
562 if (noClip(e, E_headclip))
563 ED_head_port(e).clip = false;
564}
565
566static boxf addLabelBB(boxf bb, textlabel_t * lp, bool flipxy)
567{
568 double width, height;
569 pointf p = lp->pos;
570 double min, max;
571
572 if (flipxy) {
573 height = lp->dimen.x;
574 width = lp->dimen.y;
575 }
576 else {
577 width = lp->dimen.x;
578 height = lp->dimen.y;
579 }
580 min = p.x - width / 2.;
581 max = p.x + width / 2.;
582 if (min < bb.LL.x)
583 bb.LL.x = min;
584 if (max > bb.UR.x)
585 bb.UR.x = max;
586
587 min = p.y - height / 2.;
588 max = p.y + height / 2.;
589 if (min < bb.LL.y)
590 bb.LL.y = min;
591 if (max > bb.UR.y)
592 bb.UR.y = max;
593
594 return bb;
595}
596
600boxf
602{
603 const size_t sides = poly->sides;
604 const size_t peris = MAX(poly->peripheries, (size_t)1);
605 pointf* verts = poly->vertices + (peris-1)*sides;
606 boxf bb;
607
608 bb.LL = bb.UR = verts[0];
609 for (size_t i = 1; i < sides; i++) {
610 bb.LL.x = MIN(bb.LL.x,verts[i].x);
611 bb.LL.y = MIN(bb.LL.y,verts[i].y);
612 bb.UR.x = MAX(bb.UR.x,verts[i].x);
613 bb.UR.y = MAX(bb.UR.y,verts[i].y);
614 }
615 return bb;
616}
617
622{
623 GD_bb(g) = addLabelBB(GD_bb(g), lp, GD_flip(g));
624}
625
631{
632 node_t *n;
633 edge_t *e;
634 boxf b, bb;
635 boxf BF;
636 pointf ptf, s2;
637
638 if (agnnodes(g) == 0 && GD_n_cluster(g) == 0) {
639 bb.LL = (pointf){0};
640 bb.UR = (pointf){0};
641 return;
642 }
643
644 bb.LL = (pointf){INT_MAX, INT_MAX};
645 bb.UR = (pointf){-INT_MAX, -INT_MAX};
646 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
647 ptf = coord(n);
648 s2.x = ND_xsize(n) / 2.0;
649 s2.y = ND_ysize(n) / 2.0;
650 b.LL = sub_pointf(ptf, s2);
651 b.UR = add_pointf(ptf, s2);
652
653 EXPANDBB(&bb, b);
654 if (ND_xlabel(n) && ND_xlabel(n)->set) {
655 bb = addLabelBB(bb, ND_xlabel(n), GD_flip(g));
656 }
657 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
658 if (ED_spl(e) == 0)
659 continue;
660 for (size_t i = 0; i < ED_spl(e)->size; i++) {
661 for (size_t j = 0; j < (((Agedgeinfo_t*)AGDATA(e))->spl)->list[i].size; j++) {
662 ptf = ED_spl(e)->list[i].list[j];
663 expandbp(&bb, ptf);
664 }
665 }
666 if (ED_label(e) && ED_label(e)->set) {
667 bb = addLabelBB(bb, ED_label(e), GD_flip(g));
668 }
669 if (ED_head_label(e) && ED_head_label(e)->set) {
670 bb = addLabelBB(bb, ED_head_label(e), GD_flip(g));
671 }
672 if (ED_tail_label(e) && ED_tail_label(e)->set) {
673 bb = addLabelBB(bb, ED_tail_label(e), GD_flip(g));
674 }
675 if (ED_xlabel(e) && ED_xlabel(e)->set) {
676 bb = addLabelBB(bb, ED_xlabel(e), GD_flip(g));
677 }
678 }
679 }
680
681 for (int i = 1; i <= GD_n_cluster(g); i++) {
682 B2BF(GD_bb(GD_clust(g)[i]), BF);
683 EXPANDBB(&bb, BF);
684 }
685 if (GD_label(g) && GD_label(g)->set) {
686 bb = addLabelBB(bb, GD_label(g), GD_flip(g));
687 }
688
689 GD_bb(g) = bb;
690}
691
693{
694 return g == g->root || !strncasecmp(agnameof(g), "cluster", 7) ||
695 mapbool(agget(g, "cluster"));
696}
697
701Agsym_t *setAttr(graph_t * g, void *obj, char *name, char *value,
702 Agsym_t * ap)
703{
704 if (ap == NULL) {
705 switch (agobjkind(obj)) {
706 case AGRAPH:
707 ap = agattr_text(g, AGRAPH,name, "");
708 break;
709 case AGNODE:
710 ap = agattr_text(g,AGNODE, name, "");
711 break;
712 case AGEDGE:
713 ap = agattr_text(g,AGEDGE, name, "");
714 break;
715 }
716 }
717 agxset(obj, ap, value);
718 return ap;
719}
720
726static node_t *clustNode(node_t * n, graph_t * cg, agxbuf * xb,
727 graph_t * clg)
728{
729 node_t *cn;
730 static int idx = 0;
731
732 agxbprint(xb, "__%d:%s", idx++, agnameof(cg));
733
734 cn = agnode(agroot(cg), agxbuse(xb), 1);
735 agbindrec(cn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), true);
736
737 SET_CLUST_NODE(cn);
738 agsubnode(cg,cn,1);
739 agsubnode(clg,n,1);
740
741 /* set attributes */
742 N_label = setAttr(agraphof(cn), cn, "label", "", N_label);
743 N_style = setAttr(agraphof(cn), cn, "style", "invis", N_style);
744 N_shape = setAttr(agraphof(cn), cn, "shape", "box", N_shape);
745
746 return cn;
747}
748
749typedef struct {
750 Dtlink_t link; /* cdt data */
751 void *p[2]; /* key */
754} item;
755
756static int cmpItem(void *pp1, void *pp2) {
757 const void **p1 = pp1;
758 const void **p2 = pp2;
759 if ((uintptr_t)p1[0] < (uintptr_t)p2[0])
760 return -1;
761 if ((uintptr_t)p1[0] > (uintptr_t)p2[0])
762 return 1;
763 if ((uintptr_t)p1[1] < (uintptr_t)p2[1])
764 return -1;
765 if ((uintptr_t)p1[1] > (uintptr_t)p2[1])
766 return 1;
767 return 0;
768}
769
770static void *newItem(void *p, Dtdisc_t *disc) {
771 item *objp = p;
772 item *newp = gv_alloc(sizeof(item));
773
774 (void)disc;
775 newp->p[0] = objp->p[0];
776 newp->p[1] = objp->p[1];
777 newp->t = objp->t;
778 newp->h = objp->h;
779
780 return newp;
781}
782
784 .key = offsetof(item, p),
785 .size = sizeof(2 * sizeof(void *)),
786 .link = offsetof(item, link),
787 .makef = newItem,
788 .freef = free,
789 .comparf = cmpItem,
790};
791
793static edge_t *cloneEdge(edge_t * e, node_t * ct, node_t * ch)
794{
795 graph_t *g = agraphof(ct);
796 edge_t *ce = agedge(g, ct, ch,NULL,1);
797 agbindrec(ce, "Agedgeinfo_t", sizeof(Agedgeinfo_t), true);
798 agcopyattr(e, ce);
799 ED_compound(ce) = true;
800
801 return ce;
802}
803
804static void insertEdge(Dt_t * map, void *t, void *h, edge_t * e)
805{
806 item dummy1 = {.p = {t, h}, .t = agtail(e), .h = aghead(e)};
807 dtinsert(map, &dummy1);
808
809 item dummy2 = {.p = {h, t}, .t = aghead(e), .h = agtail(e)};
810 dtinsert(map, &dummy2);
811}
812
814static item *mapEdge(Dt_t * map, edge_t * e)
815{
816 void *key[] = {agtail(e), aghead(e)};
817 return dtmatch(map, &key);
818}
819
820static graph_t *mapc(Dt_t *cmap, node_t *n) {
821 if (startswith(agnameof(n), "cluster")) {
822 return findCluster(cmap, agnameof(n));
823 }
824 return NULL;
825}
826
842static int
843checkCompound(edge_t * e, graph_t * clg, agxbuf * xb, Dt_t * map, Dt_t* cmap)
844{
845 node_t *cn;
846 node_t *cn1;
847 node_t *t = agtail(e);
848 node_t *h = aghead(e);
849 edge_t *ce;
850 item *ip;
851
852 if (IS_CLUST_NODE(h)) return 0;
853 graph_t *const tg = mapc(cmap, t);
854 graph_t *const hg = mapc(cmap, h);
855 if (!tg && !hg)
856 return 0;
857 if (tg == hg) {
858 agwarningf("cluster cycle %s -- %s not supported\n", agnameof(t),
859 agnameof(t));
860 return 0;
861 }
862 ip = mapEdge(map, e);
863 if (ip) {
864 cloneEdge(e, ip->t, ip->h);
865 return 1;
866 }
867
868 if (hg) {
869 if (tg) {
870 if (agcontains(hg, tg)) {
871 agwarningf("tail cluster %s inside head cluster %s\n",
872 agnameof(tg), agnameof(hg));
873 return 0;
874 }
875 if (agcontains(tg, hg)) {
876 agwarningf("head cluster %s inside tail cluster %s\n",
877 agnameof(hg),agnameof(tg));
878 return 0;
879 }
880 cn = clustNode(t, tg, xb, clg);
881 cn1 = clustNode(h, hg, xb, clg);
882 ce = cloneEdge(e, cn, cn1);
883 insertEdge(map, t, h, ce);
884 } else {
885 if (agcontains(hg, t)) {
886 agwarningf("tail node %s inside head cluster %s\n",
887 agnameof(t), agnameof(hg));
888 return 0;
889 }
890 cn = clustNode(h, hg, xb, clg);
891 ce = cloneEdge(e, t, cn);
892 insertEdge(map, t, h, ce);
893 }
894 } else {
895 if (agcontains(tg, h)) {
896 agwarningf("head node %s inside tail cluster %s\n", agnameof(h),
897 agnameof(tg));
898 return 0;
899 }
900 cn = clustNode(t, tg, xb, clg);
901 ce = cloneEdge(e, cn, h);
902 insertEdge(map, t, h, ce);
903 }
904 return 1;
905}
906
907typedef struct {
910} cl_edge_t;
911
912static int
914{
915 cl_edge_t* cl_info = (cl_edge_t*)HAS_CLUST_EDGE(g);
916 if (cl_info)
917 return cl_info->n_cluster_edges;
918 return 0;
919}
920
928{
929 int num_cl_edges = 0;
930 node_t *n;
931 node_t *nxt;
932 edge_t *e;
933 graph_t *clg;
934 agxbuf xb = {0};
935 Dt_t *map;
936 Dt_t *cmap = mkClustMap (g);
937
938 map = dtopen(&mapDisc, Dtoset);
939 clg = agsubg(g, "__clusternodes",1);
940 agbindrec(clg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
941 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
942 if (IS_CLUST_NODE(n)) continue;
943 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
944 num_cl_edges += checkCompound(e, clg, &xb, map, cmap);
945 }
946 }
947 agxbfree(&xb);
948 dtclose(map);
949 for (n = agfstnode(clg); n; n = nxt) {
950 nxt = agnxtnode(clg, n);
951 agdelete(g, n);
952 }
953 agclose(clg);
954 if (num_cl_edges) {
955 cl_edge_t* cl_info;
956 cl_info = agbindrec(g, CL_EDGE_TAG, sizeof(cl_edge_t), false);
957 cl_info->n_cluster_edges = num_cl_edges;
958 }
959 dtclose(cmap);
960}
961
969static node_t *mapN(node_t * n, graph_t * clg)
970{
971 node_t *nn;
972 char *name;
973 graph_t *g = agraphof(n);
974 Agsym_t *sym;
975
976 if (!IS_CLUST_NODE(n))
977 return n;
978 agsubnode(clg, n, 1);
979 name = strchr(agnameof(n), ':');
980 assert(name);
981 name++;
982 if ((nn = agfindnode(g, name)))
983 return nn;
984 nn = agnode(g, name, 1);
985 agbindrec(nn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), true);
986 SET_CLUST_NODE(nn);
987
988 /* Set all attributes to default */
989 for (sym = agnxtattr(g, AGNODE, NULL); sym; (sym = agnxtattr(g, AGNODE, sym))) {
990 if (agxget(nn, sym) != sym->defval)
991 agxset(nn, sym, sym->defval);
992 }
993 return nn;
994}
995
996static void undoCompound(edge_t * e, graph_t * clg)
997{
998 node_t *t = agtail(e);
999 node_t *h = aghead(e);
1000 node_t *ntail;
1001 node_t *nhead;
1002 edge_t* ce;
1003
1004 ntail = mapN(t, clg);
1005 nhead = mapN(h, clg);
1006 ce = cloneEdge(e, ntail, nhead);
1007
1008 /* transfer drawing information */
1009 ED_spl(ce) = ED_spl(e);
1010 ED_spl(e) = NULL;
1011 ED_label(ce) = ED_label(e);
1012 ED_label(e) = NULL;
1013 ED_xlabel(ce) = ED_xlabel(e);
1014 ED_xlabel(e) = NULL;
1016 ED_head_label(e) = NULL;
1018 ED_tail_label(e) = NULL;
1019 gv_cleanup_edge(e);
1020}
1021
1027{
1028 node_t *n;
1029 node_t *nextn;
1030 edge_t *e;
1031 graph_t *clg;
1032 int ecnt = num_clust_edges(g);
1033 int i = 0;
1034
1035 if (!ecnt) return;
1036 clg = agsubg(g, "__clusternodes",1);
1037 agbindrec(clg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
1038 edge_t **edgelist = gv_calloc(ecnt, sizeof(edge_t*));
1039 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1040 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1041 if (ED_compound(e))
1042 edgelist[i++] = e;
1043 }
1044 }
1045 assert(i == ecnt);
1046 for (i = 0; i < ecnt; i++)
1047 undoCompound(edgelist[i], clg);
1048 free (edgelist);
1049 for (n = agfstnode(clg); n; n = nextn) {
1050 nextn = agnxtnode(clg, n);
1051 gv_cleanup_node(n);
1052 agdelete(g, n);
1053 }
1054 agclose(clg);
1055}
1056
1061attrsym_t *safe_dcl(graph_t *g, int obj_kind, char *name, char *defaultValue) {
1062 attrsym_t *a = agattr_text(g,obj_kind,name, NULL);
1063 if (!a) /* attribute does not exist */
1064 a = agattr_text(g, obj_kind, name, defaultValue);
1065 return a;
1066}
1067
1068static int comp_entities(const void *e1, const void *e2) {
1069 const strview_t *key = e1;
1070 const struct entities_s *candidate = e2;
1071 return strview_cmp(*key, strview(candidate->name, '\0'));
1072}
1073
1078char* scanEntity (char* t, agxbuf* xb)
1079{
1080 const strview_t key = strview(t, ';');
1081 struct entities_s *res;
1082
1083 agxbputc(xb, '&');
1084 if (key.data[key.size] == '\0') return t;
1085 if (key.size > ENTITY_NAME_LENGTH_MAX || key.size < 2) return t;
1086 res = bsearch(&key, entities, NR_OF_ENTITIES,
1087 sizeof(entities[0]), comp_entities);
1088 if (!res) return t;
1089 agxbprint(xb, "#%d;", res->value);
1090 return t + key.size + 1;
1091}
1092
1099static int
1101{
1102 struct entities_s *res;
1103 unsigned char* str = *(unsigned char**)s;
1104 unsigned int byte;
1105 int i, n = 0;
1106
1107 byte = *str;
1108 if (byte == '#') {
1109 byte = *(str + 1);
1110 if (byte == 'x' || byte == 'X') {
1111 for (i = 2; i < 8; i++) {
1112 byte = *(str + i);
1113 if (byte >= 'A' && byte <= 'F')
1114 byte = byte - 'A' + 10;
1115 else if (byte >= 'a' && byte <= 'f')
1116 byte = byte - 'a' + 10;
1117 else if (byte >= '0' && byte <= '9')
1118 byte = byte - '0';
1119 else
1120 break;
1121 n = n * 16 + (int)byte;
1122 }
1123 }
1124 else {
1125 for (i = 1; i < 8; i++) {
1126 byte = *(str + i);
1127 if (byte >= '0' && byte <= '9')
1128 n = n * 10 + ((int)byte - '0');
1129 else
1130 break;
1131 }
1132 }
1133 if (byte == ';') {
1134 str += i+1;
1135 }
1136 else {
1137 n = 0;
1138 }
1139 }
1140 else {
1141 strview_t key = {.data = (char *)str};
1142 for (i = 0; i < ENTITY_NAME_LENGTH_MAX; i++) {
1143 byte = *(str + i);
1144 if (byte == '\0') break;
1145 if (byte == ';') {
1146 res = bsearch(&key, entities, NR_OF_ENTITIES,
1147 sizeof(entities[0]), comp_entities);
1148 if (res) {
1149 n = res->value;
1150 str += i+1;
1151 }
1152 break;
1153 }
1154 ++key.size;
1155 }
1156 }
1157 *s = (char*)str;
1158 return n;
1159}
1160
1161static unsigned char
1162cvtAndAppend (unsigned char c, agxbuf* xb)
1163{
1164 char buf[] = {c, '\0'};
1165 char *s = latin1ToUTF8(buf);
1166 char *p = s;
1167 size_t len = strlen(s);
1168 while (len-- > 1)
1169 agxbputc(xb, *p++);
1170 c = *p;
1171 free (s);
1172 return c;
1173}
1174
1179char* htmlEntityUTF8 (char* s, graph_t* g)
1180{
1181 static graph_t* lastg;
1182 static atomic_flag warned;
1183 unsigned char c;
1184 unsigned int v;
1185
1186 int uc;
1187 int ui;
1188
1189 if (lastg != g) {
1190 lastg = g;
1191 atomic_flag_clear(&warned);
1192 }
1193
1194 agxbuf xb = {0};
1195
1196 while ((c = *(unsigned char*)s++)) {
1197 if (c < 0xC0)
1198 /*
1199 * Handles properly formed UTF-8 characters between
1200 * 0x01 and 0x7F. Also treats \0 and naked trail
1201 * bytes 0x80 to 0xBF as valid characters representing
1202 * themselves.
1203 */
1204 uc = 0;
1205 else if (c < 0xE0)
1206 uc = 1;
1207 else if (c < 0xF0)
1208 uc = 2;
1209 else if (c < 0xF8)
1210 uc = 3;
1211 else {
1212 uc = -1;
1213 if (!atomic_flag_test_and_set(&warned)) {
1214 agwarningf("UTF8 codes > 4 bytes are not currently supported (graph %s) - treated as Latin-1. Perhaps \"-Gcharset=latin1\" is needed?\n", agnameof(g));
1215 }
1216 c = cvtAndAppend (c, &xb);
1217 }
1218
1219 if (uc == 0 && c == '&') {
1220 /* replace html entity sequences like: &amp;
1221 * and: &#123; with their UTF8 equivalents */
1222 v = htmlEntity (&s);
1223 if (v) {
1224 if (v < 0x7F) /* entity needs 1 byte in UTF8 */
1225 c = v;
1226 else if (v < 0x07FF) { /* entity needs 2 bytes in UTF8 */
1227 agxbputc(&xb, (char)((v >> 6) | 0xC0));
1228 c = (v & 0x3F) | 0x80;
1229 }
1230 else { /* entity needs 3 bytes in UTF8 */
1231 agxbputc(&xb, (char)((v >> 12) | 0xE0));
1232 agxbputc(&xb, (char)(((v >> 6) & 0x3F) | 0x80));
1233 c = (v & 0x3F) | 0x80;
1234 }
1235 }
1236 }
1237 else /* copy n byte UTF8 characters */
1238 for (ui = 0; ui < uc; ++ui)
1239 if ((*s & 0xC0) == 0x80) {
1240 agxbputc(&xb, (char)c);
1241 c = *(unsigned char*)s++;
1242 }
1243 else {
1244 if (!atomic_flag_test_and_set(&warned)) {
1245 agwarningf("Invalid %d-byte UTF8 found in input of graph %s - treated as Latin-1. Perhaps \"-Gcharset=latin1\" is needed?\n", uc + 1, agnameof(g));
1246 }
1247 c = cvtAndAppend (c, &xb);
1248 break;
1249 }
1250 agxbputc(&xb, (char)c);
1251 }
1252 return agxbdisown(&xb);
1253}
1254
1256char* latin1ToUTF8 (char* s)
1257{
1258 agxbuf xb = {0};
1259 unsigned int v;
1260
1261 /* Values are either a byte (<= 256) or come from htmlEntity, whose
1262 * values are all less than 0x07FF, so we need at most 3 bytes.
1263 */
1264 while ((v = *(unsigned char*)s++)) {
1265 if (v == '&') {
1266 v = htmlEntity (&s);
1267 if (!v) v = '&';
1268 }
1269 if (v < 0x7F)
1270 agxbputc(&xb, (char)v);
1271 else if (v < 0x07FF) {
1272 agxbputc(&xb, (char)((v >> 6) | 0xC0));
1273 agxbputc(&xb, (char)((v & 0x3F) | 0x80));
1274 }
1275 else {
1276 agxbputc(&xb, (char)((v >> 12) | 0xE0));
1277 agxbputc(&xb, (char)(((v >> 6) & 0x3F) | 0x80));
1278 agxbputc(&xb, (char)((v & 0x3F) | 0x80));
1279 }
1280 }
1281 return agxbdisown(&xb);
1282}
1283
1288char*
1290{
1291 agxbuf xb = {0};
1292 unsigned char c;
1293
1294 while ((c = *(unsigned char*)s++)) {
1295 if (c < 0x7F)
1296 agxbputc(&xb, (char)c);
1297 else {
1298 unsigned char outc = (c & 0x03) << 6;
1299 c = *(unsigned char *)s++;
1300 outc = outc | (c & 0x3F);
1301 agxbputc(&xb, (char)outc);
1302 }
1303 }
1304 return agxbdisown(&xb);
1305}
1306
1308 if (! OVERLAP(b, ND_bb(n)))
1309 return false;
1310
1311 /* FIXME - need to do something better about CLOSEENOUGH */
1312 pointf p = sub_pointf(ND_coord(n), mid_pointf(b.UR, b.LL));
1313
1314 inside_t ictxt = {.s.n = n};
1315
1316 return ND_shape(n)->fns->insidefn(&ictxt, p);
1317}
1318
1320{
1321 const pointf s = {.x = lp->dimen.x / 2.0, .y = lp->dimen.y / 2.0};
1322 boxf bb = {.LL = sub_pointf(lp->pos, s), .UR = add_pointf(lp->pos, s)};
1323 return OVERLAP(b, bb);
1324}
1325
1326static bool overlap_arrow(pointf p, pointf u, double scale, boxf b)
1327{
1328 // FIXME - check inside arrow shape
1329 return OVERLAP(b, arrow_bb(p, u, scale));
1330}
1331
1332static bool overlap_bezier(bezier bz, boxf b) {
1333 assert(bz.size);
1334 pointf u = bz.list[0];
1335 for (size_t i = 1; i < bz.size; i++) {
1336 pointf p = bz.list[i];
1337 if (lineToBox(p, u, b) != -1)
1338 return true;
1339 u = p;
1340 }
1341
1342 /* check arrows */
1343 if (bz.sflag) {
1344 if (overlap_arrow(bz.sp, bz.list[0], 1, b))
1345 return true;
1346 }
1347 if (bz.eflag) {
1348 if (overlap_arrow(bz.ep, bz.list[bz.size - 1], 1, b))
1349 return true;
1350 }
1351 return false;
1352}
1353
1355{
1356 splines *spl = ED_spl(e);
1357 if (spl && boxf_overlap(spl->bb, b))
1358 for (size_t i = 0; i < spl->size; i++)
1359 if (overlap_bezier(spl->list[i], b))
1360 return true;
1361
1362 textlabel_t *lp = ED_label(e);
1363 if (lp && overlap_label(lp, b))
1364 return true;
1365
1366 return false;
1367}
1368
1370static int edgeType(const char *s, int defaultValue) {
1371 if (s == NULL || strcmp(s, "") == 0) {
1372 return defaultValue;
1373 }
1374
1375 if (*s == '0') { /* false */
1376 return EDGETYPE_LINE;
1377 } else if (*s >= '1' && *s <= '9') { /* true */
1378 return EDGETYPE_SPLINE;
1379 } else if (strcasecmp(s, "curved") == 0) {
1380 return EDGETYPE_CURVED;
1381 } else if (strcasecmp(s, "compound") == 0) {
1382 return EDGETYPE_COMPOUND;
1383 } else if (strcasecmp(s, "false") == 0) {
1384 return EDGETYPE_LINE;
1385 } else if (strcasecmp(s, "line") == 0) {
1386 return EDGETYPE_LINE;
1387 } else if (strcasecmp(s, "none") == 0) {
1388 return EDGETYPE_NONE;
1389 } else if (strcasecmp(s, "no") == 0) {
1390 return EDGETYPE_LINE;
1391 } else if (strcasecmp(s, "ortho") == 0) {
1392 return EDGETYPE_ORTHO;
1393 } else if (strcasecmp(s, "polyline") == 0) {
1394 return EDGETYPE_PLINE;
1395 } else if (strcasecmp(s, "spline") == 0) {
1396 return EDGETYPE_SPLINE;
1397 } else if (strcasecmp(s, "true") == 0) {
1398 return EDGETYPE_SPLINE;
1399 } else if (strcasecmp(s, "yes") == 0) {
1400 return EDGETYPE_SPLINE;
1401 }
1402
1403 agwarningf("Unknown \"splines\" value: \"%s\" - ignored\n", s);
1404 return defaultValue;
1405}
1406
1419void setEdgeType(graph_t *g, int defaultValue) {
1420 char* s = agget(g, "splines");
1421 int et;
1422
1423 if (!s) {
1424 et = defaultValue;
1425 }
1426 else if (*s == '\0') {
1427 et = EDGETYPE_NONE;
1428 } else {
1429 et = edgeType(s, defaultValue);
1430 }
1431 GD_flags(g) |= et;
1432}
1433
1442void get_gradient_points(pointf *A, pointf *G, size_t n, double angle, int flags) {
1443 pointf min,max,center;
1444 int isRadial = flags & 1;
1445 int isRHS = flags & 2;
1446
1447 if (n == 2) {
1448 double rx = A[1].x - A[0].x;
1449 double ry = A[1].y - A[0].y;
1450 min.x = A[0].x - rx;
1451 max.x = A[0].x + rx;
1452 min.y = A[0].y - ry;
1453 max.y = A[0].y + ry;
1454 }
1455 else {
1456 min.x = max.x = A[0].x;
1457 min.y = max.y = A[0].y;
1458 for (size_t i = 0; i < n; i++) {
1459 min.x = MIN(A[i].x, min.x);
1460 min.y = MIN(A[i].y, min.y);
1461 max.x = MAX(A[i].x, max.x);
1462 max.y = MAX(A[i].y, max.y);
1463 }
1464 }
1465 center.x = min.x + (max.x - min.x)/2;
1466 center.y = min.y + (max.y - min.y)/2;
1467 if (isRadial) {
1468 double inner_r, outer_r;
1469 outer_r = hypot(center.x - min.x, center.y - min.y);
1470 inner_r = outer_r /4.;
1471 if (isRHS) {
1472 G[0].y = center.y;
1473 }
1474 else {
1475 G[0].y = -center.y;
1476 }
1477 G[0].x = center.x;
1478 G[1].x = inner_r;
1479 G[1].y = outer_r;
1480 }
1481 else {
1482 double half_x = max.x - center.x;
1483 double half_y = max.y - center.y;
1484 double sina = sin(angle);
1485 double cosa = cos(angle);
1486 if (isRHS) {
1487 G[0].y = center.y - half_y * sina;
1488 G[1].y = center.y + half_y * sina;
1489 }
1490 else {
1491 G[0].y = -center.y + (max.y - center.y) * sin(angle);
1492 G[1].y = -center.y - (center.y - min.y) * sin(angle);
1493 }
1494 G[0].x = center.x - half_x * cosa;
1495 G[1].x = center.x + half_x * cosa;
1496 }
1497}
1498
1500 if (ED_spl(e)) {
1501 for (size_t i = 0; i < ED_spl(e)->size; i++)
1502 free(ED_spl(e)->list[i].list);
1503 free(ED_spl(e)->list);
1504 free(ED_spl(e));
1505 }
1506 ED_spl(e) = NULL;
1507}
1508
1510{
1511 free(ED_path(e).ps);
1512 gv_free_splines(e);
1513 free_label(ED_label(e));
1517 /*FIX HERE , shallow cleaning may not be enough here */
1518 agdelrec(e, "Agedgeinfo_t");
1519}
1520
1522{
1523 free(ND_pos(n));
1524 if (ND_shape(n))
1525 ND_shape(n)->fns->freefn(n);
1526 free_label(ND_label(n));
1528 /*FIX HERE , shallow cleaning may not be enough here */
1529 agdelrec(n, "Agnodeinfo_t");
1530}
1531
1532void gv_nodesize(node_t *n, bool flip) {
1533 if (flip) {
1534 double w = INCH2PS(ND_height(n));
1535 ND_lw(n) = ND_rw(n) = w / 2;
1536 ND_ht(n) = INCH2PS(ND_width(n));
1537 }
1538 else {
1539 double w = INCH2PS(ND_width(n));
1540 ND_lw(n) = ND_rw(n) = w / 2;
1541 ND_ht(n) = INCH2PS(ND_height(n));
1542 }
1543}
1544
1545#ifndef HAVE_DRAND48
1546double drand48(void)
1547{
1548 double d;
1549 d = rand();
1550 d = d / RAND_MAX;
1551 return d;
1552}
1553#endif
1554typedef struct {
1556 char* name;
1558} clust_t;
1559
1561 .key = offsetof(clust_t, name),
1562 .size = -1,
1563 .link = offsetof(clust_t, link),
1564 .freef = free,
1565};
1566
1567static void fillMap (Agraph_t* g, Dt_t* map)
1568{
1569 for (int c = 1; c <= GD_n_cluster(g); c++) {
1570 Agraph_t *cl = GD_clust(g)[c];
1571 char *s = agnameof(cl);
1572 if (dtmatch(map, s)) {
1573 agwarningf("Two clusters named %s - the second will be ignored\n", s);
1574 } else {
1575 clust_t *ip = gv_alloc(sizeof(clust_t));
1576 ip->name = s;
1577 ip->clp = cl;
1578 dtinsert (map, ip);
1579 }
1580 fillMap (cl, map);
1581 }
1582}
1583
1589{
1590 Dt_t* map = dtopen (&strDisc, Dtoset);
1591
1592 fillMap (g, map);
1593
1594 return map;
1595}
1596
1597Agraph_t*
1598findCluster (Dt_t* map, char* name)
1599{
1600 clust_t* clp = dtmatch (map, name);
1601 if (clp)
1602 return clp->clp;
1603 return NULL;
1604}
1605
static void agxbfree(agxbuf *xb)
free any malloced resources
Definition agxbuf.h:78
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
Definition agxbuf.h:234
static WUR char * agxbuse(agxbuf *xb)
Definition agxbuf.h:307
static int agxbputc(agxbuf *xb, char c)
add character to buffer
Definition agxbuf.h:277
static char * agxbdisown(agxbuf *xb)
Definition agxbuf.h:327
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
Definition alloc.h:73
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static void * gv_alloc(size_t size)
Definition alloc.h:47
#define MIN(a, b)
Definition arith.h:28
boxf arrow_bb(pointf p, pointf u, double arrowsize)
Definition arrows.c:1112
#define dtmatch(d, o)
Definition cdt.h:184
#define dtinsert(d, o)
Definition cdt.h:185
CDT_API int dtclose(Dt_t *)
Definition dtclose.c:8
CDT_API Dtmethod_t * Dtoset
ordered set (self-adjusting tree)
Definition dttree.c:304
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
Definition dtopen.c:9
pointf Bezier(pointf *V, double t, pointf *Left, pointf *Right)
Definition utils.c:170
void processClusterEdges(graph_t *g)
Definition utils.c:927
void undoClusterEdges(graph_t *g)
Definition utils.c:1026
char * late_nnstring(void *obj, attrsym_t *attr, char *defaultValue)
Definition utils.c:86
char * scanEntity(char *t, agxbuf *xb)
Definition utils.c:1078
#define W_DEGREE
Definition utils.c:162
static edge_t * cloneEdge(edge_t *e, node_t *ct, node_t *ch)
Make a copy of e in e's graph but using ct and ch as nodes.
Definition utils.c:793
bool mapbool(const char *p)
Definition utils.c:337
node_t * UF_union(node_t *u, node_t *v)
Definition utils.c:110
node_t * UF_find(node_t *n)
Definition utils.c:100
static int Tflag
Definition utils.c:402
static node_t * mapN(node_t *n, graph_t *clg)
Definition utils.c:969
Dt_t * mkClustMap(Agraph_t *g)
Definition utils.c:1588
void UF_setname(node_t *u, node_t *v)
Definition utils.c:145
static void undoCompound(edge_t *e, graph_t *clg)
Definition utils.c:996
void setEdgeType(graph_t *g, int defaultValue)
Definition utils.c:1419
static port chkPort(port(*pf)(node_t *, char *, char *), node_t *n, char *s)
Definition utils.c:486
char * late_string(void *obj, attrsym_t *attr, char *defaultValue)
Definition utils.c:80
void gv_free_splines(edge_t *e)
Definition utils.c:1499
boxf polyBB(polygon_t *poly)
Definition utils.c:601
int late_int(void *obj, attrsym_t *attr, int defaultValue, int minimum)
Definition utils.c:35
static Dtdisc_t mapDisc
Definition utils.c:783
void gv_cleanup_edge(edge_t *e)
Definition utils.c:1509
static void insertEdge(Dt_t *map, void *t, void *h, edge_t *e)
Definition utils.c:804
void common_init_node(node_t *n)
Definition utils.c:423
bool overlap_label(textlabel_t *lp, boxf b)
Definition utils.c:1319
int maptoken(char *p, char **name, int *val)
Definition utils.c:311
double late_double(void *obj, attrsym_t *attr, double defaultValue, double minimum)
Definition utils.c:50
static char * findPath(const strview_t *dirs, const char *str)
Definition utils.c:248
static void initFontLabelEdgeAttr(edge_t *e, struct fontinfo *fi, struct fontinfo *lfi)
Definition utils.c:461
bool overlap_node(node_t *n, boxf b)
Definition utils.c:1307
static int comp_entities(const void *e1, const void *e2)
Definition utils.c:1068
void common_init_edge(edge_t *e)
Definition utils.c:506
static bool noClip(edge_t *e, attrsym_t *sym)
Return true if head/tail end of edge should not be clipped to node.
Definition utils.c:472
const char * safefile(const char *filename)
Definition utils.c:260
pointf dotneato_closest(splines *spl, pointf pt)
Definition utils.c:342
static strview_t * mkDirlist(const char *list)
Definition utils.c:236
static bool overlap_bezier(bezier bz, boxf b)
Definition utils.c:1332
pointf coord(node_t *n)
Definition utils.c:152
static void * newItem(void *p, Dtdisc_t *disc)
Definition utils.c:770
attrsym_t * safe_dcl(graph_t *g, int obj_kind, char *name, char *defaultValue)
Definition utils.c:1061
void UF_singleton(node_t *u)
Definition utils.c:138
static void initFontEdgeAttr(edge_t *e, struct fontinfo *fi)
Definition utils.c:453
char * utf8ToLatin1(char *s)
Definition utils.c:1289
static int cmpItem(void *pp1, void *pp2)
Definition utils.c:756
char * latin1ToUTF8(char *s)
Converts string from Latin1 encoding to utf8. Also translates HTML entities.
Definition utils.c:1256
double get_inputscale(graph_t *g)
Definition utils.c:73
static int edgeType(const char *s, int defaultValue)
Convert string to edge type.
Definition utils.c:1370
static boxf addLabelBB(boxf bb, textlabel_t *lp, bool flipxy)
Definition utils.c:566
void updateBB(graph_t *g, textlabel_t *lp)
Definition utils.c:621
static bool overlap_arrow(pointf p, pointf u, double scale, boxf b)
Definition utils.c:1326
static int checkCompound(edge_t *e, graph_t *clg, agxbuf *xb, Dt_t *map, Dt_t *cmap)
Definition utils.c:843
bool overlap_edge(edge_t *e, boxf b)
Definition utils.c:1354
static unsigned char cvtAndAppend(unsigned char c, agxbuf *xb)
Definition utils.c:1162
void compute_bb(graph_t *g)
Definition utils.c:630
static void fillMap(Agraph_t *g, Dt_t *map)
Definition utils.c:1567
static Dtdisc_t strDisc
Definition utils.c:1560
static node_t * clustNode(node_t *n, graph_t *cg, agxbuf *xb, graph_t *clg)
Definition utils.c:726
void gv_cleanup_node(node_t *n)
Definition utils.c:1521
bool mapBool(const char *p, bool defaultValue)
Definition utils.c:321
char * htmlEntityUTF8(char *s, graph_t *g)
Definition utils.c:1179
static int num_clust_edges(graph_t *g)
Definition utils.c:913
#define PATHSEP
Definition utils.c:233
void get_gradient_points(pointf *A, pointf *G, size_t n, double angle, int flags)
Definition utils.c:1442
void gv_nodesize(node_t *n, bool flip)
Definition utils.c:1532
int test_toggle(void)
Definition utils.c:412
static item * mapEdge(Dt_t *map, edge_t *e)
Check if we already have cluster edge corresponding to t->h, and return it.
Definition utils.c:814
static int htmlEntity(char **s)
Definition utils.c:1100
bool is_a_cluster(Agraph_t *g)
Definition utils.c:692
static graph_t * mapc(Dt_t *cmap, node_t *n)
Definition utils.c:820
bool late_bool(void *obj, attrsym_t *attr, bool defaultValue)
Definition utils.c:93
Agraph_t * findCluster(Dt_t *map, char *name)
Definition utils.c:1598
double drand48(void)
Definition utils.c:1546
Agsym_t * setAttr(graph_t *g, void *obj, char *name, char *value, Agsym_t *ap)
Definition utils.c:701
#define HEAD_LABEL
Definition const.h:177
#define NORMAL
Definition const.h:24
#define EDGETYPE_SPLINE
Definition const.h:253
#define EDGE_XLABEL
Definition const.h:181
#define DEFAULT_NODEHEIGHT
Definition const.h:72
#define TAIL_LABEL
Definition const.h:178
#define EDGE_LABEL
Definition const.h:176
#define EDGETYPE_CURVED
Definition const.h:250
#define DEFAULT_COLOR
Definition const.h:48
#define DEFAULT_NODEWIDTH
Definition const.h:74
#define LT_RECD
Definition const.h:239
#define EDGETYPE_ORTHO
Definition const.h:252
#define MIN_NODEWIDTH
Definition const.h:75
#define DEFAULT_FONTSIZE
Definition const.h:61
#define MIN_FONTSIZE
Definition const.h:63
#define EDGETYPE_PLINE
Definition const.h:251
#define EDGETYPE_LINE
Definition const.h:249
#define LT_NONE
Definition const.h:237
#define DEFAULT_FONTNAME
Definition const.h:67
#define EDGETYPE_NONE
Definition const.h:248
#define EDGETYPE_COMPOUND
Definition const.h:254
#define DEFAULT_NODESHAPE
Definition const.h:76
#define NODE_XLABEL
Definition const.h:180
#define LT_HTML
Definition const.h:238
#define MIN_NODEHEIGHT
Definition const.h:73
#define ENTITY_NAME_LENGTH_MAX
Definition entities.h:274
static const struct entities_s entities[]
#define NR_OF_ENTITIES
Definition entities.h:275
static Dtdisc_t disc
Definition exparse.y:207
#define A(n, t)
Definition expr.h:76
static int flags
Definition gc.c:61
#define G
Definition gdefs.h:7
#define V
Definition gdefs.h:5
int lineToBox(pointf p, pointf q, boxf b)
Definition geom.c:47
#define B2BF(b, bf)
Definition geom.h:69
#define OVERLAP(b0, b1)
Definition geom.h:48
struct pointf_s pointf
#define DIST2(p, q)
Definition geom.h:55
#define POINTS_PER_INCH
Definition geom.h:58
#define INCH2PS(a_inches)
Definition geom.h:63
geometric functions (e.g. on points and boxes)
static pointf mid_pointf(pointf p, pointf q)
Definition geomprocs.h:106
static void expandbp(boxf *b, pointf p)
expand box b as needed to enclose point p
Definition geomprocs.h:44
static pointf add_pointf(pointf p, pointf q)
Definition geomprocs.h:88
static pointf sub_pointf(pointf p, pointf q)
Definition geomprocs.h:97
static pointf scale(double c, pointf p)
Definition geomprocs.h:155
static bool boxf_overlap(boxf b0, boxf b1)
Definition geomprocs.h:142
#define EXPANDBB(b0, b1)
Definition geomprocs.h:64
Agsym_t * N_fontsize
Definition globals.h:75
Agsym_t * E_labelfontsize
Definition globals.h:89
Agsym_t * E_fontcolor
Definition globals.h:83
Agsym_t * N_width
Definition globals.h:74
Agsym_t * E_headclip
Definition globals.h:91
Agsym_t * E_headlabel
Definition globals.h:88
Agsym_t * N_showboxes
Definition globals.h:76
Agsym_t * N_fontname
Definition globals.h:75
Agsym_t * E_fontname
Definition globals.h:83
Agsym_t * N_style
Definition globals.h:76
char * HTTPServerEnVar
Definition globals.h:53
char * Gvimagepath
Definition globals.h:49
Agsym_t * E_label
Definition globals.h:84
double PSinputscale
Definition globals.h:56
char * Gvfilepath
Definition globals.h:48
Agsym_t * N_shape
Definition globals.h:74
Agsym_t * N_xlabel
Definition globals.h:76
Agsym_t * E_label_float
Definition globals.h:86
Agsym_t * E_taillabel
Definition globals.h:88
Agsym_t * N_label
Definition globals.h:76
Agsym_t * E_fontsize
Definition globals.h:83
Agsym_t * E_labelfontname
Definition globals.h:89
Agsym_t * E_xlabel
Definition globals.h:84
Agsym_t * N_fontcolor
Definition globals.h:75
Agsym_t * E_labelfontcolor
Definition globals.h:89
Agsym_t * E_tailclip
Definition globals.h:91
Agsym_t * N_height
Definition globals.h:74
static double len(glCompPoint p)
Definition glutils.c:150
void free(void *)
#define SIZE_MAX
Definition gmlscan.c:347
node NULL
Definition grammar.y:163
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:200
int agnnodes(Agraph_t *g)
Definition graph.c:159
Agsym_t * agattr_text(Agraph_t *g, int kind, char *name, const char *value)
creates or looks up text attributes of a graph
Definition attr.c:357
Agsym_t * agnxtattr(Agraph_t *g, int kind, Agsym_t *attr)
permits traversing the list of attributes of a given type
Definition attr.c:386
int agxset(void *obj, Agsym_t *sym, const char *value)
Definition attr.c:546
char * agget(void *obj, char *name)
Definition attr.c:472
char * agxget(void *obj, Agsym_t *sym)
Definition attr.c:482
int agcopyattr(void *oldobj, void *newobj)
copies all of the attributes from one object to another
Definition attr.c:659
#define ED_compound(e)
Definition types.h:583
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition edge.c:256
#define ED_xlabel(e)
Definition types.h:590
#define ED_label_ontop(e)
Definition types.h:591
#define ED_head_label(e)
Definition types.h:587
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:24
#define ED_spl(e)
Definition types.h:595
#define agtail(e)
Definition cgraph.h:986
#define ED_path(e)
Definition types.h:593
#define agfindedge(g, t, h)
Definition types.h:609
#define ED_tail_label(e)
Definition types.h:596
#define aghead(e)
Definition cgraph.h:987
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:39
#define ED_head_port(e)
Definition types.h:588
#define ED_label(e)
Definition types.h:589
#define ED_tail_port(e)
Definition types.h:597
void agwarningf(const char *fmt,...)
Definition agerror.c:173
#define agfindgraphattr(g, a)
Definition types.h:613
#define GD_has_labels(g)
Definition types.h:368
#define GD_clust(g)
Definition types.h:360
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Definition graph.c:97
#define GD_flags(g)
Definition types.h:365
#define GD_bb(g)
Definition types.h:354
#define GD_n_cluster(g)
Definition types.h:389
#define GD_label(g)
Definition types.h:374
#define GD_flip(g)
Definition types.h:378
Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition node.c:140
#define ND_ht(n)
Definition types.h:500
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:47
#define ND_bb(n)
Definition types.h:488
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:40
#define ND_showboxes(n)
Definition types.h:530
#define ND_has_port(n)
Definition types.h:495
#define ND_ysize(n)
Definition types.h:538
Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition node.c:254
#define ND_label(n)
Definition types.h:502
#define ND_rw(n)
Definition types.h:525
#define ND_height(n)
Definition types.h:498
#define ND_width(n)
Definition types.h:536
#define ND_lw(n)
Definition types.h:506
#define ND_UF_parent(n)
Definition types.h:485
#define ND_xlabel(n)
Definition types.h:503
#define ND_UF_size(n)
Definition types.h:487
#define ND_pos(n)
Definition types.h:520
#define ND_ranktype(n)
Definition types.h:524
#define agfindnode(g, n)
Definition types.h:611
#define ND_coord(n)
Definition types.h:490
#define ND_shape(n)
Definition types.h:528
#define ND_xsize(n)
Definition types.h:537
Agraph_t * agraphof(void *obj)
Definition obj.c:185
#define AGDATA(obj)
returns Agrec_t
Definition cgraph.h:227
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
int agdelete(Agraph_t *g, void *obj)
deletes object. Equivalent to agclose, agdelnode, and agdeledge for obj being a graph,...
Definition obj.c:20
int agcontains(Agraph_t *, void *obj)
returns non-zero if obj is a member of (sub)graph
Definition obj.c:233
int agobjkind(void *obj)
Definition obj.c:252
Agraph_t * agroot(void *obj)
Definition obj.c:168
@ AGEDGE
Definition cgraph.h:207
@ AGNODE
Definition cgraph.h:207
@ AGRAPH
Definition cgraph.h:207
void * agbindrec(void *obj, const char *name, unsigned int recsize, int move_to_front)
attaches a new record of the given size to the object
Definition rec.c:89
int agdelrec(void *obj, const char *name)
deletes a named record from one object
Definition rec.c:137
int aghtmlstr(const char *)
Definition refstr.c:438
Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition subg.c:55
void gvToggle(int s)
Definition utils.c:403
replacements for ctype.h functions
static bool gv_isdigit(int c)
Definition gv_ctype.h:41
Arithmetic helper functions.
static bool is_exactly_zero(double v)
is a value precisely 0.0?
Definition gv_math.h:63
static int imin(int a, int b)
minimum of two integers
Definition gv_math.h:28
Graphviz context library.
#define DIRSEP
Definition gvcint.h:164
static bool onetime
textitem scanner parser str
Definition htmlparse.y:224
textlabel_t * make_label(void *obj, char *str, int kind, double fontsize, char *fontname, char *fontcolor)
Definition labels.c:108
void free_label(textlabel_t *p)
Definition labels.c:199
static int * ps
Definition lu.c:51
#define IS_CLUST_NODE(n)
Definition macros.h:23
#define SET_CLUST_NODE(n)
Definition macros.h:22
#define CL_EDGE_TAG
Definition macros.h:21
#define HAS_CLUST_EDGE(g)
Definition macros.h:24
#define ND_id(n)
Definition mm2gv.c:39
NEATOPROCS_API void s1(graph_t *, node_t *)
Definition stuff.c:671
shape_kind shapeOf(node_t *)
Definition shapes.c:1906
shape_desc * bind_shape(char *name, node_t *)
Definition shapes.c:3994
static double cg(SparseMatrix A, const double *precond, int n, int dim, double *x0, double *rhs, double tol, double maxit)
static bool startswith(const char *s, const char *prefix)
does the string s begin with the string prefix?
Definition startswith.h:11
platform abstraction for case-insensitive string functions
static bool streq(const char *a, const char *b)
are a and b equal?
Definition streq.h:11
graph or subgraph
Definition cgraph.h:424
Agraph_t * root
subgraphs - ancestors
Definition cgraph.h:433
implementation of Agrec_t
Definition cgraph.h:172
string attribute descriptor symbol in Agattr_s.dict
Definition cgraph.h:651
char * defval
Definition cgraph.h:654
size_t size
number of characters in the buffer
Definition agxbuf.h:58
Definition types.h:89
size_t size
Definition types.h:91
pointf sp
Definition types.h:94
pointf * list
Definition types.h:90
uint32_t eflag
Definition types.h:93
pointf ep
Definition types.h:95
uint32_t sflag
Definition types.h:92
Definition geom.h:41
pointf UR
Definition geom.h:41
pointf LL
Definition geom.h:41
Agrec_t hdr
Definition utils.c:908
int n_cluster_edges
Definition utils.c:909
Agraph_t * clp
Definition utils.c:1557
char * name
Definition utils.c:1556
Dtlink_t link
Definition utils.c:1555
Definition cdt.h:100
int key
Definition cdt.h:85
char * name
Definition entities.h:17
int value
Definition entities.h:18
double fontsize
Definition utils.c:418
char * fontcolor
Definition utils.c:420
char * fontname
Definition utils.c:419
Definition utils.c:749
node_t * t
Definition utils.c:752
node_t * h
Definition utils.c:753
void * p[2]
Definition utils.c:751
Dtlink_t link
Definition utils.c:750
int y
Definition geom.h:27
int x
Definition geom.h:27
double x
Definition geom.h:29
double y
Definition geom.h:29
Definition types.h:48
char * name
Definition types.h:63
bezier * list
Definition types.h:99
boxf bb
Definition types.h:101
size_t size
Definition types.h:100
a non-owning string reference
Definition strview.h:20
const char * data
start of the pointed to string
Definition strview.h:21
size_t size
extent of the string in bytes
Definition strview.h:22
pointf pos
Definition types.h:114
pointf dimen
Definition types.h:110
state for an in-progress string tokenization
Definition tokenize.h:36
Non-owning string references.
static int strview_cmp(strview_t a, strview_t b)
compare two string references
Definition strview.h:71
static strview_t strview(const char *referent, char terminator)
create a string reference
Definition strview.h:26
static point center(point vertex[], size_t n)
String tokenization.
static strview_t tok_get(const tok_t *t)
get the current token
Definition tokenize.h:76
static tok_t tok(const char *input, const char *separators)
begin tokenization of a new string
Definition tokenize.h:43
static bool tok_end(const tok_t *t)
is this tokenizer exhausted?
Definition tokenize.h:68
static void tok_next(tok_t *t)
advance to the next token in the string being scanned
Definition tokenize.h:85
#define ag_xget(x, a)
Definition types.h:606
#define TAIL_ID
Definition types.h:43
@ SH_RECORD
Definition types.h:187
#define HEAD_ID
Definition types.h:44
struct inside_t::@82 s
node_t * n
Definition types.h:160
Definition grammar.c:93
#define MAX(a, b)
Definition write.c:31
int(* pf)(void *, char *,...)
Definition xdot.c:396