Graphviz  2.39.20141220.0545
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  agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
38 
39  ED_factor(e) = late_double(e, E_weight, 1.0, 0.0);
40 }
41 
42 
43 static void circular_init_node_edge(graph_t * g)
44 {
45  node_t *n;
46  edge_t *e;
47  int i = 0;
48  ndata* alg = N_NEW(agnnodes(g), ndata);
49 
50  GD_neato_nlist(g) = N_NEW(agnnodes(g) + 1, node_t *);
51  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
52  neato_init_node(n);
53  ND_alg(n) = alg + i;
54  GD_neato_nlist(g)[i++] = n;
55  }
56  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
57  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
58  circular_init_edge(e);
59  }
60  }
61 }
62 
63 
65 {
66  setEdgeType (g, ET_LINE);
67  /* GD_ndim(g) = late_int(g,agfindattr(g,"dim"),2,2); */
68  Ndim = GD_ndim(g) = 2; /* The algorithm only makes sense in 2D */
69  circular_init_node_edge(g);
70 }
71 
72 /* makeDerivedNode:
73  * Make a node in the derived graph, with the given name.
74  * orig points to what it represents, either a real node or
75  * a cluster. Copy size info from original node; needed for
76  * adjustNodes and packSubgraphs.
77  */
78 static node_t *makeDerivedNode(graph_t * dg, char *name, int isNode,
79  void *orig)
80 {
81  node_t *n = agnode(dg, name,1);
82  agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); //node custom data
83  ND_alg(n) = (void *) NEW(cdata);
84  if (isNode) {
85  ND_pos(n) = N_NEW(Ndim, double);
86  ND_lw(n) = ND_lw((node_t *) orig);
87  ND_rw(n) = ND_rw((node_t *) orig);
88  ND_ht(n) = ND_ht((node_t *) orig);
89  ORIGN(n) = (node_t *) orig;
90  } else
91  ORIGG(n) = (graph_t *) orig;
92  return n;
93 }
94 
95 /* circomps:
96  * Construct a strict, undirected graph with no loops from g.
97  * Construct the connected components with the provision that all
98  * nodes in a block subgraph are considered connected.
99  * Return array of components with number of components in cnt.
100  * Each component has its blocks as subgraphs.
101  * FIX: Check that blocks are disjoint.
102  */
103 Agraph_t **circomps(Agraph_t * g, int *cnt)
104 {
105  int c_cnt;
106  Agraph_t **ccs;
107  Agraph_t *dg;
108  Agnode_t *n, *v, *dt, *dh;
109  Agedge_t *e;
110  Agraph_t *sg;
111  int i;
112  Agedge_t *ep;
113  Agnode_t *p;
114 
115  dg = agopen("derived", Agstrictundirected,NIL(Agdisc_t *));
116  agbindrec (dg, "info", sizeof(Agraphinfo_t), TRUE);
117  GD_alg(g) = dg; /* store derived graph for closing later */
118 
119  for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
120  if (DNODE(v))
121  continue;
122  n = makeDerivedNode(dg, agnameof(v), 1, v);
123  DNODE(v) = n;
124  }
125 
126  for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
127  for (e = agfstout(g, v); e; e = agnxtout(g, e)) {
128  dt = DNODE(agtail(e));
129  dh = DNODE(aghead(e));
130  if (dt != dh) {
131  agbindrec(agedge(dg, dt, dh, NULL, 1), "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
132  }
133  }
134  }
135 
136  ccs = ccomps(dg, &c_cnt, 0);
137 
138  /* replace block nodes with block contents */
139  for (i = 0; i < c_cnt; i++) {
140  sg = ccs[i];
141 
142  /* add edges: since sg is a union of components, all edges
143  * of any node should be added, except loops.
144  */
145  for (n = agfstnode(sg); n; n = agnxtnode(sg, n)) {
146  p = ORIGN(n);
147  for (e = agfstout(g, p); e; e = agnxtout(g, e)) {
148  /* n = DNODE(agtail(e)); by construction since agtail(e) == p */
149  dh = DNODE(aghead(e));
150  if (n != dh) {
151  ep = agedge(dg, n, dh, NULL, 1);
152  agbindrec(ep, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
153  agsubedge(sg,ep,1);
154  }
155  }
156  }
157  }
158 
159  /* Finally, add edge data to edges */
160  for (n = agfstnode(dg); n; n = agnxtnode(dg, n)) {
161  for (e = agfstout(dg, n); e; e = agnxtout(dg, e)) {
162  ED_alg(e) = NEW(edata);
163  }
164  }
165 
166  *cnt = c_cnt;
167  return ccs;
168 }
169 
170 /* closeDerivedGraph:
171  */
172 static void closeDerivedGraph(graph_t * g)
173 {
174  node_t *n;
175  edge_t *e;
176 
177  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
178  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
179  free(ED_alg(e));
180  }
181  free(ND_alg(n));
182  free(ND_pos(n));
183  }
184  agclose(g);
185 }
186 
187 /* copyPosns:
188  * Copy position of nodes in given subgraph of derived graph
189  * to corresponding node in original graph.
190  * FIX: consider assigning from n directly to ORIG(n).
191  */
192 static void copyPosns(graph_t * g)
193 {
194  node_t *n;
195  node_t *v;
196 
197  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
198  v = ORIGN(n);
199  ND_pos(v)[0] = ND_pos(n)[0];
200  ND_pos(v)[1] = ND_pos(n)[1];
201  }
202 }
203 
204 /* circoLayout:
205  */
207 {
208  Agraph_t **ccs;
209  Agraph_t *sg;
210  int ncc;
211  int i;
212 
213  if (agnnodes(g)) {
214  ccs = circomps(g, &ncc);
215 
216  if (ncc == 1) {
217  circularLayout(ccs[0], g);
218  copyPosns(ccs[0]);
219  adjustNodes(g);
220  } else {
221  Agraph_t *dg = ccs[0]->root;
222  pack_info pinfo;
223  getPackInfo(g, l_node, CL_OFFSET, &pinfo);
224 
225  for (i = 0; i < ncc; i++) {
226  sg = ccs[i];
227  circularLayout(sg, g);
228  adjustNodes(sg);
229  }
230  /* FIX: splines have not been calculated for dg
231  * To use, either do splines in dg and copy to g, or
232  * construct components of g from ccs and use that in packing.
233  */
234  packSubgraphs(ncc, ccs, dg, &pinfo);
235  for (i = 0; i < ncc; i++)
236  copyPosns(ccs[i]);
237  }
238  free(ccs);
239  }
240 }
241 
242 /* circo_layout:
243  */
245 {
246  if (agnnodes(g) == 0) return;
247  circo_init_graph(g);
248  circoLayout(g);
249  /* Release ND_alg as we need to reuse it during edge routing */
250  free(ND_alg(agfstnode(g)));
251  spline_edges(g);
253 }
254 
255 /* circo_cleanup:
256  * ND_alg is freed in circo_layout
257  */
259 {
260  node_t *n;
261  edge_t *e;
262 
263  n = agfstnode(g);
264  if (n == NULL)
265  return; /* g is empty */
266 
267  closeDerivedGraph((graph_t*)GD_alg(g)); /* delete derived graph */
268 
269  /* free (ND_alg(n)); */
270  for (; n; n = agnxtnode(g, n)) {
271  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
272  gv_cleanup_edge(e);
273  }
274  gv_cleanup_node(n);
275  }
276  free(GD_neato_nlist(g));
277  if (g != agroot(g))
278  agclean (g,AGRAPH,"Agraphinfo_t");
279 }
void dotneato_postprocess(Agraph_t *g)
Definition: postproc.c:693
Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:494
Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:502
#define N_NEW(n, t)
Definition: memory.h:36
Definition: pack.h:49
void circularLayout(Agraph_t *g, Agraph_t *realg)
Definition: circular.c:92
Definition: pack.h:37
void circo_init_graph(graph_t *g)
Definition: circularinit.c:64
Definition: circular.h:73
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
Agdesc_t Agstrictundirected
Definition: graph.c:279
int agclose(Agraph_t *g)
Definition: graph.c:93
int agnnodes(Agraph_t *g)
void circoLayout(Agraph_t *g)
Definition: circularinit.c:206
#define ND_pos(n)
Definition: types.h:487
void gv_cleanup_edge(Agedge_t *e)
Definition: utils.c:1907
pack_mode getPackInfo(Agraph_t *g, pack_mode dflt, int dfltMargin, pack_info *pinfo)
Definition: pack.c:1398
Definition: circular.h:44
Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition: node.c:142
void agclean(Agraph_t *g, int kind, char *rec_name)
Definition: rec.c:231
#define NIL(t)
Definition: dthdr.h:20
#define ND_ht(n)
Definition: types.h:467
void free()
int i
Definition: gvdevice.c:448
Definition: circular.h:30
Agraph_t * agroot(void *obj)
Definition: obj.c:169
Agraph_t ** circomps(Agraph_t *g, int *cnt)
Definition: circularinit.c:103
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
void spline_edges(Agraph_t *)
Definition: neatosplines.c:801
Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
Definition: graph.c:44
#define ND_rw(n)
Definition: types.h:492
#define ET_LINE
Definition: const.h:270
int adjustNodes(graph_t *G)
Definition: adjust.c:1229
Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define GD_ndim(g)
Definition: types.h:378
#define GD_alg(g)
Definition: types.h:341
#define CL_OFFSET
Definition: const.h:155
#define ND_lw(n)
Definition: types.h:474
#define ND_alg(n)
Definition: types.h:451
#define ED_factor(e)
Definition: types.h:542
int packSubgraphs(int ng, Agraph_t **gs, Agraph_t *root, pack_info *info)
Definition: pack.c:1163
#define NULL
Definition: logic.h:50
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
EXTERN Agsym_t * E_weight
Definition: globals.h:116
double late_double(void *obj, attrsym_t *attr, double def, double low)
Definition: utils.c:85
void gv_cleanup_node(Agnode_t *n)
Definition: utils.c:1919
char * agnameof(void *)
Definition: id.c:143
#define ED_alg(e)
Definition: types.h:536
#define DNODE(n)
Definition: circular.h:79
#define ORIGN(n)
Definition: circular.h:87
int common_init_edge(edge_t *e)
Definition: utils.c:711
void circo_layout(Agraph_t *g)
Definition: circularinit.c:244
void setEdgeType(graph_t *g, int dflt)
Definition: utils.c:1762
void neato_init_node(node_t *n)
Definition: neatoinit.c:44
#define ORIGG(n)
Definition: circular.h:86
Agraph_t ** ccomps(Agraph_t *g, int *ncc, char *pfx)
Definition: ccomps.c:288
Agraph_t * root
Definition: cgraph.h:241
Agedge_t * agsubedge(Agraph_t *g, Agedge_t *e, int createflag)
Definition: edge.c:378
void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
void circo_cleanup(graph_t *g)
Definition: circularinit.c:258
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition: edge.c:281
#define GD_neato_nlist(g)
Definition: types.h:380
EXTERN int Ndim
Definition: globals.h:88
#define NEW(t)
Definition: memory.h:35
#define AGRAPH
Definition: cgraph.h:87
#define TRUE
Definition: cgraph.h:27