← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to dotneato/neatogen/adjust.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
dotneato/neatogen/adjust.c
 
1
/*
 
2
    This software may only be used by you under license from AT&T Corp.
 
3
    ("AT&T").  A copy of AT&T's Source Code Agreement is available at
 
4
    AT&T's Internet website having the URL:
 
5
    <http://www.research.att.com/sw/tools/graphviz/license/source.html>
 
6
    If you received this software without first entering into a license
 
7
    with AT&T, you have an infringing copy of this software and cannot use
 
8
    it without violating AT&T's intellectual property rights.
 
9
*/
 
10
#pragma prototyped
 
11
/* adjust.c
 
12
 * Routines for repositioning nodes after initial layout in
 
13
 * order to reduce/remove node overlaps.
 
14
 */
 
15
 
 
16
#include "neato.h"
 
17
#include "voronoi.h"
 
18
#include "info.h"
 
19
#include "edges.h"
 
20
#include "site.h"
 
21
#include "info.h"
 
22
 
 
23
#ifdef DMALLOC
 
24
#include "dmalloc.h"
 
25
#endif
 
26
 
 
27
static float    margin = 0.05;     /* Create initial bounding box by adding
 
28
                                    * margin * dimension around box enclosing
 
29
                                    * nodes.
 
30
                                    */
 
31
static float    incr = 0.05;       /* Increase bounding box by adding
 
32
                                    * incr * dimension around box.
 
33
                                    */
 
34
static float    pmargin = 5.0/72;  /* Margin around polygons, in inches */
 
35
static int      iterations = -1;  /* Number of iterations */
 
36
static int      useIter    = 0;   /* Use specified number of iterations */
 
37
 
 
38
static int      doAll      = 0;  /* Move all nodes, regardless of overlap */
 
39
static Site**   sites;           /* Array of pointers to sites; used in qsort */
 
40
static Site**   endSite;         /* Sentinel on sites array */
 
41
static Point nw, ne, sw, se;     /* Corners of clipping window */
 
42
 
 
43
static Site** nextSite;
 
44
 
 
45
static void
 
46
setBoundBox (Point* ll, Point* ur)
 
47
{
 
48
    pxmin = ll->x;
 
49
    pxmax = ur->x;
 
50
    pymin = ll->y;
 
51
    pymax = ur->y;
 
52
    nw.x = sw.x = pxmin;
 
53
    ne.x = se.x = pxmax;
 
54
    nw.y = ne.y = pymax;
 
55
    sw.y = se.y = pymin;
 
56
}
 
57
 
 
58
 /* freeNodes:
 
59
  * Free node resources.
 
60
  */
 
61
static void
 
62
freeNodes ()
 
63
{
 
64
    int          i;
 
65
    Info_t*      ip = nodeInfo;
 
66
 
 
67
    for (i=0; i < nsites; i++) {
 
68
      breakPoly (&ip->poly);
 
69
      ip++;
 
70
    }
 
71
    polyFree ();
 
72
    infoinit ();       /* Free vertices */
 
73
    free (nodeInfo);
 
74
}
 
75
 
 
76
/* chkBoundBox:
 
77
 *   Compute extremes of graph, then set up bounding box.
 
78
 *   If user supplied a bounding box, use that;
 
79
 *   else if "window" is a graph attribute, use that; 
 
80
 *   otherwise, define bounding box as a percentage expansion of
 
81
 *   graph extremes.
 
82
 *   In the first two cases, check that graph fits in bounding box.
 
83
 */
 
84
static void
 
85
chkBoundBox (Agraph_t* graph)
 
