Graphviz  2.41.20170921.2350
utils.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 #include "render.h"
15 #include "agxbuf.h"
16 #include "htmltable.h"
17 #include "entities.h"
18 #include "logic.h"
19 #include "gvc.h"
20 
21 #ifdef _WIN32
22 #define R_OK 4
23 #endif
24 
25 #ifdef HAVE_UNISTD_H
26 # include <unistd.h>
27 #endif // HAVE_UNISTD_H
28 
29 #include <ctype.h>
30 
31 /*
32  * a queue of nodes
33  */
35 {
36  nodequeue *q = NEW(nodequeue);
37 
38  if (sz <= 1)
39  sz = 2;
40  q->head = q->tail = q->store = N_NEW(sz, node_t *);
41  q->limit = q->store + sz;
42  return q;
43 }
44 
46 {
47  free(q->store);
48  free(q);
49 }
50 
51 void enqueue(nodequeue * q, node_t * n)
52 {
53  *(q->tail++) = n;
54  if (q->tail >= q->limit)
55  q->tail = q->store;
56 }
57 
59 {
60  node_t *n;
61  if (q->head == q->tail)
62  n = NULL;
63  else {
64  n = *(q->head++);
65  if (q->head >= q->limit)
66  q->head = q->store;
67  }
68  return n;
69 }
70 
71 int late_int(void *obj, attrsym_t * attr, int def, int low)
72 {
73  char *p;
74  char *endp;
75  int rv;
76  if (attr == NULL)
77  return def;
78  p = ag_xget(obj, attr);
79  if (!p || p[0] == '\0')
80  return def;
81  rv = strtol (p, &endp, 10);
82  if (p == endp) return def; /* invalid int format */
83  if (rv < low) return low;
84  else return rv;
85 }
86 
87 double late_double(void *obj, attrsym_t * attr, double def, double low)
88 {
89  char *p;
90  char *endp;
91  double rv;
92 
93  if (!attr || !obj)
94  return def;
95  p = ag_xget(obj, attr);
96  if (!p || p[0] == '\0')
97  return def;
98  rv = strtod (p, &endp);
99  if (p == endp) return def; /* invalid double format */
100  if (rv < low) return low;
101  else return rv;
102 }
103 
104 /* get_inputscale:
105  * Return value for PSinputscale. If this is > 0, it has been set on the
106  * command line and this value is used.
107  * Otherwise, we check the graph's inputscale attribute. If this is not set
108  * or has a bad value, we return -1.
109  * If the value is 0, we return the default. Otherwise, we return the value.
110  * Set but negative values are treated like 0.
111  */
113 {
114  double d;
115 
116  if (PSinputscale > 0) return PSinputscale; /* command line flag prevails */
117  d = late_double(g, agfindgraphattr(g, "inputscale"), -1, 0);
118  if (d == 0) return POINTS_PER_INCH;
119  else return d;
120 }
121 
122 char *late_string(void *obj, attrsym_t * attr, char *def)
123 {
124  if (!attr || !obj)
125  return def;
126  return agxget(obj, attr);
127 }
128 
129 char *late_nnstring(void *obj, attrsym_t * attr, char *def)
130 {
131  char *rv = late_string(obj, attr, def);
132  if (!rv || (rv[0] == '\0'))
133  rv = def;
134  return rv;
135 }
136 
137 boolean late_bool(void *obj, attrsym_t * attr, int def)
138 {
139  if (attr == NULL)
140  return def;
141 
142  return mapbool(agxget(obj, attr));
143 }
144 
145 /* union-find */
147 {
148  while (ND_UF_parent(n) && (ND_UF_parent(n) != n)) {
149  if (ND_UF_parent(ND_UF_parent(n)))
151  n = ND_UF_parent(n);
152  }
153  return n;
154 }
155 
157 {
158  if (u == v)
159  return u;
160  if (ND_UF_parent(u) == NULL) {
161  ND_UF_parent(u) = u;
162  ND_UF_size(u) = 1;
163  } else
164  u = UF_find(u);
165  if (ND_UF_parent(v) == NULL) {
166  ND_UF_parent(v) = v;
167  ND_UF_size(v) = 1;
168  } else
169  v = UF_find(v);
170  if (ND_id(u) > ND_id(v)) {
171  ND_UF_parent(u) = v;
172  ND_UF_size(v) += ND_UF_size(u);
173  } else {
174  ND_UF_parent(v) = u;
175  ND_UF_size(u) += ND_UF_size(v);
176  v = u;
177  }
178  return v;
179 }
180 
181 void UF_remove(node_t * u, node_t * v)
182 {
183  assert(ND_UF_size(u) == 1);
184  ND_UF_parent(u) = u;
185  ND_UF_size(v) -= ND_UF_size(u);
186 }
187 
189 {
190  ND_UF_size(u) = 1;
191  ND_UF_parent(u) = NULL;
192  ND_ranktype(u) = NORMAL;
193 }
194 
195 void UF_setname(node_t * u, node_t * v)
196 {
197  assert(u == UF_find(u));
198  ND_UF_parent(u) = v;
199  ND_UF_size(v) += ND_UF_size(u);
200 }
201 
203 {
204  pointf r;
205 
206  r.x = POINTS_PER_INCH * ND_pos(n)[0];
207  r.y = POINTS_PER_INCH * ND_pos(n)[1];
208  return r;
209 }
210 
211 /* from Glassner's Graphics Gems */
212 #define W_DEGREE 5
213 
214 /*
215  * Bezier :
216  * Evaluate a Bezier curve at a particular parameter value
217  * Fill in control points for resulting sub-curves if "Left" and
218  * "Right" are non-null.
219  *
220  */
221 pointf Bezier(pointf * V, int degree, double t, pointf * Left, pointf * Right)
222 {
223  int i, j; /* Index variables */
224  pointf Vtemp[W_DEGREE + 1][W_DEGREE + 1];
225 
226  /* Copy control points */
227  for (j = 0; j <= degree; j++) {
228  Vtemp[0][j] = V[j];
229  }
230 
231  /* Triangle computation */
232  for (i = 1; i <= degree; i++) {
233  for (j = 0; j <= degree - i; j++) {
234  Vtemp[i][j].x =
235  (1.0 - t) * Vtemp[i - 1][j].x + t * Vtemp[i - 1][j + 1].x;
236  Vtemp[i][j].y =
237  (1.0 - t) * Vtemp[i - 1][j].y + t * Vtemp[i - 1][j + 1].y;
238  }
239  }
240 
241  if (Left != NULL)
242  for (j = 0; j <= degree; j++)
243  Left[j] = Vtemp[j][0];
244  if (Right != NULL)
245  for (j = 0; j <= degree; j++)
246  Right[j] = Vtemp[degree - j][j];
247 
248  return (Vtemp[degree][0]);
249 }
250 
251 #ifdef DEBUG
252 edge_t *debug_getedge(graph_t * g, char *s0, char *s1)
253 {
254  node_t *n0, *n1;
255  n0 = agfindnode(g, s0);
256  n1 = agfindnode(g, s1);
257  if (n0 && n1)
258  return agfindedge(g, n0, n1);
259  else
260  return NULL;
261 }
262 Agraphinfo_t* GD_info(graph_t * g) { return ((Agraphinfo_t*)AGDATA(g));}
263 Agnodeinfo_t* ND_info(node_t * n) { return ((Agnodeinfo_t*)AGDATA(n));}
264 #endif
265 
266 #if !defined(_WIN32)
267 #include <pwd.h>
268 
269 #if 0
270 static void cleanup(void)
271 {
272  agxbfree(&xb);
273 }
274 #endif
275 #endif
276 
277 /* Fgets:
278  * Read a complete line.
279  * Return pointer to line,
280  * or 0 on EOF
281  */
282 char *Fgets(FILE * fp)
283 {
284  static int bsize = 0;
285  static char *buf;
286  char *lp;
287  int len;
288 
289  len = 0;
290  do {
291  if (bsize - len < BUFSIZ) {
292  bsize += BUFSIZ;
293  buf = grealloc(buf, bsize);
294  }
295  lp = fgets(buf + len, bsize - len, fp);
296  if (lp == 0)
297  break;
298  len += strlen(lp); /* since lp != NULL, len > 0 */
299  } while (buf[len - 1] != '\n');
300 
301  if (len > 0)
302  return buf;
303  else
304  return 0;
305 }
306 
307 /* safefile:
308  * Check to make sure it is okay to read in files.
309  * It returns NULL if the filename is trivial.
310  *
311  * If the application has set the SERVER_NAME environment variable,
312  * this indicates it is web-active. In this case, it requires that the GV_FILE_PATH
313  * environment variable be set. This gives the legal directories
314  * from which files may be read. safefile then derives the rightmost component
315  * of filename, where components are separated by a slash, backslash or colon,
316  * It then checks for the existence of a file consisting of a directory from
317  * GV_FILE_PATH followed by the rightmost component of filename. It returns the
318  * first such found, or NULL otherwise.
319  * The filename returned is thus
320  * Gvfilepath concatenated with the last component of filename,
321  * where a component is determined by a slash, backslash or colon
322  * character.
323  *
324  * If filename contains multiple components, the user is
325  * warned, once, that everything to the left is ignored.
326  *
327  * For non-server applications, we use the path list in Gvimagepath to
328  * resolve relative pathnames.
329  *
330  * N.B. safefile uses a fixed buffer, so functions using it should use the
331  * value immediately or make a copy.
332  */
333 #ifdef _WIN32
334 #define PATHSEP ";"
335 #else
336 #define PATHSEP ":"
337 #endif
338 
339 static char** mkDirlist (const char* list, int* maxdirlen)
340 {
341  int cnt = 0;
342  char* s = strdup (list);
343  char* dir;
344  char** dirs = NULL;
345  int maxlen = 0;
346 
347  for (dir = strtok (s, PATHSEP); dir; dir = strtok (NULL, PATHSEP)) {
348  dirs = ALLOC (cnt+2,dirs,char*);
349  dirs[cnt++] = dir;
350  maxlen = MAX(maxlen, strlen (dir));
351  }
352  dirs[cnt] = NULL;
353  *maxdirlen = maxlen;
354  return dirs;
355 }
356 
357 static char* findPath (char** dirs, int maxdirlen, const char* str)
358 {
359  static char *safefilename = NULL;
360  char** dp;
361 
362  /* allocate a buffer that we are sure is big enough
363  * +1 for null character.
364  * +1 for directory separator character.
365  */
366  safefilename = realloc(safefilename, (maxdirlen + strlen(str) + 2));
367 
368  for (dp = dirs; *dp; dp++) {
369  sprintf (safefilename, "%s%s%s", *dp, DIRSEP, str);
370  if (access (safefilename, R_OK) == 0)
371  return safefilename;
372  }
373  return NULL;
374 }
375 
376 const char *safefile(const char *filename)
377 {
378  static boolean onetime = TRUE;
379  static char *pathlist = NULL;
380  static int maxdirlen;
381  static char** dirs;
382  const char *str, *p;
383 
384  if (!filename || !filename[0])
385  return NULL;
386 
387  if (HTTPServerEnVar) { /* If used as a server */
388  /*
389  * If we are running in an http server we allow
390  * files only from the directory specified in
391  * the GV_FILE_PATH environment variable.
392  */
393  if (!Gvfilepath || (*Gvfilepath == '\0')) {
394  if (onetime) {
395  agerr(AGWARN,
396  "file loading is disabled because the environment contains SERVER_NAME=\"%s\"\n"
397  "and the GV_FILE_PATH variable is unset or empty.\n",
399  onetime = FALSE;
400  }
401  return NULL;
402  }
403  if (!pathlist) {
404  dirs = mkDirlist (Gvfilepath, &maxdirlen);
405  pathlist = Gvfilepath;
406  }
407 
408  str = filename;
409  if ((p = strrchr(str, '/')))
410  str = ++p;
411  if ((p = strrchr(str, '\\')))
412  str = ++p;
413  if ((p = strrchr(str, ':')))
414  str = ++p;
415 
416  if (onetime && str != filename) {
417  agerr(AGWARN, "Path provided to file: \"%s\" has been ignored"
418  " because files are only permitted to be loaded from the directories in \"%s\""
419  " when running in an http server.\n", filename, Gvfilepath);
420  onetime = FALSE;
421  }
422 
423  return findPath (dirs, maxdirlen, str);
424  }
425 
426  if (pathlist != Gvimagepath) {
427  if (dirs) {
428  free (dirs[0]);
429  free (dirs);
430  dirs = NULL;
431  }
432  pathlist = Gvimagepath;
433  if (pathlist && *pathlist)
434  dirs = mkDirlist (pathlist, &maxdirlen);
435  }
436 
437  if ((*filename == DIRSEP[0]) || !dirs)
438  return filename;
439 
440  return findPath (dirs, maxdirlen, filename);
441 }
442 
443 int maptoken(char *p, char **name, int *val)
444 {
445  int i;
446  char *q;
447 
448  for (i = 0; (q = name[i]) != 0; i++)
449  if (p && streq(p, q))
450  break;
451  return val[i];
452 }
453 
454 boolean mapBool(char *p, boolean dflt)
455 {
456  if (!p || (*p == '\0'))
457  return dflt;
458  if (!strcasecmp(p, "false"))
459  return FALSE;
460  if (!strcasecmp(p, "no"))
461  return FALSE;
462  if (!strcasecmp(p, "true"))
463  return TRUE;
464  if (!strcasecmp(p, "yes"))
465  return TRUE;
466  if (isdigit(*p))
467  return atoi(p);
468  else
469  return dflt;
470 }
471 
472 boolean mapbool(char *p)
473 {
474  return mapBool (p, FALSE);
475 }
476 
478 {
479  int i, j, k, besti, bestj;
480  double bestdist2, d2, dlow2, dhigh2; /* squares of distances */
481  double low, high, t;
482  pointf c[4], pt2;
483  bezier bz;
484 
485  besti = bestj = -1;
486  bestdist2 = 1e+38;
487  for (i = 0; i < spl->size; i++) {
488  bz = spl->list[i];
489  for (j = 0; j < bz.size; j++) {
490  pointf b;
491 
492  b.x = bz.list[j].x;
493  b.y = bz.list[j].y;
494  d2 = DIST2(b, pt);
495  if ((bestj == -1) || (d2 < bestdist2)) {
496  besti = i;
497  bestj = j;
498  bestdist2 = d2;
499  }
500  }
501  }
502 
503  bz = spl->list[besti];
504  /* Pick best Bezier. If bestj is the last point in the B-spline, decrement.
505  * Then set j to be the first point in the corresponding Bezier by dividing
506  * then multiplying be 3. Thus, 0,1,2 => 0; 3,4,5 => 3, etc.
507  */
508  if (bestj == bz.size-1)
509  bestj--;
510  j = 3*(bestj / 3);
511  for (k = 0; k < 4; k++) {
512  c[k].x = bz.list[j + k].x;
513  c[k].y = bz.list[j + k].y;
514  }
515  low = 0.0;
516  high = 1.0;
517  dlow2 = DIST2(c[0], pt);
518  dhigh2 = DIST2(c[3], pt);
519  do {
520  t = (low + high) / 2.0;
521  pt2 = Bezier(c, 3, t, NULL, NULL);
522  if (fabs(dlow2 - dhigh2) < 1.0)
523  break;
524  if (fabs(high - low) < .00001)
525  break;
526  if (dlow2 < dhigh2) {
527  high = t;
528  dhigh2 = DIST2(pt2, pt);
529  } else {
530  low = t;
531  dlow2 = DIST2(pt2, pt);
532  }
533  } while (1);
534  return pt2;
535 }
536 
537 pointf spline_at_y(splines * spl, double y)
538 {
539  int i, j;
540  double low, high, d, t;
541  pointf c[4], p;
542  static bezier bz;
543 
544 /* this caching seems to prevent p.x from getting set from bz.list[0].x
545  - optimizer problem ? */
546 
547 #if 0
548  static splines *mem = NULL;
549 
550  if (mem != spl) {
551  mem = spl;
552 #endif
553  for (i = 0; i < spl->size; i++) {
554  bz = spl->list[i];
555  if (BETWEEN(bz.list[bz.size - 1].y, y, bz.list[0].y))
556  break;
557  }
558 #if 0
559  }
560 #endif
561  if (y > bz.list[0].y)
562  p = bz.list[0];
563  else if (y < bz.list[bz.size - 1].y)
564  p = bz.list[bz.size - 1];
565  else {
566  for (i = 0; i < bz.size; i += 3) {
567  for (j = 0; j < 3; j++) {
568  if ((bz.list[i + j].y <= y) && (y <= bz.list[i + j + 1].y))
569  break;
570  if ((bz.list[i + j].y >= y) && (y >= bz.list[i + j + 1].y))
571  break;
572  }
573  if (j < 3)
574  break;
575  }
576  assert(i < bz.size);
577  for (j = 0; j < 4; j++) {
578  c[j].x = bz.list[i + j].x;
579  c[j].y = bz.list[i + j].y;
580  /* make the spline be monotonic in Y, awful but it works for now */
581  if ((j > 0) && (c[j].y > c[j - 1].y))
582  c[j].y = c[j - 1].y;
583  }
584  low = 0.0;
585  high = 1.0;
586  do {
587  t = (low + high) / 2.0;
588  p = Bezier(c, 3, t, NULL, NULL);
589  d = p.y - y;
590  if (ABS(d) <= 1)
591  break;
592  if (d < 0)
593  high = t;
594  else
595  low = t;
596  } while (1);
597  }
598  p.y = y;
599  return p;
600 }
601 
603 {
604 /* this is a stub so that we can share a common emit.c between dot and neato */
605 
606  return spline_at_y(spl, p.y);
607 }
608 
609 static int Tflag;
610 void gvToggle(int s)
611 {
612  Tflag = !Tflag;
613 #if !defined(_WIN32)
614  signal(SIGUSR1, gvToggle);
615 #endif
616 }
617 
619 {
620  return Tflag;
621 }
622 
623 struct fontinfo {
624  double fontsize;
625  char *fontname;
626  char *fontcolor;
627 };
628 
630 {
631  struct fontinfo fi;
632  char *str;
633  ND_width(n) =
635  ND_height(n) =
637  ND_shape(n) =
639  str = agxget(n, N_label);
643  ND_label(n) = make_label((void*)n, str,
644  ((aghtmlstr(str) ? LT_HTML : LT_NONE) | ( (shapeOf(n) == SH_RECORD) ? LT_RECD : LT_NONE)),
645  fi.fontsize, fi.fontname, fi.fontcolor);
646  if (N_xlabel && (str = agxget(n, N_xlabel)) && (str[0])) {
647  ND_xlabel(n) = make_label((void*)n, str, (aghtmlstr(str) ? LT_HTML : LT_NONE),
648  fi.fontsize, fi.fontname, fi.fontcolor);
650  }
651 
652  ND_showboxes(n) = late_int(n, N_showboxes, 0, 0);
653  ND_shape(n)->fns->initfn(n);
654 }
655 
656 static void initFontEdgeAttr(edge_t * e, struct fontinfo *fi)
657 {
661 }
662 
663 static void
664 initFontLabelEdgeAttr(edge_t * e, struct fontinfo *fi,
665  struct fontinfo *lfi)
666 {
667  if (!fi->fontname) initFontEdgeAttr(e, fi);
671 }
672 
673 /* noClip:
674  * Return true if head/tail end of edge should not be clipped
675  * to node.
676  */
677 static boolean
678 noClip(edge_t *e, attrsym_t* sym)
679 {
680  char *str;
681  boolean rv = FALSE;
682 
683  if (sym) { /* mapbool isn't a good fit, because we want "" to mean true */
684  str = agxget(e,sym);
685  if (str && str[0]) rv = !mapbool(str);
686  else rv = FALSE;
687  }
688  return rv;
689 }
690 
691 /*chkPort:
692  */
693 static port
694 chkPort (port (*pf)(node_t*, char*, char*), node_t* n, char* s)
695 {
696  port pt;
697  char* cp=NULL;
698  if(s)
699  cp= strchr(s,':');
700  if (cp) {
701  *cp = '\0';
702  pt = pf(n, s, cp+1);
703  *cp = ':';
704  pt.name = cp+1;
705  }
706  else {
707  pt = pf(n, s, NULL);
708  pt.name = s;
709  }
710  return pt;
711 }
712 
713 /* return true if edge has label */
715 {
716  char *str;
717  int r = 0;
718  struct fontinfo fi;
719  struct fontinfo lfi;
720  graph_t *sg = agraphof(agtail(e));
721 
722  fi.fontname = NULL;
723  lfi.fontname = NULL;
724  if (E_label && (str = agxget(e, E_label)) && (str[0])) {
725  r = 1;
726  initFontEdgeAttr(e, &fi);
727  ED_label(e) = make_label((void*)e, str, (aghtmlstr(str) ? LT_HTML : LT_NONE),
728  fi.fontsize, fi.fontname, fi.fontcolor);
729  GD_has_labels(sg) |= EDGE_LABEL;
730  ED_label_ontop(e) =
731  mapbool(late_string(e, E_label_float, "false"));
732  }
733 
734  if (E_xlabel && (str = agxget(e, E_xlabel)) && (str[0])) {
735  if (!fi.fontname)
736  initFontEdgeAttr(e, &fi);
737  ED_xlabel(e) = make_label((void*)e, str, (aghtmlstr(str) ? LT_HTML : LT_NONE),
738  fi.fontsize, fi.fontname, fi.fontcolor);
739  GD_has_labels(sg) |= EDGE_XLABEL;
740  }
741 
742 
743  /* vladimir */
744  if (E_headlabel && (str = agxget(e, E_headlabel)) && (str[0])) {
745  initFontLabelEdgeAttr(e, &fi, &lfi);
746  ED_head_label(e) = make_label((void*)e, str, (aghtmlstr(str) ? LT_HTML : LT_NONE),
747  lfi.fontsize, lfi.fontname, lfi.fontcolor);
748  GD_has_labels(sg) |= HEAD_LABEL;
749  }
750  if (E_taillabel && (str = agxget(e, E_taillabel)) && (str[0])) {
751  if (!lfi.fontname)
752  initFontLabelEdgeAttr(e, &fi, &lfi);
753  ED_tail_label(e) = make_label((void*)e, str, (aghtmlstr(str) ? LT_HTML : LT_NONE),
754  lfi.fontsize, lfi.fontname, lfi.fontcolor);
755  GD_has_labels(sg) |= TAIL_LABEL;
756  }
757  /* end vladimir */
758 
759  /* We still accept ports beginning with colons but this is deprecated
760  * That is, we allow tailport = ":abc" as well as the preferred
761  * tailport = "abc".
762  */
763  str = agget(e, TAIL_ID);
764  /* libgraph always defines tailport/headport; libcgraph doesn't */
765  if (!str) str = "";
766  if (str && str[0])
767  ND_has_port(agtail(e)) = TRUE;
768  ED_tail_port(e) = chkPort (ND_shape(agtail(e))->fns->portfn, agtail(e), str);
769  if (noClip(e, E_tailclip))
770  ED_tail_port(e).clip = FALSE;
771  str = agget(e, HEAD_ID);
772  /* libgraph always defines tailport/headport; libcgraph doesn't */
773  if (!str) str = "";
774  if (str && str[0])
775  ND_has_port(aghead(e)) = TRUE;
776  ED_head_port(e) = chkPort(ND_shape(aghead(e))->fns->portfn, aghead(e), str);
777  if (noClip(e, E_headclip))
778  ED_head_port(e).clip = FALSE;
779 
780  return r;
781 }
782 
783 /* addLabelBB:
784  */
785 static boxf addLabelBB(boxf bb, textlabel_t * lp, boolean flipxy)
786 {
787  double width, height;
788  pointf p = lp->pos;
789  double min, max;
790 
791  if (flipxy) {
792  height = lp->dimen.x;
793  width = lp->dimen.y;
794  }
795  else {
796  width = lp->dimen.x;
797  height = lp->dimen.y;
798  }
799  min = p.x - width / 2.;
800  max = p.x + width / 2.;
801  if (min < bb.LL.x)
802  bb.LL.x = min;
803  if (max > bb.UR.x)
804  bb.UR.x = max;
805 
806  min = p.y - height / 2.;
807  max = p.y + height / 2.;
808  if (min < bb.LL.y)
809  bb.LL.y = min;
810  if (max > bb.UR.y)
811  bb.UR.y = max;
812 
813  return bb;
814 }
815 
816 /* polyBB:
817  * Compute the bounding box of a polygon.
818  * We only need to use the outer periphery.
819  */
820 boxf
822 {
823  int i, sides = poly->sides;
824  int peris = MAX(poly->peripheries,1);
825  pointf* verts = poly->vertices + (peris-1)*sides;
826  boxf bb;
827 
828  bb.LL = bb.UR = verts[0];
829  for (i = 1; i < sides; i++) {
830  bb.LL.x = MIN(bb.LL.x,verts[i].x);
831  bb.LL.y = MIN(bb.LL.y,verts[i].y);
832  bb.UR.x = MAX(bb.UR.x,verts[i].x);
833  bb.UR.y = MAX(bb.UR.y,verts[i].y);
834  }
835  return bb;
836 }
837 
838 /* updateBB:
839  * Reset graph's bounding box to include bounding box of the given label.
840  * Assume the label's position has been set.
841  */
842 void updateBB(graph_t * g, textlabel_t * lp)
843 {
844  GD_bb(g) = addLabelBB(GD_bb(g), lp, GD_flip(g));
845 }
846 
847 /* compute_bb:
848  * Compute bounding box of g using nodes, splines, and clusters.
849  * Assumes bb of clusters already computed.
850  * store in GD_bb.
851  */
853 {
854  node_t *n;
855  edge_t *e;
856  boxf b, bb;
857  boxf BF;
858  pointf ptf, s2;
859  int i, j;
860 
861  if ((agnnodes(g) == 0) && (GD_n_cluster(g) ==0)) {
862  bb.LL = pointfof(0, 0);
863  bb.UR = pointfof(0, 0);
864  return;
865  }
866 
867  bb.LL = pointfof(INT_MAX, INT_MAX);
868  bb.UR = pointfof(-INT_MAX, -INT_MAX);
869  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
870  ptf = coord(n);
871  s2.x = ND_xsize(n) / 2.0;
872  s2.y = ND_ysize(n) / 2.0;
873  b.LL = sub_pointf(ptf, s2);
874  b.UR = add_pointf(ptf, s2);
875 
876  EXPANDBB(bb,b);
877  if (ND_xlabel(n) && ND_xlabel(n)->set) {
878  bb = addLabelBB(bb, ND_xlabel(n), GD_flip(g));
879  }
880  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
881  if (ED_spl(e) == 0)
882  continue;
883  for (i = 0; i < ED_spl(e)->size; i++) {
884  for (j = 0; j < (((Agedgeinfo_t*)AGDATA(e))->spl)->list[i].size; j++) {
885  ptf = ED_spl(e)->list[i].list[j];
886  EXPANDBP(bb,ptf);
887  }
888  }
889  if (ED_label(e) && ED_label(e)->set) {
890  bb = addLabelBB(bb, ED_label(e), GD_flip(g));
891  }
892  if (ED_head_label(e) && ED_head_label(e)->set) {
893  bb = addLabelBB(bb, ED_head_label(e), GD_flip(g));
894  }
895  if (ED_tail_label(e) && ED_tail_label(e)->set) {
896  bb = addLabelBB(bb, ED_tail_label(e), GD_flip(g));
897  }
898  if (ED_xlabel(e) && ED_xlabel(e)->set) {
899  bb = addLabelBB(bb, ED_xlabel(e), GD_flip(g));
900  }
901  }
902  }
903 
904  for (i = 1; i <= GD_n_cluster(g); i++) {
905  B2BF(GD_bb(GD_clust(g)[i]), BF);
906  EXPANDBB(bb,BF);
907  }
908  if (GD_label(g) && GD_label(g)->set) {
909  bb = addLabelBB(bb, GD_label(g), GD_flip(g));
910  }
911 
912  GD_bb(g) = bb;
913 }
914 
916 {
917  return ((g == g->root) || (!strncasecmp(agnameof(g), "cluster", 7)));
918 }
919 
920 /* setAttr:
921  * Sets object's name attribute to the given value.
922  * Creates the attribute if not already set.
923  */
924 Agsym_t *setAttr(graph_t * g, void *obj, char *name, char *value,
925  Agsym_t * ap)
926 {
927  if (ap == NULL) {
928  switch (agobjkind(obj)) {
929  case AGRAPH:
930  ap = agattr(g, AGRAPH,name, "");
931  break;
932  case AGNODE:
933  ap = agattr(g,AGNODE, name, "");
934  break;
935  case AGEDGE:
936  ap = agattr(g,AGEDGE, name, "");
937  break;
938  }
939  }
940  agxset(obj, ap, value);
941  return ap;
942 }
943 
944 /* clustNode:
945  * Generate a special cluster node representing the end node
946  * of an edge to the cluster cg. n is a node whose name is the same
947  * as the cluster cg. clg is the subgraph of all of
948  * the original nodes, which will be deleted later.
949  */
950 static node_t *clustNode(node_t * n, graph_t * cg, agxbuf * xb,
951  graph_t * clg)
952 {
953  node_t *cn;
954  static int idx = 0;
955  char num[100];
956 
957  agxbput(xb, "__");
958  sprintf(num, "%d", idx++);
959  agxbput(xb, num);
960  agxbputc(xb, ':');
961  agxbput(xb, agnameof(cg));
962 
963  cn = agnode(agroot(cg), agxbuse(xb), 1);
964  agbindrec(cn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE);
965 
966  SET_CLUST_NODE(cn);
967  agsubnode(cg,cn,1);
968  //aginsert(cg, cn);
969  agsubnode(clg,n,1);
970  //aginsert(clg, n);
971 
972  /* set attributes */
973  N_label = setAttr(agraphof(cn), cn, "label", "", N_label);
974  N_style = setAttr(agraphof(cn), cn, "style", "invis", N_style);
975  N_shape = setAttr(agraphof(cn), cn, "shape", "box", N_shape);
976  /* N_width = setAttr (cn->graph, cn, "width", "0.0001", N_width); */
977 
978  return cn;
979 }
980 
981 typedef struct {
982  Dtlink_t link; /* cdt data */
983  void *p[2]; /* key */
986 } item;
987 
988 static int cmpItem(Dt_t * d, void *p1[], void *p2[], Dtdisc_t * disc)
989 {
990  NOTUSED(d);
991  NOTUSED(disc);
992 
993  if (p1[0] < p2[0])
994  return -1;
995  else if (p1[0] > p2[0])
996  return 1;
997  else if (p1[1] < p2[1])
998  return -1;
999  else if (p1[1] > p2[1])
1000  return 1;
1001  else
1002  return 0;
1003 }
1004 
1005 /* newItem:
1006  */
1007 static void *newItem(Dt_t * d, item * objp, Dtdisc_t * disc)
1008 {
1009  item *newp = NEW(item);
1010 
1011  NOTUSED(disc);
1012  newp->p[0] = objp->p[0];
1013  newp->p[1] = objp->p[1];
1014  newp->t = objp->t;
1015  newp->h = objp->h;
1016 
1017  return newp;
1018 }
1019 
1020 /* freeItem:
1021  */
1022 static void freeItem(Dt_t * d, item * obj, Dtdisc_t * disc)
1023 {
1024  free(obj);
1025 }
1026 
1027 static Dtdisc_t mapDisc = {
1028  offsetof(item, p),
1029  sizeof(2 * sizeof(void *)),
1030  offsetof(item, link),
1031  (Dtmake_f) newItem,
1032  (Dtfree_f) freeItem,
1033  (Dtcompar_f) cmpItem,
1034  NIL(Dthash_f),
1035  NIL(Dtmemory_f),
1036  NIL(Dtevent_f)
1037 };
1038 
1039 /* cloneEdge:
1040  * Make a copy of e in e's graph but using ct and ch as nodes
1041  */
1042 static edge_t *cloneEdge(edge_t * e, node_t * ct, node_t * ch)
1043 {
1044  graph_t *g = agraphof(ct);
1045  edge_t *ce = agedge(g, ct, ch,NULL,1);
1046  agbindrec(ce, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE);
1047  agcopyattr(e, ce);
1048  ED_compound(ce) = TRUE;
1049 
1050  return ce;
1051 }
1052 
1053 /* insertEdge:
1054  */
1055 static void insertEdge(Dt_t * map, void *t, void *h, edge_t * e)
1056 {
1057  item dummy;
1058 
1059  dummy.p[0] = t;
1060  dummy.p[1] = h;
1061  dummy.t = agtail(e);
1062  dummy.h = aghead(e);
1063  dtinsert(map, &dummy);
1064 
1065  dummy.p[0] = h;
1066  dummy.p[1] = t;
1067  dummy.t = aghead(e);
1068  dummy.h = agtail(e);
1069  dtinsert(map, &dummy);
1070 }
1071 
1072 /* mapEdge:
1073  * Check if we already have cluster edge corresponding to t->h,
1074  * and return it.
1075  */
1076 static item *mapEdge(Dt_t * map, edge_t * e)
1077 {
1078  void *key[2];
1079 
1080  key[0] = agtail(e);
1081  key[1] = aghead(e);
1082  return (item *) dtmatch(map, &key);
1083 }
1084 
1085 /* checkCompound:
1086  * If endpoint names a cluster, mark for temporary deletion and create
1087  * special node and insert into cluster. Then clone the edge. Real edge
1088  * will be deleted when we delete the original node.
1089  * Invariant: new edge has same sense as old. That is, given t->h with
1090  * t and h mapped to ct and ch, the new edge is ct->ch.
1091  *
1092  * In the current model, we create a cluster node for each cluster edge
1093  * between the cluster and some other node or cluster, treating the
1094  * cluster node as a port on the cluster. This should help with better
1095  * routing to avoid edge crossings. At present, this is not implemented,
1096  * so we could use a simpler model in which we create a single cluster
1097  * node for each cluster used in a cluster edge.
1098  *
1099  * Return 1 if cluster edge is created.
1100  */
1101 #define MAPC(n) (strncmp(agnameof(n),"cluster",7)?NULL:findCluster(cmap,agnameof(n)))
1102 
1103 static int
1104 checkCompound(edge_t * e, graph_t * clg, agxbuf * xb, Dt_t * map, Dt_t* cmap)
1105 {
1106  graph_t *tg;
1107  graph_t *hg;
1108  node_t *cn;
1109  node_t *cn1;
1110  node_t *t = agtail(e);
1111  node_t *h = aghead(e);
1112  edge_t *ce;
1113  item *ip;
1114 
1115  if (IS_CLUST_NODE(h)) return 0;
1116  tg = MAPC(t);
1117  hg = MAPC(h);
1118  if (!tg && !hg)
1119  return 0;
1120  if (tg == hg) {
1121  agerr(AGWARN, "cluster cycle %s -- %s not supported\n", agnameof(t),
1122  agnameof(t));
1123  return 0;
1124  }
1125  ip = mapEdge(map, e);
1126  if (ip) {
1127  cloneEdge(e, ip->t, ip->h);
1128  return 1;
1129  }
1130 
1131  if (hg) {
1132  if (tg) {
1133  if (agcontains(hg, tg)) {
1134  agerr(AGWARN, "tail cluster %s inside head cluster %s\n",
1135  agnameof(tg), agnameof(hg));
1136  return 0;
1137  }
1138  if (agcontains(tg, hg)) {
1139  agerr(AGWARN, "head cluster %s inside tail cluster %s\n",
1140  agnameof(hg),agnameof(tg));
1141  return 0;
1142  }
1143  cn = clustNode(t, tg, xb, clg);
1144  cn1 = clustNode(h, hg, xb, clg);
1145  ce = cloneEdge(e, cn, cn1);
1146  insertEdge(map, t, h, ce);
1147  } else {
1148  if (agcontains(hg, t)) {
1149  agerr(AGWARN, "tail node %s inside head cluster %s\n",
1150  agnameof(t), agnameof(hg));
1151  return 0;
1152  }
1153  cn = clustNode(h, hg, xb, clg);
1154  ce = cloneEdge(e, t, cn);
1155  insertEdge(map, t, h, ce);
1156  }
1157  } else {
1158  if (agcontains(tg, h)) {
1159  agerr(AGWARN, "head node %s inside tail cluster %s\n", agnameof(h),
1160  agnameof(tg));
1161  return 0;
1162  }
1163  cn = clustNode(t, tg, xb, clg);
1164  ce = cloneEdge(e, cn, h);
1165  insertEdge(map, t, h, ce);
1166  }
1167  return 1;
1168 }
1169 
1170 typedef struct {
1173 } cl_edge_t;
1174 
1175 static int
1176 num_clust_edges(graph_t * g)
1177 {
1178  cl_edge_t* cl_info = (cl_edge_t*)HAS_CLUST_EDGE(g);
1179  if (cl_info)
1180  return cl_info->n_cluster_edges;
1181  else
1182  return 0;
1183 }
1184 
1185 /* processClusterEdges:
1186  * Look for cluster edges. Replace cluster edge endpoints
1187  * corresponding to a cluster with special cluster nodes.
1188  * Delete original nodes.
1189  * If cluster edges are found, a cl_edge_t record will be
1190  * attached to the graph, containing the count of such edges.
1191  */
1193 {
1194  int num_cl_edges = 0;
1195  node_t *n;
1196  node_t *nxt;
1197  edge_t *e;
1198  graph_t *clg;
1199  agxbuf xb;
1200  Dt_t *map;
1201  Dt_t *cmap = mkClustMap (g);
1202  unsigned char buf[SMALLBUF];
1203 
1204  map = dtopen(&mapDisc, Dtoset);
1205  clg = agsubg(g, "__clusternodes",1);
1206  agbindrec(clg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
1207  agxbinit(&xb, SMALLBUF, buf);
1208  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1209  if (IS_CLUST_NODE(n)) continue;
1210  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1211  num_cl_edges += checkCompound(e, clg, &xb, map, cmap);
1212  }
1213  }
1214  agxbfree(&xb);
1215  dtclose(map);
1216  for (n = agfstnode(clg); n; n = nxt) {
1217  nxt = agnxtnode(clg, n);
1218  agdelete(g, n);
1219  }
1220  agclose(clg);
1221  if (num_cl_edges) {
1222  cl_edge_t* cl_info;
1223  cl_info = agbindrec(g, CL_EDGE_TAG, sizeof(cl_edge_t), FALSE);
1224  cl_info->n_cluster_edges = num_cl_edges;
1225  }
1226  dtclose(cmap);
1227 }
1228 
1229 /* mapN:
1230  * Convert cluster nodes back to ordinary nodes
1231  * If n is already ordinary, return it.
1232  * Otherwise, we know node's name is "__i:xxx"
1233  * where i is some number and xxx is the nodes's original name.
1234  * Create new node of name xxx if it doesn't exist and add n to clg
1235  * for later deletion.
1236  */
1237 static node_t *mapN(node_t * n, graph_t * clg)
1238 {
1239  node_t *nn;
1240  char *name;
1241  graph_t *g = agraphof(n);
1242  Agsym_t *sym;
1243 
1244  if (!(IS_CLUST_NODE(n)))
1245  return n;
1246  agsubnode(clg, n, 1);
1247  name = strchr(agnameof(n), ':');
1248  assert(name);
1249  name++;
1250  if ((nn = agfindnode(g, name)))
1251  return nn;
1252  nn = agnode(g, name, 1);
1253  agbindrec(nn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE);
1254  SET_CLUST_NODE(nn);
1255 
1256  /* Set all attributes to default */
1257  for (sym = agnxtattr(g, AGNODE, NULL); sym; (sym = agnxtattr(g, AGNODE, sym))) {
1258  if (agxget(nn, sym) != sym->defval)
1259  agxset(nn, sym, sym->defval);
1260  }
1261  return nn;
1262 }
1263 
1264 static void undoCompound(edge_t * e, graph_t * clg)
1265 {
1266  node_t *t = agtail(e);
1267  node_t *h = aghead(e);
1268  node_t *ntail;
1269  node_t *nhead;
1270  edge_t* ce;
1271 
1272  ntail = mapN(t, clg);
1273  nhead = mapN(h, clg);
1274  ce = cloneEdge(e, ntail, nhead);
1275 
1276  /* transfer drawing information */
1277  ED_spl(ce) = ED_spl(e);
1278  ED_spl(e) = NULL;
1279  ED_label(ce) = ED_label(e);
1280  ED_label(e) = NULL;
1281  ED_xlabel(ce) = ED_xlabel(e);
1282  ED_xlabel(e) = NULL;
1283  ED_head_label(ce) = ED_head_label(e);
1284  ED_head_label(e) = NULL;
1285  ED_tail_label(ce) = ED_tail_label(e);
1286  ED_tail_label(e) = NULL;
1287  gv_cleanup_edge(e);
1288 }
1289 
1290 /* undoClusterEdges:
1291  * Replace cluster nodes with originals. Make sure original has
1292  * no attributes. Replace original edges. Delete cluster nodes,
1293  * which will also delete cluster edges.
1294  */
1296 {
1297  node_t *n;
1298  node_t *nextn;
1299  edge_t *e;
1300  graph_t *clg;
1301  edge_t **elist;
1302  int ecnt = num_clust_edges(g);
1303  int i = 0;
1304 
1305  if (!ecnt) return;
1306  clg = agsubg(g, "__clusternodes",1);
1307  agbindrec(clg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
1308  elist = N_NEW(ecnt, edge_t*);
1309  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1310  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1311  if (ED_compound(e))
1312  elist[i++] = e;
1313  }
1314  }
1315  assert(i == ecnt);
1316  for (i = 0; i < ecnt; i++)
1317  undoCompound(elist[i], clg);
1318  free (elist);
1319  for (n = agfstnode(clg); n; n = nextn) {
1320  nextn = agnxtnode(clg, n);
1321  gv_cleanup_node(n);
1322  agdelete(g, n);
1323  }
1324  agclose(clg);
1325 }
1326 
1327 /* safe_dcl:
1328  * Find the attribute belonging to graph g for objects like obj
1329  * with given name. If one does not exist, create it with the
1330  * default value def.
1331  */
1332 attrsym_t*
1333 safe_dcl(graph_t * g, int obj_kind, char *name, char *def)
1334 {
1335  attrsym_t *a = agattr(g,obj_kind,name, NULL);
1336  if (!a) /* attribute does not exist */
1337  a = agattr(g,obj_kind,name,def);
1338  return a;
1339 }
1340 
1341 static int comp_entities(const void *e1, const void *e2) {
1342  return strcmp(((struct entities_s *)e1)->name, ((struct entities_s *)e2)->name);
1343 }
1344 
1345 #define MAXENTLEN 8
1346 
1347 /* scanEntity:
1348  * Scan non-numeric entity, convert to &#...; form and store in xbuf.
1349  * t points to first char after '&'. Return after final semicolon.
1350  * If unknown, we return t and let libexpat flag the error.
1351  * */
1352 char* scanEntity (char* t, agxbuf* xb)
1353 {
1354  char* endp = strchr (t, ';');
1355  struct entities_s key, *res;
1356  int len;
1357  char buf[MAXENTLEN+1];
1358 
1359  agxbputc(xb, '&');
1360  if (!endp) return t;
1361  if (((len = endp-t) > MAXENTLEN) || (len < 2)) return t;
1362  strncpy (buf, t, len);
1363  buf[len] = '\0';
1364  key.name = buf;
1365  res = bsearch(&key, entities, NR_OF_ENTITIES,
1366  sizeof(entities[0]), comp_entities);
1367  if (!res) return t;
1368  sprintf (buf, "%d", res->value);
1369  agxbputc(xb, '#');
1370  agxbput(xb, buf);
1371  agxbputc(xb, ';');
1372  return (endp+1);
1373 }
1374 
1375 
1376 /* htmlEntity:
1377  * Check for an HTML entity for a special character.
1378  * Assume *s points to first byte after '&'.
1379  * If successful, return the corresponding value and update s to
1380  * point after the terminating ';'.
1381  * On failure, return 0 and leave s unchanged.
1382  */
1383 static int
1384 htmlEntity (char** s)
1385 {
1386  char *p;
1387  struct entities_s key, *res;
1388  char entity_name_buf[ENTITY_NAME_LENGTH_MAX+1];
1389  unsigned char* str = *(unsigned char**)s;
1390  unsigned int byte;
1391  int i, n = 0;
1392 
1393  byte = *str;
1394  if (byte == '#') {
1395  byte = *(str + 1);
1396  if (byte == 'x' || byte == 'X') {
1397  for (i = 2; i < 8; i++) {
1398  byte = *(str + i);
1399  if (byte >= 'A' && byte <= 'F')
1400  byte = byte - 'A' + 10;
1401  else if (byte >= 'a' && byte <= 'f')
1402  byte = byte - 'a' + 10;
1403  else if (byte >= '0' && byte <= '9')
1404  byte = byte - '0';
1405  else
1406  break;
1407  n = (n * 16) + byte;
1408  }
1409  }
1410  else {
1411  for (i = 1; i < 8; i++) {
1412  byte = *(str + i);
1413  if (byte >= '0' && byte <= '9')
1414  n = (n * 10) + (byte - '0');
1415  else
1416  break;
1417  }
1418  }
1419  if (byte == ';') {
1420  str += i+1;
1421  }
1422  else {
1423  n = 0;
1424  }
1425  }
1426  else {
1427  key.name = p = entity_name_buf;
1428  for (i = 0; i < ENTITY_NAME_LENGTH_MAX; i++) {
1429  byte = *(str + i);
1430  if (byte == '\0') break;
1431  if (byte == ';') {
1432  *p++ = '\0';
1433  res = bsearch(&key, entities, NR_OF_ENTITIES,
1434  sizeof(entities[0]), *comp_entities);
1435  if (res) {
1436  n = res->value;
1437  str += i+1;
1438  }
1439  break;
1440  }
1441  *p++ = byte;
1442  }
1443  }
1444  *s = (char*)str;
1445  return n;
1446 }
1447 
1448 static unsigned char
1449 cvtAndAppend (unsigned char c, agxbuf* xb)
1450 {
1451  char buf[2];
1452  char* s;
1453  char* p;
1454  int len;
1455 
1456  buf[0] = c;
1457  buf[1] = '\0';
1458 
1459  p = s = latin1ToUTF8 (buf);
1460  len = strlen(s);
1461  while (len-- > 1)
1462  agxbputc(xb, *p++);
1463  c = *p;
1464  free (s);
1465  return c;
1466 }
1467 
1468 /* htmlEntityUTF8:
1469  * substitute html entities like: &#123; and: &amp; with the UTF8 equivalents
1470  * check for invalid utf8. If found, treat a single byte as Latin-1, convert it to
1471  * utf8 and warn the user.
1472  */
1473 char* htmlEntityUTF8 (char* s, graph_t* g)
1474 {
1475  static graph_t* lastg;
1476  static boolean warned;
1477  char* ns;
1478  agxbuf xb;
1479  unsigned char buf[BUFSIZ];
1480  unsigned char c;
1481  unsigned int v;
1482 
1483  int uc;
1484  int ui;
1485 
1486  if (lastg != g) {
1487  lastg = g;
1488  warned = 0;
1489  }
1490 
1491  agxbinit(&xb, BUFSIZ, buf);
1492 
1493  while ((c = *(unsigned char*)s++)) {
1494  if (c < 0xC0)
1495  /*
1496  * Handles properly formed UTF-8 characters between
1497  * 0x01 and 0x7F. Also treats \0 and naked trail
1498  * bytes 0x80 to 0xBF as valid characters representing
1499  * themselves.
1500  */
1501  uc = 0;
1502  else if (c < 0xE0)
1503  uc = 1;
1504  else if (c < 0xF0)
1505  uc = 2;
1506  else if (c < 0xF8)
1507  uc = 3;
1508  else {
1509  uc = -1;
1510  if (!warned) {
1511  agerr(AGWARN, "UTF8 codes > 4 bytes are not currently supported (graph %s) - treated as Latin-1. Perhaps \"-Gcharset=latin1\" is needed?\n", agnameof(g));
1512  warned = 1;
1513  }
1514  c = cvtAndAppend (c, &xb);
1515  }
1516 
1517  if (uc == 0 && c == '&') {
1518  /* replace html entity sequences like: &amp;
1519  * and: &#123; with their UTF8 equivalents */
1520  v = htmlEntity (&s);
1521  if (v) {
1522  if (v < 0x7F) /* entity needs 1 byte in UTF8 */
1523  c = v;
1524  else if (v < 0x07FF) { /* entity needs 2 bytes in UTF8 */
1525  agxbputc(&xb, (v >> 6) | 0xC0);
1526  c = (v & 0x3F) | 0x80;
1527  }
1528  else { /* entity needs 3 bytes in UTF8 */
1529  agxbputc(&xb, (v >> 12) | 0xE0);
1530  agxbputc(&xb, ((v >> 6) & 0x3F) | 0x80);
1531  c = (v & 0x3F) | 0x80;
1532  }
1533  }
1534  }
1535  else /* copy n byte UTF8 characters */
1536  for (ui = 0; ui < uc; ++ui)
1537  if ((*s & 0xC0) == 0x80) {
1538  agxbputc(&xb, c);
1539  c = *(unsigned char*)s++;
1540  }
1541  else {
1542  if (!warned) {
1543  agerr(AGWARN, "Invalid %d-byte UTF8 found in input of graph %s - treated as Latin-1. Perhaps \"-Gcharset=latin1\" is needed?\n", uc + 1, agnameof(g));
1544  warned = 1;
1545  }
1546  c = cvtAndAppend (c, &xb);
1547  break;
1548  }
1549  agxbputc(&xb, c);
1550  }
1551  ns = strdup (agxbuse(&xb));
1552  agxbfree(&xb);
1553  return ns;
1554 }
1555 
1556 /* latin1ToUTF8:
1557  * Converts string from Latin1 encoding to utf8
1558  * Also translates HTML entities.
1559  *
1560  */
1561 char* latin1ToUTF8 (char* s)
1562 {
1563  char* ns;
1564  agxbuf xb;
1565  unsigned char buf[BUFSIZ];
1566  unsigned int v;
1567 
1568  agxbinit(&xb, BUFSIZ, buf);
1569 
1570  /* Values are either a byte (<= 256) or come from htmlEntity, whose
1571  * values are all less than 0x07FF, so we need at most 3 bytes.
1572  */
1573  while ((v = *(unsigned char*)s++)) {
1574  if (v == '&') {
1575  v = htmlEntity (&s);
1576  if (!v) v = '&';
1577  }
1578  if (v < 0x7F)
1579  agxbputc(&xb, v);
1580  else if (v < 0x07FF) {
1581  agxbputc(&xb, (v >> 6) | 0xC0);
1582  agxbputc(&xb, (v & 0x3F) | 0x80);
1583  }
1584  else {
1585  agxbputc(&xb, (v >> 12) | 0xE0);
1586  agxbputc(&xb, ((v >> 6) & 0x3F) | 0x80);
1587  agxbputc(&xb, (v & 0x3F) | 0x80);
1588  }
1589  }
1590  ns = strdup (agxbuse(&xb));
1591  agxbfree(&xb);
1592  return ns;
1593 }
1594 
1595 /* utf8ToLatin1:
1596  * Converts string from utf8 encoding to Latin1
1597  * Note that it does not attempt to reproduce HTML entities.
1598  * We assume the input string comes from latin1ToUTF8.
1599  */
1600 char*
1601 utf8ToLatin1 (char* s)
1602 {
1603  char* ns;
1604  agxbuf xb;
1605  unsigned char buf[BUFSIZ];
1606  unsigned char c;
1607  unsigned char outc;
1608 
1609  agxbinit(&xb, BUFSIZ, buf);
1610 
1611  while ((c = *(unsigned char*)s++)) {
1612  if (c < 0x7F)
1613  agxbputc(&xb, c);
1614  else {
1615  outc = (c & 0x03) << 6;
1616  c = *(unsigned char*)s++;
1617  outc = outc | (c & 0x3F);
1618  agxbputc(&xb, outc);
1619  }
1620  }
1621  ns = strdup (agxbuse(&xb));
1622  agxbfree(&xb);
1623  return ns;
1624 }
1625 
1626 boolean overlap_node(node_t *n, boxf b)
1627 {
1628  inside_t ictxt;
1629  pointf p;
1630 
1631  if (! OVERLAP(b, ND_bb(n)))
1632  return FALSE;
1633 
1634 /* FIXME - need to do something better about CLOSEENOUGH */
1635  p = sub_pointf(ND_coord(n), mid_pointf(b.UR, b.LL));
1636 
1637  ictxt.s.n = n;
1638  ictxt.s.bp = NULL;
1639 
1640  return ND_shape(n)->fns->insidefn(&ictxt, p);
1641 }
1642 
1644 {
1645  pointf s;
1646  boxf bb;
1647 
1648  s.x = lp->dimen.x / 2.;
1649  s.y = lp->dimen.y / 2.;
1650  bb.LL = sub_pointf(lp->pos, s);
1651  bb.UR = add_pointf(lp->pos, s);
1652  return OVERLAP(b, bb);
1653 }
1654 
1655 static boolean overlap_arrow(pointf p, pointf u, double scale, int flag, boxf b)
1656 {
1657  if (OVERLAP(b, arrow_bb(p, u, scale, flag))) {
1658  /* FIXME - check inside arrow shape */
1659  return TRUE;
1660  }
1661  return FALSE;
1662 }
1663 
1664 static boolean overlap_bezier(bezier bz, boxf b)
1665 {
1666  int i;
1667  pointf p, u;
1668 
1669  assert(bz.size);
1670  u = bz.list[0];
1671  for (i = 1; i < bz.size; i++) {
1672  p = bz.list[i];
1673  if (lineToBox(p, u, b) != -1)
1674  return TRUE;
1675  u = p;
1676  }
1677 
1678  /* check arrows */
1679  if (bz.sflag) {
1680  if (overlap_arrow(bz.sp, bz.list[0], 1, bz.sflag, b))
1681  return TRUE;
1682  }
1683  if (bz.eflag) {
1684  if (overlap_arrow(bz.ep, bz.list[bz.size - 1], 1, bz.eflag, b))
1685  return TRUE;
1686  }
1687  return FALSE;
1688 }
1689 
1690 boolean overlap_edge(edge_t *e, boxf b)
1691 {
1692  int i;
1693  splines *spl;
1694  textlabel_t *lp;
1695 
1696  spl = ED_spl(e);
1697  if (spl && boxf_overlap(spl->bb, b))
1698  for (i = 0; i < spl->size; i++)
1699  if (overlap_bezier(spl->list[i], b))
1700  return TRUE;
1701 
1702  lp = ED_label(e);
1703  if (lp && overlap_label(lp, b))
1704  return TRUE;
1705 
1706  return FALSE;
1707 }
1708 
1709 /* edgeType:
1710  * Convert string to edge type.
1711  */
1712 int edgeType (char* s, int dflt)
1713 {
1714  int et;
1715 
1716  if (!s || (*s == '\0')) return dflt;
1717 
1718  et = ET_NONE;
1719  switch (*s) {
1720  case '0' : /* false */
1721  et = ET_LINE;
1722  break;
1723  case '1' : /* true */
1724  case '2' :
1725  case '3' :
1726  case '4' :
1727  case '5' :
1728  case '6' :
1729  case '7' :
1730  case '8' :
1731  case '9' :
1732  et = ET_SPLINE;
1733  break;
1734  case 'c' :
1735  case 'C' :
1736  if (!strcasecmp (s+1, "urved"))
1737  et = ET_CURVED;
1738  else if (!strcasecmp (s+1, "ompound"))
1739  et = ET_COMPOUND;
1740  break;
1741  case 'f' :
1742  case 'F' :
1743  if (!strcasecmp (s+1, "alse"))
1744  et = ET_LINE;
1745  break;
1746  case 'l' :
1747  case 'L' :
1748  if (!strcasecmp (s+1, "ine"))
1749  et = ET_LINE;
1750  break;
1751  case 'n' :
1752  case 'N' :
1753  if (!strcasecmp (s+1, "one")) return et;
1754  if (!strcasecmp (s+1, "o")) return ET_LINE;
1755  break;
1756  case 'o' :
1757  case 'O' :
1758  if (!strcasecmp (s+1, "rtho"))
1759  et = ET_ORTHO;
1760  break;
1761  case 'p' :
1762  case 'P' :
1763  if (!strcasecmp (s+1, "olyline"))
1764  et = ET_PLINE;
1765  break;
1766  case 's' :
1767  case 'S' :
1768  if (!strcasecmp (s+1, "pline"))
1769  et = ET_SPLINE;
1770  break;
1771  case 't' :
1772  case 'T' :
1773  if (!strcasecmp (s+1, "rue"))
1774  et = ET_SPLINE;
1775  break;
1776  case 'y' :
1777  case 'Y' :
1778  if (!strcasecmp (s+1, "es"))
1779  et = ET_SPLINE;
1780  break;
1781  }
1782  if (!et) {
1783  agerr(AGWARN, "Unknown \"splines\" value: \"%s\" - ignored\n", s);
1784  et = dflt;
1785  }
1786  return et;
1787 }
1788 
1789 /* setEdgeType:
1790  * Sets graph's edge type based on the "splines" attribute.
1791  * If the attribute is not defined, use default.
1792  * If the attribute is "", use NONE.
1793  * If attribute value matches (case indepedent), use match.
1794  * ortho => ET_ORTHO
1795  * none => ET_NONE
1796  * line => ET_LINE
1797  * polyline => ET_PLINE
1798  * spline => ET_SPLINE
1799  * If attribute is boolean, true means ET_SPLINE, false means ET_LINE.
1800  * Else warn and use default.
1801  */
1802 void setEdgeType (graph_t* g, int dflt)
1803 {
1804  char* s = agget(g, "splines");
1805  int et;
1806 
1807  if (!s) {
1808  et = dflt;
1809  }
1810  else if (*s == '\0') {
1811  et = ET_NONE;
1812  }
1813  else et = edgeType (s, dflt);
1814  GD_flags(g) |= et;
1815 }
1816 
1817 
1818 /* get_gradient_points
1819  * Evaluates the extreme points of an ellipse or polygon
1820  * Determines the point at the center of the extreme points
1821  * If isRadial is true,sets the inner radius to half the distance to the min point;
1822  * else uses the angle parameter to identify two points on a line that defines the
1823  * gradient direction
1824  * By default, this assumes a left-hand coordinate system (for svg); if RHS = 2 flag
1825  * is set, use standard coordinate system.
1826  */
1827 void get_gradient_points(pointf * A, pointf * G, int n, float angle, int flags)
1828 {
1829  int i;
1830  double rx, ry;
1831  pointf min,max,center;
1832  int isRadial = flags & 1;
1833  int isRHS = flags & 2;
1834 
1835  if (n == 2) {
1836  rx = A[1].x - A[0].x;
1837  ry = A[1].y - A[0].y;
1838  min.x = A[0].x - rx;
1839  max.x = A[0].x + rx;
1840  min.y = A[0].y - ry;
1841  max.y = A[0].y + ry;
1842  }
1843  else {
1844  min.x = max.x = A[0].x;
1845  min.y = max.y = A[0].y;
1846  for (i = 0; i < n; i++){
1847  min.x = MIN(A[i].x,min.x);
1848  min.y = MIN(A[i].y,min.y);
1849  max.x = MAX(A[i].x,max.x);
1850  max.y = MAX(A[i].y,max.y);
1851  }
1852  }
1853  center.x = min.x + (max.x - min.x)/2;
1854  center.y = min.y + (max.y - min.y)/2;
1855  if (isRadial) {
1856  double inner_r, outer_r;
1857  outer_r = sqrt((center.x - min.x)*(center.x - min.x) +
1858  (center.y - min.y)*(center.y - min.y));
1859  inner_r = outer_r /4.;
1860  if (isRHS) {
1861  G[0].y = center.y;
1862  }
1863  else {
1864  G[0].y = -center.y;
1865  }
1866  G[0].x = center.x;
1867  G[1].x = inner_r;
1868  G[1].y = outer_r;
1869  }
1870  else {
1871  double half_x = max.x - center.x;
1872  double half_y = max.y - center.y;
1873  double sina = sin(angle);
1874  double cosa = cos(angle);
1875  if (isRHS) {
1876  G[0].y = center.y - half_y * sina;
1877  G[1].y = center.y + half_y * sina;
1878  }
1879  else {
1880  G[0].y = -center.y + (max.y - center.y) * sin(angle);
1881  G[1].y = -center.y - (center.y - min.y) * sin(angle);
1882  }
1883  G[0].x = center.x - half_x * cosa;
1884  G[1].x = center.x + half_x * cosa;
1885  }
1886 }
1887 
1888 #ifndef WIN32_STATIC
1889 #ifndef HAVE_STRCASECMP
1890 
1891 
1892 #include <string.h>
1893 //#include <ctype.h>
1894 
1895 
1896 int strcasecmp(const char *s1, const char *s2)
1897 {
1898  while ((*s1 != '\0')
1899  && (tolower(*(unsigned char *) s1) ==
1900  tolower(*(unsigned char *) s2))) {
1901  s1++;
1902  s2++;
1903  }
1904 
1905  return tolower(*(unsigned char *) s1) - tolower(*(unsigned char *) s2);
1906 }
1907 
1908 #endif /* HAVE_STRCASECMP */
1909 #endif /* WIN32_STATIC */
1910 
1911 #ifndef WIN32_STATIC
1912 #ifndef HAVE_STRNCASECMP
1913 #include <string.h>
1914 //#include <ctype.h>
1915 
1916 int strncasecmp(const char *s1, const char *s2, unsigned int n)
1917 {
1918  if (n == 0)
1919  return 0;
1920 
1921  while ((n-- != 0)
1922  && (tolower(*(unsigned char *) s1) ==
1923  tolower(*(unsigned char *) s2))) {
1924  if (n == 0 || *s1 == '\0' || *s2 == '\0')
1925  return 0;
1926  s1++;
1927  s2++;
1928  }
1929 
1930  return tolower(*(unsigned char *) s1) - tolower(*(unsigned char *) s2);
1931 }
1932 
1933 #endif /* HAVE_STRNCASECMP */
1934 #endif /* WIN32_STATIC */
1936 {
1937  int i;
1938  if (ED_spl(e)) {
1939  for (i = 0; i < ED_spl(e)->size; i++)
1940  free(ED_spl(e)->list[i].list);
1941  free(ED_spl(e)->list);
1942  free(ED_spl(e));
1943  }
1944  ED_spl(e) = NULL;
1945 }
1946 
1948 {
1949  free (ED_path(e).ps);
1950  gv_free_splines(e);
1951  free_label(ED_label(e));
1952  free_label(ED_xlabel(e));
1955  /*FIX HERE , shallow cleaning may not be enough here */
1956  agdelrec(e, "Agedgeinfo_t");
1957 }
1958 
1960 {
1961  if (ND_pos(n)) free(ND_pos(n));
1962  if (ND_shape(n))
1963  ND_shape(n)->fns->freefn(n);
1964  free_label(ND_label(n));
1965  free_label(ND_xlabel(n));
1966  /*FIX HERE , shallow cleaning may not be enough here */
1967  agdelrec(n, "Agnodeinfo_t");
1968 }
1969 
1970 void gv_nodesize(node_t * n, boolean flip)
1971 {
1972  double w;
1973 
1974  if (flip) {
1975  w = INCH2PS(ND_height(n));
1976  ND_lw(n) = ND_rw(n) = w / 2;
1977  ND_ht(n) = INCH2PS(ND_width(n));
1978  }
1979  else {
1980  w = INCH2PS(ND_width(n));
1981  ND_lw(n) = ND_rw(n) = w / 2;
1982  ND_ht(n) = INCH2PS(ND_height(n));
1983  }
1984 }
1985 
1986 #ifdef _WIN32
1987 void fix_fc(void)
1988 {
1989  char buf[28192];
1990  char buf2[28192];
1991  int cur=0;
1992  FILE* fp;
1993 
1994  if((fp = fopen("fix-fc.exe", "r")) == NULL)
1995  return ;
1996  fclose (fp);
1997  if (!system ("fix-fc.exe")) {
1998  system ("del fix-fc.exe");
1999  system ("dot -c"); //run dot -c once too since we already run things :)
2000  }
2001 }
2002 #endif
2003 
2004 #ifndef HAVE_DRAND48
2005 double drand48(void)
2006 {
2007  double d;
2008  d = rand();
2009  d = d / RAND_MAX;
2010  return d;
2011 }
2012 #endif
2013 typedef struct {
2015  char* name;
2017 } clust_t;
2018 
2019 static void free_clust (Dt_t* dt, clust_t* clp, Dtdisc_t* disc)
2020 {
2021  free (clp);
2022 }
2023 
2024 static Dtdisc_t strDisc = {
2025  offsetof(clust_t,name),
2026  -1,
2027  offsetof(clust_t,link),
2028  NIL(Dtmake_f),
2029  (Dtfree_f)free_clust,
2030  NIL(Dtcompar_f),
2031  NIL(Dthash_f),
2032  NIL(Dtmemory_f),
2033  NIL(Dtevent_f)
2034 };
2035 
2036 static void fillMap (Agraph_t* g, Dt_t* map)
2037 {
2038  Agraph_t* cl;
2039  int c;
2040  char* s;
2041  clust_t* ip;
2042 
2043  for (c = 1; c <= GD_n_cluster(g); c++) {
2044  cl = GD_clust(g)[c];
2045  s = agnameof(cl);
2046  if (dtmatch (map, s)) {
2047  agerr(AGWARN, "Two clusters named %s - the second will be ignored\n", s);
2048  }
2049  else {
2050  ip = NEW(clust_t);
2051  ip->name = s;
2052  ip->clp = cl;
2053  dtinsert (map, ip);
2054  }
2055  fillMap (cl, map);
2056  }
2057 }
2058 
2059 /* mkClustMap:
2060  * Generates a dictionary mapping cluster names to corresponding cluster.
2061  * Used with cgraph as the latter does not support a flat namespace of clusters.
2062  * Assumes G has already built a cluster tree using GD_n_cluster and GD_clust.
2063  */
2065 {
2066  Dt_t* map = dtopen (&strDisc, Dtoset);
2067 
2068  fillMap (g, map);
2069 
2070  return map;
2071 }
2072 
2073 Agraph_t*
2074 findCluster (Dt_t* map, char* name)
2075 {
2076  clust_t* clp = dtmatch (map, name);
2077  if (clp)
2078  return clp->clp;
2079  else
2080  return NULL;
2081 }
2082 
2086 /* void dumpG(Agraph_t* g) { agwrite(g, stderr); } */
void s1(graph_t *, node_t *)
Definition: stuff.c:686
#define GD_label(g)
Definition: types.h:381
int(* Dtcompar_f)(Dt_t *, void *, void *, Dtdisc_t *)
Definition: cdt.h:40
unsigned int(* Dthash_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:41
#define MAX(a, b)
Definition: agerror.c:17
void free_label(textlabel_t *p)
Definition: labels.c:209
EXTERN char * Gvimagepath
Definition: globals.h:62
#define DEFAULT_FONTNAME
Definition: const.h:70
char * fontname
Definition: utils.c:625
char * fontcolor
Definition: utils.c:626
CGRAPH_API int agobjkind(void *)
Definition: obj.c:264
EXTERN Agsym_t * N_showboxes
Definition: globals.h:95
void * p[2]
Definition: utils.c:983
CGRAPH_API Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition: node.c:142
#define ABS(a)
Definition: arith.h:45
Definition: types.h:67
#define GD_has_labels(g)
Definition: types.h:372
EXTERN Agsym_t * E_labelfontcolor
Definition: globals.h:107
CDT_API int dtclose(Dt_t *)
attrsym_t * safe_dcl(graph_t *g, int obj_kind, char *name, char *def)
Definition: utils.c:1333
int eflag
Definition: types.h:112
#define ET_SPLINE
Definition: const.h:275
#define DEFAULT_NODEWIDTH
Definition: const.h:77
Agsym_t * agattr(Agraph_t *g, int kind, char *name, char *value)
Definition: attr.c:324
#define N_NEW(n, t)
Definition: memory.h:36
#define DIRSEP
Definition: gvcint.h:152
void *(* Dtmake_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:38
char * latin1ToUTF8(char *s)
Definition: utils.c:1561
void * grealloc(void *ptr, size_t size)
Definition: memory.c:54
Agraphinfo_t * ginf(Agraph_t *g)
Definition: utils.c:2084
Agnodeinfo_t * ninf(Agnode_t *n)
Definition: utils.c:2083
Dt_t * mkClustMap(Agraph_t *g)
Definition: utils.c:2064
#define ND_xlabel(n)
Definition: types.h:510
#define agxbuse(X)
Definition: agxbuf.h:83
CGRAPH_API int aghtmlstr(char *)
Definition: refstr.c:178
Agsym_t * setAttr(graph_t *g, void *obj, char *name, char *value, Agsym_t *ap)
Definition: utils.c:924
#define MIN_NODEWIDTH
Definition: const.h:78
int size
Definition: types.h:110
char * defval
Definition: cgraph.h:327
char * htmlEntityUTF8(char *s, graph_t *g)
Definition: utils.c:1473
EXTERN Agsym_t * E_tailclip
Definition: globals.h:107
boolean overlap_edge(edge_t *e, boxf b)
Definition: utils.c:1690
Agsym_t * agnxtattr(Agraph_t *g, int kind, Agsym_t *attr)
Definition: attr.c:340
char * late_nnstring(void *obj, attrsym_t *attr, char *def)
Definition: utils.c:129
#define MIN(a, b)
Definition: arith.h:35
node_t ** store
Definition: types.h:198
Dtlink_t link
Definition: utils.c:982
#define GD_n_cluster(g)
Definition: types.h:396
int n_cluster_edges
Definition: utils.c:1172
EXTERN Agsym_t * N_fontname
Definition: globals.h:95
EXTERN Agsym_t * N_fontcolor
Definition: globals.h:95
shape_kind shapeOf(node_t *)
Definition: shapes.c:1820
#define SMALLBUF
Definition: const.h:17
EXTERN Agsym_t * N_label
Definition: globals.h:95
int agxset(void *obj, Agsym_t *sym, char *value)
Definition: attr.c:468
CDT_API Dtmethod_t * Dtoset
Definition: cdt.h:166
EXTERN Agsym_t * N_fontsize
Definition: globals.h:95
#define ALLOC(size, ptr, type)
Definition: memory.h:41
Definition: utils.c:981
EXTERN char * HTTPServerEnVar
Definition: globals.h:67
Definition: types.h:117
#define ED_head_port(e)
Definition: types.h:591
#define ED_compound(e)
Definition: types.h:586
EXTERN Agsym_t * N_height
Definition: globals.h:95
void undoClusterEdges(graph_t *g)
Definition: utils.c:1295
#define DEFAULT_NODEHEIGHT
Definition: const.h:75
int size
Definition: types.h:119
EXTERN Agsym_t * E_labelfontname
Definition: globals.h:107
#define SET_CLUST_NODE(n)
Definition: macros.h:30
#define assert(x)
Definition: cghdr.h:47
node_t ** head
Definition: types.h:200
Definition: geom.h:28
#define EXPANDBP(b, p)
Definition: geom.h:48
size_t agxbput(agxbuf *xb, const char *s)
Definition: agxbuf.c:84
#define ND_UF_size(n)
Definition: types.h:493
#define NOTUSED(var)
Definition: cghdr.h:54
Definition: cdt.h:80
EXTERN Agsym_t * E_headlabel
Definition: globals.h:107
#define ED_label(e)
Definition: types.h:592
#define GD_flags(g)
Definition: types.h:369
void common_init_node(node_t *n)
Definition: utils.c:629
EXTERN Agsym_t * E_fontcolor
Definition: globals.h:107
void UF_remove(node_t *u, node_t *v)
Definition: utils.c:181
char * name
Definition: utils.c:2015
CGRAPH_API int agdelete(Agraph_t *g, void *obj)
Definition: obj.c:16
#define ND_pos(n)
Definition: types.h:526
EXTERN Agsym_t * E_label_float
Definition: globals.h:107
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
#define ED_label_ontop(e)
Definition: types.h:594
void gv_cleanup_edge(Agedge_t *e)
Definition: utils.c:1947
#define MAXENTLEN
Definition: utils.c:1345
CGRAPH_API int agcontains(Agraph_t *, void *)
Definition: obj.c:245
CGRAPH_API Agraph_t * agroot(void *obj)
Definition: obj.c:169
bezier * list
Definition: types.h:118
#define ND_ysize(n)
Definition: types.h:544
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
#define OVERLAP(b0, b1)
Definition: geom.h:42
#define AGDATA(obj)
Definition: cgraph.h:117
node_t * t
Definition: utils.c:984
void enqueue(nodequeue *q, node_t *n)
Definition: utils.c:51
#define ED_tail_label(e)
Definition: types.h:599
#define ND_label(n)
Definition: types.h:509
void UF_setname(node_t *u, node_t *v)
Definition: utils.c:195
#define POINTS_PER_INCH
Definition: geom.h:62
Agrec_t hdr
Definition: utils.c:1171
EXTERN Agsym_t * N_style
Definition: globals.h:95
Definition: cgraph.h:388
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
Definition: dtopen.c:9
#define agxbputc(X, C)
Definition: agxbuf.h:77
char * agget(void *obj, char *name)
Definition: attr.c:428
node_t * UF_find(node_t *n)
Definition: utils.c:146
CGRAPH_API Agraph_t * agraphof(void *obj)
Definition: obj.c:185
int lineToBox(pointf p, pointf q, boxf b)
Definition: geom.c:89
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
node_t * h
Definition: utils.c:985
double fontsize
Definition: utils.c:624
nodequeue * new_queue(int sz)
Definition: utils.c:34
#define ND_bb(n)
Definition: types.h:494
CGRAPH_API Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition: subg.c:52
#define ag_xget(x, a)
Definition: types.h:608
#define ED_tail_port(e)
Definition: types.h:600
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
pointf pos
Definition: types.h:133
#define NIL(t)
Definition: dthdr.h:13
#define ED_spl(e)
Definition: types.h:598
#define TAIL_LABEL
Definition: const.h:186
#define ND_ht(n)
Definition: types.h:506
EXTERN Agsym_t * E_taillabel
Definition: globals.h:107
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
#define max(x, y)
Definition: stress.c:794
#define ND_shape(n)
Definition: types.h:534
#define ET_COMPOUND
Definition: const.h:276
#define NODE_XLABEL
Definition: const.h:188
#define DIST2(p, q)
Definition: geom.h:59
EXTERN Agsym_t * E_xlabel
Definition: globals.h:107
double y
Definition: geom.h:28
int sflag
Definition: types.h:111
CGRAPH_API int agclose(Agraph_t *g)
Definition: graph.c:93
Dtlink_t link
Definition: utils.c:2014
int strncasecmp(const char *s1, const char *s2, unsigned int n)
Definition: strncasecmp.c:20
#define ET_PLINE
Definition: const.h:273
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
EXTERN Agsym_t * E_label
Definition: globals.h:107
#define ND_height(n)
Definition: types.h:504
EXTERN char * Gvfilepath
Definition: globals.h:61
#define ND_id(n)
Definition: types.h:489
#define dtmatch(d, o)
Definition: cdt.h:261
#define INCH2PS(a_inches)
Definition: geom.h:68
#define DEFAULT_COLOR
Definition: const.h:51
int test_toggle()
Definition: utils.c:618
#define ND_UF_parent(n)
Definition: types.h:491
#define LT_NONE
Definition: const.h:259
#define ET_NONE
Definition: const.h:270
#define HEAD_ID
Definition: types.h:52
#define LT_HTML
Definition: const.h:260
#define B2BF(b, bf)
Definition: geom.h:74
EXTERN Agsym_t * N_xlabel
Definition: globals.h:95
pointf sp
Definition: types.h:113
void gvToggle(int s)
Definition: utils.c:610
char * scanEntity(char *t, agxbuf *xb)
Definition: utils.c:1352
void *(* Dtmemory_f)(Dt_t *, void *, size_t, Dtdisc_t *)
Definition: cdt.h:36
#define ND_rw(n)
Definition: types.h:531
#define ND_has_port(n)
Definition: types.h:501
#define ND_showboxes(n)
Definition: types.h:536
double drand48(void)
Definition: utils.c:2005
#define ET_LINE
Definition: const.h:271
struct elist elist
char * Fgets(FILE *fp)
Definition: utils.c:282
void compute_bb(graph_t *g)
Definition: utils.c:852
#define MIN_FONTSIZE
Definition: const.h:66
int sides
Definition: types.h:149
void agxbinit(agxbuf *xb, unsigned int hint, unsigned char *init)
Definition: agxbuf.c:25
pointf * list
Definition: types.h:109
node_t * dequeue(nodequeue *q)
Definition: utils.c:58
boolean mapBool(char *p, boolean dflt)
Definition: utils.c:454
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
int late_int(void *obj, attrsym_t *attr, int def, int low)
Definition: utils.c:71
Definition: grammar.c:79
#define GD_clust(g)
Definition: types.h:364
pointf dimen
Definition: types.h:129
Definition: cgraph.h:83
#define AGNODE
Definition: cgraph.h:101
#define GD_flip(g)
Definition: types.h:385
#define BETWEEN(a, b, c)
Definition: arith.h:74
void free_queue(nodequeue *q)
Definition: utils.c:45
void UF_singleton(node_t *u)
Definition: utils.c:188
#define dtinsert(d, o)
Definition: cdt.h:262
pointf ep
Definition: types.h:114
#define ET_CURVED
Definition: const.h:272
#define ND_width(n)
Definition: types.h:542
double get_inputscale(graph_t *g)
Definition: utils.c:112
node_t ** limit
Definition: types.h:199
const char * safefile(const char *filename)
Definition: utils.c:376
#define agfindnode(g, n)
Definition: types.h:611
void gv_free_splines(edge_t *e)
Definition: utils.c:1935
#define ND_lw(n)
Definition: types.h:513
pointf Bezier(pointf *V, int degree, double t, pointf *Left, pointf *Right)
Definition: utils.c:221
Agraph_t * findCluster(Dt_t *map, char *name)
Definition: utils.c:2074
int agcopyattr(void *oldobj, void *newobj)
Definition: attr.c:535
#define NULL
Definition: logic.h:39
#define HEAD_LABEL
Definition: const.h:185
real cg(Operator Ax, Operator precond, int n, int dim, real *x0, real *rhs, real tol, int maxit, int *flag)
Definition: sparse_solve.c:227
#define MIN_NODEHEIGHT
Definition: const.h:76
CGRAPH_API int agdelrec(void *obj, char *name)
Definition: rec.c:145
#define agfindgraphattr(g, a)
Definition: types.h:612
#define ED_head_label(e)
Definition: types.h:590
#define W_DEGREE
Definition: utils.c:212
char * utf8ToLatin1(char *s)
Definition: utils.c:1601
double x
Definition: geom.h:28
#define NR_OF_ENTITIES
Definition: entities.h:273
boxf bb
Definition: types.h:120
#define ED_xlabel(e)
Definition: types.h:593
#define ND_coord(n)
Definition: types.h:496
boxf arrow_bb(pointf p, pointf u, double arrowsize, int flag)
Definition: arrows.c:691
#define streq(s, t)
Definition: cghdr.h:52
EXTERN Agsym_t * E_fontname
Definition: globals.h:107
double late_double(void *obj, attrsym_t *attr, double def, double low)
Definition: utils.c:87
boxf * bp
Definition: types.h:63
#define ENTITY_NAME_LENGTH_MAX
Definition: entities.h:272
void gv_cleanup_node(Agnode_t *n)
Definition: utils.c:1959
Definition: types.h:108
node_t * n
Definition: types.h:62
char * name
Definition: types.h:82
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
int strcasecmp(const char *s1, const char *s2)
Definition: strcasecmp.c:21
struct inside_t::@19 s
struct item_s item
#define TAIL_ID
Definition: types.h:51
#define LT_RECD
Definition: const.h:261
int is_a_cluster(Agraph_t *g)
Definition: utils.c:915
EXTERN Agsym_t * N_shape
Definition: globals.h:95
boolean mapbool(char *p)
Definition: utils.c:472
pointf LL
Definition: geom.h:35
#define CL_EDGE_TAG
Definition: macros.h:29
CGRAPH_API Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition: edge.c:281
void updateBB(graph_t *g, textlabel_t *lp)
Definition: utils.c:842
#define ED_path(e)
Definition: types.h:596
#define IS_CLUST_NODE(n)
Definition: macros.h:31
EXTERN Agsym_t * E_labelfontsize
Definition: globals.h:107
#define ND_ranktype(n)
Definition: types.h:530
int(* Dtevent_f)(Dt_t *, int, void *, Dtdisc_t *)
Definition: cdt.h:42
#define DEFAULT_NODESHAPE
Definition: const.h:79
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
Definition: types.h:56
void(* pf)(char *, void *)
Definition: xdot.c:501
#define EDGE_XLABEL
Definition: const.h:189
void(* Dtfree_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:39
int common_init_edge(edge_t *e)
Definition: utils.c:714
int peripheries
Definition: types.h:148
Agedgeinfo_t * einf(Agedge_t *e)
Definition: utils.c:2085
EXTERN Agsym_t * E_headclip
Definition: globals.h:107
void setEdgeType(graph_t *g, int dflt)
Definition: utils.c:1802
void gv_nodesize(node_t *n, boolean flip)
Definition: utils.c:1970
#define agfindedge(g, t, h)
Definition: types.h:610
Agraph_t * clp
Definition: utils.c:2016
boolean overlap_node(node_t *n, boxf b)
Definition: utils.c:1626
#define ND_xsize(n)
Definition: types.h:543
int edgeType(char *s, int dflt)
Definition: utils.c:1712
Definition: cdt.h:99
char * late_string(void *obj, attrsym_t *attr, char *def)
Definition: utils.c:122
pointf * vertices
Definition: types.h:154
#define PATHSEP
Definition: utils.c:336
#define GD_bb(g)
Definition: types.h:357
#define DEFAULT_FONTSIZE
Definition: const.h:64
#define HAS_CLUST_EDGE(g)
Definition: macros.h:32
agxbuf * str
Definition: htmlparse.c:85
EXTERN Agsym_t * N_width
Definition: globals.h:95
boxf polyBB(polygon_t *poly)
Definition: utils.c:821
#define MAPC(n)
Definition: utils.c:1101
Definition: agxbuf.h:34
Agraph_t * root
Definition: cgraph.h:247
EXTERN double PSinputscale
Definition: globals.h:71
char * agxget(void *obj, Agsym_t *sym)
Definition: attr.c:444
EXTERN Agsym_t * E_fontsize
Definition: globals.h:107
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define NORMAL
Definition: const.h:27
boolean overlap_label(textlabel_t *lp, boxf b)
Definition: utils.c:1643
pointf coord(node_t *n)
Definition: utils.c:202
#define EDGE_LABEL
Definition: const.h:184
#define AGEDGE
Definition: cgraph.h:104
void processClusterEdges(graph_t *g)
Definition: utils.c:1192
node_t ** tail
Definition: types.h:201
int maptoken(char *p, char **name, int *val)
Definition: utils.c:443
pointf neato_closest(splines *spl, pointf p)
Definition: utils.c:602
pointf dotneato_closest(splines *spl, pointf pt)
Definition: utils.c:477
pointf UR
Definition: geom.h:35
shape_desc * bind_shape(char *name, node_t *)
Definition: shapes.c:3837
void agxbfree(agxbuf *xb)
Definition: agxbuf.c:94
Definition: geom.h:35
#define FALSE
Definition: cgraph.h:35
pointf spline_at_y(splines *spl, double y)
Definition: utils.c:537
node_t * UF_union(node_t *u, node_t *v)
Definition: utils.c:156
CGRAPH_API Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition: node.c:254
#define EXPANDBB(b0, b1)
Definition: geom.h:51
boolean late_bool(void *obj, attrsym_t *attr, int def)
Definition: utils.c:137
#define ET_ORTHO
Definition: const.h:274
void get_gradient_points(pointf *A, pointf *G, int n, float angle, int flags)
Definition: utils.c:1827
#define INT_MAX
Definition: arith.h:52
textlabel_t * make_label(void *obj, char *str, int kind, double fontsize, char *fontname, char *fontcolor)
Definition: labels.c:115
#define NEW(t)
Definition: memory.h:35
#define AGRAPH
Definition: cgraph.h:100
#define TRUE
Definition: cgraph.h:38