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 "neato.h" |
18 | #include "adjust.h" |
19 | |
20 | /* For precision, scale up before algorithms, then scale down */ |
21 | #define SCALE 10 |
22 | #define SCALE2 (SCALE/2) |
23 | |
24 | typedef struct nitem { |
25 | Dtlink_t link; |
26 | int val; |
27 | point pos; /* position for sorting */ |
28 | node_t *np; /* base node */ |
29 | node_t *cnode; /* corresponding node in constraint graph */ |
30 | node_t *vnode; /* corresponding node in neighbor graph */ |
31 | box bb; |
32 | } nitem; |
33 | |
34 | typedef int (*distfn) (box *, box *); |
35 | typedef int (*intersectfn) (nitem *, nitem *); |
36 | |
37 | static int cmpitem(Dt_t * d, int *p1, int *p2, Dtdisc_t * disc) |
38 | { |
39 | NOTUSED(d); |
40 | NOTUSED(disc); |
41 | |
42 | return (*p1 - *p2); |
43 | } |
44 | |
45 | static Dtdisc_t constr = { |
46 | offsetof(nitem, val), |
47 | sizeof(int), |
48 | offsetof(nitem, link), |
49 | NIL(Dtmake_f), |
50 | NIL(Dtfree_f), |
51 | (Dtcompar_f) cmpitem, |
52 | NIL(Dthash_f), |
53 | NIL(Dtmemory_f), |
54 | NIL(Dtevent_f) |
55 | }; |
56 | |
57 | static int distY(box * b1, box * b2) |
58 | { |
59 | return ((b1->UR.y - b1->LL.y) + (b2->UR.y - b2->LL.y)) / 2; |
60 | } |
61 | |
62 | static int distX(box * b1, box * b2) |
63 | { |
64 | return ((b1->UR.x - b1->LL.x) + (b2->UR.x - b2->LL.x)) / 2; |
65 | } |
66 | |
67 | /* intersectX0: |
68 | * Return true if boxes could overlap if shifted in y but don't, |
69 | * or if actually overlap and an y move is smallest to remove overlap. |
70 | * Otherwise (no x overlap or a x move is smaller), return false. |
71 | * Assume q pos to above of p pos. |
72 | */ |
73 | static int intersectX0(nitem * p, nitem * q) |
74 | { |
75 | int xdelta, ydelta; |
76 | int v = ((p->bb.LL.x <= q->bb.UR.x) && (q->bb.LL.x <= p->bb.UR.x)); |
77 | if (v == 0) /* no x overlap */ |
78 | return 0; |
79 | if (p->bb.UR.y < q->bb.LL.y) /* but boxes don't really overlap */ |
80 | return 1; |
81 | ydelta = distY(&p->bb,&q->bb) - (q->pos.y - p->pos.y); |
82 | if (q->pos.x >= p->pos.x) |
83 | xdelta = distX(&p->bb,&q->bb) - (q->pos.x - p->pos.x); |
84 | else |
85 | xdelta = distX(&p->bb,&q->bb) - (p->pos.x - q->pos.x); |
86 | return (ydelta <= xdelta); |
87 | } |
88 | |
89 | /* intersectY0: |
90 | * Return true if boxes could overlap if shifted in x but don't, |
91 | * or if actually overlap and an x move is smallest to remove overlap. |
92 | * Otherwise (no y overlap or a y move is smaller), return false. |
93 | * Assume q pos to right of p pos. |
94 | */ |
95 | static int intersectY0(nitem * p, nitem * q) |
96 | { |
97 | int xdelta, ydelta; |
98 | int v = ((p->bb.LL.y <= q->bb.UR.y) && (q->bb.LL.y <= p->bb.UR.y)); |
99 | if (v == 0) /* no y overlap */ |
100 | return 0; |
101 | if (p->bb.UR.x < q->bb.LL.x) /* but boxes don't really overlap */ |
102 | return 1; |
103 | xdelta = distX(&p->bb,&q->bb) - (q->pos.x - p->pos.x); |
104 | if (q->pos.y >= p->pos.y) |
105 | ydelta = distY(&p->bb,&q->bb) - (q->pos.y - p->pos.y); |
106 | else |
107 | ydelta = distY(&p->bb,&q->bb) - (p->pos.y - q->pos.y); |
108 | return (xdelta <= ydelta); |
109 | } |
110 | |
111 | static int intersectY(nitem * p, nitem * q) |
112 | { |
113 | return ((p->bb.LL.y <= q->bb.UR.y) && (q->bb.LL.y <= p->bb.UR.y)); |
114 | } |
115 | |
116 | static int intersectX(nitem * p, nitem * q) |
117 | { |
118 | return ((p->bb.LL.x <= q->bb.UR.x) && (q->bb.LL.x <= p->bb.UR.x)); |
119 | } |
120 | |
121 | /* mapGraphs: |
122 | */ |
123 | static void mapGraphs(graph_t * g, graph_t * cg, distfn dist) |
124 | { |
125 | node_t *n; |
126 | edge_t *e; |
127 | edge_t *ce; |
128 | node_t *t; |
129 | node_t *h; |
130 | nitem *tp; |
131 | nitem *hp; |
132 | int delta; |
133 | |
134 | for (n = agfstnode(g); n; n = agnxtnode(g, n)) { |
135 | tp = (nitem *) ND_alg(n); |
136 | t = tp->cnode; |
137 | for (e = agfstout(g, n); e; e = agnxtout(g, e)) { |
138 | hp = (nitem *) ND_alg(aghead(e)); |
139 | delta = dist(&tp->bb, &hp->bb); |
140 | h = hp->cnode; |
141 | ce = agedge(cg, t, h, NULL, 1); |
142 | agbindrec(ce, "Agedgeinfo_t" , sizeof(Agedgeinfo_t), TRUE); |
143 | ED_weight(ce) = 1; |
144 | if (ED_minlen(ce) < delta) { |
145 | if (ED_minlen(ce) == 0.0) { |
146 | elist_append(ce, ND_out(t)); |
147 | elist_append(ce, ND_in(h)); |
148 | } |
149 | ED_minlen(ce) = delta; |
150 | } |
151 | } |
152 | } |
153 | } |
154 | |
155 | #if DEBUG > 1 |
156 | static int |
157 | indegree (graph_t * g, node_t *n) |
158 | { |
159 | edge_t *e; |
160 | int cnt = 0; |
161 | for (e = agfstin(g,n); e; e = agnxtin(g,e)) cnt++; |
162 | return cnt; |
163 | } |
164 | |
165 | static int |
166 | outdegree (graph_t * g, node_t *n) |
167 | { |
168 | edge_t *e; |
169 | int cnt = 0; |
170 | for (e = agfstout(g,n); e; e = agnxtout(g,e)) cnt++; |
171 | return cnt; |
172 | } |
173 | |
174 | static void |
175 | validate(graph_t * g) |
176 | { |
177 | node_t *n; |
178 | edge_t *e; |
179 | int i, cnt; |
180 | |
181 | cnt = 0; |
182 | for (n = GD_nlist(g);n; n = ND_next(n)) { |
183 | assert(outdegree(g,n) == ND_out(n).size); |
184 | for (i = 0; (e = ND_out(n).list[i]); i++) { |
185 | assert(agtail(e) == n); |
186 | assert( e == agfindedge(g, n, aghead(e))); |
187 | } |
188 | assert(indegree(g,n) == ND_in(n).size); |
189 | for (i = 0; (e = ND_in(n).list[i]); i++) { |
190 | assert(aghead(e) == n); |
191 | assert( e == agfindedge(g, agtail(e), n)); |
192 | } |
193 | cnt++; |
194 | } |
195 | |
196 | assert (agnnodes(g) == cnt); |
197 | } |
198 | #endif |
199 | |
200 | #ifdef OLD |
201 | static node_t *newNode(graph_t * g) |
202 | { |
203 | static int id = 0; |
204 | char buf[100]; |
205 | |
206 | sprintf(buf, "n%d" , id++); |
207 | return agnode(g, buf); |
208 | } |
209 | #endif |
210 | |
211 | /* mkNConstraintG: |
212 | * Similar to mkConstraintG, except it doesn't enforce orthogonal |
213 | * ordering. If there is overlap, as defined by intersect, the |
214 | * nodes will kept/pushed apart in the current order. If not, no |
215 | * constraint is enforced. If a constraint edge is added, and it |
216 | * corresponds to a real edge, we increase the weight in an attempt |
217 | * to keep the resulting shift short. |
218 | */ |
219 | static graph_t *mkNConstraintG(graph_t * g, Dt_t * list, |
220 | intersectfn intersect, distfn dist) |
221 | { |
222 | nitem *p; |
223 | nitem *nxp; |
224 | node_t *n; |
225 | edge_t *e; |
226 | node_t *lastn = NULL; |
227 | graph_t *cg = agopen("cg" , Agstrictdirected, NIL(Agdisc_t *)); |
228 | agbindrec(cg, "Agraphinfo_t" , sizeof(Agraphinfo_t), TRUE); // graph custom data |
229 | |
230 | for (p = (nitem *) dtflatten(list); p; |
231 | p = (nitem *) dtlink(list, (Dtlink_t *) p)) { |
232 | n = agnode(cg, agnameof(p->np), 1); /* FIX */ |
233 | agbindrec(n, "Agnodeinfo_t" , sizeof(Agnodeinfo_t), TRUE); //node custom data |
234 | ND_alg(n) = p; |
235 | p->cnode = n; |
236 | alloc_elist(0, ND_in(n)); |
237 | alloc_elist(0, ND_out(n)); |
238 | if (lastn) { |
239 | ND_next(lastn) = n; |
240 | lastn = n; |
241 | } else { |
242 | lastn = GD_nlist(cg) = n; |
243 | } |
244 | } |
245 | for (p = (nitem *) dtflatten(list); p; |
246 | p = (nitem *) dtlink(list, (Dtlink_t *) p)) { |
247 | for (nxp = (nitem *) dtlink(link, (Dtlink_t *) p); nxp; |
248 | nxp = (nitem *) dtlink(list, (Dtlink_t *) nxp)) { |
249 | e = NULL; |
250 | if (intersect(p, nxp)) { |
251 | double delta = dist(&p->bb, &nxp->bb); |
252 | e = agedge(cg, p->cnode, nxp->cnode, NULL, 1); |
253 | agbindrec(e, "Agedgeinfo_t" , sizeof(Agedgeinfo_t), TRUE); // edge custom data |
254 | assert (delta <= 0xFFFF); |
255 | ED_minlen(e) = delta; |
256 | ED_weight(e) = 1; |
257 | } |
258 | if (e && agfindedge(g,p->np, nxp->np)) { |
259 | ED_weight(e) = 100; |
260 | } |
261 | #if 0 |
262 | if (agfindedge(g,p->np, nxp->np)) { |
263 | if (e == NULL) |
264 | e = agedge(cg, p->cnode, nxp->cnode); |
265 | ED_weight(e) = 100; |
266 | /* If minlen < SCALE, the nodes can't conflict or there's |
267 | * an overlap but it will be removed in the orthogonal pass. |
268 | * So we just keep the node's basically where they are. |
269 | */ |
270 | if (SCALE > ED_minlen(e)) |
271 | ED_minlen(e) = SCALE; |
272 | } |
273 | #endif |
274 | } |
275 | } |
276 | |
277 | for (p = (nitem *) dtflatten(list); p; |
278 | p = (nitem *) dtlink(list, (Dtlink_t *) p)) { |
279 | n = p->cnode; |
280 | for (e = agfstout(cg,n); e; e = agnxtout(cg,e)) { |
281 | elist_append(e, ND_out(n)); |
282 | elist_append(e, ND_in(aghead(e))); |
283 | } |
284 | } |
285 | |
286 | /* We could remove redundant constraints here. However, the cost of doing |
287 | * this may be a good deal more than the time saved in network simplex. |
288 | * Also, if the graph is changed, the ND_in and ND_out data has to be |
289 | * updated. |
290 | */ |
291 | return cg; |
292 | } |
293 | /* mkConstraintG: |
294 | */ |
295 | static graph_t *mkConstraintG(graph_t * g, Dt_t * list, |
296 | intersectfn intersect, distfn dist) |
297 | { |
298 | nitem *p; |
299 | nitem *nxt = NULL; |
300 | nitem *nxp; |
301 | graph_t *vg; |
302 | node_t *prev = NULL; |
303 | node_t *root = NULL; |
304 | node_t *n = NULL; |
305 | edge_t *e; |
306 | int lcnt, cnt; |
307 | int oldval = -INT_MAX; |
308 | #ifdef OLD |
309 | double root_val; |
310 | #endif |
311 | node_t *lastn = NULL; |
312 | graph_t *cg = agopen("cg" , Agstrictdirected, NIL(Agdisc_t *)); |
313 | agbindrec(cg, "Agraphinfo_t" , sizeof(Agraphinfo_t), TRUE); // graph custom data |
314 | |
315 | /* count distinct nodes */ |
316 | cnt = 0; |
317 | for (p = (nitem *) dtflatten(list); p; |
318 | p = (nitem *) dtlink(list, (Dtlink_t *) p)) { |
319 | if (oldval != p->val) { |
320 | oldval = p->val; |
321 | cnt++; |
322 | } |
323 | } |
324 | |
325 | /* construct basic chain to enforce left to right order */ |
326 | oldval = -INT_MAX; |
327 | lcnt = 0; |
328 | for (p = (nitem *) dtflatten(list); p; |
329 | p = (nitem *) dtlink(list, (Dtlink_t *) p)) { |
330 | if (oldval != p->val) { |
331 | oldval = p->val; |
332 | /* n = newNode (cg); */ |
333 | n = agnode(cg, agnameof(p->np), 1); /* FIX */ |
334 | agbindrec(n, "Agnodeinfo_t" , sizeof(Agnodeinfo_t), TRUE); //node custom data |
335 | ND_alg(n) = p; |
336 | if (root) { |
337 | ND_next(lastn) = n; |
338 | lastn = n; |
339 | } else { |
340 | root = n; |
341 | #ifdef OLD |
342 | root_val = p->val; |
343 | #endif |
344 | lastn = GD_nlist(cg) = n; |
345 | } |
346 | alloc_elist(lcnt, ND_in(n)); |
347 | if (prev) { |
348 | if (prev == root) |
349 | alloc_elist(2 * (cnt - 1), ND_out(prev)); |
350 | else |
351 | alloc_elist(cnt - lcnt - 1, ND_out(prev)); |
352 | e = agedge(cg, prev, n, NULL, 1); |
353 | agbindrec(e, "Agedgeinfo_t" , sizeof(Agedgeinfo_t), TRUE); // edge custom data |
354 | ED_minlen(e) = SCALE; |
355 | ED_weight(e) = 1; |
356 | elist_append(e, ND_out(prev)); |
357 | elist_append(e, ND_in(n)); |
358 | } |
359 | lcnt++; |
360 | prev = n; |
361 | } |
362 | p->cnode = n; |
363 | } |
364 | alloc_elist(0, ND_out(prev)); |
365 | |
366 | /* add immediate right neighbor constraints |
367 | * Construct visibility graph, then perform transitive reduction. |
368 | * Remaining outedges are immediate right neighbors. |
369 | * FIX: Incremental algorithm to construct trans. reduction? |
370 | */ |
371 | vg = agopen("vg" , Agstrictdirected, NIL(Agdisc_t *)); |
372 | for (p = (nitem *) dtflatten(list); p; |
373 | p = (nitem *) dtlink(list, (Dtlink_t *) p)) { |
374 | n = agnode(vg, agnameof(p->np), 1); /* FIX */ |
375 | agbindrec(n, "Agnodeinfo_t" , sizeof(Agnodeinfo_t), TRUE); //node custom data |
376 | p->vnode = n; |
377 | ND_alg(n) = p; |
378 | } |
379 | oldval = -INT_MAX; |
380 | for (p = (nitem *) dtflatten(list); p; |
381 | p = (nitem *) dtlink(list, (Dtlink_t *) p)) { |
382 | if (oldval != p->val) { /* new pos: reset nxt */ |
383 | oldval = p->val; |
384 | for (nxt = (nitem *) dtlink(link, (Dtlink_t *) p); nxt; |
385 | nxt = (nitem *) dtlink(list, (Dtlink_t *) nxt)) { |
386 | if (nxt->val != oldval) |
387 | break; |
388 | } |
389 | if (!nxt) |
390 | break; |
391 | } |
392 | for (nxp = nxt; nxp; |
393 | nxp = (nitem *) dtlink(list, (Dtlink_t *) nxp)) { |
394 | if (intersect(p, nxp)) |
395 | agedge(vg, p->vnode, nxp->vnode, NULL, 1); |
396 | } |
397 | } |
398 | |
399 | /* Remove redundant constraints here. However, the cost of doing this |
400 | * may be a good deal more than the time saved in network simplex. Also, |
401 | * if the graph is changed, the ND_in and ND_out data has to be updated. |
402 | */ |
403 | mapGraphs(vg, cg, dist); |
404 | agclose(vg); |
405 | |
406 | /* add dummy constraints for absolute values and initial positions */ |
407 | #ifdef OLD |
408 | for (n = agfstnode(cg); n; n = agnxtnode(cg, n)) { |
409 | node_t *vn; /* slack node for absolute value */ |
410 | node_t *an; /* node representing original position */ |
411 | |
412 | p = (nitem *) ND_alg(n); |
413 | if ((n == root) || (!p)) |
414 | continue; |
415 | vn = newNode(cg); |
416 | ND_next(lastn) = vn; |
417 | lastn = vn; |
418 | alloc_elist(0, ND_out(vn)); |
419 | alloc_elist(2, ND_in(vn)); |
420 | an = newNode(cg); |
421 | ND_next(lastn) = an; |
422 | lastn = an; |
423 | alloc_elist(1, ND_in(an)); |
424 | alloc_elist(1, ND_out(an)); |
425 | |
426 | e = agedge(cg, root, an, 1); |
427 | ED_minlen(e) = p->val - root_val; |
428 | elist_append(e, ND_out(root)); |
429 | elist_append(e, ND_in(an)); |
430 | |
431 | e = agedge(cg, an, vn, 1); |
432 | elist_append(e, ND_out(an)); |
433 | elist_append(e, ND_in(vn)); |
434 | |
435 | e = agedge(cg, n, vn, 1); |
436 | elist_append(e, ND_out(n)); |
437 | elist_append(e, ND_in(vn)); |
438 | } |
439 | #endif /* OLD */ |
440 | |
441 | return cg; |
442 | } |
443 | |
444 | static void closeGraph(graph_t * cg) |
445 | { |
446 | node_t *n; |
447 | for (n = agfstnode(cg); n; n = agnxtnode(cg, n)) { |
448 | free_list(ND_in(n)); |
449 | free_list(ND_out(n)); |
450 | } |
451 | agclose(cg); |
452 | } |
453 | |
454 | /* constrainX: |
455 | * Create the X constrains and solve. We use a linear objective function |
456 | * (absolute values rather than squares), so we can reuse network simplex. |
457 | * The constraints are encoded as a dag with edges having a minimum length. |
458 | */ |
459 | static void constrainX(graph_t* g, nitem* nlist, int nnodes, intersectfn ifn, |
460 | int ortho) |
461 | { |
462 | Dt_t *list = dtopen(&constr, Dtobag); |
463 | nitem *p = nlist; |
464 | graph_t *cg; |
465 | int i; |
466 | |
467 | for (i = 0; i < nnodes; i++) { |
468 | p->val = p->pos.x; |
469 | dtinsert(list, p); |
470 | p++; |
471 | } |
472 | if (ortho) |
473 | cg = mkConstraintG(g, list, ifn, distX); |
474 | else |
475 | cg = mkNConstraintG(g, list, ifn, distX); |
476 | rank(cg, 2, INT_MAX); |
477 | |
478 | p = nlist; |
479 | for (i = 0; i < nnodes; i++) { |
480 | int newpos, oldpos, delta; |
481 | oldpos = p->pos.x; |
482 | newpos = ND_rank(p->cnode); |
483 | delta = newpos - oldpos; |
484 | p->pos.x = newpos; |
485 | p->bb.LL.x += delta; |
486 | p->bb.UR.x += delta; |
487 | p++; |
488 | } |
489 | |
490 | closeGraph(cg); |
491 | dtclose(list); |
492 | } |
493 | |
494 | /* constrainY: |
495 | * See constrainX. |
496 | */ |
497 | static void constrainY(graph_t* g, nitem* nlist, int nnodes, intersectfn ifn, |
498 | int ortho) |
499 | { |
500 | Dt_t *list = dtopen(&constr, Dtobag); |
501 | nitem *p = nlist; |
502 | graph_t *cg; |
503 | int i; |
504 | |
505 | for (i = 0; i < nnodes; i++) { |
506 | p->val = p->pos.y; |
507 | dtinsert(list, p); |
508 | p++; |
509 | } |
510 | if (ortho) |
511 | cg = mkConstraintG(g, list, ifn, distY); |
512 | else |
513 | cg = mkNConstraintG(g, list, ifn, distY); |
514 | rank(cg, 2, INT_MAX); |
515 | #ifdef DEBUG |
516 | { |
517 | Agsym_t *mlsym = agattr(cg, AGEDGE, "minlen" , "" ); |
518 | Agsym_t *rksym = agattr(cg, AGNODE, "rank" , "" ); |
519 | char buf[100]; |
520 | node_t *n; |
521 | edge_t *e; |
522 | for (n = agfstnode(cg); n; n = agnxtnode(cg, n)) { |
523 | sprintf(buf, "%d" , ND_rank(n)); |
524 | agxset(n, rksym, buf); |
525 | for (e = agfstedge(cg, n); e; e = agnxtedge(cg, e, n)) { |
526 | sprintf(buf, "%d" , ED_minlen(e)); |
527 | agxset(e, mlsym, buf); |
528 | } |
529 | } |
530 | } |
531 | #endif |
532 | |
533 | p = nlist; |
534 | for (i = 0; i < nnodes; i++) { |
535 | int newpos, oldpos, delta; |
536 | oldpos = p->pos.y; |
537 | newpos = ND_rank(p->cnode); |
538 | delta = newpos - oldpos; |
539 | p->pos.y = newpos; |
540 | p->bb.LL.y += delta; |
541 | p->bb.UR.y += delta; |
542 | p++; |
543 | } |
544 | |
545 | closeGraph(cg); |
546 | dtclose(list); |
547 | } |
548 | |
549 | #define overlap(pb,qb) \ |
550 | ((pb.LL.x <= qb.UR.x) && (qb.LL.x <= pb.UR.x) && \ |
551 | (pb.LL.y <= qb.UR.y) && (qb.LL.y <= pb.UR.y)) |
552 | |
553 | /* overlaps: |
554 | */ |
555 | static int overlaps(nitem * p, int cnt) |
556 | { |
557 | int i, j; |
558 | nitem *pi = p; |
559 | nitem *pj; |
560 | |
561 | for (i = 0; i < cnt - 1; i++) { |
562 | pj = pi + 1; |
563 | for (j = i + 1; j < cnt; j++) { |
564 | if (overlap(pi->bb, pj->bb)) |
565 | return 1; |
566 | pj++; |
567 | } |
568 | pi++; |
569 | } |
570 | return 0; |
571 | } |
572 | |
573 | /* initItem: |
574 | */ |
575 | static void initItem(node_t * n, nitem * p, expand_t margin) |
576 | { |
577 | int x = POINTS(SCALE * ND_pos(n)[0]); |
578 | int y = POINTS(SCALE * ND_pos(n)[1]); |
579 | int w2, h2; |
580 | box b; |
581 | |
582 | if (margin.doAdd) { |
583 | w2 = SCALE * (POINTS(ND_width(n)/2.0) + margin.x); |
584 | h2 = SCALE * (POINTS(ND_height(n)/2.0) + margin.y); |
585 | } |
586 | else { |
587 | w2 = POINTS(margin.x * SCALE2 * ND_width(n)); |
588 | h2 = POINTS(margin.y * SCALE2 * ND_height(n)); |
589 | } |
590 | |
591 | b.LL.x = x - w2; |
592 | b.LL.y = y - h2; |
593 | b.UR.x = x + w2; |
594 | b.UR.y = y + h2; |
595 | |
596 | p->pos.x = x; |
597 | p->pos.y = y; |
598 | p->np = n; |
599 | p->bb = b; |
600 | } |
601 | |
602 | /* cAdjust: |
603 | * Use optimization to remove overlaps. |
604 | * Modifications; |
605 | * - do y;x then x;y and use the better one |
606 | * - for all overlaps (or if overlap with leftmost nodes), add a constraint; |
607 | * constraint could move both x and y away, or the smallest, or some |
608 | * mixture. |
609 | * - follow by a scale down using actual shapes |
610 | * We use an optimization based on Marriott, Stuckey, Tam and He, |
611 | * "Removing Node Overlapping in Graph Layout Using Constrained Optimization", |
612 | * Constraints,8(2):143--172, 2003. |
613 | * We solve 2 constraint problem, one in X, one in Y. In each dimension, |
614 | * we require relative positions to remain the same. That is, if two nodes |
615 | * have the same x originally, they have the same x at the end, and if one |
616 | * node is to the left of another, it remains to the left. In addition, if |
617 | * two nodes could overlap by moving their X coordinates, we insert a constraint * to keep the two nodes sufficiently apart. Similarly, for Y. |
618 | * |
619 | * mode = AM_ORTHOXY => first X, then Y |
620 | * mode = AM_ORTHOYX => first Y, then X |
621 | * mode = AM_ORTHO => first X, then Y |
622 | * mode = AM_ORTHO_YX => first Y, then X |
623 | * In the last 2 cases, relax the constraints as follows: during the X pass, |
624 | * if two nodes actually intersect and a smaller move in the Y direction |
625 | * will remove the overlap, we don't force the nodes apart in the X direction, |
626 | * but leave it for the Y pass to remove any remaining overlaps. Without this, |
627 | * the X pass will remove all overlaps, and the Y pass only compresses in the |
628 | * Y direction, causing a skewing of the aspect ratio. |
629 | * |
630 | * mode = AM_ORTHOXY => first X, then Y |
631 | * mode = AM_ORTHOYX => first Y, then X |
632 | * mode = AM_ORTHO => first X, then Y |
633 | * mode = AM_ORTHO_YX => first Y, then X |
634 | */ |
635 | int cAdjust(graph_t * g, int mode) |
636 | { |
637 | expand_t margin; |
638 | int ret, i, nnodes = agnnodes(g); |
639 | nitem *nlist = N_GNEW(nnodes, nitem); |
640 | nitem *p = nlist; |
641 | node_t *n; |
642 | |
643 | margin = sepFactor (g); |
644 | |
645 | for (n = agfstnode(g); n; n = agnxtnode(g, n)) { |
646 | initItem(n, p, margin); |
647 | p++; |
648 | } |
649 | |
650 | if (overlaps(nlist, nnodes)) { |
651 | point pt; |
652 | |
653 | switch ((adjust_mode)mode) { |
654 | case AM_ORTHOXY: |
655 | constrainX(g, nlist, nnodes, intersectY, 1); |
656 | constrainY(g, nlist, nnodes, intersectX, 1); |
657 | break; |
658 | case AM_ORTHOYX: |
659 | constrainY(g, nlist, nnodes, intersectX, 1); |
660 | constrainX(g, nlist, nnodes, intersectY, 1); |
661 | break; |
662 | case AM_ORTHO : |
663 | constrainX(g, nlist, nnodes, intersectY0, 1); |
664 | constrainY(g, nlist, nnodes, intersectX, 1); |
665 | case AM_ORTHO_YX : |
666 | constrainY(g, nlist, nnodes, intersectX0, 1); |
667 | constrainX(g, nlist, nnodes, intersectY, 1); |
668 | case AM_PORTHOXY: |
669 | constrainX(g, nlist, nnodes, intersectY, 0); |
670 | constrainY(g, nlist, nnodes, intersectX, 0); |
671 | break; |
672 | case AM_PORTHOYX: |
673 | constrainY(g, nlist, nnodes, intersectX, 0); |
674 | constrainX(g, nlist, nnodes, intersectY, 0); |
675 | break; |
676 | case AM_PORTHO_YX : |
677 | constrainY(g, nlist, nnodes, intersectX0, 0); |
678 | constrainX(g, nlist, nnodes, intersectY, 0); |
679 | break; |
680 | case AM_PORTHO : |
681 | default : |
682 | constrainX(g, nlist, nnodes, intersectY0, 0); |
683 | constrainY(g, nlist, nnodes, intersectX, 0); |
684 | break; |
685 | } |
686 | p = nlist; |
687 | for (i = 0; i < nnodes; i++) { |
688 | n = p->np; |
689 | pt = p->pos; |
690 | ND_pos(n)[0] = PS2INCH(pt.x) / SCALE; |
691 | ND_pos(n)[1] = PS2INCH(pt.y) / SCALE; |
692 | p++; |
693 | } |
694 | ret = 1; |
695 | } |
696 | else ret = 0; |
697 | free(nlist); |
698 | return ret; |
699 | } |
700 | |
701 | typedef struct { |
702 | pointf pos; /* position for sorting */ |
703 | boxf bb; |
704 | double wd2; |
705 | double ht2; |
706 | node_t *np; |
707 | } info; |
708 | |
709 | typedef int (*sortfn_t) (const void *, const void *); |
710 | |
711 | static int sortf(pointf * p, pointf * q) |
712 | { |
713 | if (p->x < q->x) |
714 | return -1; |
715 | else if (p->x > q->x) |
716 | return 1; |
717 | else if (p->y < q->y) |
718 | return -1; |
719 | else if (p->y > q->y) |
720 | return 1; |
721 | else |
722 | return 0; |
723 | } |
724 | |
725 | static double compress(info * nl, int nn) |
726 | { |
727 | info *p = nl; |
728 | info *q; |
729 | int i, j; |
730 | double s, sc = 0; |
731 | pointf pt; |
732 | |
733 | for (i = 0; i < nn; i++) { |
734 | q = p + 1; |
735 | for (j = i + 1; j < nn; j++) { |
736 | if (overlap(p->bb, q->bb)) |
737 | return 0; |
738 | if (p->pos.x == q->pos.x) |
739 | pt.x = HUGE_VAL; |
740 | else { |
741 | pt.x = (p->wd2 + q->wd2) / fabs(p->pos.x - q->pos.x); |
742 | } |
743 | if (p->pos.y == q->pos.y) |
744 | pt.y = HUGE_VAL; |
745 | else { |
746 | pt.y = (p->ht2 + q->ht2) / fabs(p->pos.y - q->pos.y); |
747 | } |
748 | if (pt.y < pt.x) |
749 | s = pt.y; |
750 | else |
751 | s = pt.x; |
752 | if (s > sc) |
753 | sc = s; |
754 | q++; |
755 | } |
756 | p++; |
757 | } |
758 | return sc; |
759 | } |
760 | |
761 | static pointf *mkOverlapSet(info * nl, int nn, int *cntp) |
762 | { |
763 | info *p = nl; |
764 | info *q; |
765 | int sz = nn; |
766 | pointf *S = N_GNEW(sz + 1, pointf); |
767 | int i, j; |
768 | int cnt = 0; |
769 | |
770 | for (i = 0; i < nn; i++) { |
771 | q = p + 1; |
772 | for (j = i + 1; j < nn; j++) { |
773 | if (overlap(p->bb, q->bb)) { |
774 | pointf pt; |
775 | if (cnt == sz) { |
776 | sz += nn; |
777 | S = RALLOC(sz + 1, S, pointf); |
778 | } |
779 | if (p->pos.x == q->pos.x) |
780 | pt.x = HUGE_VAL; |
781 | else { |
782 | pt.x = (p->wd2 + q->wd2) / fabs(p->pos.x - q->pos.x); |
783 | if (pt.x < 1) |
784 | pt.x = 1; |
785 | } |
786 | if (p->pos.y == q->pos.y) |
787 | pt.y = HUGE_VAL; |
788 | else { |
789 | pt.y = (p->ht2 + q->ht2) / fabs(p->pos.y - q->pos.y); |
790 | if (pt.y < 1) |
791 | pt.y = 1; |
792 | } |
793 | S[++cnt] = pt; |
794 | } |
795 | q++; |
796 | } |
797 | p++; |
798 | } |
799 | |
800 | S = RALLOC(cnt + 1, S, pointf); |
801 | *cntp = cnt; |
802 | return S; |
803 | } |
804 | |
805 | static pointf computeScaleXY(pointf * aarr, int m) |
806 | { |
807 | pointf *barr; |
808 | double cost, bestcost; |
809 | int k, best = 0; |
810 | pointf scale; |
811 | |
812 | aarr[0].x = 1; |
813 | aarr[0].y = HUGE_VAL; |
814 | qsort(aarr + 1, m, sizeof(pointf), (sortfn_t) sortf); |
815 | |
816 | barr = N_GNEW(m + 1, pointf); |
817 | barr[m].x = aarr[m].x; |
818 | barr[m].y = 1; |
819 | for (k = m - 1; k >= 0; k--) { |
820 | barr[k].x = aarr[k].x; |
821 | barr[k].y = MAX(aarr[k + 1].y, barr[k + 1].y); |
822 | } |
823 | |
824 | bestcost = HUGE_VAL; |
825 | for (k = 0; k <= m; k++) { |
826 | cost = barr[k].x * barr[k].y; |
827 | if (cost < bestcost) { |
828 | bestcost = cost; |
829 | best = k; |
830 | } |
831 | } |
832 | assert(bestcost < HUGE_VAL); |
833 | scale.x = barr[best].x; |
834 | scale.y = barr[best].y; |
835 | |
836 | return scale; |
837 | } |
838 | |
839 | /* computeScale: |
840 | * For each (x,y) in aarr, scale has to be bigger than the smallest one. |
841 | * So, the scale is the max min. |
842 | */ |
843 | static double computeScale(pointf * aarr, int m) |
844 | { |
845 | int i; |
846 | double sc = 0; |
847 | double v; |
848 | pointf p; |
849 | |
850 | aarr++; |
851 | for (i = 1; i <= m; i++) { |
852 | p = *aarr++; |
853 | v = MIN(p.x, p.y); |
854 | if (v > sc) |
855 | sc = v; |
856 | } |
857 | return sc; |
858 | } |
859 | |
860 | /* scAdjust: |
861 | * Scale the layout. |
862 | * equal > 0 => scale uniformly in x and y to remove overlaps |
863 | * equal = 0 => scale separately in x and y to remove overlaps |
864 | * equal < 0 => scale down uniformly in x and y to remove excess space |
865 | * The last assumes there are no overlaps at present. |
866 | * Based on Marriott, Stuckey, Tam and He, |
867 | * "Removing Node Overlapping in Graph Layout Using Constrained Optimization", |
868 | * Constraints,8(2):143--172, 2003. |
869 | */ |
870 | int scAdjust(graph_t * g, int equal) |
871 | { |
872 | int nnodes = agnnodes(g); |
873 | info *nlist = N_GNEW(nnodes, info); |
874 | info *p = nlist; |
875 | node_t *n; |
876 | pointf s; |
877 | int i; |
878 | expand_t margin; |
879 | pointf *aarr; |
880 | int m; |
881 | |
882 | margin = sepFactor (g); |
883 | if (margin.doAdd) { |
884 | /* we use inches below */ |
885 | margin.x = PS2INCH(margin.x); |
886 | margin.y = PS2INCH(margin.y); |
887 | } |
888 | |
889 | for (n = agfstnode(g); n; n = agnxtnode(g, n)) { |
890 | double w2, h2; |
891 | if (margin.doAdd) { |
892 | w2 = (ND_width(n) / 2.0) + margin.x; |
893 | h2 = (ND_height(n) / 2.0) + margin.y; |
894 | } |
895 | else { |
896 | w2 = margin.x * ND_width(n) / 2.0; |
897 | h2 = margin.y * ND_height(n) / 2.0; |
898 | } |
899 | p->pos.x = ND_pos(n)[0]; |
900 | p->pos.y = ND_pos(n)[1]; |
901 | p->bb.LL.x = p->pos.x - w2; |
902 | p->bb.LL.y = p->pos.y - h2; |
903 | p->bb.UR.x = p->pos.x + w2; |
904 | p->bb.UR.y = p->pos.y + h2; |
905 | p->wd2 = w2; |
906 | p->ht2 = h2; |
907 | p->np = n; |
908 | p++; |
909 | } |
910 | |
911 | if (equal < 0) { |
912 | s.x = s.y = compress(nlist, nnodes); |
913 | if (s.x == 0) { /* overlaps exist */ |
914 | free(nlist); |
915 | return 0; |
916 | } |
917 | if (Verbose) fprintf(stderr, "compress %g \n" , s.x); |
918 | } else { |
919 | aarr = mkOverlapSet(nlist, nnodes, &m); |
920 | |
921 | if (m == 0) { /* no overlaps */ |
922 | free(aarr); |
923 | free(nlist); |
924 | return 0; |
925 | } |
926 | |
927 | if (equal) { |
928 | s.x = s.y = computeScale(aarr, m); |
929 | } else { |
930 | s = computeScaleXY(aarr, m); |
931 | } |
932 | free(aarr); |
933 | if (Verbose) fprintf(stderr, "scale by %g,%g \n" , s.x, s.y); |
934 | } |
935 | |
936 | p = nlist; |
937 | for (i = 0; i < nnodes; i++) { |
938 | ND_pos(p->np)[0] = s.x * p->pos.x; |
939 | ND_pos(p->np)[1] = s.y * p->pos.y; |
940 | p++; |
941 | } |
942 | |
943 | free(nlist); |
944 | return 1; |
945 | } |
946 | |