Graphviz  2.41.20170921.2350
osageinit.c
Go to the documentation of this file.
1 /* vim:set shiftwidth=4 ts=8: */
2 
3 /*************************************************************************
4  * Copyright (c) 2011 AT&T Intellectual Property
5  * All rights reserved. This program and the accompanying materials
6  * are made available under the terms of the Eclipse Public License v1.0
7  * which accompanies this distribution, and is available at
8  * http://www.eclipse.org/legal/epl-v10.html
9  *
10  * Contributors: See CVS logs. Details at http://www.graphviz.org/
11  *************************************************************************/
12 
13 
14 /* FIX: handle cluster labels */
15 /*
16  * Written by Emden R. Gansner
17  */
18 
19 #include "osage.h"
20 #include "neatoprocs.h"
21 #include "pack.h"
22 
23 #define CL_CHUNK 10
24 #define DFLT_SZ 18
25 #define PARENT(n) ((Agraph_t*)ND_alg(n))
26 
27 static void
28 indent (int i)
29 {
30  for (; i > 0; i--)
31  fputs (" ", stderr);
32 }
33 
34 typedef struct {
36  int sz;
37  int cnt;
38 } clist_t;
39 
40 static void initCList(clist_t * clist)
41 {
42  clist->cl = 0;
43  clist->sz = 0;
44  clist->cnt = 0;
45 }
46 
47 /* addCluster:
48  * Append a new cluster to the list.
49  * NOTE: cl[0] is empty. The clusters are in cl[1..cnt].
50  * Normally, we increase the array when cnt == sz.
51  * The test for cnt > sz is necessary for the first time.
52  */
53 static void addCluster(clist_t * clist, graph_t * subg)
54 {
55  clist->cnt++;
56  if (clist->cnt >= clist->sz) {
57  clist->sz += CL_CHUNK;
58  clist->cl = RALLOC(clist->sz, clist->cl, graph_t *);
59  }
60  clist->cl[clist->cnt] = subg;
61 }
62 
63 static void cluster_init_graph(graph_t * g)
64 {
65  Agnode_t *n;
66  Agedge_t *e;
67 
68  setEdgeType (g, ET_LINE);
69  Ndim = GD_ndim(g)=2; /* The algorithm only makes sense in 2D */
70 
71  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
72  neato_init_node (n);
73  }
74  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
75  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
76  agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //edge custom data
78  }
79  }
80 }
81 
82 /* layout:
83  */
84 static void
85 layout (Agraph_t* g, int depth)
86 {
87  int i, j, total, nv;
88  int nvs = 0; /* no. of nodes in subclusters */
89  Agnode_t* n;
90  Agraph_t* subg;
91  boxf* gs;
92  point* pts;
93  boxf bb, rootbb;
94  pointf p;
95  pack_info pinfo;
96  pack_mode pmode;
97  double margin;
98  void** children;
99  Agsym_t* cattr = NULL;
100  Agsym_t* vattr = NULL;
101  Agraph_t* root = g->root;
102 
103  if (Verbose > 1) {
104  indent (depth);
105  fprintf (stderr, "layout %s\n", agnameof(g));
106  }
107 
108  /* Lay out subclusters */
109  for (i = 1; i <= GD_n_cluster(g); i++) {
110  subg = GD_clust(g)[i];
111  layout (subg, depth+1);
112  nvs += agnnodes (subg);
113  }
114 
115  nv = agnnodes(g);
116  total = (nv - nvs) + GD_n_cluster(g);
117 
118  if ((total == 0) && (GD_label(g) == NULL)) {
119  GD_bb(g).LL.x = GD_bb(g).LL.y = 0;
120  GD_bb(g).UR.x = GD_bb(g).UR.y = DFLT_SZ;
121  return;
122  }
123 
124  pmode = getPackInfo(g, l_array, DFLT_MARGIN, &pinfo);
125  if (pmode < l_graph) pinfo.mode = l_graph;
126 
127  /* add user sort values if necessary */
128  if ((pinfo.mode == l_array) && (pinfo.flags & PK_USER_VALS)) {
129  cattr = agattr(root, AGRAPH, "sortv", 0);
130  vattr = agattr(root, AGNODE, "sortv", 0);
131  if (cattr || vattr)
132  pinfo.vals = N_NEW(total, packval_t);
133  else
134  agerr (AGWARN, "Graph %s has array packing with user values but no \"sortv\" attributes are defined.",
135  agnameof(g));
136  }
137 
138  gs = N_NEW(total, boxf);
139  children = N_NEW(total, void*);
140  j = 0;
141  for (i = 1; i <= GD_n_cluster(g); i++) {
142  subg = GD_clust(g)[i];
143  gs[j] = GD_bb(subg);
144  if (pinfo.vals && cattr) {
145  pinfo.vals[j] = late_int (subg, cattr, 0, 0);
146  }
147  children[j++] = subg;
148  }
149 
150  if (nv-nvs > 0) {
151  for (n = agfstnode (g); n; n = agnxtnode (g,n)) {
152  if (ND_alg(n)) continue;
153  ND_alg(n) = g;
154  bb.LL.y = bb.LL.x = 0;
155  bb.UR.x = ND_xsize(n);
156  bb.UR.y = ND_ysize(n);
157  gs[j] = bb;
158  if (pinfo.vals && vattr) {
159  pinfo.vals[j] = late_int (n, vattr, 0, 0);
160  }
161  children[j++] = n;
162  }
163  }
164 
165  /* pack rectangles */
166  pts = putRects (total, gs, &pinfo);
167  if (pinfo.vals) {
168  free (pinfo.vals);
169  }
170 
171  rootbb.LL = pointfof(INT_MAX, INT_MAX);
172  rootbb.UR = pointfof(-INT_MAX, -INT_MAX);
173 
174  /* reposition children relative to GD_bb(g) */
175  for (j = 0; j < total; j++) {
176  P2PF(pts[j],p);
177  bb = gs[j];
178  bb.LL.x += p.x;
179  bb.UR.x += p.x;
180  bb.LL.y += p.y;
181  bb.UR.y += p.y;
182  EXPANDBB(rootbb, bb);
183  if (j < GD_n_cluster(g)) {
184  subg = (Agraph_t*)children[j];
185  GD_bb(subg) = bb;
186  if (Verbose > 1) {
187  indent (depth);
188  fprintf (stderr, "%s : %f %f %f %f\n", agnameof(subg), bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
189  }
190  }
191  else {
192  n = (Agnode_t*)children[j];
193  ND_coord(n) = mid_pointf (bb.LL, bb.UR);
194  if (Verbose > 1) {
195  indent (depth);
196  fprintf (stderr, "%s : %f %f\n", agnameof(n), ND_coord(n).x, ND_coord(n).y);
197  }
198  }
199  }
200 
201  if (GD_label(g)) {
202  pointf p;
203  double d;
204 
205  p = GD_label(g)->dimen;
206  if (total == 0) {
207  rootbb.LL.x = 0;
208  rootbb.LL.y = 0;
209  rootbb.UR.x = p.x;
210  rootbb.UR.y = p.y;
211 
212  }
213  d = p.x - (rootbb.UR.x - rootbb.LL.x);
214  if (d > 0) { /* height of label is added below */
215  d /= 2;
216  rootbb.LL.x -= d;
217  rootbb.UR.x += d;
218  }
219  }
220 
221  if (depth > 0)
222  margin = pinfo.margin/2.0;
223  else
224  margin = 0;
225  rootbb.LL.x -= margin;
226  rootbb.UR.x += margin;
227  rootbb.LL.y -= (margin + GD_border(g)[BOTTOM_IX].y);
228  rootbb.UR.y += (margin + GD_border(g)[TOP_IX].y);
229 
230  if (Verbose > 1) {
231  indent (depth);
232  fprintf (stderr, "%s : %f %f %f %f\n", agnameof(g), rootbb.LL.x, rootbb.LL.y, rootbb.UR.x, rootbb.UR.y);
233  }
234 
235  /* Translate so that rootbb.LL is origin.
236  * This makes the repositioning simpler; we just translate the clusters and nodes in g by
237  * the final bb.ll of g.
238  */
239  for (j = 0; j < total; j++) {
240  if (j < GD_n_cluster(g)) {
241  subg = (Agraph_t*)children[j];
242  bb = GD_bb(subg);
243  bb.LL = sub_pointf(bb.LL, rootbb.LL);
244  bb.UR = sub_pointf(bb.UR, rootbb.LL);
245  GD_bb(subg) = bb;
246  if (Verbose > 1) {
247  indent (depth);
248  fprintf (stderr, "%s : %f %f %f %f\n", agnameof(subg), bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
249  }
250  }
251  else {
252  n = (Agnode_t*)children[j];
253  ND_coord(n) = sub_pointf (ND_coord(n), rootbb.LL);
254  if (Verbose > 1) {
255  indent (depth);
256  fprintf (stderr, "%s : %f %f\n", agnameof(n), ND_coord(n).x, ND_coord(n).y);
257  }
258  }
259  }
260 
261  rootbb.UR = sub_pointf(rootbb.UR, rootbb.LL);
262  rootbb.LL = sub_pointf(rootbb.LL, rootbb.LL);
263  GD_bb(g) = rootbb;
264 
265  if (Verbose > 1) {
266  indent (depth);
267  fprintf (stderr, "%s : %f %f %f %f\n", agnameof(g), rootbb.LL.x, rootbb.LL.y, rootbb.UR.x, rootbb.UR.y);
268  }
269 
270  free (gs);
271  free (children);
272  free (pts);
273 }
274 
275 static void
276 reposition (Agraph_t* g, int depth)
277 {
278  boxf sbb, bb = GD_bb(g);
279  Agnode_t* n;
280  Agraph_t* subg;
281  int i;
282 
283  if (Verbose > 1) {
284  indent (depth);
285  fprintf (stderr, "reposition %s\n", agnameof(g));
286  }
287 
288  /* translate nodes in g but not in a subcluster */
289  if (depth) {
290  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
291  if (PARENT(n) != g)
292  continue;
293  ND_coord(n).x += bb.LL.x;
294  ND_coord(n).y += bb.LL.y;
295  if (Verbose > 1) {
296  indent (depth);
297  fprintf (stderr, "%s : %f %f\n", agnameof(n), ND_coord(n).x, ND_coord(n).y);
298  }
299  }
300  }
301 
302  /* translate top-level clusters and recurse */
303  for (i = 1; i <= GD_n_cluster(g); i++) {
304  subg = GD_clust(g)[i];
305  if (depth) {
306  sbb = GD_bb(subg);
307  sbb.LL.x += bb.LL.x;
308  sbb.LL.y += bb.LL.y;
309  sbb.UR.x += bb.LL.x;
310  sbb.UR.y += bb.LL.y;
311  if (Verbose > 1) {
312  indent (depth);
313  fprintf (stderr, "%s : %f %f %f %f\n", agnameof(subg), sbb.LL.x, sbb.LL.y, sbb.UR.x, sbb.UR.y);
314  }
315  GD_bb(subg) = sbb;
316  }
317  reposition (subg, depth+1);
318  }
319 
320 }
321 
322 static void
323 mkClusters (Agraph_t* g, clist_t* pclist, Agraph_t* parent)
324 {
325  graph_t* subg;
326  clist_t list;
327  clist_t* clist;
328 
329  if (pclist == NULL) {
330  clist = &list;
331  initCList(clist);
332  }
333  else
334  clist = pclist;
335 
336  for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
337  if (!strncmp(agnameof(subg), "cluster", 7)) {
338  agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
339  do_graph_label (subg);
340  addCluster(clist, subg);
341  mkClusters(subg, NULL, subg);
342  }
343  else {
344  mkClusters(subg, clist, parent);
345  }
346  }
347  if (pclist == NULL) {
348  GD_n_cluster(g) = list.cnt;
349  if (list.cnt)
350  GD_clust(g) = RALLOC(list.cnt + 1, list.cl, graph_t*);
351  }
352 }
353 
355 {
356  cluster_init_graph(g);
357  mkClusters(g, NULL, g);
358  layout(g, 0);
359  reposition (g, 0);
360 
361  if (GD_drawing(g)->ratio_kind) {
362  Agnode_t* n;
363  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
364  ND_pos(n)[0] = PS2INCH(ND_coord(n).x);
365  ND_pos(n)[1] = PS2INCH(ND_coord(n).y);
366  }
367  spline_edges0(g, TRUE);
368  }
369  else {
370  int et = EDGE_TYPE (g);
371  if (et != ET_NONE) spline_edges1(g, et);
372  }
374 }
375 
376 static void cleanup_graphs (Agraph_t *g)
377 {
378  graph_t *subg;
379  int i;
380 
381  for (i = 1; i <= GD_n_cluster(g); i++) {
382  subg = GD_clust(g)[i];
383  free_label(GD_label(subg));
384  cleanup_graphs (subg);
385  }
386  free (GD_clust(g));
387 }
388 
390 {
391  node_t *n;
392 
393  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
394  gv_cleanup_node(n);
395  }
396  cleanup_graphs(g);
397 }
void dotneato_postprocess(Agraph_t *g)
Definition: postproc.c:693
#define GD_label(g)
Definition: types.h:381
Agraph_t ** cl
Definition: osageinit.c:35
void free_label(textlabel_t *p)
Definition: labels.c:209
#define RALLOC(size, ptr, type)
Definition: memory.h:42
packval_t * vals
Definition: pack.h:56
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
pack_mode
Definition: pack.h:37
Definition: pack.h:49
int flags
Definition: pack.h:57
bool layout(Agraph_t *g, const char *engine)
Definition: gv.cpp:809
#define GD_n_cluster(g)
Definition: types.h:396
#define GD_border(g)
Definition: types.h:362
graph_t ** cl
Definition: layout.c:281
void osage_cleanup(Agraph_t *g)
Definition: osageinit.c:389
Definition: geom.h:28
#define EDGE_TYPE(g)
Definition: macros.h:33
#define ND_pos(n)
Definition: types.h:526
void do_graph_label(graph_t *sg)
Definition: input.c:892
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
CGRAPH_API Agraph_t * agfstsubg(Agraph_t *g)
Definition: subg.c:72
#define parent(i)
Definition: closest.c:88
pack_mode getPackInfo(Agraph_t *g, pack_mode dflt, int dfltMargin, pack_info *pinfo)
Definition: pack.c:1398
#define DFLT_MARGIN
Definition: adjust.h:26
#define ND_ysize(n)
Definition: types.h:544
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
pack_mode mode
Definition: pack.h:54
#define P2PF(p, pf)
Definition: geom.h:71
int cnt
Definition: layout.c:283
Definition: cgraph.h:388
#define PS2INCH(a_points)
Definition: geom.h:69
CGRAPH_API Agraph_t * agnxtsubg(Agraph_t *subg)
Definition: subg.c:77
void spline_edges0(Agraph_t *, boolean)
Definition: neatosplines.c:767
#define BOTTOM_IX
Definition: const.h:112
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
unsigned int margin
Definition: pack.h:52
double y
Definition: geom.h:28
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define CL_CHUNK
Definition: osageinit.c:23
#define ET_NONE
Definition: const.h:270
#define PK_USER_VALS
Definition: pack.h:40
#define ET_LINE
Definition: const.h:271
point * putRects(int ng, boxf *bbs, pack_info *pinfo)
Definition: pack.c:959
#define GD_ndim(g)
Definition: types.h:398
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
#define GD_clust(g)
Definition: types.h:364
#define AGNODE
Definition: cgraph.h:101
int sz
Definition: layout.c:282
#define PARENT(n)
Definition: osageinit.c:25
#define ND_alg(n)
Definition: types.h:490
Definition: pack.h:37
#define NULL
Definition: logic.h:39
Definition: geom.h:26
double x
Definition: geom.h:28
#define ND_coord(n)
Definition: types.h:496
EXTERN unsigned char Verbose
Definition: globals.h:64
void gv_cleanup_node(Agnode_t *n)
Definition: utils.c:1959
unsigned int packval_t
Definition: pack.h:47
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
void osage_layout(Agraph_t *g)
Definition: osageinit.c:354
Definition: pack.h:37
pointf LL
Definition: geom.h:35
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
int common_init_edge(edge_t *e)
Definition: utils.c:714
void setEdgeType(graph_t *g, int dflt)
Definition: utils.c:1802
void neato_init_node(node_t *n)
Definition: neatoinit.c:42
#define ND_xsize(n)
Definition: types.h:543
#define GD_bb(g)
Definition: types.h:357
Agraph_t * root
Definition: cgraph.h:247
int spline_edges1(graph_t *g, int)
Definition: neatosplines.c:748
#define DFLT_SZ
Definition: osageinit.c:24
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define GD_drawing(g)
Definition: types.h:356
pointf UR
Definition: geom.h:35
Definition: geom.h:35
#define TOP_IX
Definition: const.h:114
#define EXPANDBB(b0, b1)
Definition: geom.h:51
EXTERN int Ndim
Definition: globals.h:79
#define INT_MAX
Definition: arith.h:52
#define AGRAPH
Definition: cgraph.h:100
#define TRUE
Definition: cgraph.h:38