Graphviz  2.41.20170921.2350
sfdpinit.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 #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 
28 static void sfdp_init_edge(edge_t * e)
29 {
30  agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
32 }
33 
34 static 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 
56 static 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  */
70 static 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 
91 static 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) {
120  multilevel_spring_electrical_embedding(Ndim, A, D, ctrl, NULL, sizes, pos, n_edge_label_nodes, edge_label_nodes, &flag);
121  break;
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 {
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  }
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);
163  if (D) SparseMatrix_delete (D);
164  if (edge_label_nodes) FREE(edge_label_nodes);
165 }
166 
167 #if UNUSED
168 static int
169 late_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"))
186  else if (!strcasecmp(s, "maxent"))
188  else if (!strcasecmp(s, "stress"))
189  rv = METHOD_STRESS;
190  else if (!strcasecmp(s, "uniform"))
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 
203 static int
204 late_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"))
225  else if (!strcasecmp(s, "graph_dist"))
227  else if (!strcasecmp(s, "none"))
228  rv = SMOOTHING_NONE;
229  else if (!strcasecmp(s, "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 
249 static int
250 late_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  */
287 static void
288 tuneControl (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); */
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 
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;
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  if ((am.mode == AM_PRISM) && doAdjust) {
342  doAdjust = 0; /* overlap removal done in sfdp */
343  ctrl->overlap = am.value;
344  ctrl->initial_scaling = am.scaling;
345  sep = sepFactor(g);
346  if (sep.doAdd) {
347  pad.x = PS2INCH(sep.x);
348  pad.y = PS2INCH(sep.y);
349  } else {
350  pad.x = PS2INCH(DFLT_MARGIN);
351  pad.y = PS2INCH(DFLT_MARGIN);
352  }
353  }
354  else {
355  /* Turn off overlap removal in sfdp if prism not used */
356  ctrl->overlap = -1;
357  }
358 
359  if (Verbose)
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);
387  }
388 
390 }
391 
392 static void sfdp_cleanup_graph(graph_t * g)
393 {
394 }
395 
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 
void dotneato_postprocess(Agraph_t *g)
Definition: postproc.c:693
boolean doAdd
Definition: adjust.h:45
void uniform_stress(int dim, SparseMatrix A, real *x, int *flag)
spring_electrical_control spring_electrical_control_new()
#define N_NEW(n, t)
Definition: memory.h:36
Definition: pack.h:49
void spring_electrical_control_delete(spring_electrical_control ctrl)
Definition: pack.h:37
SparseMatrix SparseMatrix_symmetrize_nodiag(SparseMatrix A, int pattern_symmetric_only)
Definition: SparseMatrix.c:163
adjust_mode mode
Definition: adjust.h:37
int value
Definition: adjust.h:39
#define MIN(a, b)
Definition: arith.h:35
expand_t sepFactor(graph_t *g)
Definition: adjust.c:1287
int nodeInduce(Agraph_t *g)
Definition: ccomps.c:718
SparseMatrix makeMatrix(Agraph_t *g, int dim, SparseMatrix *D)
Definition: adjust.c:703
#define FREE
Definition: PriorityQueue.c:23
#define hasPos(n)
Definition: macros.h:26
Definition: geom.h:28
void stress_model(int dim, SparseMatrix A, SparseMatrix D, real **x, int edge_len_weighted, int maxit_sm, real tol, int *flag)
Definition: stress_model.c:98
CGRAPH_API int agdelete(Agraph_t *g, void *obj)
Definition: obj.c:16
#define ND_pos(n)
Definition: types.h:526
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
void gv_cleanup_edge(Agedge_t *e)
Definition: utils.c:1947
pack_mode getPackInfo(Agraph_t *g, pack_mode dflt, int dfltMargin, pack_info *pinfo)
Definition: pack.c:1398
CGRAPH_API Agraph_t * agroot(void *obj)
Definition: obj.c:169
#define DFLT_MARGIN
Definition: adjust.h:26
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
Definition: cgraph.h:388
#define PS2INCH(a_points)
Definition: geom.h:69
char * agget(void *obj, char *name)
Definition: attr.c:428
double scaling
Definition: adjust.h:40
#define GD_odim(g)
Definition: types.h:399
int user_pos(attrsym_t *posptr, attrsym_t *pinptr, node_t *np, int nG)
Definition: neatoinit.c:57
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
adjust_data * graphAdjustMode(graph_t *G, adjust_data *dp, char *dflt)
Definition: adjust.c:1077
#define AUTOP
int doSplines
Definition: pack.h:53
double y
Definition: geom.h:28
void spring_electrical_control_print(spring_electrical_control ctrl)
#define ND_id(n)
Definition: types.h:489
void spline_edges(Agraph_t *)
Definition: neatosplines.c:804
float y
Definition: adjust.h:44
SparseMatrix SparseMatrix_get_real_adjacency_matrix_symmetrized(SparseMatrix A)
void multilevel_spring_electrical_embedding(int dim, SparseMatrix A, SparseMatrix D, spring_electrical_control ctrl, real *node_weights, real *label_sizes, real *x, int n_edge_label_nodes, int *edge_label_nodes, int *flag)
#define ET_LINE
Definition: const.h:271
int removeOverlapWith(graph_t *G, adjust_data *am)
Definition: adjust.c:1118
boolean mapBool(char *p, boolean dflt)
Definition: utils.c:454
#define GD_ndim(g)
Definition: types.h:398
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
int late_int(void *obj, attrsym_t *attr, int def, int low)
Definition: utils.c:71
void SparseMatrix_delete(SparseMatrix A)
Definition: SparseMatrix.c:411
Definition: grammar.c:79
#define CL_OFFSET
Definition: const.h:155
void sfdp_layout(graph_t *g)
Definition: sfdpinit.c:317
int packSubgraphs(int ng, Agraph_t **gs, Agraph_t *root, pack_info *info)
Definition: pack.c:1163
#define NULL
Definition: logic.h:39
#define agfindgraphattr(g, a)
Definition: types.h:612
double x
Definition: geom.h:28
double late_double(void *obj, attrsym_t *attr, double def, double low)
Definition: utils.c:87
EXTERN unsigned char Verbose
Definition: globals.h:64
void gv_cleanup_node(Agnode_t *n)
Definition: utils.c:1959
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
int strcasecmp(const char *s1, const char *s2)
Definition: strcasecmp.c:21
int setSeed(graph_t *G, int dflt, long *seedp)
Definition: neatoinit.c:958
void sfdp_cleanup(graph_t *g)
Definition: sfdpinit.c:396
#define INIT_RANDOM
Definition: neato.h:33
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
SparseMatrix SparseMatrix_distance_matrix_khops(int khops, SparseMatrix D0, int weighted)
int common_init_edge(edge_t *e)
Definition: utils.c:714
void setEdgeType(graph_t *g, int dflt)
Definition: utils.c:1802
void neato_init_node(node_t *n)
Definition: neatoinit.c:42
#define MAXDIM
Definition: const.h:177
double * getSizes(Agraph_t *g, pointf pad, int *n_elabels, int **elabels)
Definition: adjust.c:670
Agraph_t ** ccomps(Agraph_t *g, int *ncc, char *pfx)
Definition: ccomps.c:288
char * agxget(void *obj, Agsym_t *sym)
Definition: attr.c:444
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
float x
Definition: adjust.h:44
#define agfindnodeattr(g, a)
Definition: types.h:613
#define FALSE
Definition: cgraph.h:35
#define MAXDOUBLE
Definition: arith.h:64
EXTERN int Ndim
Definition: globals.h:79
#define INT_MAX
Definition: arith.h:52
#define TRUE
Definition: cgraph.h:38
#define real
Definition: general.h:34