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