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