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#include <time.h>
16#include "dot.h"
17#include "pack.h"
18#include "aspect.h"
19
20static void
21dot_init_subg(graph_t * g, graph_t* droot)
22{
23 graph_t* subg;
24
25 if ((g != agroot(g)))
26 agbindrec(g, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
27 if (g == droot)
28 GD_dotroot(agroot(g)) = droot;
29
30 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
31 dot_init_subg(subg, droot);
32 }
33}
34
35
36static void
37dot_init_node(node_t * n)
38{
39 agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); //graph custom data
40 common_init_node(n);
41 gv_nodesize(n, GD_flip(agraphof(n)));
42 alloc_elist(4, ND_in(n));
43 alloc_elist(4, ND_out(n));
44 alloc_elist(2, ND_flat_in(n));
45 alloc_elist(2, ND_flat_out(n));
46 alloc_elist(2, ND_other(n));
47 ND_UF_size(n) = 1;
48}
49
50static void
51dot_init_edge(edge_t * e)
52{
53 char *tailgroup, *headgroup;
54 agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //graph custom data
55 common_init_edge(e);
56
57 ED_weight(e) = late_int(e, E_weight, 1, 0);
58 tailgroup = late_string(agtail(e), N_group, "");
59 headgroup = late_string(aghead(e), N_group, "");
60 ED_count(e) = ED_xpenalty(e) = 1;
61 if (tailgroup[0] && (tailgroup == headgroup)) {
62 ED_xpenalty(e) = CL_CROSS;
63 ED_weight(e) *= 100;
64 }
65 if (nonconstraint_edge(e)) {
66 ED_xpenalty(e) = 0;
67 ED_weight(e) = 0;
68 }
69
70 ED_showboxes(e) = late_int(e, E_showboxes, 0, 0);
71 ED_minlen(e) = late_int(e, E_minlen, 1, 0);
72}
73
74void
75dot_init_node_edge(graph_t * g)
76{
77 node_t *n;
78 edge_t *e;
79
80 for (n = agfstnode(g); n; n = agnxtnode(g, n))
81 dot_init_node(n);
82 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
83 for (e = agfstout(g, n); e; e = agnxtout(g, e))
84 dot_init_edge(e);
85 }
86}
87
88#if 0 /* not used */
89static void free_edge_list(elist L)
90{
91 edge_t *e;
92 int i;
93
94 for (i = 0; i < L.size; i++) {
95 e = L.list[i];
96 free(e);
97 }
98}
99#endif
100
101static void
102dot_cleanup_node(node_t * n)
103{
104 free_list(ND_in(n));
105 free_list(ND_out(n));
106 free_list(ND_flat_out(n));
107 free_list(ND_flat_in(n));
108 free_list(ND_other(n));
109 free_label(ND_label(n));
110 free_label(ND_xlabel(n));
111 if (ND_shape(n))
112 ND_shape(n)->fns->freefn(n);
113 agdelrec(n, "Agnodeinfo_t");
114}
115
116static void free_virtual_edge_list(node_t * n)
117{
118 edge_t *e;
119 int i;
120
121 for (i = ND_in(n).size - 1; i >= 0; i--) {
122 e = ND_in(n).list[i];
123 delete_fast_edge(e);
124 free(e->base.data);
125 free(e);
126 }
127 for (i = ND_out(n).size - 1; i >= 0; i--) {
128 e = ND_out(n).list[i];
129 delete_fast_edge(e);
130 free(e->base.data);
131 free(e);
132 }
133}
134
135static void free_virtual_node_list(node_t * vn)
136{
137 node_t *next_vn;
138
139 while (vn) {
140 next_vn = ND_next(vn);
141 free_virtual_edge_list(vn);
142 if (ND_node_type(vn) == VIRTUAL) {
143 free_list(ND_out(vn));
144 free_list(ND_in(vn));
145 free(vn->base.data);
146 free(vn);
147 }
148 vn = next_vn;
149 }
150}
151
152static void
153dot_cleanup_graph(graph_t * g)
154{
155 int i;
156 graph_t *subg;
157 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
158 dot_cleanup_graph(subg);
159 }
160 if (! agbindrec(g, "Agraphinfo_t", 0, TRUE)) return;
161 if (GD_clust(g)) free (GD_clust(g));
162 if (GD_rankleader(g)) free (GD_rankleader(g));
163
164 free_list(GD_comp(g));
165 if (GD_rank(g)) {
166 for (i = GD_minrank(g); i <= GD_maxrank(g); i++)
167 free(GD_rank(g)[i].av);
168 if (GD_minrank(g) == -1)
169 free(GD_rank(g)-1);
170 else
171 free(GD_rank(g));
172 }
173 if (g != agroot(g)) {
174 free_label (GD_label(g));
175 agdelrec(g,"Agraphinfo_t");
176 }
177}
178
179/* delete the layout (but retain the underlying graph) */
180void dot_cleanup(graph_t * g)
181{
182 node_t *n;
183 edge_t *e;
184
185 free_virtual_node_list(GD_nlist(g));
186 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
187 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
188 gv_cleanup_edge(e);
189 }
190 dot_cleanup_node(n);
191 }
192 dot_cleanup_graph(g);
193}
194
195#ifdef DEBUG
196int
197fastn (graph_t * g)
198{
199 node_t* u;
200 int cnt = 0;
201 for (u = GD_nlist(g); u; u = ND_next(u)) cnt++;
202 return cnt;
203}
204
205#if DEBUG > 1
206static void
207dumpRanks (graph_t * g)
208{
209 int i, j;
210 node_t* u;
211 rank_t *rank = GD_rank(g);
212 int rcnt = 0;
213 for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
214 fprintf (stderr, "[%d] :", i);
215 for (j = 0; j < rank[i].n; j++) {
216 u = rank[i].v[j];
217 rcnt++;
218 if (streq(agnameof(u),"virtual"))
219 fprintf (stderr, " %x", u);
220 else
221 fprintf (stderr, " %s", agnameof(u));
222
223 }
224 fprintf (stderr, "\n");
225 }
226 fprintf (stderr, "count %d rank count = %d\n", fastn(g), rcnt);
227}
228#endif
229#endif
230
231
232static void
233remove_from_rank (Agraph_t * g, Agnode_t* n)
234{
235 Agnode_t* v = NULL;
236 int j, rk = ND_rank(n);
237
238 for (j = 0; j < GD_rank(g)[rk].n; j++) {
239 v = GD_rank(g)[rk].v[j];
240 if (v == n) {
241 for (j++; j < GD_rank(g)[rk].n; j++) {
242 GD_rank(g)[rk].v[j-1] = GD_rank(g)[rk].v[j];
243 }
244 GD_rank(g)[rk].n--;
245 break;
246 }
247 }
248 assert (v == n); /* if found */
249}
250
251/* removeFill:
252 * This removes all of the fill nodes added in mincross.
253 * It appears to be sufficient to remove them only from the
254 * rank array and fast node list of the root graph.
255 */
256static void
257removeFill (Agraph_t * g)
258{
259 Agnode_t* n;
260 Agnode_t* nxt;
261 Agraph_t* sg = agsubg (g, "_new_rank", 0);
262
263 if (!sg) return;
264 for (n = agfstnode(sg); n; n = nxt) {
265 nxt = agnxtnode(sg, n);
266 delete_fast_node (g, n);
267 remove_from_rank (g, n);
268 dot_cleanup_node (n);
269 agdelnode(g, n);
270 }
271 agdelsubg (g, sg);
272
273}
274
275#define ag_xset(x,a,v) agxset(x,a,v)
276#define agnodeattr(g,n,v) agattr(g,AGNODE,n,v)
277
278static void
279attach_phase_attrs (Agraph_t * g, int maxphase)
280{
281 Agsym_t* rk = agnodeattr(g,"rank","");
282 Agsym_t* order = agnodeattr(g,"order","");
283 Agnode_t* n;
284 char buf[BUFSIZ];
285
286 for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
287 if (maxphase >= 1) {
288 sprintf(buf, "%d", ND_rank(n));
289 ag_xset(n,rk,buf);
290 }
291 if (maxphase >= 2) {
292 sprintf(buf, "%d", ND_order(n));
293 ag_xset(n,order,buf);
294 }
295 }
296}
297
298static void dotLayout(Agraph_t * g)
299{
300 aspect_t aspect;
301 aspect_t* asp;
302 int maxphase = late_int(g, agfindgraphattr(g,"phase"), -1, 1);
303
304 setEdgeType (g, ET_SPLINE);
305 asp = setAspect (g, &aspect);
306
307 dot_init_subg(g,g);
308 dot_init_node_edge(g);
309
310 do {
311 dot_rank(g, asp);
312 if (maxphase == 1) {
313 attach_phase_attrs (g, 1);
314 return;
315 }
316 if (aspect.badGraph) {
317 agerr(AGWARN, "dot does not support the aspect attribute for disconnected graphs or graphs with clusters\n");
318 asp = NULL;
319 aspect.nextIter = 0;
320 }
321 dot_mincross(g, (asp != NULL));
322 if (maxphase == 2) {
323 attach_phase_attrs (g, 2);
324 return;
325 }
326 dot_position(g, asp);
327 if (maxphase == 3) {
328 attach_phase_attrs (g, 2); /* positions will be attached on output */
329 return;
330 }
331 aspect.nPasses--;
332 } while (aspect.nextIter && aspect.nPasses);
333 if (GD_flags(g) & NEW_RANK)
334 removeFill (g);
335 dot_sameports(g);
336 dot_splines(g);
337 if (mapbool(agget(g, "compound")))
338 dot_compoundEdges(g);
339}
340
341static void
342initSubg (Agraph_t* sg, Agraph_t* g)
343{
344 agbindrec(sg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
345 GD_drawing(sg) = NEW(layout_t);
346 GD_drawing(sg)->quantum = GD_drawing(g)->quantum;
347 GD_drawing(sg)->dpi = GD_drawing(g)->dpi;
348 GD_gvc(sg) = GD_gvc (g);
349 GD_charset(sg) = GD_charset (g);
350 GD_rankdir2(sg) = GD_rankdir2 (g);
351 GD_nodesep(sg) = GD_nodesep(g);
352 GD_ranksep(sg) = GD_ranksep(g);
353 GD_fontnames(sg) = GD_fontnames(g);
354}
355
356/* attachPos:
357 * the packing library assumes all units are in inches stored in ND_pos, so we
358 * have to copy the position info there.
359 */
360static void
361attachPos (Agraph_t* g)
362{
363 node_t* np;
364 double* ps = N_NEW(2*agnnodes(g), double);
365
366 for (np = agfstnode(g); np; np = agnxtnode(g, np)) {
367 ND_pos(np) = ps;
368 ps[0] = PS2INCH(ND_coord(np).x);
369 ps[1] = PS2INCH(ND_coord(np).y);
370 ps += 2;
371 }
372}
373
374/* resetCoord:
375 * Store new position info from pack library call, stored in ND_pos in inches,
376 * back to ND_coord in points.
377 */
378static void
379resetCoord (Agraph_t* g)
380{
381 node_t* np = agfstnode(g);
382 double* sp = ND_pos(np);
383 double* ps = sp;
384
385 for (np = agfstnode(g); np; np = agnxtnode(g, np)) {
386 ND_pos(np) = 0;
387 ND_coord(np).x = INCH2PS(ps[0]);
388 ND_coord(np).y = INCH2PS(ps[1]);
389 ps += 2;
390 }
391 free (sp);
392}
393
394/* copyCluster:
395 */
396static void
397copyCluster (Agraph_t* scl, Agraph_t* cl)
398{
399 int nclust, j;
400 Agraph_t* cg;
401
402 agbindrec(cl, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
403 GD_bb(cl) = GD_bb(scl);
404 GD_label_pos(cl) = GD_label_pos(scl);
405 memcpy(GD_border(cl), GD_border(scl), 4*sizeof(pointf));
406 nclust = GD_n_cluster(cl) = GD_n_cluster(scl);
407 GD_clust(cl) = N_NEW(nclust+1,Agraph_t*);
408 for (j = 1; j <= nclust; j++) {
409 cg = mapClust(GD_clust(scl)[j]);
410 GD_clust(cl)[j] = cg;
411 copyCluster (GD_clust(scl)[j], cg);
412 }
413 /* transfer cluster label to original cluster */
414 GD_label(cl) = GD_label(scl);
415 GD_label(scl) = NULL;
416}
417
418/* copyClusterInfo:
419 * Copy cluster tree and info from components to main graph.
420 * Note that the original clusters have no Agraphinfo_t at this time.
421 */
422static void
423copyClusterInfo (int ncc, Agraph_t** ccs, Agraph_t* root)
424{
425 int j, i, nclust = 0;
426 Agraph_t* sg;
427 Agraph_t* cg;
428
429 for (i = 0; i < ncc; i++)
430 nclust += GD_n_cluster(ccs[i]);
431
432 GD_n_cluster(root) = nclust;
433 GD_clust(root) = N_NEW(nclust+1,Agraph_t*);
434 nclust = 1;
435 for (i = 0; i < ncc; i++) {
436 sg = ccs[i];
437 for (j = 1; j <= GD_n_cluster(sg); j++) {
438 cg = mapClust(GD_clust(sg)[j]);
439 GD_clust(root)[nclust++] = cg;
440 copyCluster (GD_clust(sg)[j], cg);
441 }
442 }
443}
444
445/* doDot:
446 * Assume g has nodes.
447 */
448static void doDot (Agraph_t* g)
449{
450 Agraph_t **ccs;
451 Agraph_t *sg;
452 int ncc;
453 int i;
454 pack_info pinfo;
455 int Pack = getPack(g, -1, CL_OFFSET);
456 pack_mode mode = getPackModeInfo (g, l_undef, &pinfo);
457 getPackInfo(g, l_node, CL_OFFSET, &pinfo);
458
459 if ((mode == l_undef) && (Pack < 0)) {
460 /* No pack information; use old dot with components
461 * handled during layout
462 */
463 dotLayout(g);
464 } else {
465 /* fill in default values */
466 if (mode == l_undef)
467 pinfo.mode = l_graph;
468 else if (Pack < 0)
469 Pack = CL_OFFSET;
470 pinfo.margin = Pack;
471 pinfo.fixed = 0;
472
473 /* components using clusters */
474 ccs = cccomps(g, &ncc, 0);
475 if (ncc == 1) {
476 dotLayout(g);
477 } else if (GD_drawing(g)->ratio_kind == R_NONE) {
478 pinfo.doSplines = 1;
479
480 for (i = 0; i < ncc; i++) {
481 sg = ccs[i];
482 initSubg (sg, g);
483 dotLayout (sg);
484 }
485 attachPos (g);
486 packSubgraphs(ncc, ccs, g, &pinfo);
487 resetCoord (g);
488 copyClusterInfo (ncc, ccs, g);
489 } else {
490 /* Not sure what semantics should be for non-trivial ratio
491 * attribute with multiple components.
492 * One possibility is to layout nodes, pack, then apply the ratio
493 * adjustment. We would then have to re-adjust all positions.
494 */
495 dotLayout(g);
496 }
497
498 for (i = 0; i < ncc; i++) {
499 free (GD_drawing(ccs[i]));
500 dot_cleanup_graph(ccs[i]);
501 agdelete(g, ccs[i]);
502 }
503 free(ccs);
504 }
505}
506
507void dot_layout(Agraph_t * g)
508{
509 if (agnnodes(g)) doDot (g);
510 dotneato_postprocess(g);
511}
512
513Agraph_t * dot_root (void* p)
514{
515 return GD_dotroot(agroot(p));
516}
517
518