Graphviz  2.41.20170921.2350
constraint.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 
15 #include "config.h"
16 
17 #include "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 {
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 */
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,
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 */
704  double wd2;
705  double ht2;
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 }
boolean doAdd
Definition: adjust.h:45
int(* Dtcompar_f)(Dt_t *, void *, void *, Dtdisc_t *)
Definition: cdt.h:40
unsigned int(* Dthash_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:41
#define MAX(a, b)
Definition: agerror.c:17
#define ND_rank(n)
Definition: types.h:529
CGRAPH_API Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition: node.c:142
#define RALLOC(size, ptr, type)
Definition: memory.h:42
int(* intersectfn)(nitem *, nitem *)
Definition: constraint.c:35
point pos
Definition: constraint.c:27
CGRAPH_API Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
Definition: graph.c:44
#define GD_nlist(g)
Definition: types.h:401
CDT_API int dtclose(Dt_t *)
Agsym_t * agattr(Agraph_t *g, int kind, char *name, char *value)
Definition: attr.c:324
#define elist_append(item, L)
Definition: types.h:272
void *(* Dtmake_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:38
struct nitem nitem
#define MIN(a, b)
Definition: arith.h:35
expand_t sepFactor(graph_t *g)
Definition: adjust.c:1287
node_t * cnode
Definition: constraint.c:29
CDT_API Dtlink_t * dtflatten(Dt_t *)
Definition: dtflatten.c:9
CGRAPH_API Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition: edge.c:56
int agxset(void *obj, Agsym_t *sym, char *value)
Definition: attr.c:468
int(* sortfn_t)(const void *, const void *)
Definition: constraint.c:709
#define assert(x)
Definition: cghdr.h:47
Definition: geom.h:28
int cAdjust(graph_t *, int)
Definition: constraint.c:635
#define NOTUSED(var)
Definition: cghdr.h:54
Definition: cdt.h:80
#define ED_weight(e)
Definition: types.h:606
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
#define ND_pos(n)
Definition: types.h:526
#define alloc_elist(n, L)
Definition: types.h:273
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
int intersect(Ppoint_t a, Ppoint_t b, Ppoint_t c, Ppoint_t d)
Definition: visibility.c:153
point UR
Definition: geom.h:33
int x
Definition: geom.h:26
int scAdjust(graph_t *, int)
Definition: constraint.c:870
#define POINTS(a_inches)
Definition: geom.h:67
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
Definition: dtopen.c:9
#define PS2INCH(a_points)
Definition: geom.h:69
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
CGRAPH_API Agdesc_t Agstrictdirected
Definition: cgraph.h:419
box bb
Definition: constraint.c:31
int rank(graph_t *g, int balance, int maxiter)
Definition: ns.c:866
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
#define NIL(t)
Definition: dthdr.h:13
int
Definition: grammar.c:1264
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
node_t * vnode
Definition: constraint.c:30
double y
Definition: geom.h:28
CGRAPH_API int agclose(Agraph_t *g)
Definition: graph.c:93
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define ND_height(n)
Definition: types.h:504
float y
Definition: adjust.h:44
void *(* Dtmemory_f)(Dt_t *, void *, size_t, Dtdisc_t *)
Definition: cdt.h:36
#define overlap(pb, qb)
Definition: constraint.c:549
Dtlink_t link
Definition: constraint.c:25
point LL
Definition: geom.h:33
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
Definition: grammar.c:79
#define SCALE
Definition: constraint.c:21
#define AGNODE
Definition: cgraph.h:101
double wd2
Definition: constraint.c:704
#define dtinsert(d, o)
Definition: cdt.h:262
#define ND_width(n)
Definition: types.h:542
boxf bb
Definition: constraint.c:703
#define ND_alg(n)
Definition: types.h:490
#define NULL
Definition: logic.h:39
real cg(Operator Ax, Operator precond, int n, int dim, real *x0, real *rhs, real tol, int maxit, int *flag)
Definition: sparse_solve.c:227
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
Definition: geom.h:26
double x
Definition: geom.h:28
#define ND_in(n)
Definition: types.h:507
#define ND_next(n)
Definition: types.h:517
EXTERN unsigned char Verbose
Definition: globals.h:64
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
int val
Definition: constraint.c:26
#define ND_out(n)
Definition: types.h:522
pointf LL
Definition: geom.h:35
CGRAPH_API Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition: edge.c:281
double ht2
Definition: constraint.c:705
node_t * np
Definition: constraint.c:28
int(* Dtevent_f)(Dt_t *, int, void *, Dtdisc_t *)
Definition: cdt.h:42
pointf pos
Definition: constraint.c:702
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
int(* distfn)(box *, box *)
Definition: constraint.c:34
void(* Dtfree_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:39
CGRAPH_API Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition: edge.c:70
#define agfindedge(g, t, h)
Definition: types.h:610
Definition: cdt.h:99
#define SCALE2
Definition: constraint.c:22
double dist(Site *s, Site *t)
Definition: site.c:41
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define AGEDGE
Definition: cgraph.h:104
float x
Definition: adjust.h:44
int y
Definition: geom.h:26
pointf UR
Definition: geom.h:35
#define dtlink(d, e)
Definition: cdt.h:250
adjust_mode
Definition: adjust.h:28
Definition: geom.h:35
#define N_GNEW(n, t)
Definition: agxbuf.c:20
CDT_API Dtmethod_t * Dtobag
Definition: cdt.h:167
#define free_list(L)
Definition: types.h:274
#define ED_minlen(e)
Definition: types.h:595
Definition: geom.h:33
#define INT_MAX
Definition: arith.h:52
node_t * np
Definition: constraint.c:706
#define TRUE
Definition: cgraph.h:38