Graphviz  2.41.20170921.2350
position.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 
15 /*
16  * position(g): set ND_coord(n) (x and y) for all nodes n of g, using GD_rank(g).
17  * (the graph may be modified by merging certain edges with a common endpoint.)
18  * the coordinates are computed by constructing and ranking an auxiliary graph.
19  * then leaf nodes are inserted in the fast graph. cluster boundary nodes are
20  * created and correctly separated.
21  */
22 
23 #include "dot.h"
24 #include "aspect.h"
25 
26 static int nsiter2(graph_t * g);
27 static void create_aux_edges(graph_t * g);
28 static void remove_aux_edges(graph_t * g);
29 static void set_xcoords(graph_t * g);
30 static void set_ycoords(graph_t * g);
31 static void set_aspect(graph_t * g, aspect_t* );
32 static void expand_leaves(graph_t * g);
33 static void make_lrvn(graph_t * g);
34 static void contain_nodes(graph_t * g);
35 static boolean idealsize(graph_t * g, double);
36 
37 #if DEBUG > 1
38 static void
39 dumpNS (graph_t * g)
40 {
41  node_t* n = GD_nlist(g);
42  elist el;
43  edge_t* e;
44  int i;
45 
46  while (n) {
47  el = ND_out(n);
48  for (i = 0; i < el.size; i++) {
49  e = el.list[i];
50  fprintf (stderr, "%s(%x) -> ", agnameof(agtail(e)),agtail(e));
51  fprintf (stderr, "%s(%x) : %d\n", agnameof(aghead(e)), aghead(e),
52  ED_minlen(e));
53  }
54  n = ND_next(n);
55  }
56 }
57 #endif
58 
59 static double
60 largeMinlen (double l)
61 {
62  agerr (AGERR, "Edge length %f larger than maximum %u allowed.\nCheck for overwide node(s).\n", l, USHRT_MAX);
63  return (double)USHRT_MAX;
64 }
65 
66 /* connectGraph:
67  * When source and/or sink nodes are defined, it is possible that
68  * after the auxiliary edges are added, the graph may still have 2 or
69  * 3 components. To fix this, we put trivial constraints connecting the
70  * first items of each rank.
71  */
72 static void
73 connectGraph (graph_t* g)
74 {
75  int i, j, r, found;
76  node_t* tp;
77  node_t* hp;
78  node_t* sn;
79  edge_t* e;
80  rank_t* rp;
81 
82  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
83  rp = GD_rank(g)+r;
84  found =FALSE;
85  tp = NULL;
86  for (i = 0; i < rp->n; i++) {
87  tp = rp->v[i];
88  if (ND_save_out(tp).list) {
89  for (j = 0; (e = ND_save_out(tp).list[j]); j++) {
90  if ((ND_rank(aghead(e)) > r) || (ND_rank(agtail(e)) > r)) {
91  found = TRUE;
92  break;
93  }
94  }
95  if (found) break;
96  }
97  if (ND_save_in(tp).list) {
98  for (j = 0; (e = ND_save_in(tp).list[j]); j++) {
99  if ((ND_rank(agtail(e)) > r) || (ND_rank(aghead(e)) > r)) {
100  found = TRUE;
101  break;
102  }
103  }
104  if (found) break;
105  }
106  }
107  if (found || !tp) continue;
108  tp = rp->v[0];
109  if (r < GD_maxrank(g)) hp = (rp+1)->v[0];
110  else hp = (rp-1)->v[0];
111  assert (hp);
112  sn = virtual_node(g);
113  ND_node_type(sn) = SLACKNODE;
114  make_aux_edge(sn, tp, 0, 0);
115  make_aux_edge(sn, hp, 0, 0);
116  ND_rank(sn) = MIN(ND_rank(tp), ND_rank(hp));
117  }
118 }
119 
121 {
122  if (GD_nlist(g) == NULL)
123  return; /* ignore empty graph */
124  mark_lowclusters(g); /* we could remove from splines.c now */
125  set_ycoords(g);
126  if (Concentrate)
127  dot_concentrate(g);
128  expand_leaves(g);
129  if (flat_edges(g))
130  set_ycoords(g);
131  create_aux_edges(g);
132  if (rank(g, 2, nsiter2(g))) { /* LR balance == 2 */
133  connectGraph (g);
134  const int rank_result = rank(g, 2, nsiter2(g));
135  assert(rank_result == 0);
136  }
137  set_xcoords(g);
138  set_aspect(g, asp);
139  remove_aux_edges(g); /* must come after set_aspect since we now
140  * use GD_ln and GD_rn for bbox width.
141  */
142 }
143 
144 static int nsiter2(graph_t * g)
145 {
146  int maxiter = INT_MAX;
147  char *s;
148 
149  if ((s = agget(g, "nslimit")))
150  maxiter = atof(s) * agnnodes(g);
151  return maxiter;
152 }
153 
154 static int go(node_t * u, node_t * v)
155 {
156  int i;
157  edge_t *e;
158 
159  if (u == v)
160  return TRUE;
161  for (i = 0; (e = ND_out(u).list[i]); i++) {
162  if (go(aghead(e), v))
163  return TRUE;
164  }
165  return FALSE;
166 }
167 
168 static int canreach(node_t * u, node_t * v)
169 {
170  return go(u, v);
171 }
172 
173 edge_t *make_aux_edge(node_t * u, node_t * v, double len, int wt)
174 {
175  edge_t *e;
176 
178  AGTYPE(&(e2->in)) = AGINEDGE;
179  AGTYPE(&(e2->out)) = AGOUTEDGE;
180  e2->out.base.data = (Agrec_t*)NEW(Agedgeinfo_t);
181  e = &(e2->out);
182 
183  agtail(e) = u;
184  aghead(e) = v;
185  if (len > USHRT_MAX)
186  len = largeMinlen (len);
187  ED_minlen(e) = ROUND(len);
188  ED_weight(e) = wt;
189  fast_edge(e);
190  return e;
191 }
192 
193 static void allocate_aux_edges(graph_t * g)
194 {
195  int i, j, n_in;
196  node_t *n;
197 
198  /* allocate space for aux edge lists */
199  for (n = GD_nlist(g); n; n = ND_next(n)) {
200  ND_save_in(n) = ND_in(n);
201  ND_save_out(n) = ND_out(n);
202  for (i = 0; ND_out(n).list[i]; i++);
203  for (j = 0; ND_in(n).list[j]; j++);
204  n_in = i + j;
205  alloc_elist(n_in + 3, ND_in(n));
206  alloc_elist(3, ND_out(n));
207  }
208 }
209 
210 /* make_LR_constraints:
211  */
212 static void
213 make_LR_constraints(graph_t * g)
214 {
215  int i, j, k;
216  int sw; /* self width */
217  int m0, m1;
218  double width;
219  int sep[2];
220  int nodesep; /* separation between nodes on same rank */
221  edge_t *e, *e0, *e1, *ff;
222  node_t *u, *v, *t0, *h0;
223  rank_t *rank = GD_rank(g);
224 
225  /* Use smaller separation on odd ranks if g has edge labels */
226  if (GD_has_labels(g->root) & EDGE_LABEL) {
227  sep[0] = GD_nodesep(g);
228  sep[1] = 5;
229  }
230  else {
231  sep[1] = sep[0] = GD_nodesep(g);
232  }
233  /* make edges to constrain left-to-right ordering */
234  for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
235  double last;
236  last = ND_rank(rank[i].v[0]) = 0;
237  nodesep = sep[i & 1];
238  for (j = 0; j < rank[i].n; j++) {
239  u = rank[i].v[j];
240  ND_mval(u) = ND_rw(u); /* keep it somewhere safe */
241  if (ND_other(u).size > 0) { /* compute self size */
242  /* FIX: dot assumes all self-edges go to the right. This
243  * is no longer true, though makeSelfEdge still attempts to
244  * put as many as reasonable on the right. The dot code
245  * should be modified to allow a box reflecting the placement
246  * of all self-edges, and use that to reposition the nodes.
247  * Note that this would not only affect left and right
248  * positioning but may also affect interrank spacing.
249  */
250  sw = 0;
251  for (k = 0; (e = ND_other(u).list[k]); k++) {
252  if (agtail(e) == aghead(e)) {
253  sw += selfRightSpace (e);
254  }
255  }
256  ND_rw(u) += sw; /* increment to include self edges */
257  }
258  v = rank[i].v[j + 1];
259  if (v) {
260  width = ND_rw(u) + ND_lw(v) + nodesep;
261  e0 = make_aux_edge(u, v, width, 0);
262  last = (ND_rank(v) = last + width);
263  }
264 
265  /* constraints from labels of flat edges on previous rank */
266  if ((e = (edge_t*)ND_alg(u))) {
267  e0 = ND_save_out(u).list[0];
268  e1 = ND_save_out(u).list[1];
269  if (ND_order(aghead(e0)) > ND_order(aghead(e1))) {
270  ff = e0;
271  e0 = e1;
272  e1 = ff;
273  }
274  m0 = (ED_minlen(e) * GD_nodesep(g)) / 2;
275  m1 = m0 + ND_rw(aghead(e0)) + ND_lw(agtail(e0));
276  /* these guards are needed because the flat edges
277  * work very poorly with cluster layout */
278  if (canreach(agtail(e0), aghead(e0)) == FALSE)
279  make_aux_edge(aghead(e0), agtail(e0), m1,
280  ED_weight(e));
281  m1 = m0 + ND_rw(agtail(e1)) + ND_lw(aghead(e1));
282  if (canreach(aghead(e1), agtail(e1)) == FALSE)
283  make_aux_edge(agtail(e1), aghead(e1), m1,
284  ED_weight(e));
285  }
286 
287  /* position flat edge endpoints */
288  for (k = 0; k < ND_flat_out(u).size; k++) {
289  e = ND_flat_out(u).list[k];
290  if (ND_order(agtail(e)) < ND_order(aghead(e))) {
291  t0 = agtail(e);
292  h0 = aghead(e);
293  } else {
294  t0 = aghead(e);
295  h0 = agtail(e);
296  }
297 
298  width = ND_rw(t0) + ND_lw(h0);
299  m0 = ED_minlen(e) * GD_nodesep(g) + width;
300 
301  if ((e0 = find_fast_edge(t0, h0))) {
302  /* flat edge between adjacent neighbors
303  * ED_dist contains the largest label width.
304  */
305  m0 = MAX(m0, width + GD_nodesep(g) + ROUND(ED_dist(e)));
306  if (m0 > USHRT_MAX)
307  m0 = largeMinlen (m0);
308  ED_minlen(e0) = MAX(ED_minlen(e0), m0);
309  ED_weight(e0) = MAX(ED_weight(e0), ED_weight(e));
310  }
311  else if (!ED_label(e)) {
312  /* unlabeled flat edge between non-neighbors
313  * ED_minlen(e) is max of ED_minlen of all equivalent
314  * edges.
315  */
316  make_aux_edge(t0, h0, m0, ED_weight(e));
317  }
318  /* labeled flat edges between non-neighbors have already
319  * been constrained by the label above.
320  */
321  }
322  }
323  }
324 }
325 
326 /* make_edge_pairs: make virtual edge pairs corresponding to input edges */
327 static void make_edge_pairs(graph_t * g)
328 {
329  int i, m0, m1;
330  node_t *n, *sn;
331  edge_t *e;
332 
333  for (n = GD_nlist(g); n; n = ND_next(n)) {
334  if (ND_save_out(n).list)
335  for (i = 0; (e = ND_save_out(n).list[i]); i++) {
336  sn = virtual_node(g);
337  ND_node_type(sn) = SLACKNODE;
338  m0 = (ED_head_port(e).p.x - ED_tail_port(e).p.x);
339  if (m0 > 0)
340  m1 = 0;
341  else {
342  m1 = -m0;
343  m0 = 0;
344  }
345 #ifdef NOTDEF
346 /* was trying to improve LR balance */
347  if ((ND_save_out(n).size % 2 == 0)
348  && (i == ND_save_out(n).size / 2 - 1)) {
349  node_t *u = ND_save_out(n).list[i]->head;
350  node_t *v = ND_save_out(n).list[i + 1]->head;
351  double width = ND_rw(u) + ND_lw(v) + GD_nodesep(g);
352  m0 = width / 2 - 1;
353  }
354 #endif
355  make_aux_edge(sn, agtail(e), m0 + 1, ED_weight(e));
356  make_aux_edge(sn, aghead(e), m1 + 1, ED_weight(e));
357  ND_rank(sn) =
358  MIN(ND_rank(agtail(e)) - m0 - 1,
359  ND_rank(aghead(e)) - m1 - 1);
360  }
361  }
362 }
363 
364 static void contain_clustnodes(graph_t * g)
365 {
366  int c;
367  edge_t *e;
368 
369  if (g != dot_root(g)) {
370  contain_nodes(g);
371  if ((e = find_fast_edge(GD_ln(g),GD_rn(g)))) /* maybe from lrvn()?*/
372  ED_weight(e) += 128;
373  else
374  make_aux_edge(GD_ln(g), GD_rn(g), 1, 128); /* clust compaction edge */
375  }
376  for (c = 1; c <= GD_n_cluster(g); c++)
377  contain_clustnodes(GD_clust(g)[c]);
378 }
379 
380 static int vnode_not_related_to(graph_t * g, node_t * v)
381 {
382  edge_t *e;
383 
384  if (ND_node_type(v) != VIRTUAL)
385  return FALSE;
386  for (e = ND_save_out(v).list[0]; ED_to_orig(e); e = ED_to_orig(e));
387  if (agcontains(g, agtail(e)))
388  return FALSE;
389  if (agcontains(g, aghead(e)))
390  return FALSE;
391  return TRUE;
392 }
393 
394 /* keepout_othernodes:
395  * Guarantee nodes outside the cluster g are placed outside of it.
396  * This is done by adding constraints to make sure such nodes have
397  * a gap of margin from the left or right bounding box node ln or rn.
398  *
399  * We could probably reduce some of these constraints by checking if
400  * the node is in a cluster, since elsewhere we make constrain a
401  * separate between clusters. Also, we should be able to skip the
402  * first loop if g is the root graph.
403  */
404 static void keepout_othernodes(graph_t * g)
405 {
406  int i, c, r, margin;
407  node_t *u, *v;
408 
409  margin = late_int (g, G_margin, CL_OFFSET, 0);
410  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
411  if (GD_rank(g)[r].n == 0)
412  continue;
413  v = GD_rank(g)[r].v[0];
414  if (v == NULL)
415  continue;
416  for (i = ND_order(v) - 1; i >= 0; i--) {
417  u = GD_rank(dot_root(g))[r].v[i];
418  /* can't use "is_a_vnode_of" because elists are swapped */
419  if ((ND_node_type(u) == NORMAL) || vnode_not_related_to(g, u)) {
420  make_aux_edge(u, GD_ln(g), margin + ND_rw(u), 0);
421  break;
422  }
423  }
424  for (i = ND_order(v) + GD_rank(g)[r].n; i < GD_rank(dot_root(g))[r].n;
425  i++) {
426  u = GD_rank(dot_root(g))[r].v[i];
427  if ((ND_node_type(u) == NORMAL) || vnode_not_related_to(g, u)) {
428  make_aux_edge(GD_rn(g), u, margin + ND_lw(u), 0);
429  break;
430  }
431  }
432  }
433 
434  for (c = 1; c <= GD_n_cluster(g); c++)
435  keepout_othernodes(GD_clust(g)[c]);
436 }
437 
438 /* contain_subclust:
439  * Make sure boxes of subclusters of g are offset from the
440  * box of g. This is done by a constraint between the left and
441  * right bounding box nodes ln and rn of g and a subcluster.
442  * The gap needs to include any left or right labels.
443  */
444 static void contain_subclust(graph_t * g)
445 {
446  int margin, c;
447  graph_t *subg;
448 
449  margin = late_int (g, G_margin, CL_OFFSET, 0);
450  make_lrvn(g);
451  for (c = 1; c <= GD_n_cluster(g); c++) {
452  subg = GD_clust(g)[c];
453  make_lrvn(subg);
454  make_aux_edge(GD_ln(g), GD_ln(subg),
455  margin + GD_border(g)[LEFT_IX].x, 0);
456  make_aux_edge(GD_rn(subg), GD_rn(g),
457  margin + GD_border(g)[RIGHT_IX].x, 0);
458  contain_subclust(subg);
459  }
460 }
461 
462 /* separate_subclust:
463  * Guarantee space between subcluster of g.
464  * This is done by adding a constraint between the right bbox node rn
465  * of the left cluster and the left bbox node ln of the right cluster.
466  * This is only done if the two clusters overlap in some rank.
467  */
468 static void separate_subclust(graph_t * g)
469 {
470  int i, j, margin;
471  graph_t *low, *high;
472  graph_t *left, *right;
473 
474  margin = late_int (g, G_margin, CL_OFFSET, 0);
475  for (i = 1; i <= GD_n_cluster(g); i++)
476  make_lrvn(GD_clust(g)[i]);
477  for (i = 1; i <= GD_n_cluster(g); i++) {
478  for (j = i + 1; j <= GD_n_cluster(g); j++) {
479  low = GD_clust(g)[i];
480  high = GD_clust(g)[j];
481  if (GD_minrank(low) > GD_minrank(high)) {
482  graph_t *temp = low;
483  low = high;
484  high = temp;
485  }
486  if (GD_maxrank(low) < GD_minrank(high))
487  continue;
488  if (ND_order(GD_rank(low)[GD_minrank(high)].v[0])
489  < ND_order(GD_rank(high)[GD_minrank(high)].v[0])) {
490  left = low;
491  right = high;
492  } else {
493  left = high;
494  right = low;
495  }
496  make_aux_edge(GD_rn(left), GD_ln(right), margin, 0);
497  }
498  separate_subclust(GD_clust(g)[i]);
499  }
500 }
501 
502 /* pos_clusters: create constraints for:
503  * node containment in clusters,
504  * cluster containment in clusters,
505  * separation of sibling clusters.
506  */
507 static void pos_clusters(graph_t * g)
508 {
509  if (GD_n_cluster(g) > 0) {
510  contain_clustnodes(g);
511  keepout_othernodes(g);
512  contain_subclust(g);
513  separate_subclust(g);
514  }
515 }
516 
517 static void compress_graph(graph_t * g)
518 {
519  double x;
520  pointf p;
521 
522  if (GD_drawing(g)->ratio_kind != R_COMPRESS)
523  return;
524  p = GD_drawing(g)->size;
525  if (p.x * p.y <= 1)
526  return;
527  contain_nodes(g);
528  if (GD_flip(g) == FALSE)
529  x = p.x;
530  else
531  x = p.y;
532 
533  /* Guard against huge size attribute since max. edge length is USHRT_MAX
534  * A warning might be called for. Also, one could check that the graph
535  * already fits GD_drawing(g)->size and return immediately.
536  */
537  x = MIN(x,USHRT_MAX);
538  make_aux_edge(GD_ln(g), GD_rn(g), x, 1000);
539 }
540 
541 static void create_aux_edges(graph_t * g)
542 {
543  allocate_aux_edges(g);
544  make_LR_constraints(g);
545  make_edge_pairs(g);
546  pos_clusters(g);
547  compress_graph(g);
548 }
549 
550 static void remove_aux_edges(graph_t * g)
551 {
552  int i;
553  node_t *n, *nnext, *nprev;
554  edge_t *e;
555 
556  for (n = GD_nlist(g); n; n = ND_next(n)) {
557  for (i = 0; (e = ND_out(n).list[i]); i++) {
558  free(e->base.data);
559  free(e);
560  }
561  free_list(ND_out(n));
562  free_list(ND_in(n));
563  ND_out(n) = ND_save_out(n);
564  ND_in(n) = ND_save_in(n);
565  }
566  /* cannot be merged with previous loop */
567  nprev = NULL;
568  for (n = GD_nlist(g); n; n = nnext) {
569  nnext = ND_next(n);
570  if (ND_node_type(n) == SLACKNODE) {
571  if (nprev)
572  ND_next(nprev) = nnext;
573  else
574  GD_nlist(g) = nnext;
575  free(n->base.data);
576  free(n);
577  } else
578  nprev = n;
579  }
580  ND_prev(GD_nlist(g)) = NULL;
581 }
582 
583 /* set_xcoords:
584  * Set x coords of nodes.
585  */
586 static void
587 set_xcoords(graph_t * g)
588 {
589  int i, j;
590  node_t *v;
591  rank_t *rank = GD_rank(g);
592 
593  for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
594  for (j = 0; j < rank[i].n; j++) {
595  v = rank[i].v[j];
596  ND_coord(v).x = ND_rank(v);
597  ND_rank(v) = i;
598  }
599  }
600 }
601 
602 /* adjustSimple:
603  * Expand cluster height by delta, adding half to top
604  * and half to bottom. If the bottom expansion exceeds the
605  * ht1 of the rank, shift the ranks in the cluster up.
606  * If the top expansion, including any shift from the bottom
607  * expansion, exceeds to ht2 of the rank, shift the ranks above
608  * the cluster up.
609  *
610  * FIX: There can be excess space between ranks. Not sure where this is
611  * coming from but it could be cleaned up.
612  */
613 static void adjustSimple(graph_t * g, int delta, int margin_total)
614 {
615  int r, bottom, deltop, delbottom;
616  graph_t *root = dot_root(g);
617  rank_t *rank = GD_rank(root);
618  int maxr = GD_maxrank(g);
619  int minr = GD_minrank(g);
620 
621  bottom = (delta+1) / 2;
622  delbottom = GD_ht1(g) + bottom - (rank[maxr].ht1 - margin_total);
623  if (delbottom > 0) {
624  for (r = maxr; r >= minr; r--) {
625  if (rank[r].n > 0)
626  ND_coord(rank[r].v[0]).y += delbottom;
627  }
628  deltop = GD_ht2(g) + (delta-bottom) + delbottom - (rank[minr].ht2 - margin_total);
629  }
630  else
631  deltop = GD_ht2(g) + (delta-bottom) - (rank[minr].ht2 - margin_total);
632  if (deltop > 0) {
633  for (r = minr-1; r >= GD_minrank(root); r--) {
634  if (rank[r].n > 0)
635  ND_coord(rank[r].v[0]).y += deltop;
636  }
637  }
638  GD_ht2(g) += (delta - bottom);
639  GD_ht1(g) += bottom;
640 }
641 
642 /* adjustRanks:
643  * Recursively adjust ranks to take into account
644  * wide cluster labels when rankdir=LR.
645  * We divide the extra space between the top and bottom.
646  * Adjust the ht1 and ht2 values in the process.
647  */
648 static void adjustRanks(graph_t * g, int margin_total)
649 {
650  double lht; /* label height */
651  double rht; /* height between top and bottom ranks */
652  int maxr, minr, margin;
653  int c;
654  double delta, ht1, ht2;
655 
656  rank_t *rank = GD_rank(dot_root(g));
657  if (g == dot_root(g))
658  margin = 0;
659  else
660  margin = late_int (g, G_margin, CL_OFFSET, 0);
661 
662  ht1 = GD_ht1(g);
663  ht2 = GD_ht2(g);
664 
665  for (c = 1; c <= GD_n_cluster(g); c++) {
666  graph_t *subg = GD_clust(g)[c];
667  adjustRanks(subg, margin+margin_total);
668  if (GD_maxrank(subg) == GD_maxrank(g))
669  ht1 = MAX(ht1, GD_ht1(subg) + margin);
670  if (GD_minrank(subg) == GD_minrank(g))
671  ht2 = MAX(ht2, GD_ht2(subg) + margin);
672  }
673 
674  GD_ht1(g) = ht1;
675  GD_ht2(g) = ht2;
676 
677  if ((g != dot_root(g)) && GD_label(g)) {
678  lht = MAX(GD_border(g)[LEFT_IX].y, GD_border(g)[RIGHT_IX].y);
679  maxr = GD_maxrank(g);
680  minr = GD_minrank(g);
681  rht = ND_coord(rank[minr].v[0]).y - ND_coord(rank[maxr].v[0]).y;
682  delta = lht - (rht + ht1 + ht2);
683  if (delta > 0) {
684  adjustSimple(g, delta, margin_total);
685  }
686  }
687 
688  /* update the global ranks */
689  if (g != dot_root(g)) {
690  rank[GD_minrank(g)].ht2 = MAX(rank[GD_minrank(g)].ht2, GD_ht2(g));
691  rank[GD_maxrank(g)].ht1 = MAX(rank[GD_maxrank(g)].ht1, GD_ht1(g));
692  }
693 }
694 
695 /* clust_ht:
696  * recursively compute cluster ht requirements. assumes GD_ht1(subg) and ht2
697  * are computed from primitive nodes only. updates ht1 and ht2 to reflect
698  * cluster nesting and labels. also maintains global rank ht1 and ht2.
699  * Return true if some cluster has a label.
700  */
701 static int clust_ht(Agraph_t * g)
702 {
703  int c;
704  double ht1, ht2;
705  graph_t *subg;
706  rank_t *rank = GD_rank(dot_root(g));
707  int margin, haveClustLabel = 0;
708 
709  if (g == dot_root(g))
710  margin = CL_OFFSET;
711  else
712  margin = late_int (g, G_margin, CL_OFFSET, 0);
713 
714  ht1 = GD_ht1(g);
715  ht2 = GD_ht2(g);
716 
717  /* account for sub-clusters */
718  for (c = 1; c <= GD_n_cluster(g); c++) {
719  subg = GD_clust(g)[c];
720  haveClustLabel |= clust_ht(subg);
721  if (GD_maxrank(subg) == GD_maxrank(g))
722  ht1 = MAX(ht1, GD_ht1(subg) + margin);
723  if (GD_minrank(subg) == GD_minrank(g))
724  ht2 = MAX(ht2, GD_ht2(subg) + margin);
725  }
726 
727  /* account for a possible cluster label in clusters */
728  /* room for root graph label is handled in dotneato_postprocess */
729  if ((g != dot_root(g)) && GD_label(g)) {
730  haveClustLabel = 1;
731  if (!GD_flip(agroot(g))) {
732  ht1 += GD_border(g)[BOTTOM_IX].y;
733  ht2 += GD_border(g)[TOP_IX].y;
734  }
735  }
736  GD_ht1(g) = ht1;
737  GD_ht2(g) = ht2;
738 
739  /* update the global ranks */
740  if (g != dot_root(g)) {
741  rank[GD_minrank(g)].ht2 = MAX(rank[GD_minrank(g)].ht2, ht2);
742  rank[GD_maxrank(g)].ht1 = MAX(rank[GD_maxrank(g)].ht1, ht1);
743  }
744 
745  return haveClustLabel;
746 }
747 
748 /* set y coordinates of nodes, a rank at a time */
749 static void set_ycoords(graph_t * g)
750 {
751  int i, j, r;
752  double ht2, maxht, delta, d0, d1;
753  node_t *n;
754  edge_t *e;
755  rank_t *rank = GD_rank(g);
756  graph_t *clust;
757  int lbl;
758 
759  ht2 = maxht = 0;
760 
761  /* scan ranks for tallest nodes. */
762  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
763  for (i = 0; i < rank[r].n; i++) {
764  n = rank[r].v[i];
765 
766  /* assumes symmetry, ht1 = ht2 */
767  ht2 = ND_ht(n) / 2;
768 
769 
770  /* have to look for high self-edge labels, too */
771  if (ND_other(n).list)
772  for (j = 0; (e = ND_other(n).list[j]); j++) {
773  if (agtail(e) == aghead(e)) {
774  if (ED_label(e))
775  ht2 = MAX(ht2, ED_label(e)->dimen.y / 2);
776  }
777  }
778 
779  /* update global rank ht */
780  if (rank[r].pht2 < ht2)
781  rank[r].pht2 = rank[r].ht2 = ht2;
782  if (rank[r].pht1 < ht2)
783  rank[r].pht1 = rank[r].ht1 = ht2;
784 
785  /* update nearest enclosing cluster rank ht */
786  if ((clust = ND_clust(n))) {
787  int yoff = (clust == g ? 0 : late_int (clust, G_margin, CL_OFFSET, 0));
788  if (ND_rank(n) == GD_minrank(clust))
789  GD_ht2(clust) = MAX(GD_ht2(clust), ht2 + yoff);
790  if (ND_rank(n) == GD_maxrank(clust))
791  GD_ht1(clust) = MAX(GD_ht1(clust), ht2 + yoff);
792  }
793  }
794  }
795 
796  /* scan sub-clusters */
797  lbl = clust_ht(g);
798 
799  /* make the initial assignment of ycoords to leftmost nodes by ranks */
800  maxht = 0;
801  r = GD_maxrank(g);
802  (ND_coord(rank[r].v[0])).y = rank[r].ht1;
803  while (--r >= GD_minrank(g)) {
804  d0 = rank[r + 1].pht2 + rank[r].pht1 + GD_ranksep(g); /* prim node sep */
805  d1 = rank[r + 1].ht2 + rank[r].ht1 + CL_OFFSET; /* cluster sep */
806  delta = MAX(d0, d1);
807  if (rank[r].n > 0) /* this may reflect some problem */
808  (ND_coord(rank[r].v[0])).y = (ND_coord(rank[r + 1].v[0])).y + delta;
809 #ifdef DEBUG
810  else
811  fprintf(stderr, "dot set_ycoords: rank %d is empty\n",
812  rank[r].n);
813 #endif
814  maxht = MAX(maxht, delta);
815  }
816 
817  /* If there are cluster labels and the drawing is rotated, we need special processing to
818  * allocate enough room. We use adjustRanks for this, and then recompute the maxht if
819  * the ranks are to be equally spaced. This seems simpler and appears to work better than
820  * handling equal spacing as a special case.
821  */
822  if (lbl && GD_flip(g)) {
823  adjustRanks(g, 0);
824  if (GD_exact_ranksep(g)) { /* recompute maxht */
825  maxht = 0;
826  r = GD_maxrank(g);
827  d0 = (ND_coord(rank[r].v[0])).y;
828  while (--r >= GD_minrank(g)) {
829  d1 = (ND_coord(rank[r].v[0])).y;
830  delta = d1 - d0;
831  maxht = MAX(maxht, delta);
832  d0 = d1;
833  }
834  }
835  }
836 
837  /* re-assign if ranks are equally spaced */
838  if (GD_exact_ranksep(g)) {
839  for (r = GD_maxrank(g) - 1; r >= GD_minrank(g); r--)
840  if (rank[r].n > 0) /* this may reflect the same problem :-() */
841  (ND_coord(rank[r].v[0])).y=
842  (ND_coord(rank[r + 1].v[0])).y + maxht;
843  }
844 
845  /* copy ycoord assignment from leftmost nodes to others */
846  for (n = GD_nlist(g); n; n = ND_next(n))
847  ND_coord(n).y = (ND_coord(rank[ND_rank(n)].v[0])).y;
848 }
849 
850 /* dot_compute_bb:
851  * Compute bounding box of g.
852  * The x limits of clusters are given by the x positions of ln and rn.
853  * This information is stored in the rank field, since it was calculated
854  * using network simplex.
855  * For the root graph, we don't enforce all the constraints on lr and
856  * rn, so we traverse the nodes and subclusters.
857  */
858 static void dot_compute_bb(graph_t * g, graph_t * root)
859 {
860  int r, c;
861  double x, offset;
862  node_t *v;
863  pointf LL, UR;
864 
865  if (g == dot_root(g)) {
866  LL.x = (double)(INT_MAX);
867  UR.x = (double)(-INT_MAX);
868  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
869  int rnkn = GD_rank(g)[r].n;
870  if (rnkn == 0)
871  continue;
872  if ((v = GD_rank(g)[r].v[0]) == NULL)
873  continue;
874  for (c = 1; (ND_node_type(v) != NORMAL) && c < rnkn; c++)
875  v = GD_rank(g)[r].v[c];
876  if (ND_node_type(v) == NORMAL) {
877  x = ND_coord(v).x - ND_lw(v);
878  LL.x = MIN(LL.x, x);
879  }
880  else continue;
881  /* At this point, we know the rank contains a NORMAL node */
882  v = GD_rank(g)[r].v[rnkn - 1];
883  for (c = rnkn-2; ND_node_type(v) != NORMAL; c--)
884  v = GD_rank(g)[r].v[c];
885  x = ND_coord(v).x + ND_rw(v);
886  UR.x = MAX(UR.x, x);
887  }
888  offset = CL_OFFSET;
889  for (c = 1; c <= GD_n_cluster(g); c++) {
890  x = (double)(GD_bb(GD_clust(g)[c]).LL.x - offset);
891  LL.x = MIN(LL.x, x);
892  x = (double)(GD_bb(GD_clust(g)[c]).UR.x + offset);
893  UR.x = MAX(UR.x, x);
894  }
895  } else {
896  LL.x = (double)(ND_rank(GD_ln(g)));
897  UR.x = (double)(ND_rank(GD_rn(g)));
898  }
899  LL.y = ND_coord(GD_rank(root)[GD_maxrank(g)].v[0]).y - GD_ht1(g);
900  UR.y = ND_coord(GD_rank(root)[GD_minrank(g)].v[0]).y + GD_ht2(g);
901  GD_bb(g).LL = LL;
902  GD_bb(g).UR = UR;
903 }
904 
905 static void rec_bb(graph_t * g, graph_t * root)
906 {
907  int c;
908  for (c = 1; c <= GD_n_cluster(g); c++)
909  rec_bb(GD_clust(g)[c], root);
910  dot_compute_bb(g, root);
911 }
912 
913 /* scale_bb:
914  * Recursively rescale all bounding boxes using scale factors
915  * xf and yf. We assume all the bboxes have been computed.
916  */
917 static void scale_bb(graph_t * g, graph_t * root, double xf, double yf)
918 {
919  int c;
920 
921  for (c = 1; c <= GD_n_cluster(g); c++)
922  scale_bb(GD_clust(g)[c], root, xf, yf);
923  GD_bb(g).LL.x *= xf;
924  GD_bb(g).LL.y *= yf;
925  GD_bb(g).UR.x *= xf;
926  GD_bb(g).UR.y *= yf;
927 }
928 
929 /* adjustAspectRatio:
930  */
931 static void adjustAspectRatio (graph_t* g, aspect_t* asp)
932 {
933  double AR = (GD_bb(g).UR.x - GD_bb(g).LL.x)/(GD_bb(g).UR.y - GD_bb(g).LL.y);
934  if (Verbose) {
935  fprintf(stderr, "AR=%0.4lf\t Area= %0.4lf\t", AR, (double)(GD_bb(g).UR.x - GD_bb(g).LL.x)*(GD_bb(g).UR.y - GD_bb(g).LL.y)/10000.0);
936  fprintf(stderr, "Dummy=%d\n", countDummyNodes(g));
937  }
938  if (AR > 1.1*asp->targetAR) {
939  asp->nextIter = (int)(asp->targetAR * (double)(asp->curIterations - asp->prevIterations)/(AR));
940  }
941  else if (AR <= 0.8 * asp->targetAR) {
942  asp->nextIter = -1;
943  if (Verbose)
944  fprintf(stderr, "Going to apply another expansion.\n");
945  }
946  else {
947  asp->nextIter = 0;
948  }
949  if (Verbose)
950  fprintf(stderr, "next#iter=%d\n", asp->nextIter);
951 }
952 
953 /* set_aspect:
954  * Set bounding boxes and, if ratio is set, rescale graph.
955  * Note that if some dimension shrinks, there may be problems
956  * with labels.
957  */
958 static void set_aspect(graph_t * g, aspect_t* asp)
959 {
960  double xf = 0.0, yf = 0.0, actual, desired;
961  node_t *n;
962  boolean scale_it, filled;
963  point sz;
964 
965  rec_bb(g, g);
966  if ((GD_maxrank(g) > 0) && (GD_drawing(g)->ratio_kind)) {
967  sz.x = GD_bb(g).UR.x - GD_bb(g).LL.x;
968  sz.y = GD_bb(g).UR.y - GD_bb(g).LL.y; /* normalize */
969  if (GD_flip(g)) {
970  int t = sz.x;
971  sz.x = sz.y;
972  sz.y = t;
973  }
974  scale_it = TRUE;
975  if (GD_drawing(g)->ratio_kind == R_AUTO)
976  filled = idealsize(g, .5);
977  else
978  filled = (GD_drawing(g)->ratio_kind == R_FILL);
979  if (filled) {
980  /* fill is weird because both X and Y can stretch */
981  if (GD_drawing(g)->size.x <= 0)
982  scale_it = FALSE;
983  else {
984  xf = (double) GD_drawing(g)->size.x / (double) sz.x;
985  yf = (double) GD_drawing(g)->size.y / (double) sz.y;
986  if ((xf < 1.0) || (yf < 1.0)) {
987  if (xf < yf) {
988  yf = yf / xf;
989  xf = 1.0;
990  } else {
991  xf = xf / yf;
992  yf = 1.0;
993  }
994  }
995  }
996  } else if (GD_drawing(g)->ratio_kind == R_EXPAND) {
997  if (GD_drawing(g)->size.x <= 0)
998  scale_it = FALSE;
999  else {
1000  xf = (double) GD_drawing(g)->size.x /
1001  (double) GD_bb(g).UR.x;
1002  yf = (double) GD_drawing(g)->size.y /
1003  (double) GD_bb(g).UR.y;
1004  if ((xf > 1.0) && (yf > 1.0)) {
1005  double scale = MIN(xf, yf);
1006  xf = yf = scale;
1007  } else
1008  scale_it = FALSE;
1009  }
1010  } else if (GD_drawing(g)->ratio_kind == R_VALUE) {
1011  desired = GD_drawing(g)->ratio;
1012  actual = ((double) sz.y) / ((double) sz.x);
1013  if (actual < desired) {
1014  yf = desired / actual;
1015  xf = 1.0;
1016  } else {
1017  xf = actual / desired;
1018  yf = 1.0;
1019  }
1020  } else
1021  scale_it = FALSE;
1022  if (scale_it) {
1023  if (GD_flip(g)) {
1024  double t = xf;
1025  xf = yf;
1026  yf = t;
1027  }
1028  for (n = GD_nlist(g); n; n = ND_next(n)) {
1029  ND_coord(n).x = ROUND(ND_coord(n).x * xf);
1030  ND_coord(n).y = ROUND(ND_coord(n).y * yf);
1031  }
1032  scale_bb(g, g, xf, yf);
1033  }
1034  }
1035 
1036  if (asp) adjustAspectRatio (g, asp);
1037 }
1038 
1039 static point resize_leaf(node_t * leaf, point lbound)
1040 {
1041  gv_nodesize(leaf, GD_flip(agraphof(leaf)));
1042  ND_coord(leaf).y = lbound.y;
1043  ND_coord(leaf).x = lbound.x + ND_lw(leaf);
1044  lbound.x = lbound.x + ND_lw(leaf) + ND_rw(leaf) + GD_nodesep(agraphof(leaf));
1045  return lbound;
1046 }
1047 
1048 static point place_leaf(graph_t* ing, node_t * leaf, point lbound, int order)
1049 {
1050  node_t *leader;
1051  graph_t *g = dot_root(ing);
1052 
1053  leader = UF_find(leaf);
1054  if (leaf != leader)
1055  fast_nodeapp(leader, leaf);
1056  ND_order(leaf) = order;
1057  ND_rank(leaf) = ND_rank(leader);
1058  GD_rank(g)[ND_rank(leaf)].v[ND_order(leaf)] = leaf;
1059  return resize_leaf(leaf, lbound);
1060 }
1061 
1062 /* make space for the leaf nodes of each rank */
1063 static void make_leafslots(graph_t * g)
1064 {
1065  int i, j, r;
1066  node_t *v;
1067 
1068  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1069  j = 0;
1070  for (i = 0; i < GD_rank(g)[r].n; i++) {
1071  v = GD_rank(g)[r].v[i];
1072  ND_order(v) = j;
1073  if (ND_ranktype(v) == LEAFSET)
1074  j = j + ND_UF_size(v);
1075  else
1076  j++;
1077  }
1078  if (j <= GD_rank(g)[r].n)
1079  continue;
1080  GD_rank(g)[r].v = ALLOC(j + 1, GD_rank(g)[r].v, node_t *);
1081  for (i = GD_rank(g)[r].n - 1; i >= 0; i--) {
1082  v = GD_rank(g)[r].v[i];
1083  GD_rank(g)[r].v[ND_order(v)] = v;
1084  }
1085  GD_rank(g)[r].n = j;
1086  GD_rank(g)[r].v[j] = NULL;
1087  }
1088 }
1089 
1090 static void do_leaves(graph_t * g, node_t * leader)
1091 {
1092  int j;
1093  point lbound;
1094  node_t *n;
1095  edge_t *e;
1096 
1097  if (ND_UF_size(leader) <= 1)
1098  return;
1099  lbound.x = ND_coord(leader).x - ND_lw(leader);
1100  lbound.y = ND_coord(leader).y;
1101  lbound = resize_leaf(leader, lbound);
1102  if (ND_out(leader).size > 0) { /* in-edge leaves */
1103  n = aghead(ND_out(leader).list[0]);
1104  j = ND_order(leader) + 1;
1105  for (e = agfstin(g, n); e; e = agnxtin(g, e)) {
1106  edge_t *e1 = AGMKOUT(e);
1107  if ((agtail(e1) != leader) && (UF_find(agtail(e1)) == leader)) {
1108  lbound = place_leaf(g, agtail(e1), lbound, j++);
1109  unmerge_oneway(e1);
1110  elist_append(e1, ND_in(aghead(e1)));
1111  }
1112  }
1113  } else { /* out edge leaves */
1114  n = agtail(ND_in(leader).list[0]);
1115  j = ND_order(leader) + 1;
1116  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1117  if ((aghead(e) != leader) && (UF_find(aghead(e)) == leader)) {
1118  lbound = place_leaf(g, aghead(e), lbound, j++);
1119  unmerge_oneway(e);
1120  elist_append(e, ND_out(agtail(e)));
1121  }
1122  }
1123  }
1124 }
1125 
1126 int ports_eq(edge_t * e, edge_t * f)
1127 {
1128  return ((ED_head_port(e).defined == ED_head_port(f).defined)
1129  && (((ED_head_port(e).p.x == ED_head_port(f).p.x) &&
1130  (ED_head_port(e).p.y == ED_head_port(f).p.y))
1131  || (ED_head_port(e).defined == FALSE))
1132  && (((ED_tail_port(e).p.x == ED_tail_port(f).p.x) &&
1133  (ED_tail_port(e).p.y == ED_tail_port(f).p.y))
1134  || (ED_tail_port(e).defined == FALSE))
1135  );
1136 }
1137 
1138 static void expand_leaves(graph_t * g)
1139 {
1140  int i, d;
1141  node_t *n;
1142  edge_t *e, *f;
1143 
1144  make_leafslots(g);
1145  for (n = GD_nlist(g); n; n = ND_next(n)) {
1146  if (ND_inleaf(n))
1147  do_leaves(g, ND_inleaf(n));
1148  if (ND_outleaf(n))
1149  do_leaves(g, ND_outleaf(n));
1150  if (ND_other(n).list)
1151  for (i = 0; (e = ND_other(n).list[i]); i++) {
1152  if ((d = ND_rank(aghead(e)) - ND_rank(aghead(e))) == 0)
1153  continue;
1154  f = ED_to_orig(e);
1155  if (ports_eq(e, f) == FALSE) {
1156  zapinlist(&(ND_other(n)), e);
1157  if (d == 1)
1158  fast_edge(e);
1159  /*else unitize(e); ### */
1160  i--;
1161  }
1162  }
1163  }
1164 }
1165 
1166 /* make_lrvn:
1167  * Add left and right slacknodes to a cluster which
1168  * are used in the LP to constrain nodes not in g but
1169  * sharing its ranks to be to the left or right of g
1170  * by a specified amount.
1171  * The slacknodes ln and rn give the x position of the
1172  * left and right side of the cluster's bounding box. In
1173  * particular, any cluster labels on the left or right side
1174  * are inside.
1175  * If a cluster has a label, and we have rankdir!=LR, we make
1176  * sure the cluster is wide enough for the label. Note that
1177  * if the label is wider than the cluster, the nodes in the
1178  * cluster may not be centered.
1179  */
1180 static void make_lrvn(graph_t * g)
1181 {
1182  node_t *ln, *rn;
1183 
1184  if (GD_ln(g))
1185  return;
1186  ln = virtual_node(dot_root(g));
1187  ND_node_type(ln) = SLACKNODE;
1188  rn = virtual_node(dot_root(g));
1189  ND_node_type(rn) = SLACKNODE;
1190 
1191  if (GD_label(g) && (g != dot_root(g)) && !GD_flip(agroot(g))) {
1192  int w = MAX(GD_border(g)[BOTTOM_IX].x, GD_border(g)[TOP_IX].x);
1193  make_aux_edge(ln, rn, w, 0);
1194  }
1195 
1196  GD_ln(g) = ln;
1197  GD_rn(g) = rn;
1198 }
1199 
1200 /* contain_nodes:
1201  * make left and right bounding box virtual nodes ln and rn
1202  * constrain interior nodes
1203  */
1204 static void contain_nodes(graph_t * g)
1205 {
1206  int margin, r;
1207  node_t *ln, *rn, *v;
1208 
1209  margin = late_int (g, G_margin, CL_OFFSET, 0);
1210  make_lrvn(g);
1211  ln = GD_ln(g);
1212  rn = GD_rn(g);
1213  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1214  if (GD_rank(g)[r].n == 0)
1215  continue;
1216  v = GD_rank(g)[r].v[0];
1217  if (v == NULL) {
1218  agerr(AGERR, "contain_nodes clust %s rank %d missing node\n",
1219  agnameof(g), r);
1220  continue;
1221  }
1222  make_aux_edge(ln, v,
1223  ND_lw(v) + margin + GD_border(g)[LEFT_IX].x, 0);
1224  v = GD_rank(g)[r].v[GD_rank(g)[r].n - 1];
1225  make_aux_edge(v, rn,
1226  ND_rw(v) + margin + GD_border(g)[RIGHT_IX].x, 0);
1227  }
1228 }
1229 
1230 /* idealsize:
1231  * set g->drawing->size to a reasonable default.
1232  * returns a boolean to indicate if drawing is to
1233  * be scaled and filled */
1234 static boolean idealsize(graph_t * g, double minallowed)
1235 {
1236  double xf, yf, f, R;
1237  pointf b, relpage, margin;
1238 
1239  /* try for one page */
1240  relpage = GD_drawing(g)->page;
1241  if (relpage.x < 0.001 || relpage.y < 0.001)
1242  return FALSE; /* no page was specified */
1243  margin = GD_drawing(g)->margin;
1244  relpage = sub_pointf(relpage, margin);
1245  relpage = sub_pointf(relpage, margin);
1246  b.x = GD_bb(g).UR.x;
1247  b.y = GD_bb(g).UR.y;
1248  xf = relpage.x / b.x;
1249  yf = relpage.y / b.y;
1250  if ((xf >= 1.0) && (yf >= 1.0))
1251  return FALSE; /* fits on one page */
1252 
1253  f = MIN(xf, yf);
1254  xf = yf = MAX(f, minallowed);
1255 
1256  R = ceil((xf * b.x) / relpage.x);
1257  xf = ((R * relpage.x) / b.x);
1258  R = ceil((yf * b.y) / relpage.y);
1259  yf = ((R * relpage.y) / b.y);
1260  GD_drawing(g)->size.x = b.x * xf;
1261  GD_drawing(g)->size.y = b.y * yf;
1262  return TRUE;
1263 }
double pht1
Definition: types.h:217
int curIterations
Definition: aspect.h:21
#define GD_label(g)
Definition: types.h:381
#define MAX(a, b)
Definition: agerror.c:17
#define LEFT_IX
Definition: const.h:115
#define ND_rank(n)
Definition: types.h:529
Definition: cgraph.h:388
#define GD_has_labels(g)
Definition: types.h:372
#define GD_nlist(g)
Definition: types.h:401
int nextIter
Definition: aspect.h:22
#define elist_append(item, L)
Definition: types.h:272
double ht1
Definition: types.h:215
#define MIN(a, b)
Definition: arith.h:35
#define GD_n_cluster(g)
Definition: types.h:396
#define GD_border(g)
Definition: types.h:362
void fast_nodeapp(Agnode_t *, Agnode_t *)
Definition: fastgr.c:218
Agedge_t * find_fast_edge(Agnode_t *, Agnode_t *)
Definition: fastgr.c:42
#define ND_inleaf(n)
Definition: types.h:508
CGRAPH_API Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition: edge.c:56
#define ND_node_type(n)
Definition: types.h:518
#define ALLOC(size, ptr, type)
Definition: memory.h:41
#define ED_head_port(e)
Definition: types.h:591
#define ND_save_in(n)
Definition: types.h:532
#define ROUND(f)
Definition: arith.h:84
#define assert(x)
Definition: cghdr.h:47
Agedge_t in
Definition: cgraph.h:147
Agnode_t * virtual_node(Agraph_t *)
Definition: fastgr.c:240
#define GD_ht2(g)
Definition: types.h:378
Definition: geom.h:28
#define ND_UF_size(n)
Definition: types.h:493
EXTERN Agsym_t * G_margin
Definition: globals.h:88
#define ED_to_orig(e)
Definition: types.h:601
#define ED_weight(e)
Definition: types.h:606
#define ED_label(e)
Definition: types.h:592
void unmerge_oneway(Agedge_t *)
Definition: fastgr.c:353
double pht2
Definition: types.h:218
Agobj_t base
Definition: cgraph.h:134
#define GD_ln(g)
Definition: types.h:388
Definition: types.h:226
#define alloc_elist(n, L)
Definition: types.h:273
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
CGRAPH_API int agcontains(Agraph_t *, void *)
Definition: obj.c:245
CGRAPH_API Agraph_t * agroot(void *obj)
Definition: obj.c:169
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
#define AGOUTEDGE
Definition: cgraph.h:102
void dot_concentrate(graph_t *g)
Definition: conc.c:197
int x
Definition: geom.h:26
#define GD_ranksep(g)
Definition: types.h:406
#define AGTYPE(obj)
Definition: cgraph.h:113
#define ND_clust(n)
Definition: types.h:495
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
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
#define BOTTOM_IX
Definition: const.h:112
#define ED_tail_port(e)
Definition: types.h:600
int rank(graph_t *g, int balance, int maxiter)
Definition: ns.c:866
Definition: types.h:261
int
Definition: grammar.c:1264
#define ND_ht(n)
Definition: types.h:506
Definition: types.h:226
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
Agedge_t out
Definition: cgraph.h:147
double y
Definition: geom.h:28
#define ND_order(n)
Definition: types.h:520
#define SLACKNODE
Definition: const.h:29
int selfRightSpace(edge_t *e)
Definition: splines.c:1163
double targetAR
Definition: aspect.h:18
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define ND_mval(n)
Definition: types.h:515
#define VIRTUAL
Definition: const.h:28
#define GD_maxrank(g)
Definition: types.h:389
int n
Definition: types.h:211
void mark_lowclusters(Agraph_t *root)
Definition: cluster.c:395
htmllabel_t * lbl
Definition: htmlparse.c:81
#define LEAFSET
Definition: const.h:42
#define ND_rw(n)
Definition: types.h:531
double ht2
Definition: types.h:216
edge_t ** list
Definition: types.h:262
#define AGMKOUT(e)
Definition: cgraph.h:404
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
int prevIterations
Definition: aspect.h:20
Definition: cgraph.h:83
#define GD_flip(g)
Definition: types.h:385
Agobj_t base
Definition: cgraph.h:140
Agraph_t * dot_root(void *p)
Definition: dotinit.c:513
#define ND_outleaf(n)
Definition: types.h:523
#define CL_OFFSET
Definition: const.h:155
if(aagss+aagstacksize-1<=aagssp)
Definition: grammar.c:1332
#define GD_exact_ranksep(g)
Definition: types.h:367
Definition: types.h:226
#define ND_lw(n)
Definition: types.h:513
#define ND_alg(n)
Definition: types.h:490
EXTERN unsigned char Concentrate
Definition: globals.h:76
#define NULL
Definition: logic.h:39
node_t ** v
Definition: types.h:212
Definition: geom.h:26
double x
Definition: geom.h:28
#define ND_in(n)
Definition: types.h:507
#define ND_coord(n)
Definition: types.h:496
#define right(i)
Definition: closest.c:87
#define ND_next(n)
Definition: types.h:517
EXTERN unsigned char Verbose
Definition: globals.h:64
void zapinlist(elist *, Agedge_t *)
Definition: fastgr.c:100
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
Agrec_t * data
Definition: cgraph.h:109
#define ND_out(n)
Definition: types.h:522
int size
Definition: types.h:263
#define ND_ranktype(n)
Definition: types.h:530
#define ND_other(n)
Definition: types.h:521
#define left
Definition: dthdr.h:16
#define AGINEDGE
Definition: cgraph.h:103
CGRAPH_API Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition: edge.c:70
void gv_nodesize(node_t *n, boolean flip)
Definition: utils.c:1970
#define GD_ht1(g)
Definition: types.h:377
int countDummyNodes(graph_t *g)
Definition: aspect.c:129
#define GD_bb(g)
Definition: types.h:357
#define GD_nodesep(g)
Definition: types.h:402
#define GD_minrank(g)
Definition: types.h:391
Agedge_t * make_aux_edge(Agnode_t *, Agnode_t *, double, int)
Definition: position.c:173
#define RIGHT_IX
Definition: const.h:113
int flat_edges(Agraph_t *)
Definition: flat.c:260
Agraph_t * root
Definition: cgraph.h:247
#define ND_flat_out(n)
Definition: types.h:499
#define GD_rank(g)
Definition: types.h:404
Definition: types.h:210
#define GD_rn(g)
Definition: types.h:407
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define NORMAL
Definition: const.h:27
#define GD_drawing(g)
Definition: types.h:356
#define EDGE_LABEL
Definition: const.h:184
#define ND_save_out(n)
Definition: types.h:533
void dot_position(Agraph_t *, aspect_t *)
Definition: position.c:120
int y
Definition: geom.h:26
#define ND_prev(n)
Definition: types.h:527
#define ED_dist(e)
Definition: types.h:605
char * el(GVJ_t *job, char *template,...)
int ports_eq(edge_t *, edge_t *)
Definition: position.c:1126
#define FALSE
Definition: cgraph.h:35
#define TOP_IX
Definition: const.h:114
#define free_list(L)
Definition: types.h:274
Agedge_t * fast_edge(Agedge_t *)
Definition: fastgr.c:74
#define ED_minlen(e)
Definition: types.h:595
#define INT_MAX
Definition: arith.h:52
#define NEW(t)
Definition: memory.h:35
#define TRUE
Definition: cgraph.h:38