86
{
 
87
    char*        marg;
 
88
    Point        ll, ur;
 
89
    int          i;
 
90
    float        x, y;
 
91
    float        xmin, xmax, ymin, ymax;
 
92
    float        xmn, xmx, ymn, ymx;
 
93
    float        ydelta, xdelta;
 
94
    Info_t*      ip;
 
95
    Poly*        pp;
 
96
    /* int          cnt; */
 
97
 
 
98
    ip = nodeInfo;
 
99
    pp = &ip->poly;
 
100
    x = ip->site.coord.x;
 
101
    y = ip->site.coord.y;
 
102
    xmin = pp->origin.x + x;
 
103
    ymin = pp->origin.y + y;
 
104
    xmax = pp->corner.x + x;
 
105
    ymax = pp->corner.y + y;
 
106
    for(i = 1; i < nsites; i++) {
 
107
        ip++;
 
108
        pp = &ip->poly;
 
109
        x = ip->site.coord.x;
 
110
        y = ip->site.coord.y;
 
111
        xmn = pp->origin.x + x;
 
112
        ymn = pp->origin.y + y;
 
113
        xmx = pp->corner.x + x;
 
114
        ymx = pp->corner.y + y;
 
115
        if(xmn < xmin) xmin = xmn;
 
116
        if(ymn < ymin) ymin = ymn;
 
117
        if(xmx > xmax) xmax = xmx;
 
118
        if(ymx > ymax) ymax = ymx;
 
119
    }
 
120
 
 
121
    marg = agget (graph, "voro_margin");
 
122
    if (marg && (*marg != '\0')) {
 
123
      margin = atof (marg);
 
124
    }
 
125
    ydelta = margin * (ymax - ymin);
 
126
    xdelta = margin * (xmax - xmin);
 
127
    ll.x = xmin - xdelta;
 
128
    ll.y = ymin - ydelta;
 
129
    ur.x = xmax + xdelta;
 
130
    ur.y = ymax + ydelta;
 
131
 
 
132
    setBoundBox (&ll, &ur);
 
133
}
 
134
 
 
135
 /* makeInfo:
 
136
  * For each node in the graph, create a Info data structure 
 
137
  */
 
138
static void
 
139
makeInfo(Agraph_t* graph)
 
140
{
 
141
    Agnode_t*    node;
 
142
    int          i;
 
143
    Info_t*      ip;
 
144
    char*        marg;
 
145
 
 
146
    nsites = agnnodes (graph);
 
147
    geominit ();
 
148
 
 
149
    nodeInfo = (Info_t *) malloc(nsites * (sizeof (Info_t)));
 
150
 
 
151
    node = agfstnode (graph);
 
152
    ip = nodeInfo;
 
153
 
 
154
#ifdef OLD
 
155
    marg = agget (graph, "voro_pmargin");
 
156
    if (marg && (*marg != '\0')) {
 
157
      pmargin = atof (marg);
 
158
    }
 
159
#else
 
160
    if ((marg = agget(graph,"sep"))) {pmargin = 1.0 + atof(marg);}
 
161
    else pmargin = 1.01;
 
162
#endif
 
163
 
 
164
    for (i = 0; i < nsites; i++) {
 
165
        ip->site.coord.x = node->u.pos[0];
 
166
        ip->site.coord.y = node->u.pos[1];
 
167
 
 
168
        makePoly (&ip->poly, node, pmargin);
 
169
 
 
170
        ip->site.sitenbr = i;
 
171
        ip->site.refcnt = 1;
 
172
        ip->node = node;
 
173
        ip->verts = NULL;
 
174
        node = agnxtnode (graph, node);
 
175
        ip++;
 
176
    }
 
177
}
 
178
 
 
179
/* sort sites on y, then x, coord */
 
180
static int 
 
181
scomp(const void *S1, const void *S2)
 
182
{
 
183
    Site *s1,*s2;
 
184
 
 
185
    s1 = *(Site**)S1;
 
186
    s2 = *(Site**)S2;
 
187
    if(s1 -> coord.y < s2 -> coord.y) return(-1);
 
188
    if(s1 -> coord.y > s2 -> coord.y) return(1);
 
189
    if(s1 -> coord.x < s2 -> coord.x) return(-1);
 
190
    if(s1 -> coord.x > s2 -> coord.x) return(1);
 
191
    return(0);
 
192
}
 
