Graphviz  2.35.20130930.0449
circularinit.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  * Circular layout. Biconnected components are put on circles.
17  * block-cutnode tree is done recursively, with children placed
18  * about parent block.
19  * Based on:
20  * Six and Tollis, "A Framework for Circular Drawings of
21  * Networks", GD '99, LNCS 1731, pp. 107-116;
22  * Six and Tollis, "Circular Drawings of Biconnected Graphs",
23  * Proc. ALENEX '99, pp 57-73.
24  * Kaufmann and Wiese, "Maintaining the Mental Map for Circular
25  * Drawings", GD '02, LNCS 2528, pp. 12-22.
26  */
27 
28 #include "circular.h"
29 #include "adjust.h"
30 #include "pack.h"
31 #include "neatoprocs.h"
32 #include <string.h>
33 
34 static void circular_init_edge(edge_t * e)
35 {
36 #ifdef WITH_CGRAPH
37  agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
38 #endif /* WITH_CGRAPH */
40 
41  ED_factor(e) = late_double(e, E_weight, 1.0, 0.0);
42 }
43 
44 
45 static void circular_init_node_edge(graph_t * g)
46 {
47  node_t *n;
48  edge_t *e;
49  int i = 0;
50  ndata* alg = N_NEW(agnnodes(g), ndata);
51 
52  GD_neato_nlist(g) = N_NEW(agnnodes(g) + 1, node_t *);
53  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
54  neato_init_node(n);
55  ND_alg(n) = alg + i;
56  GD_neato_nlist(g)[i++] = n;
57  }
58  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
59  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
60  circular_init_edge(e);
61  }
62  }
63 }
64 
65 
67 {
68  setEdgeType (g, ET_LINE);
69  /* GD_ndim(g) = late_int(g,agfindattr(g,"dim"),2,2); */
70  Ndim = GD_ndim(g) = 2; /* The algorithm only makes sense in 2D */
71  circular_init_node_edge(g);
72 }
73 
74 /* makeDerivedNode:
75  * Make a node in the derived graph, with the given name.
76  * orig points to what it represents, either a real node or
77  * a cluster. Copy size info from original node; needed for
78  * adjustNodes and packSubgraphs.
79  */
80 static node_t *makeDerivedNode(graph_t * dg, char *name, int isNode,
81  void *orig)
82 {
83 #ifndef WITH_CGRAPH
84  node_t *n = agnode(dg, name);
85 #else /* WITH_CGRAPH */
86  node_t *n = agnode(dg, name,1);
87  agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); //node custom data
88 #endif /* WITH_CGRAPH */
89  ND_alg(n) = (void *) NEW(cdata);
90  if (isNode) {
91  ND_pos(n) = N_NEW(Ndim, double);
92  ND_lw(n) = ND_lw((node_t *) orig);
93  ND_rw(n) = ND_rw((node_t *) orig);
94  ND_ht(n) = ND_ht((node_t *) orig);
95  ORIGN(n) = (node_t *) orig;
96  } else
97  ORIGG(n) = (graph_t *) orig;
98  return n;
99 }
100 
101 /* circomps:
102  * Construct a strict, undirected graph with no loops from g.
103  * Construct the connected components with the provision that all
104  * nodes in a block subgraph are considered connected.
105  * Return array of components with number of components in cnt.
106  * Each component has its blocks as subgraphs.
107  * FIX: Check that blocks are disjoint.
108  */
109 Agraph_t **circomps(Agraph_t * g, int *cnt)
110 {
111  int c_cnt;
112  Agraph_t **ccs;
113  Agraph_t *dg;
114  Agnode_t *n, *v, *dt, *dh;
115  Agedge_t *e;
116  Agraph_t *sg;
117  int i;
118  Agedge_t *ep;
119  Agnode_t *p;
120 
121 #ifndef WITH_CGRAPH
122  dg = agopen("derived", AGFLAG_STRICT);
123 #else /* WITH_CGRAPH */
124  dg = agopen("derived", Agstrictundirected,NIL(Agdisc_t *));
125  agbindrec (dg, "info", sizeof(Agraphinfo_t), TRUE);
126 #endif /* WITH_CGRAPH */
127  GD_alg(g) = dg; /* store derived graph for closing later */
128 
129  for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
130  if (DNODE(v))
131  continue;
132  n = makeDerivedNode(dg, agnameof(v), 1, v);
133  DNODE(v) = n;
134  }
135 
136  for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
137  for (e = agfstout(g, v); e; e = agnxtout(g, e)) {
138  dt = DNODE(agtail(e));
139  dh = DNODE(aghead(e));
140  if (dt != dh) {
141 #ifndef WITH_CGRAPH
142  agedge(dg, dt, dh);
143 #else /* WITH_CGRAPH */
144  agbindrec(agedge(dg, dt, dh, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
145 #endif /* WITH_CGRAPH */
146  }
147  }
148  }
149 
150  ccs = ccomps(dg, &c_cnt, 0);
151 
152  /* replace block nodes with block contents */
153  for (i = 0; i < c_cnt; i++) {
154  sg = ccs[i];
155 
156  /* add edges: since sg is a union of components, all edges
157  * of any node should be added, except loops.
158  */
159  for (n = agfstnode(sg); n; n = agnxtnode(sg, n)) {
160  p = ORIGN(n);
161  for (e = agfstout(g, p); e; e = agnxtout(g, e)) {
162  /* n = DNODE(agtail(e)); by construction since agtail(e) == p */
163  dh = DNODE(aghead(e));
164  if (n != dh) {
165 #ifndef WITH_CGRAPH
166  ep = agedge(dg, n, dh);
167  aginsert(sg, ep);
168 #else /* WITH_CGRAPH */
169  ep = agedge(dg, n, dh, NULL, 1);
170  agbindrec(ep, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
171  agsubedge(sg,ep,1);
172 #endif /* WITH_CGRAPH */
173  }
174  }
175  }
176  }
177 
178  /* Finally, add edge data to edges */
179  for (n = agfstnode(dg); n; n = agnxtnode(dg, n)) {
180  for (e = agfstout(dg, n); e; e = agnxtout(dg, e)) {
181  ED_alg(e) = NEW(edata);
182  }
183  }
184 
185  *cnt = c_cnt;
186  return ccs;
187 }
188 
189 /* closeDerivedGraph:
190  */
191 static void closeDerivedGraph(graph_t * g)
192 {
193  node_t *n;
194  edge_t *e;
195 
196  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
197  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
198  free(ED_alg(e));
199  }
200  free(ND_alg(n));
201  free(ND_pos(n));
202  }
203  agclose(g);
204 }
205 
206 /* copyPosns:
207  * Copy position of nodes in given subgraph of derived graph
208  * to corresponding node in original graph.
209  * FIX: consider assigning from n directly to ORIG(n).
210  */
211 static void copyPosns(graph_t * g)
212 {
213  node_t *n;
214  node_t *v;
215 
216  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
217  v = ORIGN(n);
218  ND_pos(v)[0] = ND_pos(n)[0];
219  ND_pos(v)[1] = ND_pos(n)[1];
220  }
221 }
222 
223 /* circoLayout:
224  */
226 {
227  Agraph_t **ccs;
228  Agraph_t *sg;
229  int ncc;
230  int i;
231 
232  if (agnnodes(g)) {
233  ccs = circomps(g, &ncc);
234 
235  if (ncc == 1) {
236  circularLayout(ccs[0], g);
237  copyPosns(ccs[0]);
238  adjustNodes(g);
239  } else {
240  Agraph_t *dg = ccs[0]->root;
241  pack_info pinfo;
242  getPackInfo(g, l_node, CL_OFFSET, &pinfo);
243 
244  for (i = 0; i < ncc; i++) {
245  sg = ccs[i];
246  circularLayout(sg, g);
247  adjustNodes(sg);
248  }
249  /* FIX: splines have not been calculated for dg
250  * To use, either do splines in dg and copy to g, or
251  * construct components of g from ccs and use that in packing.
252  */
253  packSubgraphs(ncc, ccs, dg, &pinfo);
254  for (i = 0; i < ncc; i++)
255  copyPosns(ccs[i]);
256  }
257  free(ccs);
258  }
259 }
260 
261 /* circo_layout:
262  */
264 {
265  if (agnnodes(g) == 0) return;
266  circo_init_graph(g);
267  circoLayout(g);
268  /* Release ND_alg as we need to reuse it during edge routing */
269  free(ND_alg(agfstnode(g)));
270  spline_edges(g);
272 }
273 
274 /* circo_cleanup:
275  * ND_alg is freed in circo_layout
276  */
278 {
279  node_t *n;
280  edge_t *e;
281 
282  n = agfstnode(g);
283  if (n == NULL)
284  return; /* g is empty */
285 
286  closeDerivedGraph((graph_t*)GD_alg(g)); /* delete derived graph */
287 
288  /* free (ND_alg(n)); */
289  for (; n; n = agnxtnode(g, n)) {
290  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
291  gv_cleanup_edge(e);
292  }
293  gv_cleanup_node(n);
294  }
295  free(GD_neato_nlist(g));
296  if (g != agroot(g))
297 #ifndef WITH_CGRAPH
298  memset(&(g->u), 0, sizeof(Agraphinfo_t));
299 #else /* WITH_CGRAPH */
300  agclean (g,AGRAPH,"Agraphinfo_t");
301 #endif /* WITH_CGRAPH */
302 }