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 * Written by Emden R. Gansner
17 * Derived from Graham Wills' algorithm described in GD'97.
18 */
19
20#include "circle.h"
21#include "adjust.h"
22#include "pack.h"
23#include "neatoprocs.h"
24
25static void twopi_init_edge(edge_t * e)
26{
27 agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //edge custom data
28 common_init_edge(e);
29 ED_factor(e) = late_double(e, E_weight, 1.0, 0.0);
30}
31
32static void twopi_init_node_edge(graph_t * g)
33{
34 node_t *n;
35 edge_t *e;
36 int i = 0;
37 int n_nodes = agnnodes(g);
38 rdata* alg;
39
40 alg = N_NEW(n_nodes, rdata);
41 GD_neato_nlist(g) = N_NEW(n_nodes + 1, node_t *);
42 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
43 neato_init_node(n);
44 ND_alg(n) = alg + i;
45 GD_neato_nlist(g)[i++] = n;
46 }
47 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
48 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
49 twopi_init_edge(e);
50 }
51 }
52}
53
54void twopi_init_graph(graph_t * g)
55{
56 setEdgeType (g, ET_LINE);
57 /* GD_ndim(g) = late_int(g,agfindgraphattr(g,"dim"),2,2); */
58 Ndim = GD_ndim(g)=2; /* The algorithm only makes sense in 2D */
59 twopi_init_node_edge(g);
60}
61
62static Agnode_t* findRootNode (Agraph_t* sg, Agsym_t* rootattr)
63{
64 Agnode_t* n;
65
66 for (n = agfstnode(sg); n; n = agnxtnode(sg,n)) {
67 if (mapbool(agxget(n,rootattr))) return n;
68 }
69 return NULL;
70
71}
72
73/* twopi_layout:
74 */
75void twopi_layout(Agraph_t * g)
76{
77 Agnode_t *ctr = 0;
78 char *s;
79 int setRoot = 0;
80 int setLocalRoot = 0;
81 pointf sc;
82 int doScale = 0;
83 int r;
84 Agsym_t* rootattr;
85
86 if (agnnodes(g) == 0) return;
87
88 twopi_init_graph(g);
89 if ((s = agget(g, "root"))) {
90 if (*s) {
91 ctr = agfindnode(g, s);
92 if (!ctr) {
93 agerr(AGWARN, "specified root node \"%s\" was not found.", s);
94 agerr(AGPREV, "Using default calculation for root node\n");
95 setRoot = 1;
96 }
97 }
98 else {
99 setRoot = 1;
100 }
101 }
102 if ((rootattr = agattr(g, AGNODE, "root", 0))) {
103 setLocalRoot = 1;
104 }
105
106 if ((s = agget(g, "scale")) && *s) {
107 if ((r = sscanf (s, "%lf,%lf",&sc.x,&sc.y))) {
108 if (r == 1) sc.y = sc.x;
109 doScale = 1;
110 }
111 }
112
113 if (agnnodes(g)) {
114 Agraph_t **ccs;
115 Agraph_t *sg;
116 Agnode_t *c = NULL;
117 Agnode_t *n;
118 int ncc;
119 int i;
120 Agnode_t* lctr;
121
122 ccs = ccomps(g, &ncc, 0);
123 if (ncc == 1) {
124 if (ctr)
125 lctr = ctr;
126 else if (!rootattr || !(lctr = findRootNode(g, rootattr)))
127 lctr = 0;
128 c = circleLayout(g, lctr);
129 if (setRoot && !ctr)
130 ctr = c;
131 if (setLocalRoot && !lctr)
132 agxset (c, rootattr, "1");
133 n = agfstnode(g);
134 free(ND_alg(n));
135 ND_alg(n) = NULL;
136 adjustNodes(g);
137 spline_edges(g);
138 } else {
139 pack_info pinfo;
140 getPackInfo (g, l_node, CL_OFFSET, &pinfo);
141 pinfo.doSplines = 0;
142
143 for (i = 0; i < ncc; i++) {
144 sg = ccs[i];
145 if (ctr && agcontains(sg, ctr))
146 lctr = ctr;
147 else if (!rootattr || !(lctr = findRootNode(sg, rootattr)))
148 lctr = 0;
149 nodeInduce(sg);
150 c = circleLayout(sg, lctr);
151 if (setRoot && !ctr)
152 ctr = c;
153 if (setLocalRoot && (!lctr || (lctr == ctr)))
154 agxset (c, rootattr, "1");
155 adjustNodes(sg);
156 }
157 n = agfstnode(g);
158 free(ND_alg(n));
159 ND_alg(n) = NULL;
160 packSubgraphs(ncc, ccs, g, &pinfo);
161 spline_edges(g);
162 }
163 for (i = 0; i < ncc; i++) {
164 agdelete(g, ccs[i]);
165 }
166 free(ccs);
167 }
168 if (setRoot)
169 agset (g, "root", agnameof (ctr));
170 dotneato_postprocess(g);
171
172}
173
174static void twopi_cleanup_graph(graph_t * g)
175{
176 free(GD_neato_nlist(g));
177 if (g != agroot(g))
178 agclean(g,AGRAPH,"Agraphinfo_t");
179}
180
181/* twopi_cleanup:
182 * The ND_alg data used by twopi is freed in twopi_layout
183 * before edge routing as edge routing may use this field.
184 */
185void twopi_cleanup(graph_t * g)
186{
187 node_t *n;
188 edge_t *e;
189
190 n = agfstnode (g);
191 if (!n) return; /* empty graph */
192 /* free (ND_alg(n)); */
193 for (; n; n = agnxtnode(g, n)) {
194 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
195 gv_cleanup_edge(e);
196 }
197 gv_cleanup_node(n);
198 }
199 twopi_cleanup_graph(g);
200}
201