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
36static attrsym_t *N_pos;
37static int Pack; /* If >= 0, layout components separately and pack together
38 * The value of Pack gives margins around graphs.
39 */
40static char *cc_pfx = "_neato_cc";
41
42void neato_init_node(node_t * n)
43{
44 agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); //node custom data
45 common_init_node(n);
46 ND_pos(n) = N_NEW(GD_ndim(agraphof(n)), double);
47 gv_nodesize(n, GD_flip(agraphof(n)));
48}
49
50static void neato_init_edge(edge_t * e)
51{
52 agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //node custom data
53 common_init_edge(e);
54 ED_factor(e) = late_double(e, E_weight, 1.0, 1.0);
55}
56
57int 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
112static 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
132static 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
142void neato_cleanup(graph_t * g)
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
156static 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
173static 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
185static 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
240static 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 */
257static 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 */
366typedef 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 */
373static 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 */
405static 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));
415 free_label(ED_head_label(e));
416 free_label(ED_tail_label(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
427static 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
449static 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
459static 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 */
468static void
469dfs(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 */
491static void
492nop_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 */
528int 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
609static 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
621static 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 */
654static 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 */
685static 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 */
703static void
704dfsCycle (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 */
735static void
736acyclic (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 */
772static 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
926static 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 */
957int
958setSeed (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
1005static 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 */
1025int 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
1041void 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}
1082void 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}
1107void 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 */
1125static void
1126majorization(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
1264static 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 */
1286static 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 */
1306static 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 */
1340static void
1341neatoLayout(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)
1350 MaxIter = DFLT_ITERATIONS;
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 */
1367static 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
1381static void
1382addCluster (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 */
1399static void doEdges(Agraph_t* g)
1400{
1401 compute_bb(g);
1402 spline_edges0(g, TRUE);
1403}
1404
1405/* neato_layout:
1406 */
1407void neato_layout(Agraph_t * g)
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;
1418 PSinputscale = POINTS_PER_INCH;
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);
1429 PSinputscale = get_inputscale (g);
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}
1509