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
34static void circular_init_edge(edge_t * e)
35{
36 agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
37 common_init_edge(e);
38
39 ED_factor(e) = late_double(e, E_weight, 1.0, 0.0);
40}
41
42
43static 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
64void circo_init_graph(graph_t * g)
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 */
78static 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 */
103Agraph_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 */
172static 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 */
192static 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 */
206void circoLayout(Agraph_t * g)
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 */
244void circo_layout(Agraph_t * g)
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);
252 dotneato_postprocess(g);
253}
254
255/* circo_cleanup:
256 * ND_alg is freed in circo_layout
257 */
258void circo_cleanup(graph_t * g)
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}
280