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 "config.h"
16#include <limits.h>
17#include <sfdp.h>
18#include <neato.h>
19#include <adjust.h>
20#include <pack.h>
21#include <assert.h>
22#include <ctype.h>
23#include <spring_electrical.h>
24#include <overlap.h>
25#include <uniform_stress.h>
26#include <stress_model.h>
27
28static void sfdp_init_edge(edge_t * e)
29{
30 agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
31 common_init_edge(e);
32}
33
34static void sfdp_init_node_edge(graph_t * g)
35{
36 node_t *n;
37 edge_t *e;
38#if 0
39 int nnodes = agnnodes(g);
40 attrsym_t *N_pos = agfindnodeattr(g, "pos");
41#endif
42
43 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
44 neato_init_node(n);
45#if 0
46 FIX so that user positions works with multiscale
47 user_pos(N_pos, NULL, n, nnodes);
48#endif
49 }
50 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
51 for (e = agfstout(g, n); e; e = agnxtout(g, e))
52 sfdp_init_edge(e);
53 }
54}
55
56static void sfdp_init_graph(Agraph_t * g)
57{
58 int outdim;
59
60 setEdgeType(g, ET_LINE);
61 outdim = late_int(g, agfindgraphattr(g, "dimen"), 2, 2);
62 GD_ndim(agroot(g)) = late_int(g, agfindgraphattr(g, "dim"), outdim, 2);
63 Ndim = GD_ndim(agroot(g)) = MIN(GD_ndim(agroot(g)), MAXDIM);
64 GD_odim(agroot(g)) = MIN(outdim, Ndim);
65 sfdp_init_node_edge(g);
66}
67
68/* getPos:
69 */
70static real *getPos(Agraph_t * g, spring_electrical_control ctrl)
71{
72 Agnode_t *n;
73 real *pos = N_NEW(Ndim * agnnodes(g), real);
74 int ix, i;
75
76 if (agfindnodeattr(g, "pos") == NULL)
77 return pos;
78
79 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
80 i = ND_id(n);
81 if (hasPos(n)) {
82 for (ix = 0; ix < Ndim; ix++) {
83 pos[i * Ndim + ix] = ND_pos(n)[ix];
84 }
85 }
86 }
87
88 return pos;
89}
90
91static void sfdpLayout(graph_t * g, spring_electrical_control ctrl,
92 int hops, pointf pad)
93{
94 real *sizes;
95 real *pos;
96 Agnode_t *n;
97 int flag, i;
98 int n_edge_label_nodes = 0, *edge_label_nodes = NULL;
99 SparseMatrix D = NULL;
100 SparseMatrix A;
101
102 if (ctrl->method == METHOD_SPRING_MAXENT) /* maxent can work with distance matrix */
103 A = makeMatrix(g, Ndim, &D);
104 else
105 A = makeMatrix(g, Ndim, NULL);
106
107 if (ctrl->overlap >= 0) {
108 if (ctrl->edge_labeling_scheme > 0)
109 sizes = getSizes(g, pad, &n_edge_label_nodes, &edge_label_nodes);
110 else
111 sizes = getSizes(g, pad, NULL, NULL);
112 }
113 else
114 sizes = NULL;
115 pos = getPos(g, ctrl);
116
117 switch (ctrl->method) {
118 case METHOD_SPRING_ELECTRICAL:
119 case METHOD_SPRING_MAXENT:
120 multilevel_spring_electrical_embedding(Ndim, A, D, ctrl, NULL, sizes, pos, n_edge_label_nodes, edge_label_nodes, &flag);
121 break;
122 case METHOD_UNIFORM_STRESS:
123 uniform_stress(Ndim, A, pos, &flag);
124 break;
125 case METHOD_STRESS:{
126 int maxit = 200;
127 real tol = 0.001;
128 int weighted = TRUE;
129
130 if (!D){
131 D = SparseMatrix_get_real_adjacency_matrix_symmetrized(A);/* all distance 1 */
132 weighted = FALSE;
133 } else {
134 D = SparseMatrix_symmetrize_nodiag(D, FALSE);
135 weighted = TRUE;
136 }
137 if (hops > 0){
138 SparseMatrix DD;
139 DD = SparseMatrix_distance_matrix_khops(hops, D, weighted);
140 if (Verbose){
141 fprintf(stderr,"extracted a %d-neighborhood graph of %d edges from a graph of %d edges\n",
142 hops, (DD->nz)/2, (D->nz/2));
143 }
144 SparseMatrix_delete(D);
145 D = DD;
146 }
147
148 stress_model(Ndim, A, D, &pos, TRUE, maxit, tol, &flag);
149 }
150 break;
151 }
152
153 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
154 real *npos = pos + (Ndim * ND_id(n));
155 for (i = 0; i < Ndim; i++) {
156 ND_pos(n)[i] = npos[i];
157 }
158 }
159
160 free(sizes);
161 free(pos);
162 SparseMatrix_delete (A);
163 if (D) SparseMatrix_delete (D);
164 if (edge_label_nodes) FREE(edge_label_nodes);
165}
166
167#if UNUSED
168static int
169late_mode (graph_t* g, Agsym_t* sym, int dflt)
170{
171 char* s;
172 int v;
173 int rv;
174
175 if (!sym) return dflt;
176 s = agxget (g, sym);
177 if (isdigit(*s)) {
178 if ((v = atoi (s)) <= METHOD_UNIFORM_STRESS)
179 rv = v;
180 else
181 rv = dflt;
182 }
183 else if (isalpha(*s)) {
184 if (!strcasecmp(s, "spring"))
185 rv = METHOD_SPRING_ELECTRICAL;
186 else if (!strcasecmp(s, "maxent"))
187 rv = METHOD_SPRING_MAXENT;
188 else if (!strcasecmp(s, "stress"))
189 rv = METHOD_STRESS;
190 else if (!strcasecmp(s, "uniform"))
191 rv = METHOD_UNIFORM_STRESS;
192 else {
193 agerr (AGWARN, "Unknown value \"%s\" for mode attribute\n", s);
194 rv = dflt;
195 }
196 }
197 else
198 rv = dflt;
199 return rv;
200}
201#endif
202
203static int
204late_smooth (graph_t* g, Agsym_t* sym, int dflt)
205{
206 char* s;
207 int v;
208 int rv;
209
210 if (!sym) return dflt;
211 s = agxget (g, sym);
212 if (isdigit(*s)) {
213#if (HAVE_GTS || HAVE_TRIANGLE)
214 if ((v = atoi (s)) <= SMOOTHING_RNG)
215#else
216 if ((v = atoi (s)) <= SMOOTHING_SPRING)
217#endif
218 rv = v;
219 else
220 rv = dflt;
221 }
222 else if (isalpha(*s)) {
223 if (!strcasecmp(s, "avg_dist"))
224 rv = SMOOTHING_STRESS_MAJORIZATION_AVG_DIST;
225 else if (!strcasecmp(s, "graph_dist"))
226 rv = SMOOTHING_STRESS_MAJORIZATION_GRAPH_DIST;
227 else if (!strcasecmp(s, "none"))
228 rv = SMOOTHING_NONE;
229 else if (!strcasecmp(s, "power_dist"))
230 rv = SMOOTHING_STRESS_MAJORIZATION_POWER_DIST;
231#if (HAVE_GTS || HAVE_TRIANGLE)
232 else if (!strcasecmp(s, "rng"))
233 rv = SMOOTHING_RNG;
234#endif
235 else if (!strcasecmp(s, "spring"))
236 rv = SMOOTHING_SPRING;
237#if (HAVE_GTS || HAVE_TRIANGLE)
238 else if (!strcasecmp(s, "triangle"))
239 rv = SMOOTHING_TRIANGLE;
240#endif
241 else
242 rv = dflt;
243 }
244 else
245 rv = dflt;
246 return rv;
247}
248
249static int
250late_quadtree_scheme (graph_t* g, Agsym_t* sym, int dflt)
251{
252 char* s;
253 int v;
254 int rv;
255
256 if (!sym) return dflt;
257 s = agxget (g, sym);
258 if (isdigit(*s)) {
259 if ((v = atoi (s)) <= QUAD_TREE_FAST && v >= QUAD_TREE_NONE){
260 rv = v;
261 } else {
262 rv = dflt;
263 }
264 } else if (isalpha(*s)) {
265 if (!strcasecmp(s, "none") || !strcasecmp(s, "false") ){
266 rv = QUAD_TREE_NONE;
267 } else if (!strcasecmp(s, "normal") || !strcasecmp(s, "true") || !strcasecmp(s, "yes")){
268 rv = QUAD_TREE_NORMAL;
269 } else if (!strcasecmp(s, "fast")){
270 rv = QUAD_TREE_FAST;
271 } else {
272 rv = dflt;
273 }
274 } else {
275 rv = dflt;
276 }
277 return rv;
278}
279
280
281/* tuneControl:
282 * Use user values to reset control
283 *
284 * Possible parameters:
285 * ctrl->use_node_weights
286 */
287static void
288tuneControl (graph_t* g, spring_electrical_control ctrl)
289{
290 long seed;
291 int init;
292
293 seed = ctrl->random_seed;
294 init = setSeed (g, INIT_RANDOM, &seed);
295 if (init != INIT_RANDOM) {
296 agerr(AGWARN, "sfdp only supports start=random\n");
297 }
298 ctrl->random_seed = seed;
299
300 ctrl->K = late_double(g, agfindgraphattr(g, "K"), -1.0, 0.0);
301 ctrl->p = -1.0*late_double(g, agfindgraphattr(g, "repulsiveforce"), -AUTOP, 0.0);
302 ctrl->multilevels = late_int(g, agfindgraphattr(g, "levels"), INT_MAX, 0);
303 ctrl->smoothing = late_smooth(g, agfindgraphattr(g, "smoothing"), SMOOTHING_NONE);
304 ctrl->tscheme = late_quadtree_scheme(g, agfindgraphattr(g, "quadtree"), QUAD_TREE_NORMAL);
305 /* ctrl->method = late_mode(g, agfindgraphattr(g, "mode"), METHOD_SPRING_ELECTRICAL); */
306 ctrl->method = METHOD_SPRING_ELECTRICAL;
307 ctrl->beautify_leaves = mapBool (agget(g, "beautify"), FALSE);
308 ctrl->do_shrinking = mapBool (agget(g, "overlap_shrink"), TRUE);
309 ctrl->rotation = late_double(g, agfindgraphattr(g, "rotation"), 0.0, -MAXDOUBLE);
310 ctrl->edge_labeling_scheme = late_int(g, agfindgraphattr(g, "label_scheme"), 0, 0);
311 if (ctrl->edge_labeling_scheme > 4) {
312 agerr (AGWARN, "label_scheme = %d > 4 : ignoring\n", ctrl->edge_labeling_scheme);
313 ctrl->edge_labeling_scheme = 0;
314 }
315}
316
317void sfdp_layout(graph_t * g)
318{
319 int doAdjust;
320 adjust_data am;
321 int hops = -1;
322 sfdp_init_graph(g);
323 doAdjust = (Ndim == 2);
324
325 if (agnnodes(g)) {
326 Agraph_t **ccs;
327 Agraph_t *sg;
328 int ncc;
329 int i;
330 expand_t sep;
331 pointf pad;
332 spring_electrical_control ctrl = spring_electrical_control_new();
333
334 tuneControl (g, ctrl);
335#if (HAVE_GTS || HAVE_TRIANGLE)
336 graphAdjustMode(g, &am, "prism0");
337#else
338 graphAdjustMode(g, &am, 0);
339#endif
340
341 pad.x = PS2INCH(DFLT_MARGIN);
342 pad.y = PS2INCH(DFLT_MARGIN);
343
344 if ((am.mode == AM_PRISM) && doAdjust) {
345 doAdjust = 0; /* overlap removal done in sfdp */
346 ctrl->overlap = am.value;
347 ctrl->initial_scaling = am.scaling;
348 sep = sepFactor(g);
349 if (sep.doAdd) {
350 pad.x = PS2INCH(sep.x);
351 pad.y = PS2INCH(sep.y);
352 }
353 }
354 else {
355 /* Turn off overlap removal in sfdp if prism not used */
356 ctrl->overlap = -1;
357 }
358
359 if (Verbose)
360 spring_electrical_control_print(ctrl);
361
362 ccs = ccomps(g, &ncc, 0);
363 if (ncc == 1) {
364 sfdpLayout(g, ctrl, hops, pad);
365 if (doAdjust) removeOverlapWith(g, &am);
366 spline_edges(g);
367 } else {
368 pack_info pinfo;
369 getPackInfo(g, l_node, CL_OFFSET, &pinfo);
370 pinfo.doSplines = 1;
371
372 for (i = 0; i < ncc; i++) {
373 sg = ccs[i];
374 nodeInduce(sg);
375 sfdpLayout(sg, ctrl, hops, pad);
376 if (doAdjust) removeOverlapWith(sg, &am);
377 setEdgeType(sg, ET_LINE);
378 spline_edges(sg);
379 }
380 packSubgraphs(ncc, ccs, g, &pinfo);
381 }
382 for (i = 0; i < ncc; i++) {
383 agdelete(g, ccs[i]);
384 }
385 free(ccs);
386 spring_electrical_control_delete(ctrl);
387 }
388
389 dotneato_postprocess(g);
390}
391
392static void sfdp_cleanup_graph(graph_t * g)
393{
394}
395
396void sfdp_cleanup(graph_t * g)
397{
398 node_t *n;
399 edge_t *e;
400
401 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
402 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
403 gv_cleanup_edge(e);
404 }
405 gv_cleanup_node(n);
406 }
407 sfdp_cleanup_graph(g);
408}
409
410