193
 
 
194
 /* sortSites:
 
195
  * Fill array of pointer to sites and sort the sites using scomp
 
196
  */
 
197
static void
 
198
sortSites ()
 
199
{
 
200
    int          i;
 
201
    Site**       sp;
 
202
    Info_t*      ip;
 
203
 
 
204
    if (sites == 0) {
 
205
        sites = (Site**)malloc(nsites * sizeof(Site*));
 
206
        endSite = sites + nsites;
 
207
    }
 
208
 
 
209
    sp = sites;
 
210
    ip = nodeInfo;
 
211
    infoinit ();
 
212
    for (i=0; i < nsites; i++) {
 
213
        *sp++ = &(ip->site);
 
214
        ip->verts = NULL;
 
215
        ip->site.refcnt = 1;
 
216
        ip++;
 
217
    }
 
218
 
 
219
    qsort(sites, nsites, sizeof (Site *), scomp);
 
220
 
 
221
    /* Reset site index for nextOne */
 
222
    nextSite = sites;
 
223
 
 
224
}
 
225
 
 
226
static void
 
227
geomUpdate ()
 
228
{
 
229
    int      i;
 
230
 
 
231
    sortSites ();
 
232
 
 
233
    /* compute ranges */
 
234
    xmin=sites[0]->coord.x; 
 
235
    xmax=sites[0]->coord.x;
 
236
    for(i = 1; i < nsites; i++) {
 
237
        if(sites[i]->coord.x < xmin) xmin = sites[i]->coord.x;
 
238
        if(sites[i]->coord.x > xmax) xmax = sites[i]->coord.x;
 
239
    }
 
240
    ymin = sites[0]->coord.y;
 
241
    ymax = sites[nsites-1]->coord.y;
 
242
 
 
243
    deltay = ymax - ymin;
 
244
    deltax = xmax - xmin;
 
245
}
 
246
 
 
247
static 
 
248
Site *nextOne()
 
249
{
 
250
    Site*   s;
 
251
 
 
252
    if(nextSite < endSite) {
 
253
        s = *nextSite++;
 
254
        return (s);
 
255
    }
 
256
    else
 
257
        return((Site *)NULL);
 
258
}
 
259
 
 
260
static int
 
261
countOverlap (int iter)
 
262
{
 
263
    int          count = 0;
 
264
    int          i, j;
 
265
    Info_t*      ip = nodeInfo;
 
266
    Info_t*      jp;
 
267
 
 
268
    for (i = 0; i < nsites; i++)
 
269
      nodeInfo[i].overlaps = 0;
 
270
 
 
271
    for (i = 0; i < nsites-1; i++) {
 
272
      jp = ip+1;
 
273
      for (j = i+1; j < nsites; j++) {
 
274
        if (polyOverlap (ip->site.coord, &ip->poly, jp->site.coord, &jp->poly)){
 
275
          count++;
 
276
          ip->overlaps = 1;
 
277
          jp->overlaps = 1;
 
278
        }
 
279
        jp++;
 
280
      }
 
281
      ip++;
 
282
    }
 
283
 
 
284
    if (Verbose > 1)
 
285
      fprintf (stderr, "overlap [%d] : %d\n", iter, count);
 
286
    return count;
 
287
}
 
288
 
 
289
static void
 
290
increaseBoundBox ()
 
291
{
 
292
    float        ydelta, xdelta;
 
293
    Point        ll, ur;
 
294
    
 
295
    ur.x = pxmax;
 
296
    ur.y = pymax;
 
297
    ll.x = pxmin;
 
298
    ll.y = pymin;
 
299
    
 
300
    ydelta = incr * (ur.y - ll.y);
 
301
    xdelta = incr * (ur.x - ll.x);
 
302
 
 
303
    ur.x += xdelta;
 
304
    ur.y += ydelta;
 
305
    ll.x -= xdelta;
 
306
    ll.y -= ydelta;
 
307
 
 
308
    setBoundBox (&ll, &ur);
 
309
}
 
