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