Graphviz  2.41.20170921.2350
patchwork.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 <stdio.h>
15 #include <stdlib.h>
16 #include <patchwork.h>
17 #include <tree_map.h>
18 #include "render.h"
19 
20 typedef struct treenode_t treenode_t;
21 struct treenode_t {
22  double area;
23  double child_area;
26  union {
29  } u;
30  int kind;
32 };
33 
34 #define DFLT_SZ 1.0
35 #define SCALE 1000.0 /* scale up so that 1 is a reasonable default size */
36 
37 #ifdef DEBUG
38 void dumpTree (treenode_t* r, int ind)
39 {
40  int i;
41  treenode_t* cp;
42 
43  for (i=0; i < ind; i++) fputs(" ", stderr);
44  fprintf (stderr, "%s (%f)\n", (r->kind == AGNODE?agnameof(r->u.n):agnameof(r->u.subg)), r->area);
45  for (cp = r->leftchild; cp; cp = cp->rightsib)
46  dumpTree (cp, ind+1);
47 }
48 #endif
49 
50 /* fullArea:
51  * Allow extra area for specified inset. Assume p->kind = AGRAPH
52  * and p->child_area is set. At present, inset is additive; we
53  * may want to allow a multiplicative inset as well.
54  */
55 static double fullArea (treenode_t* p, attrsym_t* mp)
56 {
57  double m = late_double (p->u.subg, mp, 0, 0);
58  if (m == 0) return p->child_area;
59  else {
60  double wid = (2.0*m + sqrt(p->child_area));
61  return wid*wid;
62  }
63 }
64 
65 static double getArea (void* obj, attrsym_t* ap)
66 {
67  double area = late_double (obj, ap, DFLT_SZ, 0);
68  if (area == 0) area = DFLT_SZ;
69  area *= SCALE;
70  return area;
71 }
72 
73 /* mkTreeNode:
74  */
75 static treenode_t* mkTreeNode (Agnode_t* n, attrsym_t* ap)
76 {
78 
79  p->area = getArea (n, ap);
80  p->kind = AGNODE;
81  p->u.n = n;
82 
83  return p;
84 }
85 
86 #define INSERT(cp) if(!first) first=cp; if(prev) prev->rightsib=cp; prev=cp;
87 
88 /* mkTree:
89  * Recursively build tree from graph
90  * Pre-condition: agnnodes(g) != 0
91  */
92 static treenode_t *mkTree (Agraph_t * g, attrsym_t* gp, attrsym_t* ap, attrsym_t* mp)
93 {
95  Agraph_t *subg;
96  Agnode_t *n;
97  treenode_t *cp;
98  treenode_t *first = 0;
99  treenode_t *prev = 0;
100  int i, n_children = 0;
101  double area = 0;
102 
103  p->kind = AGRAPH;
104  p->u.subg = g;
105 
106  for (i = 1; i <= GD_n_cluster(g); i++) {
107  subg = GD_clust(g)[i];
108  cp = mkTree (subg, gp, ap, mp);
109  n_children++;
110  area += cp->area;
111  INSERT(cp);
112  }
113 
114  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
115  if (SPARENT(n))
116  continue;
117  cp = mkTreeNode (n, ap);
118  n_children++;
119  area += cp->area;
120  INSERT(cp);
121  SPARENT(n) = g;
122  }
123 
124  p->n_children = n_children;
125  if (n_children) {
126  p->child_area = area;
127  p->area = fullArea (p, mp);
128  }
129  else {
130  p->area = getArea (g, gp);
131  }
132  p->leftchild = first;
133 
134  return p;
135 }
136 
137 static int nodecmp (treenode_t** p0, treenode_t** p1)
138 {
139  double diff = (*p0)->area - (*p1)->area;
140 
141  if (diff < 0) return 1;
142  else if (diff > 0) return -1;
143  else return 0;
144 }
145 
146 static void layoutTree(treenode_t * tree)
147 {
148  rectangle *recs;
149  treenode_t** nodes;
150  double* areas_sorted;
151  int i, nc;
152  treenode_t* cp;
153 
154  /* if (tree->kind == AGNODE) return; */
155  if (tree->n_children == 0) return;
156 
157  nc = tree->n_children;
158  nodes = N_NEW(nc, treenode_t*);
159  cp = tree->leftchild;
160  for (i = 0; i < nc; i++) {
161  nodes[i] = cp;
162  cp = cp->rightsib;
163  }
164 
165  qsort (nodes, nc, sizeof(treenode_t*), (qsort_cmpf)nodecmp);
166  areas_sorted = N_NEW(nc,double);
167  for (i = 0; i < nc; i++) {
168  areas_sorted[i] = nodes[i]->area;
169  }
170  if (tree->area == tree->child_area)
171  recs = tree_map(nc, areas_sorted, tree->r);
172  else {
173  rectangle crec;
174  double disc, delta, m, h = tree->r.size[1], w = tree->r.size[0];
175  crec.x[0] = tree->r.x[0];
176  crec.x[1] = tree->r.x[1];
177  delta = h - w;
178  disc = sqrt(delta*delta + 4.0*tree->child_area);
179  m = (h + w - disc)/2.0;
180  crec.size[0] = w - m;
181  crec.size[1] = h - m;
182  recs = tree_map(nc, areas_sorted, crec);
183  }
184  if (Verbose)
185  fprintf (stderr, "rec %f %f %f %f\n", tree->r.x[0], tree->r.x[1], tree->r.size[0], tree->r.size[1]);
186  for (i = 0; i < nc; i++) {
187  nodes[i]->r = recs[i];
188  if (Verbose)
189  fprintf (stderr, "%f - %f %f %f %f = %f (%f %f %f %f)\n", areas_sorted[i],
190  recs[i].x[0]-recs[i].size[0]*0.5, recs[i].x[1]-recs[i].size[1]*0.5,
191  recs[i].x[0]+recs[i].size[0]*0.5, recs[i].x[1]+recs[i].size[1]*0.5, recs[i].size[0]*recs[i].size[1],
192  recs[i].x[0], recs[i].x[1], recs[i].size[0], recs[i].size[1]);
193 
194  }
195  free (nodes);
196  free (areas_sorted);
197  free (recs);
198 
199  cp = tree->leftchild;
200  for (i = 0; i < nc; i++) {
201  if (cp->kind == AGRAPH)
202  layoutTree (cp);
203  cp = cp->rightsib;
204  }
205 }
206 
207 static void finishNode(node_t * n)
208 {
209  char buf [40];
210  if (N_fontsize) {
211  char* str = agxget(n, N_fontsize);
212  if (*str == '\0') {
213  sprintf (buf, "%.03f", ND_ht(n)*0.7);
214  agxset(n, N_fontsize, buf);
215  }
216  }
217  common_init_node (n);
218 }
219 
220 static void walkTree(treenode_t * tree)
221 {
222  treenode_t *p;
223  Agnode_t *n;
224  pointf center;
225  rectangle rr;
226  boxf r;
227  double x0, y0, wd, ht;
228 
229  if (tree->kind == AGRAPH) {
230  for (p = tree->leftchild; p; p = p->rightsib)
231  walkTree (p);
232  x0 = tree->r.x[0];
233  y0 = tree->r.x[1];
234  wd = tree->r.size[0];
235  ht = tree->r.size[1];
236  r.LL.x = x0 - wd/2.0;
237  r.LL.y = y0 - ht/2.0;
238  r.UR.x = r.LL.x + wd;
239  r.UR.y = r.LL.y + ht;
240  GD_bb(tree->u.subg) = r;
241  }
242  else {
243  rr = tree->r;
244  center.x = rr.x[0];
245  center.y = rr.x[1];
246 
247  n = tree->u.n;
248  ND_coord(n) = center;
249  ND_width(n) = PS2INCH(rr.size[0]);
250  ND_height(n) = PS2INCH(rr.size[1]);
251  gv_nodesize(n, GD_flip(agraphof(n)));
252  finishNode(n);
253  if (Verbose)
254  fprintf(stderr,"%s coord %.5g %.5g ht %f width %f\n",
255  agnameof(n), ND_coord(n).x, ND_coord(n).y, ND_ht(n), ND_xsize(n));
256  }
257 }
258 
259 /* freeTree:
260  */
261 static void freeTree (treenode_t* tp)
262 {
263  treenode_t* cp = tp->leftchild;
264  int i, nc = tp->n_children;
265 
266  for (i = 0; i < nc; i++) {
267  freeTree (cp);
268  cp = cp->rightsib;
269  }
270  free (tp);
271 }
272 
273 /* patchworkLayout:
274  */
276 {
277  treenode_t* root;
278  attrsym_t * ap = agfindnodeattr(g, "area");
279  attrsym_t * gp = agfindgraphattr(g, "area");
280  attrsym_t * mp = agfindgraphattr(g, "inset");
281  double total;
282 
283  root = mkTree (g,gp,ap,mp);
284  total = root->area;
285  root->r = rectangle_new(0, 0, sqrt(total + 0.1), sqrt(total + 0.1));
286  layoutTree(root);
287  walkTree(root);
288  freeTree (root);
289 }
void patchworkLayout(Agraph_t *g)
Definition: patchwork.c:275
#define N_NEW(n, t)
Definition: memory.h:36
Agnode_t * n
Definition: patchwork.c:28
int kind
Definition: patchwork.c:30
#define GD_n_cluster(g)
Definition: types.h:396
int agxset(void *obj, Agsym_t *sym, char *value)
Definition: attr.c:468
EXTERN Agsym_t * N_fontsize
Definition: globals.h:95
Definition: geom.h:28
double area
Definition: patchwork.c:22
void common_init_node(node_t *n)
Definition: utils.c:629
#define SPARENT(n)
Definition: patchwork.h:29
Agraph_t * subg
Definition: patchwork.c:27
#define PS2INCH(a_points)
Definition: geom.h:69
CGRAPH_API Agraph_t * agraphof(void *obj)
Definition: obj.c:185
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
#define ND_ht(n)
Definition: types.h:506
rectangle * tree_map(int n, real *area, rectangle fillrec)
Definition: tree_map.c:100
union treenode_t::@26 u
double y
Definition: geom.h:28
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define ND_height(n)
Definition: types.h:504
rectangle rectangle_new(real x, real y, real width, real height)
Definition: tree_map.c:120
rectangle r
Definition: patchwork.c:24
treenode_t * rightsib
Definition: patchwork.c:25
int(* qsort_cmpf)(const void *, const void *)
Definition: types.h:45
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define DFLT_SZ
Definition: patchwork.c:34
#define GD_clust(g)
Definition: types.h:364
#define AGNODE
Definition: cgraph.h:101
#define GD_flip(g)
Definition: types.h:385
#define ND_width(n)
Definition: types.h:542
#define agfindgraphattr(g, a)
Definition: types.h:612
double x
Definition: geom.h:28
#define SCALE
Definition: patchwork.c:35
#define ND_coord(n)
Definition: types.h:496
double late_double(void *obj, attrsym_t *attr, double def, double low)
Definition: utils.c:87
EXTERN unsigned char Verbose
Definition: globals.h:64
int n_children
Definition: patchwork.c:31
pointf LL
Definition: geom.h:35
double child_area
Definition: patchwork.c:23
real size[2]
Definition: tree_map.h:21
treenode_t * leftchild
Definition: patchwork.c:25
void gv_nodesize(node_t *n, boolean flip)
Definition: utils.c:1970
#define ND_xsize(n)
Definition: types.h:543
#define GD_bb(g)
Definition: types.h:357
#define INSERT(cp)
Definition: patchwork.c:86
agxbuf * str
Definition: htmlparse.c:85
char * agxget(void *obj, Agsym_t *sym)
Definition: attr.c:444
#define agfindnodeattr(g, a)
Definition: types.h:613
pointf UR
Definition: geom.h:35
Definition: geom.h:35
#define NEW(t)
Definition: memory.h:35
#define AGRAPH
Definition: cgraph.h:100