310
 
 
311
 /* areaOf:
 
312
  * Area of triangle whose vertices are a,b,c
 
313
  */
 
314
static float
 
315
areaOf (Point a,Point b,Point c)
 
316
{
 
317
    float area;
 
318
 
 
319
    area = (float)(fabs(a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y))/2);
 
320
    return area;
 
321
}
 
322
 
 
323
 /* centroidOf:
 
324
  * Compute centroid of triangle with vertices a, b, c.
 
325
  * Return coordinates in x and y.
 
326
  */
 
327
static void
 
328
centroidOf (Point a,Point b,Point c, float *x, float *y)
 
329
{
 
330
    *x = (a.x + b.x + c.x)/3;
 
331
    *y = (a.y + b.y + c.y)/3;
 
332
}
 
333
 
 
334
 /* newpos;
 
335
  * The new position is the centroid of the
 
336
  * voronoi polygon. This is the weighted sum of the
 
337
  * centroids of a triangulation, normalized to the
 
338
  * total area.
 
339
  */
 
340
static void
 
341
newpos (Info_t* ip)
 
342
{
 
343
    PtItem*  anchor = ip->verts;
 
344
    PtItem   *p, *q;
 
345
    float    totalArea = 0.0;
 
346
    float    cx = 0.0;
 
347
    float    cy = 0.0;
 
348
    float    x;
 
349
    float    y;
 
350
    float    area;
 
351
 
 
352
    p = anchor->next;
 
353
    q = p->next;
 
354
    while(q != NULL) {
 
355
      area = areaOf (anchor->p, p->p, q->p);
 
356
      centroidOf (anchor->p, p->p, q->p, &x, &y);
 
357
      cx = cx + area*x;
 
358
      cy = cy + area*y;
 
359
      totalArea = totalArea + area;
 
360
      p = q;
 
361
      q = q->next;
 
362
    }
 
363
 
 
364
    ip->site.coord.x = cx/totalArea;
 
365
    ip->site.coord.y = cy/totalArea;
 
366
}
 
367
 
 
368
 /* addCorners:
 
369
  * Add corners of clipping window to appropriate sites.
 
370
  * A site gets a corner if it is the closest site to that corner.
 
371
  */
 
372
static void
 
373
addCorners ()
 
374
{
 
375
    Info_t    *ip = nodeInfo;
 
376
    Info_t    *sws = ip;
 
377
    Info_t    *nws = ip;
 
378
    Info_t    *ses = ip;
 
379
    Info_t    *nes = ip;
 
380
    float   swd = dist_2(&ip->site.coord, &sw);
 
381
    float   nwd = dist_2(&ip->site.coord, &nw);
 
382
    float   sed = dist_2(&ip->site.coord, &se);
 
383
    float   ned = dist_2(&ip->site.coord, &ne);
 
384
    float   d;
 
385
    int     i;
 
386
    
 
387
    ip++;
 
388
    for (i = 1; i < nsites; i++) {
 
389
        d = dist_2(&ip->site.coord, &sw);
 
390
        if (d < swd) {
 
391
            swd = d;
 
392
            sws = ip;
 
393
        }
 
394
        d = dist_2(&ip->site.coord, &se);
 
395
        if (d < sed) {
 
396
            sed = d;
 
397
            ses = ip;
 
398
        }
 
399
        d = dist_2(&ip->site.coord, &nw);
 
400
        if (d < nwd) {
 
401
            nwd = d;
 
402
            nws = ip;
 
403
        }
 
404
        d = dist_2(&ip->site.coord, &ne);
 
405
        if (d < ned) {
 
406
            ned = d;
 
407
            nes = ip;
 
408
        }
 
409
        ip++;
 
410
    }
 
411
 
 
412
    addVertex (&sws->site, sw.x, sw.y);
 
413
    addVertex (&ses->site, se.x, se.y);
 
414
    addVertex (&nws->site, nw.x, nw.y);
 
415
    addVertex (&nes->site, ne.x, ne.y);
 
416
}
 
