Graphviz  2.41.20170921.2350
neatoinit.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 
17 #include <time.h>
18 #ifndef _WIN32
19 #include <unistd.h>
20 #endif
21 #include <ctype.h>
22 
23 #include "neato.h"
24 #include "pack.h"
25 #include "stress.h"
26 #ifdef DIGCOLA
27 #include "digcola.h"
28 #endif
29 #include "kkutils.h"
30 #include "pointset.h"
31 
32 #ifndef HAVE_SRAND48
33 #define srand48 srand
34 #endif
35 
36 static attrsym_t *N_pos;
37 static int Pack; /* If >= 0, layout components separately and pack together
38  * The value of Pack gives margins around graphs.
39  */
40 static char *cc_pfx = "_neato_cc";
41 
43 {
44  agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); //node custom data
46  ND_pos(n) = N_NEW(GD_ndim(agraphof(n)), double);
48 }
49 
50 static void neato_init_edge(edge_t * e)
51 {
52  agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
54  ED_factor(e) = late_double(e, E_weight, 1.0, 1.0);
55 }
56 
57 int user_pos(attrsym_t * posptr, attrsym_t * pinptr, node_t * np, int nG)
58 {
59  double *pvec;
60  char *p, c;
61  double z;
62 
63  if (posptr == NULL)
64  return FALSE;
65  pvec = ND_pos(np);
66  p = agxget(np, posptr);
67  if (p[0]) {
68  c = '\0';
69  if ((Ndim >= 3) &&
70  (sscanf(p, "%lf,%lf,%lf%c", pvec, pvec+1, pvec+2, &c) >= 3)){
71  ND_pinned(np) = P_SET;
72  if (PSinputscale > 0.0) {
73  int i;
74  for (i = 0; i < Ndim; i++)
75  pvec[i] = pvec[i] / PSinputscale;
76  }
77  if (Ndim > 3)
78  jitter_d(np, nG, 3);
79  if ((c == '!') || (pinptr && mapbool(agxget(np, pinptr))))
80  ND_pinned(np) = P_PIN;
81  return TRUE;
82  }
83  else if (sscanf(p, "%lf,%lf%c", pvec, pvec + 1, &c) >= 2) {
84  ND_pinned(np) = P_SET;
85  if (PSinputscale > 0.0) {
86  int i;
87  for (i = 0; i < Ndim; i++)
88  pvec[i] = pvec[i] / PSinputscale;
89  }
90  if (Ndim > 2) {
91  if (N_z && (p = agxget(np, N_z)) && (sscanf(p,"%lf",&z) == 1)) {
92  if (PSinputscale > 0.0) {
93  pvec[2] = z / PSinputscale;
94  }
95  else
96  pvec[2] = z;
97  jitter_d(np, nG, 3);
98  }
99  else
100  jitter3d(np, nG);
101  }
102  if ((c == '!') || (pinptr && mapbool(agxget(np, pinptr))))
103  ND_pinned(np) = P_PIN;
104  return TRUE;
105  } else
106  agerr(AGERR, "node %s, position %s, expected two doubles\n",
107  agnameof(np), p);
108  }
109  return FALSE;
110 }
111 
112 static void neato_init_node_edge(graph_t * g)
113 {
114  node_t *n;
115  edge_t *e;
116  int nG = agnnodes(g);
117  attrsym_t *N_pin;
118 
119  N_pos = agfindnodeattr(g, "pos");
120  N_pin = agfindnodeattr(g, "pin");
121 
122  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
123  neato_init_node(n);
124  user_pos(N_pos, N_pin, n, nG); /* set user position if given */
125  }
126  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
127  for (e = agfstout(g, n); e; e = agnxtout(g, e))
128  neato_init_edge(e);
129  }
130 }
131 
132 static void neato_cleanup_graph(graph_t * g)
133 {
134  if (Nop || (Pack < 0)) {
135  free_scan_graph(g);
136  free(GD_clust(g));
137  }
138  if (g != agroot(g))
139  agclean(g, AGRAPH , "Agraphinfo_t");
140 }
141 
143 {
144  node_t *n;
145  edge_t *e;
146 
147  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
148  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
149  gv_cleanup_edge(e);
150  }
151  gv_cleanup_node(n);
152  }
153  neato_cleanup_graph(g);
154 }
155 
156 static int numFields(unsigned char *pos)
157 {
158  int cnt = 0;
159  unsigned char c;
160 
161  do {
162  while (isspace(*pos))
163  pos++; /* skip white space */
164  if ((c = *pos)) { /* skip token */
165  cnt++;
166  while ((c = *pos) && !isspace(c) && (c != ';'))
167  pos++;
168  }
169  } while (isspace(c));
170  return cnt;
171 }
172 
173 static void set_label(void* obj, textlabel_t * l, char *name)
174 {
175  double x, y;
176  char *lp;
177  lp = agget(obj, name);
178  if (lp && (sscanf(lp, "%lf,%lf", &x, &y) == 2)) {
179  l->pos = pointfof(x, y);
180  l->set = TRUE;
181  }
182 }
183 
184 #ifdef IPSEPCOLA
185 static cluster_data* cluster_map(graph_t *mastergraph, graph_t *g)
186 {
187  graph_t *subg;
188  node_t *n;
189  /* array of arrays of node indices in each cluster */
190  int **cs,*cn;
191  int i,j,nclusters=0;
192  boolean* assigned = N_NEW(agnnodes(g), boolean);
193  cluster_data *cdata = GNEW(cluster_data);
194 
195  cdata->ntoplevel = agnnodes(g);
196  for (subg = agfstsubg(mastergraph); subg; subg = agnxtsubg(subg)) {
197  if (!strncmp(agnameof(subg), "cluster", 7)) {
198  nclusters++;
199  }
200  }
201  cdata->nvars=0;
202  cdata->nclusters = nclusters;
203  cs = cdata->clusters = N_GNEW(nclusters,int*);
204  cn = cdata->clustersizes = N_GNEW(nclusters,int);
205  for (subg = agfstsubg(mastergraph); subg; subg = agnxtsubg(subg)) {
206  /* clusters are processed by separate calls to ordered_edges */
207  if (!strncmp(agnameof(subg), "cluster", 7)) {
208  int *c;
209 
210  *cn = agnnodes(subg);
211  cdata->nvars += *cn;
212  c = *cs++ = N_GNEW(*cn++,int);
213  /* fprintf(stderr,"Cluster with %d nodes...\n",agnnodes(subg)); */
214  for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
215  node_t *gn;
216  int ind = 0;
217  for (gn = agfstnode(g); gn; gn = agnxtnode(g, gn)) {
218  if(AGSEQ(gn)==AGSEQ(n)) break;
219  ind++;
220  }
221  /* fprintf(stderr," node=%s, id=%d, ind=%d\n",agnameof(n),n->id,ind); */
222  *c++=ind;
223  assigned[ind]=TRUE;
224  cdata->ntoplevel--;
225  }
226  }
227  }
228  cdata->bb=N_GNEW(cdata->nclusters,boxf);
229  cdata->toplevel=N_GNEW(cdata->ntoplevel,int);
230  for(i=j=0;i<agnnodes(g);i++) {
231  if(!assigned[i]) {
232  cdata->toplevel[j++]=i;
233  }
234  }
235  assert(cdata->ntoplevel==agnnodes(g)-cdata->nvars);
236  free (assigned);
237  return cdata;
238 }
239 
240 static void freeClusterData(cluster_data *c) {
241  if(c->nclusters>0) {
242  free(c->clusters[0]);
243  free(c->clusters);
244  free(c->clustersizes);
245  free(c->toplevel);
246  free(c->bb);
247  }
248  free(c);
249 }
250 #endif
251 
252 /* user_spline:
253  * Attempt to use already existing pos info for spline
254  * Return 1 if successful, 0 otherwise.
255  * Assume E_pos != NULL and ED_spl(e) == NULL.
256  */
257 static int user_spline(attrsym_t * E_pos, edge_t * e)
258 {
259  char *pos;
260  int i, n, npts, nc;
261  pointf *ps = 0;
262  pointf *pp;
263  double x, y;
264  int sflag = 0, eflag = 0;
265  pointf sp = { 0, 0 }, ep = { 0, 0};
266  bezier *newspl;
267  int more = 1;
268  int stype, etype;
269  static boolean warned;
270 
271  pos = agxget(e, E_pos);
272  if (*pos == '\0')
273  return 0;
274 
275  arrow_flags(e, &stype, &etype);
276  do {
277  /* check for s head */
278  i = sscanf(pos, "s,%lf,%lf%n", &x, &y, &nc);
279  if (i == 2) {
280  sflag = 1;
281  pos = pos + nc;
282  sp.x = x;
283  sp.y = y;
284  }
285 
286  /* check for e head */
287  i = sscanf(pos, " e,%lf,%lf%n", &x, &y, &nc);
288  if (i == 2) {
289  eflag = 1;
290  pos = pos + nc;
291  ep.x = x;
292  ep.y = y;
293  }
294 
295  npts = numFields((unsigned char *) pos); /* count potential points */
296  n = npts;
297  if ((n < 4) || (n % 3 != 1)) {
298  gv_free_splines(e);
299  if (!warned) {
300  warned = 1;
301  agerr(AGWARN, "pos attribute for edge (%s,%s) doesn't have 3n+1 points\n", agnameof(agtail(e)), agnameof(aghead(e)));
302  }
303  return 0;
304  }
305  ps = ALLOC(n, 0, pointf);
306  pp = ps;
307  while (n) {
308  i = sscanf(pos, "%lf,%lf%n", &x, &y, &nc);
309  if (i < 2) {
310  if (!warned) {
311  warned = 1;
312  agerr(AGWARN, "syntax error in pos attribute for edge (%s,%s)\n", agnameof(agtail(e)), agnameof(aghead(e)));
313  }
314  free(ps);
315  gv_free_splines(e);
316  return 0;
317  }
318  pos = pos + nc;
319  pp->x = x;
320  pp->y = y;
321  pp++;
322  n--;
323  }
324  while (isspace(*pos)) pos++;
325  if (*pos == '\0')
326  more = 0;
327  else
328  pos++;
329 
330  /* parsed successfully; create spline */
331  newspl = new_spline(e, npts);
332  if (sflag) {
333  newspl->sflag = stype;
334  newspl->sp = sp;
335  }
336  if (eflag) {
337  newspl->eflag = etype;
338  newspl->ep = ep;
339  }
340  for (i = 0; i < npts; i++) {
341  newspl->list[i] = ps[i];
342  }
343  free(ps);
344  } while (more);
345 
346  if (ED_label(e))
347  set_label(e, ED_label(e), "lp");
348  if (ED_xlabel(e))
349  set_label(e, ED_xlabel(e), "xlp");
350  if (ED_head_label(e))
351  set_label(e, ED_head_label(e), "head_lp");
352  if (ED_tail_label(e))
353  set_label(e, ED_tail_label(e), "tail_lp");
354 
355  return 1;
356 }
357 
358 /* Nop can be:
359  * 0 - do full layout
360  * 1 - assume initial node positions, do (optional) adjust and all splines
361  * 2 - assume final node and edges positions, do nothing except compute
362  * missing splines
363  */
364 
365  /* Indicates the amount of edges with position information */
366 typedef enum { NoEdges, SomeEdges, AllEdges } pos_edge;
367 
368 /* nop_init_edges:
369  * Check edges for position info.
370  * If position info exists, check for edge label positions.
371  * Return number of edges with position info.
372  */
373 static pos_edge nop_init_edges(Agraph_t * g)
374 {
375  node_t *n;
376  edge_t *e;
377  int nedges = 0;
378  attrsym_t *E_pos;
379 
380  if (agnedges(g) == 0)
381  return AllEdges;
382 
383  E_pos = agfindedgeattr(g, "pos");
384  if (!E_pos || (Nop < 2))
385  return NoEdges;
386 
387  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
388  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
389  if (user_spline(E_pos, e)) {
390  nedges++;
391  }
392  }
393  }
394  if (nedges) {
395  if (nedges == agnedges(g))
396  return AllEdges;
397  else
398  return SomeEdges;
399  } else
400  return NoEdges;
401 }
402 
403 /* freeEdgeInfo:
404  */
405 static void freeEdgeInfo (Agraph_t * g)
406 {
407  node_t *n;
408  edge_t *e;
409 
410  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
411  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
412  gv_free_splines(e);
413  free_label(ED_label(e));
414  free_label(ED_xlabel(e));
417  }
418  }
419 }
420 
421 /* chkBB:
422  * Scans for a correct bb attribute. If available, sets it
423  * in the graph and returns 1.
424  */
425 #define BS "%lf,%lf,%lf,%lf"
426 
427 static int chkBB(Agraph_t * g, attrsym_t * G_bb, boxf* bbp)
428 {
429  char *s;
430  boxf bb;
431 
432  s = agxget(g, G_bb);
433  if (sscanf(s, BS, &bb.LL.x, &bb.LL.y, &bb.UR.x, &bb.UR.y) == 4) {
434  if (bb.LL.y > bb.UR.y) {
435  /* If the LL.y coordinate is bigger than the UR.y coordinate,
436  * we assume the input was produced using -y, so we normalize
437  * the bb.
438  */
439  double tmp = bb.LL.y;
440  bb.LL.y = bb.UR.y;
441  bb.UR.y = tmp;
442  }
443  *bbp = bb;
444  return 1;
445  } else
446  return 0;
447 }
448 
449 static void add_cluster(Agraph_t * g, Agraph_t * subg)
450 {
451  int cno;
452  cno = ++(GD_n_cluster(g));
453  GD_clust(g) = ZALLOC(cno + 1, GD_clust(g), graph_t *, GD_n_cluster(g));
454  GD_clust(g)[cno] = subg;
455  do_graph_label(subg);
456 }
457 
458 
459 static void nop_init_graphs(Agraph_t *, attrsym_t *, attrsym_t *);
460 
461 /* dfs:
462  * Process subgraph subg of parent graph g
463  * If subg is a cluster, add its bounding box, if any; attach to
464  * cluster array of parent, and recursively initialize subg.
465  * If not a cluster, recursively call this function on the subgraphs
466  * of subg, using parentg as the parent graph.
467  */
468 static void
469 dfs(Agraph_t * subg, Agraph_t * parentg, attrsym_t * G_lp, attrsym_t * G_bb)
470 {
471  boxf bb;
472 
473  if (!strncmp(agnameof(subg), "cluster", 7) && chkBB(subg, G_bb, &bb)) {
474  agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
475  GD_bb(subg) = bb;
476  add_cluster(parentg, subg);
477  nop_init_graphs(subg, G_lp, G_bb);
478  } else {
479  graph_t *sg;
480  for (sg = agfstsubg(subg); sg; sg = agnxtsubg(sg)) {
481  dfs(sg, parentg, G_lp, G_bb);
482  }
483  }
484 }
485 
486 /* nop_init_graphs:
487  * Read in clusters and graph label info.
488  * A subgraph is a cluster if its name starts with "cluster" and
489  * it has a valid bb.
490  */
491 static void
492 nop_init_graphs(Agraph_t * g, attrsym_t * G_lp, attrsym_t * G_bb)
493 {
494  graph_t *subg;
495  char *s;
496  double x, y;
497 
498  if (GD_label(g) && G_lp) {
499  s = agxget(g, G_lp);
500  if (sscanf(s, "%lf,%lf", &x, &y) == 2) {
501  GD_label(g)->pos = pointfof(x, y);
502  GD_label(g)->set = TRUE;
503  }
504  }
505 
506  if (!G_bb)
507  return;
508  for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
509  dfs(subg, g, G_lp, G_bb);
510  }
511 }
512 
513 /* init_nop:
514  * This assumes all nodes have been positioned.
515  * It also assumes none of the relevant fields in A*info_t have been set.
516  * The input may provide additional position information for
517  * clusters, edges and labels. If certain position information
518  * is missing, init_nop will use a standard neato technique to
519  * supply it.
520  *
521  * If adjust is false, init_nop does nothing but initialize all
522  * of the basic graph information. No tweaking of positions or
523  * filling in edge splines is done.
524  *
525  * Returns 0 on normal success, 1 if layout has a background, and -1
526  * on failure.
527  */
528 int init_nop(Agraph_t * g, int adjust)
529 {
530  int i;
531  node_t *np;
532  pos_edge posEdges; /* How many edges have spline info */
533  attrsym_t *G_lp = agfindgraphattr(g, "lp");
534  attrsym_t *G_bb = agfindgraphattr(g, "bb");
535  int didAdjust = 0; /* Have nodes been moved? */
536  int haveBackground;
537  boolean translate = !mapBool(agget(g, "notranslate"), FALSE);
538 
539  /* If G_bb not defined, define it */
540  if (!G_bb)
541  G_bb = agattr(g, AGRAPH, "bb", "");
542 
543  scan_graph(g); /* mainly to set up GD_neato_nlist */
544  for (i = 0; (np = GD_neato_nlist(g)[i]); i++) {
545  if (!hasPos(np) && strncmp(agnameof(np), "cluster", 7)) {
546  agerr(AGERR, "node %s in graph %s has no position\n",
547  agnameof(np), agnameof(g));
548  return -1;
549  }
550  if (ND_xlabel(np))
551  set_label(np, ND_xlabel(np), "xlp");
552  }
553  nop_init_graphs(g, G_lp, G_bb);
554  posEdges = nop_init_edges(g);
555 
556  if (GD_drawing(g)->xdots) {
557  haveBackground = 1;
558  GD_drawing(g)->ratio_kind = R_NONE; /* Turn off any aspect change if background present */
559  }
560  else
561  haveBackground = 0;
562 
563  if (adjust && (Nop == 1) && !haveBackground)
564  didAdjust = adjustNodes(g);
565 
566  if (didAdjust) {
567  if (GD_label(g)) GD_label(g)->set = FALSE;
568 /* FIX:
569  * - if nodes are moved, clusters are no longer valid.
570  */
571  }
572 
573  compute_bb(g);
574 
575  /* Adjust bounding box for any background */
576  if (haveBackground)
577  GD_bb(g) = xdotBB (g);
578 
579  /* At this point, all bounding boxes should be correctly defined.
580  */
581 
582  if (!adjust) {
583  node_t *n;
584  State = GVSPLINES;
585  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
586  ND_coord(n).x = POINTS_PER_INCH * (ND_pos(n)[0]);
587  ND_coord(n).y = POINTS_PER_INCH * (ND_pos(n)[1]);
588  }
589  }
590  else {
591  boolean didShift;
592  if (translate && !haveBackground && ((GD_bb(g).LL.x != 0)||(GD_bb(g).LL.y != 0)))
593  neato_translate (g);
594  didShift = neato_set_aspect(g);
595  /* if we have some edge positions and we either shifted or adjusted, free edge positions */
596  if ((posEdges != NoEdges) && (didShift || didAdjust)) {
597  freeEdgeInfo (g);
598  posEdges = NoEdges;
599  }
600  if (posEdges != AllEdges)
601  spline_edges0(g, FALSE); /* add edges */
602  else
603  State = GVSPLINES;
604  }
605 
606  return haveBackground;
607 }
608 
609 static void neato_init_graph (Agraph_t * g)
610 {
611  int outdim;
612 
613  setEdgeType (g, ET_LINE);
614  outdim = late_int(g, agfindgraphattr(g, "dimen"), 2, 2);
615  GD_ndim(agroot(g)) = late_int(g, agfindgraphattr(g, "dim"), outdim, 2);
616  Ndim = GD_ndim(g->root) = MIN(GD_ndim(g->root), MAXDIM);
617  GD_odim(g->root) = MIN(outdim, Ndim);
618  neato_init_node_edge(g);
619 }
620 
621 static int neatoModel(graph_t * g)
622 {
623  char *p = agget(g, "model");
624  char c;
625 
626  if (!p || (!(c = *p))) /* if p is NULL or "" */
627  return MODEL_SHORTPATH;
628  if ((c == 'c') && streq(p, "circuit"))
629  return MODEL_CIRCUIT;
630  if (c == 's') {
631  if (streq(p, "subset"))
632  return MODEL_SUBSET;
633  else if (streq(p, "shortpath"))
634  return MODEL_SHORTPATH;
635  }
636  if ((c == 'm') && streq(p, "mds")) {
637  if (agattr(g, AGEDGE, "len", 0))
638  return MODEL_MDS;
639  else {
640  agerr(AGWARN,
641  "edges in graph %s have no len attribute. Hence, the mds model\n", agnameof(g));
642  agerr(AGPREV, "is inappropriate. Reverting to the shortest path model.\n");
643  return MODEL_SHORTPATH;
644  }
645  }
646  agerr(AGWARN,
647  "Unknown value %s for attribute \"model\" in graph %s - ignored\n",
648  p, agnameof(g));
649  return MODEL_SHORTPATH;
650 }
651 
652 /* neatoMode:
653  */
654 static int neatoMode(graph_t * g)
655 {
656  char *str;
657  int mode = MODE_MAJOR; /* default mode */
658 
659  str = agget(g, "mode");
660  if (str && *str) {
661  if (streq(str, "KK"))
662  mode = MODE_KK;
663  else if (streq(str, "major"))
664  mode = MODE_MAJOR;
665 #ifdef DIGCOLA
666  else if (streq(str, "hier"))
667  mode = MODE_HIER;
668 #ifdef IPSEPCOLA
669  else if (streq(str, "ipsep"))
670  mode = MODE_IPSEP;
671 #endif
672 #endif
673  else
674  agerr(AGWARN,
675  "Illegal value %s for attribute \"mode\" in graph %s - ignored\n",
676  str, agnameof(g));
677  }
678 
679  return mode;
680 }
681 
682 /* checkEdge:
683  *
684  */
685 static int checkEdge(PointMap * pm, edge_t * ep, int idx)
686 {
687  int i = ND_id(agtail(ep));
688  int j = ND_id(aghead(ep));
689  int tmp;
690 
691  if (i > j) {
692  tmp = i;
693  i = j;
694  j = tmp;
695  }
696  return insertPM(pm, i, j, idx);
697 }
698 
699 #ifdef DIGCOLA
700 /* dfsCycle:
701  * dfs for breaking cycles in vtxdata
702  */
703 static void
704 dfsCycle (vtx_data* graph, int i,int mode, node_t* nodes[])
705 {
706  node_t *np, *hp;
707  int j, e, f;
708  /* if mode is IPSEP make it an in-edge
709  * at both ends, so that an edge constraint won't be generated!
710  */
711  double x = (mode==MODE_IPSEP?-1.0:1.0);
712 
713  np = nodes[i];
714  ND_mark(np) = TRUE;
715  ND_onstack(np) = TRUE;
716  for (e = 1; e < graph[i].nedges; e++) {
717  if (graph[i].edists[e] == 1.0) continue; /* in edge */
718  j = graph[i].edges[e];
719  hp = nodes[j];
720  if (ND_onstack(hp)) { /* back edge: reverse it */
721  graph[i].edists[e] = x;
722  for (f = 1; (f < graph[j].nedges) &&(graph[j].edges[f] != i); f++) ;
723  assert (f < graph[j].nedges);
724  graph[j].edists[f] = -1.0;
725  }
726  else if (ND_mark(hp) == FALSE) dfsCycle(graph, j, mode, nodes);
727 
728  }
729  ND_onstack(np) = FALSE;
730 }
731 
732 /* acyclic:
733  * Do a dfs of the vtx_data, looking for cycles, reversing edges.
734  */
735 static void
736 acyclic (vtx_data* graph, int nv, int mode, node_t* nodes[])
737 {
738  int i;
739  node_t* np;
740 
741  for (i = 0; i < nv; i++) {
742  np = nodes[i];
743  ND_mark(np) = FALSE;
744  ND_onstack(np) = FALSE;
745  }
746  for (i = 0; i < nv; i++) {
747  if (ND_mark(nodes[i])) continue;
748  dfsCycle (graph, i, mode, nodes);
749  }
750 
751 }
752 #endif
753 
754 /* makeGraphData:
755  * Create sparse graph representation via arrays.
756  * Each node is represented by a vtx_data.
757  * The index of each neighbor is stored in the edges array;
758  * the corresponding edge lengths and weights go on ewgts and eweights.
759  * We do not allocate the latter 2 if the graph does not use them.
760  * By convention, graph[i].edges[0] == i.
761  * The values graph[i].ewgts[0] and graph[i].eweights[0] are left undefined.
762  *
763  * In constructing graph from g, we neglect loops. We track multiedges (ignoring
764  * direction). Edge weights are additive; the final edge length is the max.
765  *
766  * If direction is used, we set the edists field, -1 for tail, +1 for head.
767  * graph[i].edists[0] is left undefined. If multiedges exist, the direction
768  * of the first one encountered is used. Finally, a pass is made to guarantee
769  * the graph is acyclic.
770  *
771  */
772 static vtx_data *makeGraphData(graph_t * g, int nv, int *nedges, int mode, int model, node_t*** nodedata)
773 {
774  vtx_data *graph;
775  node_t** nodes;
776  int ne = agnedges(g); /* upper bound */
777  int *edges;
778  float *ewgts = NULL;
779  node_t *np;
780  edge_t *ep;
781  float *eweights = NULL;
782 #ifdef DIGCOLA
783  float *edists = NULL;
784 #endif
785  attrsym_t *haveLen;
786  int haveWt;
787  int haveDir;
788  PointMap *ps = newPM();
789  int i, i_nedges, idx;
790 
791  /* lengths and weights unused in reweight model */
792  if (model == MODEL_SUBSET) {
793  haveLen = FALSE;
794  haveWt = FALSE;
795  } else {
796  haveLen = agattr(g, AGEDGE, "len", 0) ;
797  haveWt = (E_weight != 0);
798  }
799  if (mode == MODE_HIER || mode == MODE_IPSEP)
800  haveDir = TRUE;
801  else
802  haveDir = FALSE;
803 
804  graph = N_GNEW(nv, vtx_data);
805  nodes = N_GNEW(nv, node_t*);
806  edges = N_GNEW(2 * ne + nv, int); /* reserve space for self loops */
807  if (haveLen || haveDir)
808  ewgts = N_GNEW(2 * ne + nv, float);
809  if (haveWt)
810  eweights = N_GNEW(2 * ne + nv, float);
811 #ifdef DIGCOLA
812  if (haveDir)
813  edists = N_GNEW(2*ne+nv,float);
814 #endif
815 
816  i = 0;
817  ne = 0;
818  for (np = agfstnode(g); np; np = agnxtnode(g, np)) {
819  int j = 1; /* index of neighbors */
820  clearPM(ps);
821  assert(ND_id(np) == i);
822  nodes[i] = np;
823  graph[i].edges = edges++; /* reserve space for the self loop */
824  if (haveLen || haveDir)
825  graph[i].ewgts = ewgts++;
826  else
827  graph[i].ewgts = NULL;
828  if (haveWt)
829  graph[i].eweights = eweights++;
830  else
831  graph[i].eweights = NULL;
832 #ifdef DIGCOLA
833  if (haveDir) {
834  graph[i].edists = edists++;
835  }
836  else
837  graph[i].edists = NULL;
838 #endif
839  i_nedges = 1; /* one for the self */
840 
841  for (ep = agfstedge(g, np); ep; ep = agnxtedge(g, ep, np)) {
842  if (aghead(ep) == agtail(ep))
843  continue; /* ignore loops */
844  idx = checkEdge(ps, ep, j);
845  if (idx != j) { /* seen before */
846  if (haveWt)
847  graph[i].eweights[idx] += ED_factor(ep);
848  if (haveLen) {
849  int curlen = graph[i].ewgts[idx];
850  graph[i].ewgts[idx] = MAX(ED_dist(ep), curlen);
851  }
852  } else {
853  node_t *vp = (((agtail(ep)) == np) ? aghead(ep) : agtail(ep));
854  ne++;
855  j++;
856 
857  *edges++ = ND_id(vp);
858  if (haveWt)
859  *eweights++ = ED_factor(ep);
860  if (haveLen)
861  *ewgts++ = ED_dist(ep);
862  else if (haveDir)
863  *ewgts++ = 1.0;
864 #ifdef DIGCOLA
865  if (haveDir) {
866  char *s = agget(ep,"dir");
867  if(s&&!strncmp(s,"none",4)) {
868  *edists++ = 0;
869  } else {
870  *edists++ = (np == aghead(ep) ? 1.0 : -1.0);
871  }
872  }
873 #endif
874  i_nedges++;
875  }
876  }
877 
878  graph[i].nedges = i_nedges;
879  graph[i].edges[0] = i;
880 #ifdef USE_STYLES
881  graph[i].styles = NULL;
882 #endif
883  i++;
884  }
885 #ifdef DIGCOLA
886  if (haveDir) {
887  /* Make graph acyclic */
888  acyclic (graph, nv, mode, nodes);
889  }
890 #endif
891 
892  ne /= 2; /* every edge is counted twice */
893 
894  /* If necessary, release extra memory. */
895  if (ne != agnedges(g)) {
896  edges = RALLOC(2 * ne + nv, graph[0].edges, int);
897  if (haveLen)
898  ewgts = RALLOC(2 * ne + nv, graph[0].ewgts, float);
899  if (haveWt)
900  eweights = RALLOC(2 * ne + nv, graph[0].eweights, float);
901 
902  for (i = 0; i < nv; i++) {
903  int sz = graph[i].nedges;
904  graph[i].edges = edges;
905  edges += sz;
906  if (haveLen) {
907  graph[i].ewgts = ewgts;
908  ewgts += sz;
909  }
910  if (haveWt) {
911  graph[i].eweights = eweights;
912  eweights += sz;
913  }
914  }
915  }
916 
917  *nedges = ne;
918  if (nodedata)
919  *nodedata = nodes;
920  else
921  free (nodes);
922  freePM(ps);
923  return graph;
924 }
925 
926 static void initRegular(graph_t * G, int nG)
927 {
928  double a, da;
929  node_t *np;
930 
931  a = 0.0;
932  da = (2 * M_PI) / nG;
933  for (np = agfstnode(G); np; np = agnxtnode(G, np)) {
934  ND_pos(np)[0] = nG * Spring_coeff * cos(a);
935  ND_pos(np)[1] = nG * Spring_coeff * sin(a);
936  ND_pinned(np) = P_SET;
937  a = a + da;
938  if (Ndim > 2)
939  jitter3d(np, nG);
940  }
941 }
942 
943 #define SLEN(s) (sizeof(s)-1)
944 #define SMART "self"
945 #define REGULAR "regular"
946 #define RANDOM "random"
947 
948 /* setSeed:
949  * Analyze "start" attribute. If unset, return dflt.
950  * If it begins with self, regular, or random, return set init to same,
951  * else set init to dflt.
952  * If init is random, look for value integer suffix to use a seed; if not
953  * found, use time to set seed and store seed in graph.
954  * Return seed in seedp.
955  * Return init.
956  */
957 int
958 setSeed (graph_t * G, int dflt, long* seedp)
959 {
960  char smallbuf[32];
961  char *p = agget(G, "start");
962  int init = dflt;
963 
964  if (!p || (*p == '\0')) return dflt;
965  if (isalpha(*(unsigned char *)p)) {
966  if (!strncmp(p, SMART, SLEN(SMART))) {
967  init = INIT_SELF;
968  p += SLEN(SMART);
969  } else if (!strncmp(p, REGULAR, SLEN(REGULAR))) {
970  init = INIT_REGULAR;
971  p += SLEN(REGULAR);
972  } else if (!strncmp(p, RANDOM, SLEN(RANDOM))) {
973  init = INIT_RANDOM;
974  p += SLEN(RANDOM);
975  }
976  else init = dflt;
977  }
978  else if (isdigit(*(unsigned char *)p)) {
979  init = INIT_RANDOM;
980  }
981 
982  if (init == INIT_RANDOM) {
983  long seed;
984  /* Check for seed value */
985  if (!isdigit(*(unsigned char *)p) || sscanf(p, "%ld", &seed) < 1) {
986 #if defined(_WIN32)
987  seed = (unsigned) time(NULL);
988 #else
989  seed = (unsigned) getpid() ^ (unsigned) time(NULL);
990 #endif
991  sprintf(smallbuf, "%ld", seed);
992  agset(G, "start", smallbuf);
993  }
994  *seedp = seed;
995  }
996  return init;
997 }
998 
999 /* checkExp:
1000  * Allow various weights for the scale factor in used to calculate stress.
1001  * At present, only 1 or 2 are allowed, with 2 the default.
1002  */
1003 #define exp_name "stresswt"
1004 
1005 static int checkExp (graph_t * G)
1006 {
1007  int exp = late_int(G, agfindgraphattr(G, exp_name), 2, 0);
1008  if ((exp == 0) || (exp > 2)) {
1009  agerr (AGWARN, "%s attribute value must be 1 or 2 - ignoring\n", exp_name);
1010  exp = 2;
1011  }
1012  return exp;
1013 }
1014 
1015 /* checkStart:
1016  * Analyzes start attribute, setting seed.
1017  * If set,
1018  * If start is regular, places nodes and returns INIT_REGULAR.
1019  * If start is self, returns INIT_SELF.
1020  * If start is random, returns INIT_RANDOM
1021  * Set RNG seed
1022  * else return default
1023  *
1024  */
1025 int checkStart(graph_t * G, int nG, int dflt)
1026 {
1027  long seed;
1028  int init;
1029 
1030  seed = 1;
1031  init = setSeed (G, dflt, &seed);
1032  if (N_pos && (init != INIT_RANDOM)) {
1033  agerr(AGWARN, "node positions are ignored unless start=random\n");
1034  }
1035  if (init == INIT_REGULAR) initRegular(G, nG);
1036  srand48(seed);
1037  return init;
1038 }
1039 
1040 #ifdef DEBUG_COLA
1041 void dumpData(graph_t * g, vtx_data * gp, int nv, int ne)
1042 {
1043  node_t *v;
1044  int i, j, n;
1045 
1046  fprintf(stderr, "#nodes %d #edges %d\n", nv, ne);
1047  for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
1048  fprintf(stderr, "\"%s\" %d\n", agnameof(v), ND_id(v));
1049  }
1050  for (i = 0; i < nv; i++) {
1051  n = gp[i].nedges;
1052  fprintf(stderr, "[%d] %d\n", i, n);
1053  for (j = 0; j < n; j++) {
1054  fprintf(stderr, " %3d", gp[i].edges[j]);
1055  }
1056  fputs("\n", stderr);
1057  if (gp[i].ewgts) {
1058  fputs(" ewgts", stderr);
1059  for (j = 0; j < n; j++) {
1060  fprintf(stderr, " %3f", gp[i].ewgts[j]);
1061  }
1062  fputs("\n", stderr);
1063  }
1064  if (gp[i].eweights) {
1065  fputs(" eweights", stderr);
1066  for (j = 0; j < n; j++) {
1067  fprintf(stderr, " %3f", gp[i].eweights[j]);
1068  }
1069  fputs("\n", stderr);
1070  }
1071  if (gp[i].edists) {
1072  fputs(" edists", stderr);
1073  for (j = 0; j < n; j++) {
1074  fprintf(stderr, " %3f", gp[i].edists[j]);
1075  }
1076  fputs("\n", stderr);
1077  }
1078  fputs("\n", stderr);
1079 
1080  }
1081 }
1082 void dumpClusterData (cluster_data* dp)
1083 {
1084  int i, j, sz;
1085 
1086  fprintf (stderr, "nvars %d nclusters %d ntoplevel %d\n", dp->nvars, dp->nclusters, dp->ntoplevel);
1087  fprintf (stderr, "Clusters:\n");
1088  for (i = 0; i < dp->nclusters; i++) {
1089  sz = dp->clustersizes[i];
1090  fprintf (stderr, " [%d] %d vars\n", i, sz);
1091  for (j = 0; j < sz; j++)
1092  fprintf (stderr, " %d", dp->clusters[i][j]);
1093  fprintf (stderr, "\n");
1094  }
1095 
1096 
1097  fprintf (stderr, "Toplevel:\n");
1098  for (i = 0; i < dp->ntoplevel; i++)
1099  fprintf (stderr, " %d\n", dp->toplevel[i]);
1100 
1101  fprintf (stderr, "Boxes:\n");
1102  for (i = 0; i < dp->nclusters; i++) {
1103  boxf bb = dp->bb[i];
1104  fprintf (stderr, " (%f,%f) (%f,%f)\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
1105  }
1106 }
1107 void dumpOpts (ipsep_options* opp, int nv)
1108 {
1109  int i;
1110 
1111  fprintf (stderr, "diredges %d edge_gap %f noverlap %d gap (%f,%f)\n", opp->diredges, opp->edge_gap, opp->noverlap, opp->gap.x, opp->gap.y);
1112  for (i = 0; i < nv; i++)
1113  fprintf (stderr, " (%f,%f)\n", opp->nsize[i].x, opp->nsize[i].y);
1114  if (opp->clusters)
1115  dumpClusterData (opp->clusters);
1116 }
1117 #endif
1118 
1119 /* majorization:
1120  * Solve stress using majorization.
1121  * Old neato attributes to incorporate:
1122  * weight
1123  * mode will be MODE_MAJOR, MODE_HIER or MODE_IPSEP
1124  */
1125 static void
1126 majorization(graph_t *mg, graph_t * g, int nv, int mode, int model, int dim, int steps, adjust_data* am)
1127 {
1128  double **coords;
1129  int ne;
1130  int i, rv = 0;
1131  node_t *v;
1132  vtx_data *gp;
1133  node_t** nodes;
1134 #ifdef DIGCOLA
1135 #ifdef IPSEPCOLA
1136  expand_t margin;
1137 #endif
1138 #endif
1139  int init = checkStart(g, nv, (mode == MODE_HIER ? INIT_SELF : INIT_RANDOM));
1140  int opts = checkExp (g);
1141 
1142  if (init == INIT_SELF)
1143  opts |= opt_smart_init;
1144 
1145  coords = N_GNEW(dim, double *);
1146  coords[0] = N_GNEW(nv * dim, double);
1147  for (i = 1; i < Ndim; i++) {
1148  coords[i] = coords[0] + i * nv;
1149  }
1150  if (Verbose) {
1151  fprintf(stderr, "model %d smart_init %d stresswt %d iterations %d tol %f\n",
1152  model, (init == INIT_SELF), opts & opt_exp_flag, MaxIter, Epsilon);
1153  fprintf(stderr, "convert graph: ");
1154  start_timer();
1155  fprintf(stderr, "majorization\n");
1156 // fprintf(stderr, "%i\n", count_nodes(g));
1157  }
1158  gp = makeGraphData(g, nv, &ne, mode, model, &nodes);
1159 
1160  if (Verbose) {
1161  fprintf(stderr, "%d nodes %.2f sec\n", nv, elapsed_sec());
1162  }
1163 
1164 #ifdef DIGCOLA
1165  if (mode != MODE_MAJOR) {
1166  double lgap = late_double(g, agfindgraphattr(g, "levelsgap"), 0.0, -MAXDOUBLE);
1167  if (mode == MODE_HIER) {
1168  rv = stress_majorization_with_hierarchy(gp, nv, ne, coords, nodes, Ndim,
1169  opts, model, MaxIter, lgap);
1170  }
1171 #ifdef IPSEPCOLA
1172  else {
1173  char* str;
1174  ipsep_options opt;
1175  pointf* nsize;
1176  cluster_data *cs = (cluster_data*)cluster_map(mg,g);
1177  nsize = N_GNEW(nv, pointf);
1178  opt.edge_gap = lgap;
1179 #ifdef MOSEK
1180  opt.mosek = 0;
1181 #endif /* MOSEK */
1182  opt.nsize = nsize;
1183  opt.clusters = cs;
1184  str = agget(g, "diredgeconstraints");
1185  if (mapbool(str)) {
1186  opt.diredges = 1;
1187  if(Verbose)
1188  fprintf(stderr,"Generating Edge Constraints...\n");
1189  } else if (str && !strncasecmp(str,"hier",4)) {
1190  opt.diredges = 2;
1191  if(Verbose)
1192  fprintf(stderr,"Generating DiG-CoLa Edge Constraints...\n");
1193  }
1194  else opt.diredges = 0;
1195  if (am->mode == AM_IPSEP) {
1196  opt.noverlap = 1;
1197  if(Verbose)
1198  fprintf(stderr,"Generating Non-overlap Constraints...\n");
1199  } else if (am->mode == AM_VPSC) {
1200  opt.noverlap = 2;
1201  if(Verbose)
1202  fprintf(stderr,"Removing overlaps as postprocess...\n");
1203  }
1204  else opt.noverlap = 0;
1205 #ifdef MOSEK
1206  str = agget(g, "mosek");
1207  if(str && !strncmp(str,"true",4)) {
1208  opt.mosek = 1;
1209  if(Verbose)
1210  fprintf(stderr,"Using Mosek for constraint optimization...\n");
1211  }
1212 #endif /* MOSEK */
1213  margin = sepFactor (g);
1214  /* Multiply by 2 since opt.gap is the gap size, not the margin */
1215  if (margin.doAdd) {
1216  opt.gap.x = 2.0*PS2INCH(margin.x);
1217  opt.gap.y = 2.0*PS2INCH(margin.y);
1218  }
1219  else opt.gap.x = opt.gap.y = 2.0*PS2INCH(DFLT_MARGIN);
1220  if(Verbose)
1221  fprintf(stderr,"gap=%f,%f\n",opt.gap.x,opt.gap.y);
1222  for (i=0, v = agfstnode(g); v; v = agnxtnode(g, v),i++) {
1223  nsize[i].x = ND_width(v);
1224  nsize[i].y = ND_height(v);
1225  }
1226 
1227 #ifdef DEBUG_COLA
1228  fprintf (stderr, "nv %d ne %d Ndim %d model %d MaxIter %d\n", nv, ne, Ndim, model, MaxIter);
1229  fprintf (stderr, "Nodes:\n");
1230  for (i = 0; i < nv; i++) {
1231  fprintf (stderr, " %s (%f,%f)\n", nodes[i]->name, coords[0][i], coords[1][i]);
1232  }
1233  fprintf (stderr, "\n");
1234  dumpData(g, gp, nv, ne);
1235  fprintf (stderr, "\n");
1236  dumpOpts (&opt, nv);
1237 #endif
1238  rv = stress_majorization_cola(gp, nv, ne, coords, nodes, Ndim, model, MaxIter, &opt);
1239  freeClusterData(cs);
1240  free (nsize);
1241  }
1242 #endif
1243  }
1244  else
1245 #endif
1246  rv = stress_majorization_kD_mkernel(gp, nv, ne, coords, nodes, Ndim, opts, model, MaxIter);
1247 
1248  if (rv < 0) {
1249  agerr(AGPREV, "layout aborted\n");
1250  }
1251  else for (v = agfstnode(g); v; v = agnxtnode(g, v)) { /* store positions back in nodes */
1252  int idx = ND_id(v);
1253  int i;
1254  for (i = 0; i < Ndim; i++) {
1255  ND_pos(v)[i] = coords[i][idx];
1256  }
1257  }
1258  freeGraphData(gp);
1259  free(coords[0]);
1260  free(coords);
1261  free(nodes);
1262 }
1263 
1264 static void subset_model(Agraph_t * G, int nG)
1265 {
1266  int i, j, ne;
1267  DistType **Dij;
1268  vtx_data *gp;
1269 
1270  gp = makeGraphData(G, nG, &ne, MODE_KK, MODEL_SUBSET, NULL);
1271  Dij = compute_apsp_artifical_weights(gp, nG);
1272  for (i = 0; i < nG; i++) {
1273  for (j = 0; j < nG; j++) {
1274  GD_dist(G)[i][j] = Dij[i][j];
1275  }
1276  }
1277  free(Dij[0]);
1278  free(Dij);
1279  freeGraphData(gp);
1280 }
1281 
1282 /* mds_model:
1283  * Assume the matrix already contains shortest path values.
1284  * Use the actual lengths provided the input for edges.
1285  */
1286 static void mds_model(graph_t * g, int nG)
1287 {
1288  long i, j;
1289  node_t *v;
1290  edge_t *e;
1291 
1292  for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
1293  for (e = agfstout(g, v); e; e = agnxtout(g, e)) {
1294  i = AGSEQ(agtail(e));
1295  j = AGSEQ(aghead(e));
1296  if (i == j)
1297  continue;
1298  GD_dist(g)[i][j] = GD_dist(g)[j][i] = ED_dist(e);
1299  }
1300  }
1301 }
1302 
1303 /* kkNeato:
1304  * Solve using gradient descent a la Kamada-Kawai.
1305  */
1306 static void kkNeato(Agraph_t * g, int nG, int model)
1307 {
1308  if (model == MODEL_SUBSET) {
1309  subset_model(g, nG);
1310  } else if (model == MODEL_CIRCUIT) {
1311  if (!circuit_model(g, nG)) {
1312  agerr(AGWARN,
1313  "graph %s is disconnected. Hence, the circuit model\n",
1314  agnameof(g));
1315  agerr(AGPREV,
1316  "is undefined. Reverting to the shortest path model.\n");
1317  agerr(AGPREV,
1318  "Alternatively, consider running neato using -Gpack=true or decomposing\n");
1319  agerr(AGPREV, "the graph into connected components.\n");
1320  shortest_path(g, nG);
1321  }
1322  } else if (model == MODEL_MDS) {
1323  shortest_path(g, nG);
1324  mds_model(g, nG);
1325  } else
1326  shortest_path(g, nG);
1327  initial_positions(g, nG);
1328  diffeq_model(g, nG);
1329  if (Verbose) {
1330  fprintf(stderr, "Solving model %d iterations %d tol %f\n",
1331  model, MaxIter, Epsilon);
1332  start_timer();
1333  }
1334  solve_model(g, nG);
1335 }
1336 
1337 /* neatoLayout:
1338  * Use stress optimization to layout a single component
1339  */
1340 static void
1341 neatoLayout(Agraph_t * mg, Agraph_t * g, int layoutMode, int layoutModel,
1342  adjust_data* am)
1343 {
1344  int nG;
1345  char *str;
1346 
1347  if ((str = agget(g, "maxiter")))
1348  MaxIter = atoi(str);
1349  else if (layoutMode == MODE_MAJOR)
1351  else
1352  MaxIter = 100 * agnnodes(g);
1353 
1354  nG = scan_graph_mode(g, layoutMode);
1355  if ((nG < 2) || (MaxIter < 0))
1356  return;
1357  if (layoutMode)
1358  majorization(mg, g, nG, layoutMode, layoutModel, Ndim, MaxIter, am);
1359  else
1360  kkNeato(g, nG, layoutModel);
1361 }
1362 
1363 /* addZ;
1364  * If dimension == 3 and z attribute is declared,
1365  * attach z value to nodes if not defined.
1366  */
1367 static void addZ (Agraph_t* g)
1368 {
1369  node_t* n;
1370  char buf[BUFSIZ];
1371 
1372  if ((Ndim >= 3) && N_z) {
1373  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1374  sprintf(buf, "%lf", POINTS_PER_INCH * (ND_pos(n)[2]));
1375  agxset(n, N_z, buf);
1376  }
1377  }
1378 }
1379 
1380 #ifdef IPSEPCOLA
1381 static void
1382 addCluster (graph_t* g)
1383 {
1384  graph_t *subg;
1385  for (subg = agfstsubg(agroot(g)); subg; subg = agnxtsubg(subg)) {
1386  if (!strncmp(agnameof(subg), "cluster", 7)) {
1387  agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
1388  add_cluster(g, subg);
1389  compute_bb(subg);
1390  }
1391  }
1392 }
1393 #endif
1394 
1395 /* doEdges:
1396  * Simple wrapper to compute graph's bb, then route edges after
1397  * a possible aspect ratio adjustment.
1398  */
1399 static void doEdges(Agraph_t* g)
1400 {
1401  compute_bb(g);
1402  spline_edges0(g, TRUE);
1403 }
1404 
1405 /* neato_layout:
1406  */
1408 {
1409  int layoutMode;
1410  int model;
1411  pack_mode mode;
1412  pack_info pinfo;
1413  adjust_data am;
1414  double save_scale = PSinputscale;
1415 
1416  if (Nop) {
1417  int ret;
1419  neato_init_graph(g);
1420  addZ (g);
1421  ret = init_nop(g, 1);
1422  if (ret < 0) {
1423  agerr(AGPREV, "as required by the -n flag\n");
1424  return;
1425  }
1426  else gv_postprocess(g, 0);
1427  } else {
1428  boolean noTranslate = mapBool(agget(g, "notranslate"), FALSE);
1430  neato_init_graph(g);
1431  layoutMode = neatoMode(g);
1432  graphAdjustMode (g, &am, 0);
1433  model = neatoModel(g);
1434  mode = getPackModeInfo (g, l_undef, &pinfo);
1435  Pack = getPack(g, -1, CL_OFFSET);
1436  /* pack if just packmode defined. */
1437  if (mode == l_undef) {
1438  /* If the user has not indicated packing but we are
1439  * using the new neato, turn packing on.
1440  */
1441  if ((Pack < 0) && layoutMode)
1442  Pack = CL_OFFSET;
1443  pinfo.mode = l_node;
1444  } else if (Pack < 0)
1445  Pack = CL_OFFSET;
1446  if (Pack >= 0) {
1447  graph_t *gc;
1448  graph_t **cc;
1449  int n_cc;
1450  int i;
1451  boolean pin;
1452 
1453  cc = pccomps(g, &n_cc, cc_pfx, &pin);
1454 
1455  if (n_cc > 1) {
1456  boolean *bp;
1457  for (i = 0; i < n_cc; i++) {
1458  gc = cc[i];
1459  nodeInduce(gc);
1460  neatoLayout(g, gc, layoutMode, model, &am);
1461  removeOverlapWith(gc, &am);
1462  setEdgeType (gc, ET_LINE);
1463  if (noTranslate) doEdges(gc);
1464  else spline_edges(gc);
1465  }
1466  if (pin) {
1467  bp = N_NEW(n_cc, boolean);
1468  bp[0] = TRUE;
1469  } else
1470  bp = 0;
1471  pinfo.margin = Pack;
1472  pinfo.fixed = bp;
1473  pinfo.doSplines = 1;
1474  packGraphs(n_cc, cc, g, &pinfo);
1475  if (bp)
1476  free(bp);
1477  }
1478  else {
1479  neatoLayout(g, g, layoutMode, model, &am);
1480  removeOverlapWith(g, &am);
1481  if (noTranslate) doEdges(g);
1482  else spline_edges(g);
1483  }
1484  compute_bb(g);
1485  addZ (g);
1486 
1487  /* cleanup and remove component subgraphs */
1488  for (i = 0; i < n_cc; i++) {
1489  gc = cc[i];
1490  free_scan_graph(gc);
1491  agdelrec (gc, "Agraphinfo_t");
1492  agdelete(g, gc);
1493  }
1494  free (cc);
1495 #ifdef IPSEPCOLA
1496  addCluster (g);
1497 #endif
1498  } else {
1499  neatoLayout(g, g, layoutMode, model, &am);
1500  removeOverlapWith(g, &am);
1501  addZ (g);
1502  if (noTranslate) doEdges(g);
1503  else spline_edges(g);
1504  }
1505  gv_postprocess(g, !noTranslate);
1506  }
1507  PSinputscale = save_scale;
1508 }
boolean doAdd
Definition: adjust.h:45
float * eweights
Definition: sparsegraph.h:83
int init_nop(Agraph_t *g, int adjust)
Definition: neatoinit.c:528
#define GD_label(g)
Definition: types.h:381
#define REGULAR
Definition: neatoinit.c:945
CGRAPH_API void agclean(Agraph_t *g, int kind, char *rec_name)
Definition: rec.c:238
#define MAX(a, b)
Definition: agerror.c:17
#define AGSEQ(obj)
Definition: cgraph.h:115
void free_label(textlabel_t *p)
Definition: labels.c:209
bezier * new_spline(edge_t *e, int sz)
Definition: splines.c:218
Definition: cgraph.h:388
#define RALLOC(size, ptr, type)
Definition: memory.h:42
#define ND_pinned(n)
Definition: types.h:525
DistType ** compute_apsp_artifical_weights(vtx_data *graph, int n)
Definition: kkutils.c:105
#define exp_name
Definition: neatoinit.c:1003
int eflag
Definition: types.h:112
void start_timer(void)
Definition: timing.c:45
void shortest_path(graph_t *, int)
Definition: stuff.c:669
Agsym_t * agattr(Agraph_t *g, int kind, char *name, char *value)
Definition: attr.c:324
#define N_NEW(n, t)
Definition: memory.h:36
void neato_layout(Agraph_t *g)
Definition: neatoinit.c:1407
pack_mode
Definition: pack.h:37
EXTERN double Epsilon
Definition: globals.h:77
Definition: pack.h:49
#define ND_xlabel(n)
Definition: types.h:510
Definition: pack.h:37
boolean set
Definition: types.h:142
adjust_mode mode
Definition: adjust.h:37
void acyclic(graph_t *g)
Definition: acyclic.c:57
#define srand48
Definition: neatoinit.c:33
void initial_positions(graph_t *, int)
Definition: stuff.c:326
#define opt_exp_flag
Definition: stress.h:44
#define MIN(a, b)
Definition: arith.h:35
#define GD_n_cluster(g)
Definition: types.h:396
EXTERN int State
Definition: globals.h:80
expand_t sepFactor(graph_t *g)
Definition: adjust.c:1287
int nodeInduce(Agraph_t *g)
Definition: ccomps.c:718
int scan_graph(graph_t *)
Definition: stuff.c:289
#define MODEL_CIRCUIT
Definition: neato.h:21
int agxset(void *obj, Agsym_t *sym, char *value)
Definition: attr.c:468
EXTERN int Nop
Definition: globals.h:70
#define ALLOC(size, ptr, type)
Definition: memory.h:41
void jitter3d(Agnode_t *, int)
Definition: stuff.c:313
#define BS
Definition: neatoinit.c:425
Definition: adjust.h:33
void neato_cleanup(graph_t *g)
Definition: neatoinit.c:142
#define hasPos(n)
Definition: macros.h:26
#define assert(x)
Definition: cghdr.h:47
int scan_graph_mode(graph_t *G, int mode)
Definition: stuff.c:218
Definition: geom.h:28
#define DFLT_ITERATIONS
Definition: stress.h:26
void gv_postprocess(Agraph_t *g, int allowTranslation)
Definition: postproc.c:603
#define ED_label(e)
Definition: types.h:592
void common_init_node(node_t *n)
Definition: utils.c:629
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
CGRAPH_API int agdelete(Agraph_t *g, void *obj)
Definition: obj.c:16
Agraph_t ** pccomps(Agraph_t *g, int *ncc, char *pfx, boolean *pinned)
Definition: ccomps.c:196
#define P_SET
Definition: const.h:283
#define GVSPLINES
Definition: const.h:181
#define ND_pos(n)
Definition: types.h:526
#define SLEN(s)
Definition: neatoinit.c:943
void do_graph_label(graph_t *sg)
Definition: input.c:892
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
void gv_cleanup_edge(Agedge_t *e)
Definition: utils.c:1947
void arrow_flags(Agedge_t *e, int *sflag, int *eflag)
Definition: arrows.c:198
CGRAPH_API Agraph_t * agfstsubg(Agraph_t *g)
Definition: subg.c:72
int insertPM(PointMap *pm, int x, int y, int v)
Definition: pointset.c:216
int packGraphs(int ng, Agraph_t **gs, Agraph_t *root, pack_info *info)
Definition: pack.c:1145
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
pack_mode mode
Definition: pack.h:54
#define ED_tail_label(e)
Definition: types.h:599
#define ND_mark(n)
Definition: types.h:514
pos_edge
Definition: neatoinit.c:366
#define SMART
Definition: neatoinit.c:944
#define POINTS_PER_INCH
Definition: geom.h:62
#define ZALLOC(size, ptr, type, osize)
Definition: memory.h:43
Definition: circular.h:44
#define opt_smart_init
Definition: stress.h:43
Definition: cgraph.h:388
#define INIT_REGULAR
Definition: neato.h:32
#define PS2INCH(a_points)
Definition: geom.h:69
char * agget(void *obj, char *name)
Definition: attr.c:428
CGRAPH_API Agraph_t * agraphof(void *obj)
Definition: obj.c:185
CGRAPH_API Agraph_t * agnxtsubg(Agraph_t *subg)
Definition: subg.c:77
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
void spline_edges0(Agraph_t *, boolean)
Definition: neatosplines.c:767
#define GD_odim(g)
Definition: types.h:399
boolean * fixed
Definition: pack.h:55
int user_pos(attrsym_t *posptr, attrsym_t *pinptr, node_t *np, int nG)
Definition: neatoinit.c:57
int agset(void *obj, char *name, char *value)
Definition: attr.c:455
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
pointf pos
Definition: types.h:133
#define MODE_MAJOR
Definition: neato.h:26
adjust_data * graphAdjustMode(graph_t *G, adjust_data *dp, char *dflt)
Definition: adjust.c:1077
int doSplines
Definition: pack.h:53
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
unsigned int margin
Definition: pack.h:52
#define GD_dist(g)
Definition: types.h:360
double y
Definition: geom.h:28
int sflag
Definition: types.h:111
pack_mode getPackModeInfo(Agraph_t *g, pack_mode dflt, pack_info *pinfo)
Definition: pack.c:1364
int strncasecmp(const char *s1, const char *s2, unsigned int n)
Definition: strncasecmp.c:20
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define MODEL_SUBSET
Definition: neato.h:22
#define ND_height(n)
Definition: types.h:504
#define ND_id(n)
Definition: types.h:489
int nedges
Definition: sparsegraph.h:80
Definition: types.h:225
void spline_edges(Agraph_t *)
Definition: neatosplines.c:804
void free_scan_graph(graph_t *)
Definition: stuff.c:294
float y
Definition: adjust.h:44
pointf sp
Definition: types.h:113
void solve_model(graph_t *, int)
Definition: stuff.c:425
#define agfindedgeattr(g, a)
Definition: types.h:614
int stress_majorization_kD_mkernel(vtx_data *graph, int n, int nedges_graph, double **d_coords, node_t **nodes, int dim, int opts, int model, int maxi)
Definition: stress.c:889
#define ET_LINE
Definition: const.h:271
#define INIT_SELF
Definition: neato.h:31
void compute_bb(graph_t *g)
Definition: utils.c:852
int * edges
Definition: sparsegraph.h:81
int adjustNodes(graph_t *G)
Definition: adjust.c:1235
int removeOverlapWith(graph_t *G, adjust_data *am)
Definition: adjust.c:1118
void clearPM(PointMap *ps)
Definition: pointset.c:182
pointf * list
Definition: types.h:109
#define MODEL_MDS
Definition: neato.h:23
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
Definition: grammar.c:79
#define GD_clust(g)
Definition: types.h:364
Agraph_t * graph(char *name)
Definition: gv.cpp:38
#define MODE_IPSEP
Definition: neato.h:28
int DistType
Definition: sparsegraph.h:92
#define GD_flip(g)
Definition: types.h:385
#define CL_OFFSET
Definition: const.h:155
boxf xdotBB(Agraph_t *g)
Definition: emit.c:3005
pointf ep
Definition: types.h:114
#define ND_width(n)
Definition: types.h:542
double get_inputscale(graph_t *g)
Definition: utils.c:112
void gv_free_splines(edge_t *e)
Definition: utils.c:1935
#define ED_factor(e)
Definition: types.h:588
#define MODEL_SHORTPATH
Definition: neato.h:20
#define NULL
Definition: logic.h:39
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
CGRAPH_API int agdelrec(void *obj, char *name)
Definition: rec.c:145
#define agfindgraphattr(g, a)
Definition: types.h:612
#define ED_head_label(e)
Definition: types.h:590
#define GNEW(t)
Definition: memory.h:37
#define ND_onstack(n)
Definition: types.h:519
EXTERN Agsym_t * E_weight
Definition: globals.h:107
#define RANDOM
Definition: neatoinit.c:946
void freePM(PointMap *ps)
Definition: pointset.c:187
double elapsed_sec(void)
Definition: timing.c:50
double x
Definition: geom.h:28
EXTERN Agsym_t * N_z
Definition: globals.h:95
#define ED_xlabel(e)
Definition: types.h:593
#define ND_coord(n)
Definition: types.h:496
float * ewgts
Definition: sparsegraph.h:82
#define streq(s, t)
Definition: cghdr.h:52
double late_double(void *obj, attrsym_t *attr, double def, double low)
Definition: utils.c:87
int getPack(Agraph_t *g, int not_def, int dflt)
Definition: pack.c:1381
EXTERN unsigned char Verbose
Definition: globals.h:64
void gv_cleanup_node(Agnode_t *n)
Definition: utils.c:1959
Definition: types.h:108
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
void freeGraphData(vtx_data *graph)
Definition: delaunay.c:908
int setSeed(graph_t *G, int dflt, long *seedp)
Definition: neatoinit.c:958
int circuit_model(graph_t *g, int nG)
Definition: circuit.c:41
boolean mapbool(char *p)
Definition: utils.c:472
pointf LL
Definition: geom.h:35
pointf * ps
Definition: multispline.c:423
#define INIT_RANDOM
Definition: neato.h:33
#define MODE_HIER
Definition: neato.h:27
void neato_translate(Agraph_t *g)
Definition: neatosplines.c:970
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
int common_init_edge(edge_t *e)
Definition: utils.c:714
Definition: pack.h:37
void setEdgeType(graph_t *g, int dflt)
Definition: utils.c:1802
void neato_init_node(node_t *n)
Definition: neatoinit.c:42
void gv_nodesize(node_t *n, boolean flip)
Definition: utils.c:1970
Definition: cdt.h:99
#define MAXDIM
Definition: const.h:177
#define GD_bb(g)
Definition: types.h:357
CGRAPH_API int agnedges(Agraph_t *g)
Definition: graph.c:167
#define M_PI
Definition: arith.h:77
agxbuf * str
Definition: htmlparse.c:85
Agraph_t * root
Definition: cgraph.h:247
int checkStart(graph_t *G, int nG, int dflt)
Definition: neatoinit.c:1025
EXTERN double PSinputscale
Definition: globals.h:71
char * agxget(void *obj, Agsym_t *sym)
Definition: attr.c:444
#define MODE_KK
Definition: neato.h:25
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define GD_drawing(g)
Definition: types.h:356
#define AGEDGE
Definition: cgraph.h:104
void diffeq_model(graph_t *, int)
Definition: stuff.c:350
Definition: cgraph.h:388
float x
Definition: adjust.h:44
#define agfindnodeattr(g, a)
Definition: types.h:613
#define ED_dist(e)
Definition: types.h:605
pointf UR
Definition: geom.h:35
#define Spring_coeff
Definition: const.h:175
void jitter_d(Agnode_t *, int, int)
Definition: stuff.c:306
#define GD_neato_nlist(g)
Definition: types.h:400
EXTERN int MaxIter
Definition: globals.h:78
Definition: geom.h:35
#define P_PIN
Definition: const.h:285
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define FALSE
Definition: cgraph.h:35
#define MAXDOUBLE
Definition: arith.h:64
EXTERN int Ndim
Definition: globals.h:79
#define AGRAPH
Definition: cgraph.h:100
boolean neato_set_aspect(graph_t *g)
PointMap * newPM(void)
Definition: pointset.c:172
#define TRUE
Definition: cgraph.h:38