Graphviz 14.0.2~dev.20251008.0253
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 = agxget(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 = agxget(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);
440 fi.fontsize, fi.fontname, fi.fontcolor);
441 if (N_xlabel && (str = agxget(n, N_xlabel)) && str[0]) {
442 ND_xlabel(n) = make_label(n, str, aghtmlstr(str), false,
443 fi.fontsize, fi.fontname, fi.fontcolor);
445 }
446
447 {
448 const int showboxes = imin(late_int(n, N_showboxes, 0, 0), UCHAR_MAX);
449 ND_showboxes(n) = (unsigned char)showboxes;
450 }
451 ND_shape(n)->fns->initfn(n);
452}
453
460
461static void
463 struct fontinfo *lfi)
464{
465 if (!fi->fontname) initFontEdgeAttr(e, fi);
469}
470
472static bool
474{
475 char *str;
476 bool rv = false;
477
478 if (sym) { /* mapbool isn't a good fit, because we want "" to mean true */
479 str = agxget(e,sym);
480 if (str && str[0]) rv = !mapbool(str);
481 else rv = false;
482 }
483 return rv;
484}
485
486static port
487chkPort (port (*pf)(node_t*, char*, char*), node_t* n, char* s)
488{
489 port pt;
490 char* cp=NULL;
491 if(s)
492 cp= strchr(s,':');
493 if (cp) {
494 *cp = '\0';
495 pt = pf(n, s, cp+1);
496 *cp = ':';
497 pt.name = cp+1;
498 }
499 else {
500 pt = pf(n, s, NULL);
501 pt.name = s;
502 }
503 return pt;
504}
505
506/* return true if edge has label */
508 char *str;
509 struct fontinfo fi;
510 struct fontinfo lfi;
511 graph_t *sg = agraphof(agtail(e));
512
513 fi.fontname = NULL;
514 lfi.fontname = NULL;
515 if (E_label && (str = agxget(e, E_label)) && str[0]) {
516 initFontEdgeAttr(e, &fi);
517 ED_label(e) = make_label(e, str, aghtmlstr(str), false,
518 fi.fontsize, fi.fontname, fi.fontcolor);
521 }
522
523 if (E_xlabel && (str = agxget(e, E_xlabel)) && str[0]) {
524 if (!fi.fontname)
525 initFontEdgeAttr(e, &fi);
526 ED_xlabel(e) = make_label(e, str, aghtmlstr(str), false,
527 fi.fontsize, fi.fontname, fi.fontcolor);
529 }
530
531 if (E_headlabel && (str = agxget(e, E_headlabel)) && str[0]) {
532 initFontLabelEdgeAttr(e, &fi, &lfi);
533 ED_head_label(e) = make_label(e, str, aghtmlstr(str), false,
534 lfi.fontsize, lfi.fontname, lfi.fontcolor);
536 }
537 if (E_taillabel && (str = agxget(e, E_taillabel)) && str[0]) {
538 if (!lfi.fontname)
539 initFontLabelEdgeAttr(e, &fi, &lfi);
540 ED_tail_label(e) = make_label(e, str, aghtmlstr(str), false,
541 lfi.fontsize, lfi.fontname, lfi.fontcolor);
543 }
544
545 /* We still accept ports beginning with colons but this is deprecated
546 * That is, we allow tailport = ":abc" as well as the preferred
547 * tailport = "abc".
548 */
549 str = agget(e, TAIL_ID);
550 /* libgraph always defines tailport/headport; libcgraph doesn't */
551 if (!str) str = "";
552 if (str && str[0])
553 ND_has_port(agtail(e)) = true;
554 ED_tail_port(e) = chkPort (ND_shape(agtail(e))->fns->portfn, agtail(e), str);
555 if (noClip(e, E_tailclip))
556 ED_tail_port(e).clip = false;
557 str = agget(e, HEAD_ID);
558 /* libgraph always defines tailport/headport; libcgraph doesn't */
559 if (!str) str = "";
560 if (str && str[0])
561 ND_has_port(aghead(e)) = true;
562 ED_head_port(e) = chkPort(ND_shape(aghead(e))->fns->portfn, aghead(e), str);
563 if (noClip(e, E_headclip))
564 ED_head_port(e).clip = false;
565}
566
567static boxf addLabelBB(boxf bb, textlabel_t * lp, bool flipxy)
568{
569 double width, height;
570 pointf p = lp->pos;
571 double min, max;
572
573 if (flipxy) {
574 height = lp->dimen.x;
575 width = lp->dimen.y;
576 }
577 else {
578 width = lp->dimen.x;
579 height = lp->dimen.y;
580 }
581 min = p.x - width / 2.;
582 max = p.x + width / 2.;
583 if (min < bb.LL.x)
584 bb.LL.x = min;
585 if (max > bb.UR.x)
586 bb.UR.x = max;
587
588 min = p.y - height / 2.;
589 max = p.y + height / 2.;
590 if (min < bb.LL.y)
591 bb.LL.y = min;
592 if (max > bb.UR.y)
593 bb.UR.y = max;
594
595 return bb;
596}
597
601boxf
603{
604 const size_t sides = poly->sides;
605 const size_t peris = MAX(poly->peripheries, (size_t)1);
606 pointf* verts = poly->vertices + (peris-1)*sides;
607 boxf bb;
608
609 bb.LL = bb.UR = verts[0];
610 for (size_t i = 1; i < sides; i++) {
611 bb.LL.x = MIN(bb.LL.x,verts[i].x);
612 bb.LL.y = MIN(bb.LL.y,verts[i].y);
613 bb.UR.x = MAX(bb.UR.x,verts[i].x);
614 bb.UR.y = MAX(bb.UR.y,verts[i].y);
615 }
616 return bb;
617}
618
623{
624 GD_bb(g) = addLabelBB(GD_bb(g), lp, GD_flip(g));
625}
626
632{
633 node_t *n;
634 edge_t *e;
635 boxf b, bb;
636 boxf BF;
637 pointf ptf, s2;
638
639 if (agnnodes(g) == 0 && GD_n_cluster(g) == 0) {
640 bb.LL = (pointf){0};
641 bb.UR = (pointf){0};
642 return;
643 }
644
645 bb.LL = (pointf){INT_MAX, INT_MAX};
646 bb.UR = (pointf){-INT_MAX, -INT_MAX};
647 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
648 ptf = coord(n);
649 s2.x = ND_xsize(n) / 2.0;
650 s2.y = ND_ysize(n) / 2.0;
651 b.LL = sub_pointf(ptf, s2);
652 b.UR = add_pointf(ptf, s2);
653
654 EXPANDBB(&bb, b);
655 if (ND_xlabel(n) && ND_xlabel(n)->set) {
656 bb = addLabelBB(bb, ND_xlabel(n), GD_flip(g));
657 }
658 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
659 if (ED_spl(e) == 0)
660 continue;
661 for (size_t i = 0; i < ED_spl(e)->size; i++) {
662 for (size_t j = 0; j < (((Agedgeinfo_t*)AGDATA(e))->spl)->list[i].size; j++) {
663 ptf = ED_spl(e)->list[i].list[j];
664 expandbp(&bb, ptf);
665 }
666 }
667 if (ED_label(e) && ED_label(e)->set) {
668 bb = addLabelBB(bb, ED_label(e), GD_flip(g));
669 }
670 if (ED_head_label(e) && ED_head_label(e)->set) {
671 bb = addLabelBB(bb, ED_head_label(e), GD_flip(g));
672 }
673 if (ED_tail_label(e) && ED_tail_label(e)->set) {
674 bb = addLabelBB(bb, ED_tail_label(e), GD_flip(g));
675 }
676 if (ED_xlabel(e) && ED_xlabel(e)->set) {
677 bb = addLabelBB(bb, ED_xlabel(e), GD_flip(g));
678 }
679 }
680 }
681
682 for (int i = 1; i <= GD_n_cluster(g); i++) {
683 B2BF(GD_bb(GD_clust(g)[i]), BF);
684 EXPANDBB(&bb, BF);
685 }
686 if (GD_label(g) && GD_label(g)->set) {
687 bb = addLabelBB(bb, GD_label(g), GD_flip(g));
688 }
689
690 GD_bb(g) = bb;
691}
692
694{
695 return g == g->root || !strncasecmp(agnameof(g), "cluster", 7) ||
696 mapbool(agget(g, "cluster"));
697}
698
702Agsym_t *setAttr(graph_t * g, void *obj, char *name, char *value,
703 Agsym_t * ap)
704{
705 if (ap == NULL) {
706 switch (agobjkind(obj)) {
707 case AGRAPH:
708 ap = agattr_text(g, AGRAPH,name, "");
709 break;
710 case AGNODE:
711 ap = agattr_text(g,AGNODE, name, "");
712 break;
713 case AGEDGE:
714 ap = agattr_text(g,AGEDGE, name, "");
715 break;
716 }
717 }
718 agxset(obj, ap, value);
719 return ap;
720}
721
727static node_t *clustNode(node_t * n, graph_t * cg, agxbuf * xb,
728 graph_t * clg)
729{
730 node_t *cn;
731 static int idx = 0;
732
733 agxbprint(xb, "__%d:%s", idx++, agnameof(cg));
734
735 cn = agnode(agroot(cg), agxbuse(xb), 1);
736 agbindrec(cn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), true);
737
738 SET_CLUST_NODE(cn);
739 agsubnode(cg,cn,1);
740 agsubnode(clg,n,1);
741
742 /* set attributes */
743 N_label = setAttr(agraphof(cn), cn, "label", "", N_label);
744 N_style = setAttr(agraphof(cn), cn, "style", "invis", N_style);
745 N_shape = setAttr(agraphof(cn), cn, "shape", "box", N_shape);
746
747 return cn;
748}
749
750typedef struct {
751 Dtlink_t link; /* cdt data */
752 void *p[2]; /* key */
755} item;
756
757static int cmpItem(void *pp1, void *pp2) {
758 const void **p1 = pp1;
759 const void **p2 = pp2;
760 if ((uintptr_t)p1[0] < (uintptr_t)p2[0])
761 return -1;
762 if ((uintptr_t)p1[0] > (uintptr_t)p2[0])
763 return 1;
764 if ((uintptr_t)p1[1] < (uintptr_t)p2[1])
765 return -1;
766 if ((uintptr_t)p1[1] > (uintptr_t)p2[1])
767 return 1;
768 return 0;
769}
770
771static void *newItem(void *p, Dtdisc_t *disc) {
772 item *objp = p;
773 item *newp = gv_alloc(sizeof(item));
774
775 (void)disc;
776 newp->p[0] = objp->p[0];
777 newp->p[1] = objp->p[1];
778 newp->t = objp->t;
779 newp->h = objp->h;
780
781 return newp;
782}
783
785 .key = offsetof(item, p),
786 .size = sizeof(2 * sizeof(void *)),
787 .link = offsetof(item, link),
788 .makef = newItem,
789 .freef = free,
790 .comparf = cmpItem,
791};
792
794static edge_t *cloneEdge(edge_t * e, node_t * ct, node_t * ch)
795{
796 graph_t *g = agraphof(ct);
797 edge_t *ce = agedge(g, ct, ch,NULL,1);
798 agbindrec(ce, "Agedgeinfo_t", sizeof(Agedgeinfo_t), true);
799 agcopyattr(e, ce);
800 ED_compound(ce) = true;
801
802 return ce;
803}
804
805static void insertEdge(Dt_t * map, void *t, void *h, edge_t * e)
806{
807 item dummy1 = {.p = {t, h}, .t = agtail(e), .h = aghead(e)};
808 dtinsert(map, &dummy1);
809
810 item dummy2 = {.p = {h, t}, .t = aghead(e), .h = agtail(e)};
811 dtinsert(map, &dummy2);
812}
813
815static item *mapEdge(Dt_t * map, edge_t * e)
816{
817 void *key[] = {agtail(e), aghead(e)};
818 return dtmatch(map, &key);
819}
820
821static graph_t *mapc(Dt_t *cmap, node_t *n) {
822 if (startswith(agnameof(n), "cluster")) {
823 return findCluster(cmap, agnameof(n));
824 }
825 return NULL;
826}
827
843static int
844checkCompound(edge_t * e, graph_t * clg, agxbuf * xb, Dt_t * map, Dt_t* cmap)
845{
846 node_t *cn;
847 node_t *cn1;
848 node_t *t = agtail(e);
849 node_t *h = aghead(e);
850 edge_t *ce;
851 item *ip;
852
853 if (IS_CLUST_NODE(h)) return 0;
854 graph_t *const tg = mapc(cmap, t);
855 graph_t *const hg = mapc(cmap, h);
856 if (!tg && !hg)
857 return 0;
858 if (tg == hg) {
859 agwarningf("cluster cycle %s -- %s not supported\n", agnameof(t),
860 agnameof(t));
861 return 0;
862 }
863 ip = mapEdge(map, e);
864 if (ip) {
865 cloneEdge(e, ip->t, ip->h);
866 return 1;
867 }
868
869 if (hg) {
870 if (tg) {
871 if (agcontains(hg, tg)) {
872 agwarningf("tail cluster %s inside head cluster %s\n",
873 agnameof(tg), agnameof(hg));
874 return 0;
875 }
876 if (agcontains(tg, hg)) {
877 agwarningf("head cluster %s inside tail cluster %s\n",
878 agnameof(hg),agnameof(tg));
879 return 0;
880 }
881 cn = clustNode(t, tg, xb, clg);
882 cn1 = clustNode(h, hg, xb, clg);
883 ce = cloneEdge(e, cn, cn1);
884 insertEdge(map, t, h, ce);
885 } else {
886 if (agcontains(hg, t)) {
887 agwarningf("tail node %s inside head cluster %s\n",
888 agnameof(t), agnameof(hg));
889 return 0;
890 }
891 cn = clustNode(h, hg, xb, clg);
892 ce = cloneEdge(e, t, cn);
893 insertEdge(map, t, h, ce);
894 }
895 } else {
896 if (agcontains(tg, h)) {
897 agwarningf("head node %s inside tail cluster %s\n", agnameof(h),
898 agnameof(tg));
899 return 0;
900 }
901 cn = clustNode(t, tg, xb, clg);
902 ce = cloneEdge(e, cn, h);
903 insertEdge(map, t, h, ce);
904 }
905 return 1;
906}
907
908typedef struct {
911} cl_edge_t;
912
913static int
915{
916 cl_edge_t* cl_info = (cl_edge_t*)HAS_CLUST_EDGE(g);
917 if (cl_info)
918 return cl_info->n_cluster_edges;
919 return 0;
920}
921
929{
930 int num_cl_edges = 0;
931 node_t *n;
932 node_t *nxt;
933 edge_t *e;
934 graph_t *clg;
935 agxbuf xb = {0};
936 Dt_t *map;
937 Dt_t *cmap = mkClustMap (g);
938
939 map = dtopen(&mapDisc, Dtoset);
940 clg = agsubg(g, "__clusternodes",1);
941 agbindrec(clg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
942 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
943 if (IS_CLUST_NODE(n)) continue;
944 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
945 num_cl_edges += checkCompound(e, clg, &xb, map, cmap);
946 }
947 }
948 agxbfree(&xb);
949 dtclose(map);
950 for (n = agfstnode(clg); n; n = nxt) {
951 nxt = agnxtnode(clg, n);
952 agdelete(g, n);
953 }
954 agclose(clg);
955 if (num_cl_edges) {
956 cl_edge_t* cl_info;
957 cl_info = agbindrec(g, CL_EDGE_TAG, sizeof(cl_edge_t), false);
958 cl_info->n_cluster_edges = num_cl_edges;
959 }
960 dtclose(cmap);
961}
962
970static node_t *mapN(node_t * n, graph_t * clg)
971{
972 node_t *nn;
973 char *name;
974 graph_t *g = agraphof(n);
975 Agsym_t *sym;
976
977 if (!IS_CLUST_NODE(n))
978 return n;
979 agsubnode(clg, n, 1);
980 name = strchr(agnameof(n), ':');
981 assert(name);
982 name++;
983 if ((nn = agfindnode(g, name)))
984 return nn;
985 nn = agnode(g, name, 1);
986 agbindrec(nn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), true);
987 SET_CLUST_NODE(nn);
988
989 /* Set all attributes to default */
990 for (sym = agnxtattr(g, AGNODE, NULL); sym; (sym = agnxtattr(g, AGNODE, sym))) {
991 if (agxget(nn, sym) != sym->defval)
992 agxset(nn, sym, sym->defval);
993 }
994 return nn;
995}
996
997static void undoCompound(edge_t * e, graph_t * clg)
998{
999 node_t *t = agtail(e);
1000 node_t *h = aghead(e);
1001 node_t *ntail;
1002 node_t *nhead;
1003 edge_t* ce;
1004
1005 ntail = mapN(t, clg);
1006 nhead = mapN(h, clg);
1007 ce = cloneEdge(e, ntail, nhead);
1008
1009 /* transfer drawing information */
1010 ED_spl(ce) = ED_spl(e);
1011 ED_spl(e) = NULL;
1012 ED_label(ce) = ED_label(e);
1013 ED_label(e) = NULL;
1014 ED_xlabel(ce) = ED_xlabel(e);
1015 ED_xlabel(e) = NULL;
1017 ED_head_label(e) = NULL;
1019 ED_tail_label(e) = NULL;
1020 gv_cleanup_edge(e);
1021}
1022
1028{
1029 node_t *n;
1030 node_t *nextn;
1031 edge_t *e;
1032 graph_t *clg;
1033 int ecnt = num_clust_edges(g);
1034 int i = 0;
1035
1036 if (!ecnt) return;
1037 clg = agsubg(g, "__clusternodes",1);
1038 agbindrec(clg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
1039 edge_t **edgelist = gv_calloc(ecnt, sizeof(edge_t*));
1040 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1041 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1042 if (ED_compound(e))
1043 edgelist[i++] = e;
1044 }
1045 }
1046 assert(i == ecnt);
1047 for (i = 0; i < ecnt; i++)
1048 undoCompound(edgelist[i], clg);
1049 free (edgelist);
1050 for (n = agfstnode(clg); n; n = nextn) {
1051 nextn = agnxtnode(clg, n);
1052 gv_cleanup_node(n);
1053 agdelete(g, n);
1054 }
1055 agclose(clg);
1056}
1057
1062attrsym_t *safe_dcl(graph_t *g, int obj_kind, char *name, char *defaultValue) {
1063 attrsym_t *a = agattr_text(g,obj_kind,name, NULL);
1064 if (!a) /* attribute does not exist */
1065 a = agattr_text(g, obj_kind, name, defaultValue);
1066 return a;
1067}
1068
1069static int comp_entities(const void *e1, const void *e2) {
1070 const strview_t *key = e1;
1071 const struct entities_s *candidate = e2;
1072 return strview_cmp(*key, strview(candidate->name, '\0'));
1073}
1074
1079char* scanEntity (char* t, agxbuf* xb)
1080{
1081 const strview_t key = strview(t, ';');
1082 struct entities_s *res;
1083
1084 agxbputc(xb, '&');
1085 if (key.data[key.size] == '\0') return t;
1086 if (key.size > ENTITY_NAME_LENGTH_MAX || key.size < 2) return t;
1087 res = bsearch(&key, entities, NR_OF_ENTITIES,
1088 sizeof(entities[0]), comp_entities);
1089 if (!res) return t;
1090 agxbprint(xb, "#%d;", res->value);
1091 return t + key.size + 1;
1092}
1093
1100static int
1102{
1103 struct entities_s *res;
1104 unsigned char* str = *(unsigned char**)s;
1105 unsigned int byte;
1106 int i, n = 0;
1107
1108 byte = *str;
1109 if (byte == '#') {
1110 byte = *(str + 1);
1111 if (byte == 'x' || byte == 'X') {
1112 for (i = 2; i < 8; i++) {
1113 byte = *(str + i);
1114 if (byte >= 'A' && byte <= 'F')
1115 byte = byte - 'A' + 10;
1116 else if (byte >= 'a' && byte <= 'f')
1117 byte = byte - 'a' + 10;
1118 else if (byte >= '0' && byte <= '9')
1119 byte = byte - '0';
1120 else
1121 break;
1122 n = n * 16 + (int)byte;
1123 }
1124 }
1125 else {
1126 for (i = 1; i < 8; i++) {
1127 byte = *(str + i);
1128 if (byte >= '0' && byte <= '9')
1129 n = n * 10 + ((int)byte - '0');
1130 else
1131 break;
1132 }
1133 }
1134 if (byte == ';') {
1135 str += i+1;
1136 }
1137 else {
1138 n = 0;
1139 }
1140 }
1141 else {
1142 strview_t key = {.data = (char *)str};
1143 for (i = 0; i < ENTITY_NAME_LENGTH_MAX; i++) {
1144 byte = *(str + i);
1145 if (byte == '\0') break;
1146 if (byte == ';') {
1147 res = bsearch(&key, entities, NR_OF_ENTITIES,
1148 sizeof(entities[0]), comp_entities);
1149 if (res) {
1150 n = res->value;
1151 str += i+1;
1152 }
1153 break;
1154 }
1155 ++key.size;
1156 }
1157 }
1158 *s = (char*)str;
1159 return n;
1160}
1161
1162static unsigned char
1163cvtAndAppend (unsigned char c, agxbuf* xb)
1164{
1165 char buf[] = {c, '\0'};
1166 char *s = latin1ToUTF8(buf);
1167 char *p = s;
1168 size_t len = strlen(s);
1169 while (len-- > 1)
1170 agxbputc(xb, *p++);
1171 c = *p;
1172 free (s);
1173 return c;
1174}
1175
1180char* htmlEntityUTF8 (char* s, graph_t* g)
1181{
1182 static graph_t* lastg;
1183 static atomic_flag warned;
1184 unsigned char c;
1185 unsigned int v;
1186
1187 int uc;
1188 int ui;
1189
1190 if (lastg != g) {
1191 lastg = g;
1192 atomic_flag_clear(&warned);
1193 }
1194
1195 agxbuf xb = {0};
1196
1197 while ((c = *(unsigned char*)s++)) {
1198 if (c < 0xC0)
1199 /*
1200 * Handles properly formed UTF-8 characters between
1201 * 0x01 and 0x7F. Also treats \0 and naked trail
1202 * bytes 0x80 to 0xBF as valid characters representing
1203 * themselves.
1204 */
1205 uc = 0;
1206 else if (c < 0xE0)
1207 uc = 1;
1208 else if (c < 0xF0)
1209 uc = 2;
1210 else if (c < 0xF8)
1211 uc = 3;
1212 else {
1213 uc = -1;
1214 if (!atomic_flag_test_and_set(&warned)) {
1215 agwarningf("UTF8 codes > 4 bytes are not currently supported (graph %s) - treated as Latin-1. Perhaps \"-Gcharset=latin1\" is needed?\n", agnameof(g));
1216 }
1217 c = cvtAndAppend (c, &xb);
1218 }
1219
1220 if (uc == 0 && c == '&') {
1221 /* replace html entity sequences like: &amp;
1222 * and: &#123; with their UTF8 equivalents */
1223 v = htmlEntity (&s);
1224 if (v) {
1225 if (v < 0x7F) /* entity needs 1 byte in UTF8 */
1226 c = v;
1227 else if (v < 0x07FF) { /* entity needs 2 bytes in UTF8 */
1228 agxbputc(&xb, (char)((v >> 6) | 0xC0));
1229 c = (v & 0x3F) | 0x80;
1230 }
1231 else { /* entity needs 3 bytes in UTF8 */
1232 agxbputc(&xb, (char)((v >> 12) | 0xE0));
1233 agxbputc(&xb, (char)(((v >> 6) & 0x3F) | 0x80));
1234 c = (v & 0x3F) | 0x80;
1235 }
1236 }
1237 }
1238 else /* copy n byte UTF8 characters */
1239 for (ui = 0; ui < uc; ++ui)
1240 if ((*s & 0xC0) == 0x80) {
1241 agxbputc(&xb, (char)c);
1242 c = *(unsigned char*)s++;
1243 }
1244 else {
1245 if (!atomic_flag_test_and_set(&warned)) {
1246 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));
1247 }
1248 c = cvtAndAppend (c, &xb);
1249 break;
1250 }
1251 agxbputc(&xb, (char)c);
1252 }
1253 return agxbdisown(&xb);
1254}
1255
1257char* latin1ToUTF8 (char* s)
1258{
1259 agxbuf xb = {0};
1260 unsigned int v;
1261
1262 /* Values are either a byte (<= 256) or come from htmlEntity, whose
1263 * values are all less than 0x07FF, so we need at most 3 bytes.
1264 */
1265 while ((v = *(unsigned char*)s++)) {
1266 if (v == '&') {
1267 v = htmlEntity (&s);
1268 if (!v) v = '&';
1269 }
1270 if (v < 0x7F)
1271 agxbputc(&xb, (char)v);
1272 else if (v < 0x07FF) {
1273 agxbputc(&xb, (char)((v >> 6) | 0xC0));
1274 agxbputc(&xb, (char)((v & 0x3F) | 0x80));
1275 }
1276 else {
1277 agxbputc(&xb, (char)((v >> 12) | 0xE0));
1278 agxbputc(&xb, (char)(((v >> 6) & 0x3F) | 0x80));
1279 agxbputc(&xb, (char)((v & 0x3F) | 0x80));
1280 }
1281 }
1282 return agxbdisown(&xb);
1283}
1284
1289char*
1291{
1292 agxbuf xb = {0};
1293 unsigned char c;
1294
1295 while ((c = *(unsigned char*)s++)) {
1296 if (c < 0x7F)
1297 agxbputc(&xb, (char)c);
1298 else {
1299 unsigned char outc = (c & 0x03) << 6;
1300 c = *(unsigned char *)s++;
1301 outc = outc | (c & 0x3F);
1302 agxbputc(&xb, (char)outc);
1303 }
1304 }
1305 return agxbdisown(&xb);
1306}
1307
1309 if (! OVERLAP(b, ND_bb(n)))
1310 return false;
1311
1312 /* FIXME - need to do something better about CLOSEENOUGH */
1313 pointf p = sub_pointf(ND_coord(n), mid_pointf(b.UR, b.LL));
1314
1315 inside_t ictxt = {.s.n = n};
1316
1317 return ND_shape(n)->fns->insidefn(&ictxt, p);
1318}
1319
1321{
1322 const pointf s = {.x = lp->dimen.x / 2.0, .y = lp->dimen.y / 2.0};
1323 boxf bb = {.LL = sub_pointf(lp->pos, s), .UR = add_pointf(lp->pos, s)};
1324 return OVERLAP(b, bb);
1325}
1326
1327static bool overlap_arrow(pointf p, pointf u, double scale, boxf b)
1328{
1329 // FIXME - check inside arrow shape
1330 return OVERLAP(b, arrow_bb(p, u, scale));
1331}
1332
1333static bool overlap_bezier(bezier bz, boxf b) {
1334 assert(bz.size);
1335 pointf u = bz.list[0];
1336 for (size_t i = 1; i < bz.size; i++) {
1337 pointf p = bz.list[i];
1338 if (lineToBox(p, u, b) != -1)
1339 return true;
1340 u = p;
1341 }
1342
1343 /* check arrows */
1344 if (bz.sflag) {
1345 if (overlap_arrow(bz.sp, bz.list[0], 1, b))
1346 return true;
1347 }
1348 if (bz.eflag) {
1349 if (overlap_arrow(bz.ep, bz.list[bz.size - 1], 1, b))
1350 return true;
1351 }
1352 return false;
1353}
1354
1356{
1357 splines *spl = ED_spl(e);
1358 if (spl && boxf_overlap(spl->bb, b))
1359 for (size_t i = 0; i < spl->size; i++)
1360 if (overlap_bezier(spl->list[i], b))
1361 return true;
1362
1363 textlabel_t *lp = ED_label(e);
1364 if (lp && overlap_label(lp, b))
1365 return true;
1366
1367 return false;
1368}
1369
1371static int edgeType(const char *s, int defaultValue) {
1372 if (s == NULL || strcmp(s, "") == 0) {
1373 return defaultValue;
1374 }
1375
1376 if (*s == '0') { /* false */
1377 return EDGETYPE_LINE;
1378 } else if (*s >= '1' && *s <= '9') { /* true */
1379 return EDGETYPE_SPLINE;
1380 } else if (strcasecmp(s, "curved") == 0) {
1381 return EDGETYPE_CURVED;
1382 } else if (strcasecmp(s, "compound") == 0) {
1383 return EDGETYPE_COMPOUND;
1384 } else if (strcasecmp(s, "false") == 0) {
1385 return EDGETYPE_LINE;
1386 } else if (strcasecmp(s, "line") == 0) {
1387 return EDGETYPE_LINE;
1388 } else if (strcasecmp(s, "none") == 0) {
1389 return EDGETYPE_NONE;
1390 } else if (strcasecmp(s, "no") == 0) {
1391 return EDGETYPE_LINE;
1392 } else if (strcasecmp(s, "ortho") == 0) {
1393 return EDGETYPE_ORTHO;
1394 } else if (strcasecmp(s, "polyline") == 0) {
1395 return EDGETYPE_PLINE;
1396 } else if (strcasecmp(s, "spline") == 0) {
1397 return EDGETYPE_SPLINE;
1398 } else if (strcasecmp(s, "true") == 0) {
1399 return EDGETYPE_SPLINE;
1400 } else if (strcasecmp(s, "yes") == 0) {
1401 return EDGETYPE_SPLINE;
1402 }
1403
1404 agwarningf("Unknown \"splines\" value: \"%s\" - ignored\n", s);
1405 return defaultValue;
1406}
1407
1420void setEdgeType(graph_t *g, int defaultValue) {
1421 char* s = agget(g, "splines");
1422 int et;
1423
1424 if (!s) {
1425 et = defaultValue;
1426 }
1427 else if (*s == '\0') {
1428 et = EDGETYPE_NONE;
1429 } else {
1430 et = edgeType(s, defaultValue);
1431 }
1432 GD_flags(g) |= et;
1433}
1434
1443void get_gradient_points(pointf *A, pointf *G, size_t n, double angle, int flags) {
1444 pointf min,max,center;
1445 int isRadial = flags & 1;
1446 int isRHS = flags & 2;
1447
1448 if (n == 2) {
1449 double rx = A[1].x - A[0].x;
1450 double ry = A[1].y - A[0].y;
1451 min.x = A[0].x - rx;
1452 max.x = A[0].x + rx;
1453 min.y = A[0].y - ry;
1454 max.y = A[0].y + ry;
1455 }
1456 else {
1457 min.x = max.x = A[0].x;
1458 min.y = max.y = A[0].y;
1459 for (size_t i = 0; i < n; i++) {
1460 min.x = MIN(A[i].x, min.x);
1461 min.y = MIN(A[i].y, min.y);
1462 max.x = MAX(A[i].x, max.x);
1463 max.y = MAX(A[i].y, max.y);
1464 }
1465 }
1466 center.x = min.x + (max.x - min.x)/2;
1467 center.y = min.y + (max.y - min.y)/2;
1468 if (isRadial) {
1469 double inner_r, outer_r;
1470 outer_r = hypot(center.x - min.x, center.y - min.y);
1471 inner_r = outer_r /4.;
1472 if (isRHS) {
1473 G[0].y = center.y;
1474 }
1475 else {
1476 G[0].y = -center.y;
1477 }
1478 G[0].x = center.x;
1479 G[1].x = inner_r;
1480 G[1].y = outer_r;
1481 }
1482 else {
1483 double half_x = max.x - center.x;
1484 double half_y = max.y - center.y;
1485 double sina = sin(angle);
1486 double cosa = cos(angle);
1487 if (isRHS) {
1488 G[0].y = center.y - half_y * sina;
1489 G[1].y = center.y + half_y * sina;
1490 }
1491 else {
1492 G[0].y = -center.y + (max.y - center.y) * sin(angle);
1493 G[1].y = -center.y - (center.y - min.y) * sin(angle);
1494 }
1495 G[0].x = center.x - half_x * cosa;
1496 G[1].x = center.x + half_x * cosa;
1497 }
1498}
1499
1501 if (ED_spl(e)) {
1502 for (size_t i = 0; i < ED_spl(e)->size; i++)
1503 free(ED_spl(e)->list[i].list);
1504 free(ED_spl(e)->list);
1505 free(ED_spl(e));
1506 }
1507 ED_spl(e) = NULL;
1508}
1509
1511{
1512 free(ED_path(e).ps);
1513 gv_free_splines(e);
1514 free_label(ED_label(e));
1518 /*FIX HERE , shallow cleaning may not be enough here */
1519 agdelrec(e, "Agedgeinfo_t");
1520}
1521
1523{
1524 free(ND_pos(n));
1525 if (ND_shape(n))
1526 ND_shape(n)->fns->freefn(n);
1527 free_label(ND_label(n));
1529 /*FIX HERE , shallow cleaning may not be enough here */
1530 agdelrec(n, "Agnodeinfo_t");
1531}
1532
1533void gv_nodesize(node_t *n, bool flip) {
1534 if (flip) {
1535 double w = INCH2PS(ND_height(n));
1536 ND_lw(n) = ND_rw(n) = w / 2;
1537 ND_ht(n) = INCH2PS(ND_width(n));
1538 }
1539 else {
1540 double w = INCH2PS(ND_width(n));
1541 ND_lw(n) = ND_rw(n) = w / 2;
1542 ND_ht(n) = INCH2PS(ND_height(n));
1543 }
1544}
1545
1546#ifndef HAVE_DRAND48
1547double drand48(void)
1548{
1549 double d;
1550 d = rand();
1551 d = d / RAND_MAX;
1552 return d;
1553}
1554#endif
1555typedef struct {
1557 char* name;
1559} clust_t;
1560
1562 .key = offsetof(clust_t, name),
1563 .size = -1,
1564 .link = offsetof(clust_t, link),
1565 .freef = free,
1566};
1567
1568static void fillMap (Agraph_t* g, Dt_t* map)
1569{
1570 for (int c = 1; c <= GD_n_cluster(g); c++) {
1571 Agraph_t *cl = GD_clust(g)[c];
1572 char *s = agnameof(cl);
1573 if (dtmatch(map, s)) {
1574 agwarningf("Two clusters named %s - the second will be ignored\n", s);
1575 } else {
1576 clust_t *ip = gv_alloc(sizeof(clust_t));
1577 ip->name = s;
1578 ip->clp = cl;
1579 dtinsert (map, ip);
1580 }
1581 fillMap (cl, map);
1582 }
1583}
1584
1590{
1591 Dt_t* map = dtopen (&strDisc, Dtoset);
1592
1593 fillMap (g, map);
1594
1595 return map;
1596}
1597
1598Agraph_t*
1599findCluster (Dt_t* map, char* name)
1600{
1601 clust_t* clp = dtmatch (map, name);
1602 if (clp)
1603 return clp->clp;
1604 return NULL;
1605}
1606
static void agxbfree(agxbuf *xb)
free any malloced resources
Definition agxbuf.h:77
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
Definition agxbuf.h:233
static WUR char * agxbuse(agxbuf *xb)
Definition agxbuf.h:306
static int agxbputc(agxbuf *xb, char c)
add character to buffer
Definition agxbuf.h:276
static char * agxbdisown(agxbuf *xb)
Definition agxbuf.h:326
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:185
#define dtinsert(d, o)
Definition cdt.h:186
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:928
void undoClusterEdges(graph_t *g)
Definition utils.c:1027
char * late_nnstring(void *obj, attrsym_t *attr, char *defaultValue)
Definition utils.c:87
char * scanEntity(char *t, agxbuf *xb)
Definition utils.c:1079
#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:794
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:970
Dt_t * mkClustMap(Agraph_t *g)
Definition utils.c:1589
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:997
void setEdgeType(graph_t *g, int defaultValue)
Definition utils.c:1420
static port chkPort(port(*pf)(node_t *, char *, char *), node_t *n, char *s)
Definition utils.c:487
char * late_string(void *obj, attrsym_t *attr, char *defaultValue)
Definition utils.c:81
void gv_free_splines(edge_t *e)
Definition utils.c:1500
boxf polyBB(polygon_t *poly)
Definition utils.c:602
int late_int(void *obj, attrsym_t *attr, int defaultValue, int minimum)
Definition utils.c:36
static Dtdisc_t mapDisc
Definition utils.c:784
void gv_cleanup_edge(edge_t *e)
Definition utils.c:1510
static void insertEdge(Dt_t *map, void *t, void *h, edge_t *e)
Definition utils.c:805
void common_init_node(node_t *n)
Definition utils.c:425
bool overlap_label(textlabel_t *lp, boxf b)
Definition utils.c:1320
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:462
bool overlap_node(node_t *n, boxf b)
Definition utils.c:1308
static int comp_entities(const void *e1, const void *e2)
Definition utils.c:1069
void common_init_edge(edge_t *e)
Definition utils.c:507
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:473
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:1333
pointf coord(node_t *n)
Definition utils.c:153
static void * newItem(void *p, Dtdisc_t *disc)
Definition utils.c:771
attrsym_t * safe_dcl(graph_t *g, int obj_kind, char *name, char *defaultValue)
Definition utils.c:1062
void UF_singleton(node_t *u)
Definition utils.c:139
static void initFontEdgeAttr(edge_t *e, struct fontinfo *fi)
Definition utils.c:454
char * utf8ToLatin1(char *s)
Definition utils.c:1290
static int cmpItem(void *pp1, void *pp2)
Definition utils.c:757
char * latin1ToUTF8(char *s)
Converts string from Latin1 encoding to utf8. Also translates HTML entities.
Definition utils.c:1257
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:1371
static boxf addLabelBB(boxf bb, textlabel_t *lp, bool flipxy)
Definition utils.c:567
void updateBB(graph_t *g, textlabel_t *lp)
Definition utils.c:622
static bool overlap_arrow(pointf p, pointf u, double scale, boxf b)
Definition utils.c:1327
static int checkCompound(edge_t *e, graph_t *clg, agxbuf *xb, Dt_t *map, Dt_t *cmap)
Definition utils.c:844
bool overlap_edge(edge_t *e, boxf b)
Definition utils.c:1355
static unsigned char cvtAndAppend(unsigned char c, agxbuf *xb)
Definition utils.c:1163
void compute_bb(graph_t *g)
Definition utils.c:631
static void fillMap(Agraph_t *g, Dt_t *map)
Definition utils.c:1568
static Dtdisc_t strDisc
Definition utils.c:1561
static node_t * clustNode(node_t *n, graph_t *cg, agxbuf *xb, graph_t *clg)
Definition utils.c:727
void gv_cleanup_node(node_t *n)
Definition utils.c:1522
bool mapBool(const char *p, bool defaultValue)
Definition utils.c:323
char * htmlEntityUTF8(char *s, graph_t *g)
Definition utils.c:1180
static int num_clust_edges(graph_t *g)
Definition utils.c:914
#define PATHSEP
Definition utils.c:234
void get_gradient_points(pointf *A, pointf *G, size_t n, double angle, int flags)
Definition utils.c:1443
void gv_nodesize(node_t *n, bool flip)
Definition utils.c:1533
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:815
static int htmlEntity(char **s)
Definition utils.c:1101
bool is_a_cluster(Agraph_t *g)
Definition utils.c:693
static graph_t * mapc(Dt_t *cmap, node_t *n)
Definition utils.c:821
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:1599
double drand48(void)
Definition utils.c:1547
Agsym_t * setAttr(graph_t *g, void *obj, char *name, char *value, Agsym_t *ap)
Definition utils.c:702
#define HEAD_LABEL
Definition const.h:177
#define NORMAL
Definition const.h:24
#define EDGETYPE_SPLINE
Definition const.h:248
#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:245
#define DEFAULT_COLOR
Definition const.h:48
#define DEFAULT_NODEWIDTH
Definition const.h:74
#define EDGETYPE_ORTHO
Definition const.h:247
#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:246
#define EDGETYPE_LINE
Definition const.h:244
#define DEFAULT_FONTNAME
Definition const.h:67
#define EDGETYPE_NONE
Definition const.h:243
#define EDGETYPE_COMPOUND
Definition const.h:249
#define DEFAULT_NODESHAPE
Definition const.h:76
#define NODE_XLABEL
Definition const.h:180
#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:209
#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 void expandbp(boxf *b, pointf p)
expand box b as needed to enclose point p
Definition geomprocs.h:45
static WUR pointf mid_pointf(pointf p, pointf q)
Definition geomprocs.h:104
static WUR pointf sub_pointf(pointf p, pointf q)
Definition geomprocs.h:96
static WUR pointf add_pointf(pointf p, pointf q)
Definition geomprocs.h:88
#define EXPANDBB(b0, b1)
Definition geomprocs.h:65
static WUR pointf scale(double c, pointf p)
Definition geomprocs.h:148
static WUR bool boxf_overlap(boxf b0, boxf b1)
Definition geomprocs.h:136
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:181
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:196
int agnnodes(Agraph_t *g)
Definition graph.c:155
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:977
#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:978
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:67
static int imin(int a, int b)
minimum of two integers
Definition gv_math.h:32
Graphviz context library.
static bool onetime
textitem scanner parser str
Definition htmlparse.y:218
textlabel_t * make_label(void *obj, char *str, bool is_html, bool is_record, double fontsize, char *fontname, char *fontcolor)
Definition labels.c:108
void free_label(textlabel_t *p)
Definition labels.c:202
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:663
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:3992
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:640
char * defval
Definition cgraph.h:643
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:909
int n_cluster_edges
Definition utils.c:910
Agraph_t * clp
Definition utils.c:1558
char * name
Definition utils.c:1557
Dtlink_t link
Definition utils.c:1556
Definition cdt.h:98
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:750
node_t * t
Definition utils.c:753
node_t * h
Definition utils.c:754
void * p[2]
Definition utils.c:752
Dtlink_t link
Definition utils.c:751
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 TAIL_ID
Definition types.h:43
@ SH_RECORD
Definition types.h:187
#define HEAD_ID
Definition types.h:44
struct inside_t::@57 s
node_t * n
Definition types.h:160
Definition grammar.c:90
#define MAX(a, b)
Definition write.c:32
int(* pf)(void *, char *,...)
Definition xdot.c:396