417
 
 
418
 /* newPos:
 
419
  * Calculate the new position of a site as the centroid
 
420
  * of its voronoi polygon, if it overlaps other nodes.
 
421
  * The polygons are finite by being clipped to the clipping
 
422
  * window.
 
423
  * We first add the corner of the clipping windows to the
 
424
  * vertex lists of the appropriate sites.
 
425
  */
 
426
static void
 
427
newPos ()
 
428
{
 
429
    int      i;
 
430
    Info_t*    ip = nodeInfo;
 
431
 
 
432
    addCorners ();
 
433
    for (i = 0; i < nsites; i++) {
 
434
        if (doAll || ip->overlaps) newpos (ip);
 
435
        ip++;
 
436
    }
 
437
}
 
438
 
 
439
static int
 
440
vAdjust ()
 
441
{
 
442
    int                iterCnt = 0;
 
443
    int                overlapCnt = 0;
 
444
    int                badLevel = 0;
 
445
    int                increaseCnt = 0;
 
446
    int                cnt;
 
447
 
 
448
    if (!useIter || (iterations > 0))
 
449
      overlapCnt = countOverlap (iterCnt);
 
450
    
 
451
    if ((overlapCnt == 0) || (iterations == 0))
 
452
      return 0;
 
453
 
 
454
    geomUpdate ();
 
455
    voronoi(0, nextOne); 
 
456
    while (1) {
 
457
      newPos ();
 
458
      iterCnt++;
 
459
      
 
460
      if (useIter && (iterCnt == iterations)) break;
 
461
      cnt = countOverlap (iterCnt);
 
462
      if (cnt == 0) break;
 
463
      if (cnt >= overlapCnt) badLevel++;
 
464
      else badLevel = 0;
 
465
      overlapCnt = cnt;
 
466
 
 
467
      switch (badLevel) {
 
468
      case 0:
 
469
        doAll = 1;
 
470
        break;
 
471
/*
 
472
      case 1:
 
473
        doAll = 1;
 
474
        break;
 
475
*/
 
476
      default :
 
477
        doAll = 1;
 
478
        increaseCnt++;
 
479
        increaseBoundBox ();
 
480
        break;
 
481
      }
 
482
 
 
483
      geomUpdate ();
 
484
      voronoi(0, nextOne); 
 
485
    }
 
486
 
 
487
    if (Verbose) {
 
488
      fprintf (stderr, "Number of iterations = %d\n", iterCnt);
 
489
      fprintf (stderr, "Number of increases = %d\n", increaseCnt);
 
490
    }
 
491
 
 
492
    return 1;
 
493
}
 
494
 
 
495
static void
 
496
rePos (Point c)
 
497
{
 
498
    int      i;
 
499
    Info_t*    ip = nodeInfo;
 
500
    double   f = 1.0 + incr;
 
501
 
 
502
  
 
503
    for (i = 0; i < nsites; i++) {
 
504
      ip->site.coord.x = f*(ip->site.coord.x - c.x) + c.x;
 
505
      ip->site.coord.y = f*(ip->site.coord.y - c.y) + c.y;
 
506
      ip++;
 
507
    }
 
508
 
 
509
}
 
510
 
 
511
static int
 
512
sAdjust ()
 
513
{
 
514
    int                iterCnt = 0;
 
515
    int                overlapCnt = 0;
 
516
    int                increaseCnt = 0;
 
517
    int                cnt;
 
518
    Point              center;
 
519
 
 
520
    if (!useIter || (iterations > 0))
 
521
      overlapCnt = countOverlap (iterCnt);
 
522
    
 
523
    if ((overlapCnt == 0) || (iterations == 0))
 
524
      return 0;
 
525
 
 
526
    center.x =  (pxmin + pxmax)/2.0;
 
527
    center.y =  (pymin + pymax)/2.0;
 
528
    while (1) {
 
529
      rePos (center);
 
530
      iterCnt++;
 
531
      
 
532
      if (useIter && (iterCnt == iterations)) break;
 
533
      cnt = countOverlap (iterCnt);
 
534
      if (cnt == 0) break;
 
535
    }
 
536
 
 
537
    if (Verbose) {
 
538
      fprintf (stderr, "Number of iterations = %d\n", iterCnt);
 
539
      fprintf (stderr, "Number of increases = %d\n", increaseCnt);
 
540
    }
 
541
 
 
542
    return 1;
 
543
}
 
544
 
 
545
 /* updateGraph:
 
546
  * Enter new node positions into the graph
 
547
  */
 
548
static void
 
549
updateGraph (Agraph_t* graph)
 
550
{
 
551
    /* Agnode_t*    node; */
 
552
    int          i;
 
553
    Info_t*        ip;
 
554
    /* char         pos[100]; */
 
555
 
 
556
    ip = nodeInfo;
 
557
    for (i = 0; i < nsites; i++) {
 
558
        ip->node->u.pos[0] = ip->site.coord.x;
 
559
        ip->node->u.pos[1] = ip->site.coord.y;
 
560
        ip++;
 
561
    }
 
562
}
 
563
 
 
564
static void normalize(graph_t *g)
 
565
{
 
566
        node_t  *v;
 
567
        edge_t  *e;
 
568
 
 
569
        double  theta;
 
570
        pointf  p;
 
571
 
 
572
        if (!mapbool(agget(g,"normalize"))) return;
 
573
 
 
574
        v = agfstnode(g); p.x = v->u.pos[0]; p.y = v->u.pos[1];
 
575
        for (v = agfstnode(g); v; v = agnxtnode(g,v))
 
576
                {v->u.pos[0] -= p.x; v->u.pos[1] -= p.y;}
 
577
 
 
578
        e = NULL;
 
579
        for (v = agfstnode(g); v; v = agnxtnode(g,v))
 
580
                if ((e = agfstout(g,v))) break;
 
581
        if (e == NULL) return;
 
582
 
 
583
        theta = -atan2(e->head->u.pos[1] - e->tail->u.pos[1],
 
584
                e->head->u.pos[0] - e->tail->u.pos[0]);
 
585
 
 
586
        for (v = agfstnode(g); v; v = agnxtnode(g,v)) {
 
587
                p.x = v->u.pos[0]; p.y = v->u.pos[1];
 
588
                v->u.pos[0] = p.x * cos(theta) - p.y * sin(theta);
 
589
                v->u.pos[1] = p.x * sin(theta) + p.y * cos(theta);
 
590
        }
 
591
}
 
592
 
 
593
void adjustNodes (graph_t* G)
 
594
{
 
595
    /* int          userWindow = 0; */
 
596
    char*        flag;
 
597
    int          doScale = 0;
 
598
    int          ret;
 
599
 
 
600
    normalize(G);
 
601
    flag = agget(G,"overlap");
 
602
    if (flag == NULL) return;
 
603
        if (!strcasecmp(flag,"scale")) doScale = 1;
 
604
    else if (mapbool(flag)) return;
 
605
 
 
606
          /* create main array */
 
607
    makeInfo(G);
 
608
 
 
609
      /* establish and verify bounding box */
 
610
    chkBoundBox (G);
 
611
 
 
612
    if (doScale) ret = sAdjust ();
 
613
    else ret = vAdjust ();
 
614
 
 
615
    if (ret) updateGraph (G);
 
616
 
 
617
    freeNodes ();
 
618
    free (sites);
 
619
 
 
620
}