← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dotneato/dotgen/position.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/dotgen/position.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
 
 
12
/*
 
13
 * position(g): set n->u.coord (x and y) for all nodes n of g, using g->u.rank.
 
14
 * (the graph may be modified by merging certain edges with a common endpoint.)
 
15
 * the coordinates are computed by constructing and ranking an auxiliary graph.
 
16
 * then leaf nodes are inserted in the fast graph.  cluster boundary nodes are
 
17
 * created and correctly separated.
 
18
 */
 
19
 
 
20
#include "dot.h"
 
21
 
 
22
#ifdef DMALLOC
 
23
#include "dmalloc.h"
 
24
#endif
 
25
 
 
26
void dot_position(graph_t* g)
 
27
{
 
28
        if (g->u.nlist == NULL) return;         /* ignore empty graph */
 
29
        mark_lowclusters(g);                            /* we could remove from splines.c now */
 
30
        set_ycoords(g);
 
31
        if (Concentrate) dot_concentrate(g);
 
32
        expand_leaves(g);
 
33
        if (flat_edges(g)) set_ycoords(g);
 
34
        create_aux_edges(g);
 
35
        rank(g,FALSE,nsiter2(g));
 
36
        set_xcoords(g);
 
37
        remove_aux_edges(g);
 
38
        set_aspect(g);
 
39
}
 
40
 
 
41
int nsiter2(graph_t* g)
 
42
{
 
43
        int             maxiter = MAXINT;
 
44
        char    *s;
 
45
 
 
46
        if ((s = agget(g,"nslimit")))
 
47
                maxiter = atof(s) * agnnodes(g);
 
48
        return maxiter;
 
49
}
 
50
 
 
51
static int searchcnt;
 
52
static int go(node_t* u, node_t* v)
 
53
{
 
54
        int             i;
 
55
        edge_t  *e;
 
56
 
 
57
        if (u == v) return TRUE;
 
58
        for (i = 0; (e = u->u.out.list[i]); i++) {
 
59
                if (go(e->head,v))
 
60
                        return TRUE;
 
61
        }
 
62
        return FALSE;
 
63
}
 
64
 
 
65
static int canreach(node_t* u, node_t* v)
 
66
{
 
67
        if (++searchcnt == 0) searchcnt = 1;
 
68
        return go(u,v);
 
69
}
 
70
 
 
71
edge_t *
 
72
make_aux_edge(node_t *u, node_t *v, int len, int wt)
 
73
{
 
74
        edge_t  *e;
 
75
 
 
76
        e = NEW(edge_t);
 
77
        e->tail = u;
 
78
        e->head = v;
 
79
        e->u.minlen = len;
 
80
        e->u.weight = wt;
 
81
        fast_edge(e);
 
82
        return e;
 
83
}
 
84
 
 
85
 
 
86
void allocate_aux_edges(graph_t* g)
 
87
{
 
88
        int             i,j,n_in;
 
89
        node_t  *n;
 
90
 
 
91
        /* allocate space for aux edge lists */
 
92
        for (n = g->u.nlist; n; n = n->u.next) {
 
93
                n->u.save_in = n->u.in;
 
94
                n->u.save_out = n->u.out;
 
95
                for (i = 0; n->u.out.list[i]; i++);
 
96
                for (j = 0; n->u.in.list[j]; j++);
 
97
                n_in = i + j;
 
98
                alloc_elist(n_in + 3,n->u.in);
 
99
                alloc_elist(3,n->u.out);
 
100
        }
 
101
}
 
102
 
 
103
void make_LR_constraints(graph_t* g)
 
104
{
 
105
        int             i,j,k;
 
106
        int             sw;             /* self width */
 
107
        int             m0,m1;
 
108
        int             width;
 
109
        edge_t  *e, *e0, *e1, *f, *ff;
 
110
        node_t  *u,*v, *t0, *h0;
 
111
        rank_t  *rank = g->u.rank;
 
112
 
 
113
        /* make edges to constrain left-to-right ordering */
 
114
        for (i = g->u.minrank; i <= g->u.maxrank; i++) {
 
115
                int             last;
 
116
                last = rank[i].v[0]->u.rank = 0;
 
117
                for (j = 0; j < rank[i].n; j++) {
 
118
                        u = rank[i].v[j];
 
119
                        u->u.mval = u->u.rw;    /* keep it somewhere safe */
 
120
                        if (u->u.other.size > 0) {      /* compute self size */
 
121
                                sw = 0;
 
122
                                for (k = 0; (e = u->u.other.list[k]); k++) {
 
123
                                        if (e->tail == e->head) {
 
124
                                                sw += SELF_EDGE_SIZE;
 
125
                                                if (e->u.label) {
 
126
                                                        double  label_width;
 
127
                                                        label_width = g->u.left_to_right? e->u.label->dimen.y : e->u.label->dimen.x;
 
128
                                                        sw += POINTS(label_width);
 
129
                                                }
 
130
                                        }
 
131
                                }
 
132
                                u->u.rw += sw;                  /* increment to include self edges */
 
133
                        }
 
134
                        v = rank[i].v[j+1];
 
135
                        if (v) {
 
136
                                width = u->u.rw + v->u.lw + g->u.nodesep;
 
137
                                e0 = make_aux_edge(u,v,width,0);
 
138
                                last = (v->u.rank = last + width);
 
139
                        }
 
140
 
 
141
                                /* position flat edge endpoints */
 
142
                        for (k = 0; k < u->u.flat_out.size; k++) {
 
143
                                e = u->u.flat_out.list[k];
 
144
                                v = e->head;
 
145
                                if (e->tail->u.order < e->head->u.order)
 
146
                                        { t0 = e->tail; h0 = e->head; }
 
147
                                else
 
148
                                        { t0 = e->head; h0 = e->tail; }
 
149
 
 
150
                                /* case 1: flat edge with a label */
 
151
                                if ((f = e->u.to_virt)) {
 
152
                                        while (f->u.to_virt) f = f->u.to_virt;
 
153
                                        e0 = f->tail->u.save_out.list[0];
 
154
                                        e1 = f->tail->u.save_out.list[1];
 
155
                                        if (e0->head->u.order > e1->head->u.order)
 
156
                                                { ff = e0; e0 = e1; e1 = ff; }
 
157
                                        m0 = (e->u.minlen *g->u.nodesep)/2;
 
158
                                        m1 = m0 + e0->head->u.rw + e0->tail->u.lw;
 
159
                                        /* these guards are needed because the flat edges
 
160
                                                work very poorly with cluster layout */
 
161
                                        if (canreach(e0->tail,e0->head) == FALSE)
 
162
                                                make_aux_edge(e0->head,e0->tail,m1,e->u.weight);
 
163
                                        m1 = m0 + e1->tail->u.rw + e1->head->u.lw;
 
164
                                        if (canreach(e1->head,e1->tail) == FALSE)
 
165
                                                make_aux_edge(e1->tail,e1->head,m1,e->u.weight);
 
166
                                        continue;
 
167
                                }
 
168
 
 
169
                                m0 = e->u.minlen *g->u.nodesep + t0->u.rw + h0->u.lw;
 
170
 
 
171
                                if ((e0 = find_fast_edge(t0,h0)))
 
172
                                        /* case 2: flat edge between neighbors */
 
173
                                        e0->u.minlen = MAX(e0->u.minlen,m0);
 
174
                                else
 
175
                                        /* case 3: flat edge between non-neighbors */
 
176
                                        make_aux_edge(t0,h0,m0,e->u.weight);
 
177
                        }
 
178
                }
 
179
        }
 
180
}
 
181
 
 
182
/* make_edge_pairs: make virtual edge pairs corresponding to input edges */
 
183
void make_edge_pairs(graph_t* g)
 
184
{
 
185
        int                     i,m0,m1;
 
186
        node_t          *n,*sn;
 
187
        edge_t          *e;
 
188
 
 
189
        for (n = g->u.nlist; n; n = n->u.next) {
 
190
                if (n->u.save_out.list) for (i = 0; (e = n->u.save_out.list[i]); i++) {
 
191
                        sn = virtual_node(g);
 
192
                        sn->u.node_type = SLACKNODE;
 
193
                        m0 = (e->u.head_port.p.x - e->u.tail_port.p.x);
 
194
                        if (m0 > 0) m1 = 0;
 
195
                        else {m1 = -m0; m0 = 0;}
 
196
                        make_aux_edge(sn,e->tail,m0+1,e->u.weight);
 
197
                        make_aux_edge(sn,e->head,m1+1,e->u.weight);
 
198
                        sn->u.rank = MIN(e->tail->u.rank - m0 -1, e->head->u.rank - m1 - 1);
 
199
                }
 
200
        }
 
201
}
 
202
 
 
203
/* pos_clusters: create constraints for:
 
204
 *      node containment in clusters,
 
205
 *      cluster containment in clusters,
 
206
 *      separation of sibling clusters.
 
207
 */
 
208
void pos_clusters(graph_t* g)
 
209
{
 
210
        if (g->u.n_cluster > 0) {
 
211
                contain_clustnodes(g);
 
212
                keepout_othernodes(g);
 
213
                contain_subclust(g);
 
214
                separate_subclust(g);
 
215
        }
 
216
}
 
217
 
 
218
void contain_clustnodes(graph_t* g)
 
219
{
 
220
        int             c;
 
221
 
 
222
        if (g != g->root) {
 
223
                contain_nodes(g);
 
224
                make_aux_edge(g->u.ln, g->u.rn, 1, 128);        /* clust compaction edge */
 
225
        }
 
226
        for (c = 1; c <= g->u.n_cluster; c++)
 
227
                contain_clustnodes(g->u.clust[c]);
 
228
}
 
229
 
 
230
int vnode_not_related_to(graph_t* g, node_t* v)
 
231
{
 
232
        edge_t  *e;
 
233
 
 
234
        if (v->u.node_type != VIRTUAL) return FALSE;
 
235
        for (e = v->u.save_out.list[0]; e->u.to_orig; e = e->u.to_orig);
 
236
        if (agcontains(g,e->tail)) return FALSE;
 
237
        if (agcontains(g,e->head)) return FALSE;
 
238
        return TRUE;
 
239
}
 
240
 
 
241
void keepout_othernodes(graph_t* g)
 
242
{
 
243
        int             i,c,r;
 
244
        node_t  *u,*v;
 
245
 
 
246
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
247
                if (g->u.rank[r].n == 0) continue;
 
248
                v = g->u.rank[r].v[0];
 
249
                if (v == NULL) continue;
 
250
                for (i = v->u.order - 1; i >= 0; i--) {
 
251
                        u = g->root->u.rank[r].v[i];
 
252
                                /* can't use "is_a_vnode_of" because elists are swapped */
 
253
                        if ((u->u.node_type == NORMAL) || vnode_not_related_to(g,u)) {
 
254
                                make_aux_edge(u,g->u.ln,CL_OFFSET+u->u.rw+g->u.border[LEFT_IX].x,0);
 
255
                                break;
 
256
                        }
 
257
                }
 
258
                for (i = v->u.order + g->u.rank[r].n; i < g->root->u.rank[r].n; i++) {
 
259
                        u = g->root->u.rank[r].v[i];
 
260
                        if ((u->u.node_type == NORMAL) || vnode_not_related_to(g,u)) {
 
261
                                make_aux_edge(g->u.rn,u,CL_OFFSET+u->u.lw+g->u.border[RIGHT_IX].x,0);
 
262
                                break;
 
263
                        }
 
264
                }
 
265
        }
 
266
        
 
267
        for (c = 1; c <= g->u.n_cluster; c++)
 
268
                keepout_othernodes(g->u.clust[c]);
 
269
}
 
270
 
 
271
void contain_subclust(graph_t* g)
 
272
{
 
273
        int             c;
 
274
        graph_t *subg;
 
275
 
 
276
        make_lrvn(g);
 
277
        for (c = 1; c <= g->u.n_cluster; c++) {
 
278
                subg = g->u.clust[c];
 
279
                make_lrvn(subg);
 
280
                make_aux_edge(g->u.ln, subg->u.ln, CL_OFFSET + subg->u.border[LEFT_IX].x, 0);
 
281
                make_aux_edge(subg->u.rn, g->u.rn, CL_OFFSET + subg->u.border[RIGHT_IX].x, 0);
 
282
                contain_subclust(subg);
 
283
        }
 
284
}
 
285
 
 
286
void separate_subclust(graph_t* g)
 
287
{
 
288
        int                     i,j;
 
289
        graph_t         *low,*high;
 
290
        graph_t         *left,*right;
 
291
 
 
292
        for (i = 1; i <= g->u.n_cluster; i++) make_lrvn(g->u.clust[i]);
 
293
        for (i = 1; i <= g->u.n_cluster; i++) {
 
294
                for (j = i + 1; j <= g->u.n_cluster; j++) {
 
295
                        low = g->u.clust[i]; high = g->u.clust[j];
 
296
                        if (low->u.minrank > high->u.minrank)
 
297
                                { graph_t       *temp = low; low = high; high= temp; }
 
298
                        if (low->u.maxrank < high->u.minrank) continue;
 
299
                        if ((low->u.rank[high->u.minrank].v[0]->u.order)
 
300
                                < (high->u.rank[high->u.minrank].v[0]->u.order))
 
301
                                        { left = low; right = high; }
 
302
                                else
 
303
                                        { left = high; right = low; }
 
304
                        make_aux_edge(left->u.rn, right->u.ln,
 
305
                                CL_OFFSET+left->u.border[RIGHT_IX].x+right->u.border[LEFT_IX].x,0);
 
306
                }
 
307
                separate_subclust(g->u.clust[i]);
 
308
        }
 
309
}
 
310
 
 
311
void create_aux_edges(graph_t* g)
 
312
{
 
313
        allocate_aux_edges(g);
 
314
        make_LR_constraints(g);
 
315
        make_edge_pairs(g);
 
316
        pos_clusters(g);
 
317
        compress_graph(g);
 
318
}
 
319
 
 
320
void remove_aux_edges(graph_t* g)
 
321
{
 
322
        int             i;
 
323
        node_t  *n,*nnext,*nprev;
 
324
        edge_t  *e;
 
325
 
 
326
        for (n = g->u.nlist; n; n = n->u.next) {
 
327
                for (i = 0; (e = n->u.out.list[i]); i++) free(e);
 
328
                free_list(n->u.out);
 
329
                free_list(n->u.in);
 
330
                n->u.out = n->u.save_out;
 
331
                n->u.in = n->u.save_in;
 
332
        }
 
333
        /* cannot be merged with previous loop */
 
334
        nprev = NULL;
 
335
        for (n = g->u.nlist; n; n = nnext) {
 
336
                nnext = n->u.next;
 
337
                if (n->u.node_type == SLACKNODE) {
 
338
                        if (nprev) nprev->u.next = nnext;
 
339
                        else g->u.nlist = nnext;
 
340
                        free(n);
 
341
                }
 
342
                else nprev = n;
 
343
        }
 
344
        g->u.nlist->u.prev = NULL;
 
345
}
 
346
 
 
347
void set_xcoords(graph_t* g)
 
348
{
 
349
        int             i,j;
 
350
        node_t  *v;
 
351
        rank_t  *rank = g->u.rank;
 
352
 
 
353
        for (i = g->u.minrank;  i <= g->u.maxrank; i++) {
 
354
                for (j = 0; j < rank[i].n; j++) {
 
355
                        v = rank[i].v[j];
 
356
                        v->u.coord.x = v->u.rank;
 
357
                        v->u.rank = i;
 
358
                }
 
359
        }
 
360
}
 
361
 
 
362
/* set y coordinates of nodes, a rank at a time */
 
363
void set_ycoords(graph_t* g)
 
364
{
 
365
        int             i,r,ht2,maxht,delta,d0,d1;
 
366
        node_t  *n;
 
367
        rank_t  *rank = g->u.rank;
 
368
        graph_t *clust;
 
369
        static void clust_ht(graph_t *g);
 
370
 
 
371
        ht2 = maxht = 0;
 
372
 
 
373
        /* scan ranks for tallest nodes.  */
 
374
        for (r = g->u.minrank; r <=  g->u.maxrank; r++) {
 
375
                for (i = 0; i < rank[r].n; i++) {
 
376
                        n = rank[r].v[i];
 
377
 
 
378
                        /* assumes symmetry, ht1 = ht2 */
 
379
                        ht2 = (n->u.ht + 1)/2;
 
380
 
 
381
                        /* update global rank ht */
 
382
                        if (rank[r].pht2 < ht2) rank[r].pht2 = rank[r].ht2 = ht2;
 
383
                        if (rank[r].pht1 < ht2) rank[r].pht1 = rank[r].ht1 = ht2;
 
384
 
 
385
                        /* update nearest enclosing cluster rank ht */
 
386
                        if ((clust = n->u.clust)) {
 
387
                                if (n->u.rank == clust->u.minrank)
 
388
                                        clust->u.ht2 = MAX(clust->u.ht2,ht2 + CL_OFFSET);
 
389
                                if (n->u.rank == clust->u.maxrank)
 
390
                                        clust->u.ht1 = MAX(clust->u.ht1,ht2 + CL_OFFSET);
 
391
                        }
 
392
                }
 
393
        }
 
394
 
 
395
        /* scan sub-clusters */
 
396
        clust_ht(g);
 
397
 
 
398
        /* make the initial assignment of ycoords to leftmost nodes by ranks */
 
399
        maxht = 0;
 
400
        r = g->u.maxrank;
 
401
        rank[r].v[0]->u.coord.y = rank[r].ht1;
 
402
        while (--r >= g->u.minrank) {
 
403
                d0 = rank[r+1].pht2 + rank[r].pht1 + g->u.ranksep; /* prim node sep */
 
404
                d1 = rank[r+1].ht2 + rank[r].ht1 + CL_OFFSET;   /* cluster sep */
 
405
                delta = MAX(d0,d1);
 
406
                if (rank[r].n > 0) /* this may reflect some problem */
 
407
                rank[r].v[0]->u.coord.y = rank[r + 1].v[0]->u.coord.y + delta;
 
408
#ifdef DEBUG
 
409
                else fprintf(stderr,"dot set_ycoords: rank %d is empty\n",rank[r].n);
 
410
#endif
 
411
                maxht = MAX(maxht,delta);
 
412
        }
 
413
 
 
414
        /* re-assign if ranks are equally spaced */
 
415
        if (g->u.exact_ranksep)
 
416
                for (r = g->u.maxrank - 1; r <=  g->u.minrank; r--)
 
417
                        if (rank[r].n > 0) /* this may reflect the same problem :-() */
 
418
                                rank[r].v[0]->u.coord.y = rank[r + 1].v[0]->u.coord.y + maxht;
 
419
 
 
420
        /* copy ycoord assignment from leftmost nodes to others */
 
421
        for (n = g->u.nlist; n; n = n->u.next)
 
422
                n->u.coord.y = rank[n->u.rank].v[0]->u.coord.y;
 
423
}
 
424
 
 
425
void compute_bb(graph_t* g, graph_t* root)
 
426
{
 
427
        int             c,r,x;
 
428
        node_t  *v;
 
429
        point   LL,UR,p,offset;
 
430
        
 
431
        LL.x = LL.y = MAXINT;
 
432
        UR.x = UR.y = -MAXINT;
 
433
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
434
                if (g->u.rank[r].n == 0) continue;
 
435
                if ((v = g->u.rank[r].v[0]) == NULL) continue;
 
436
                x = v->u.coord.x - v->u.lw;
 
437
                if (g != g->root) x-= CL_OFFSET;
 
438
                LL.x = MIN(LL.x,x);
 
439
                v = g->u.rank[r].v[g->u.rank[r].n-1];
 
440
                x = v->u.coord.x + v->u.rw;
 
441
                if (g != g->root) x+= CL_OFFSET;
 
442
                UR.x = MAX(UR.x,x);
 
443
        }
 
444
        offset.x = offset.y = CL_OFFSET;
 
445
        for (c = 1; c <= g->u.n_cluster; c++) {
 
446
                p = sub_points(g->u.clust[c]->u.bb.LL,offset);
 
447
                if (LL.x > p.x) LL.x = p.x;
 
448
                p = add_points(g->u.clust[c]->u.bb.UR,offset);
 
449
                if (UR.x < p.x) UR.x = p.x;
 
450
        }
 
451
        LL.y = root->u.rank[g->u.maxrank].v[0]->u.coord.y - g->u.ht1;
 
452
        UR.y = root->u.rank[g->u.minrank].v[0]->u.coord.y + g->u.ht2;
 
453
        g->u.bb.LL = LL; g->u.bb.UR = UR;
 
454
}
 
455
 
 
456
void update_bb(graph_t* g, point pt)
 
457
{
 
458
        if (pt.x > g->u.bb.UR.x)  g->u.bb.UR.x = pt.x;
 
459
        if (pt.y > g->u.bb.UR.y)  g->u.bb.UR.y = pt.y;
 
460
        if (pt.x < g->u.bb.LL.x)  g->u.bb.LL.x = pt.x;
 
461
        if (pt.y < g->u.bb.LL.y)  g->u.bb.LL.y = pt.y;
 
462
}
 
463
 
 
464
void rec_bb(graph_t *g, graph_t *root)
 
465
{
 
466
        int             c;
 
467
        for (c = 1; c <= g->u.n_cluster; c++)
 
468
                rec_bb(g->u.clust[c],root);
 
469
        compute_bb(g,root);
 
470
}
 
471
 
 
472
void set_aspect(graph_t* g)
 
473
{
 
474
        double  xf=0.0,yf=0.0,actual,desired;
 
475
        char    *str;
 
476
        node_t  *n;
 
477
        boolean scale_it,filled;
 
478
 
 
479
        rec_bb(g,g);
 
480
        if ((g->u.maxrank > 0) && (str = agget(g,"ratio"))) {
 
481
                g->u.bb.UR.x -= g->u.bb.LL.x;
 
482
                g->u.bb.UR.y -= g->u.bb.LL.y;   /* normalize */
 
483
                if (g->u.left_to_right)
 
484
                        {int t = g->u.bb.UR.x; g->u.bb.UR.x = g->u.bb.UR.y; g->u.bb.UR.y = t;}
 
485
                scale_it = TRUE;
 
486
                if (streq(str,"auto")) filled = idealsize(g,.5);
 
487
                else filled = (streq(str,"fill"));
 
488
                if (filled) {
 
489
                        /* fill is weird because both X and Y can stretch */
 
490
                        if (g->u.drawing->size.x <= 0) scale_it = FALSE;
 
491
                        else {
 
492
                                xf = (double)g->u.drawing->size.x / (double)g->u.bb.UR.x;
 
493
                                yf = (double)g->u.drawing->size.y / (double)g->u.bb.UR.y;
 
494
                                if ((xf < 1.0) || (yf < 1.0)) {
 
495
                                        if (xf < yf) {yf = yf / xf; xf = 1.0;}
 
496
                                        else {xf = xf / yf; yf = 1.0;}
 
497
                                }
 
498
                        }
 
499
                }
 
500
                else {
 
501
                        desired = atof(str);
 
502
                        if (desired == 0.0) scale_it = FALSE;
 
503
                        else {
 
504
                                actual = ((float)g->u.bb.UR.y)/((float)g->u.bb.UR.x);
 
505
                                if (actual < desired) {yf = desired/actual; xf = 1.0;}
 
506
                                else {xf = actual/desired; yf = 1.0;}
 
507
                        }
 
508
                }
 
509
                if (scale_it) {
 
510
                        if (g->u.left_to_right) {float t = xf; xf = yf; yf = t;}
 
511
                        for (n = g->u.nlist; n; n = n->u.next) {
 
512
                                n->u.coord.x = n->u.coord.x * xf;
 
513
                                n->u.coord.y = n->u.coord.y * yf;
 
514
                        }
 
515
                }
 
516
        }
 
517
        rec_bb(g,g);
 
518
}
 
519
 
 
520
point
 
521
resize_leaf(node_t* leaf, point lbound)
 
522
{
 
523
        dot_nodesize(leaf,leaf->graph->u.left_to_right);
 
524
        leaf->u.coord.y = lbound.y;
 
525
        leaf->u.coord.x = lbound.x + leaf->u.lw;
 
526
        lbound.x = lbound.x + leaf->u.lw + leaf->u.rw + leaf->graph->u.nodesep;
 
527
        return lbound;
 
528
}
 
529
 
 
530
point
 
531
place_leaf(node_t* leaf, point lbound, int order)
 
532
{
 
533
        node_t  *leader;
 
534
        graph_t *g = leaf->graph;
 
535
 
 
536
        leader = UF_find(leaf);
 
537
        if (leaf != leader) fast_nodeapp(leader,leaf);
 
538
        leaf->u.order = order;
 
539
        leaf->u.rank = leader->u.rank;
 
540
        g->u.rank[leaf->u.rank].v[leaf->u.order] = leaf;
 
541
        return resize_leaf(leaf,lbound);
 
542
}
 
543
 
 
544
/* make space for the leaf nodes of each rank */
 
545
void make_leafslots(graph_t* g)
 
546
{
 
547
        int             i,j,r;
 
548
        node_t  *v;
 
549
 
 
550
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
551
                j = 0;
 
552
                for (i = 0; i < g->u.rank[r].n; i++) {
 
553
                        v = g->u.rank[r].v[i];
 
554
                        v->u.order = j;
 
555
                        if (v->u.ranktype == LEAFSET) j = j + v->u.UF_size;
 
556
                        else j++;
 
557
                }
 
558
                if (j <= g->u.rank[r].n) continue;
 
559
                g->u.rank[r].v = ALLOC(j+1,g->u.rank[r].v,node_t*);
 
560
                for (i = g->u.rank[r].n - 1; i >= 0; i--) {
 
561
                        v = g->u.rank[r].v[i];
 
562
                        g->u.rank[r].v[v->u.order] = v;
 
563
                }
 
564
                g->u.rank[r].n = j;
 
565
                g->u.rank[r].v[j] = NULL;
 
566
        }
 
567
}
 
568
 
 
569
void do_leaves(graph_t* g, node_t* leader)
 
570
{
 
571
        int             j;
 
572
        point   lbound;
 
573
        node_t  *n;
 
574
        edge_t  *e;
 
575
 
 
576
        if (leader->u.UF_size <= 1) return;
 
577
        lbound.x = leader->u.coord.x - leader->u.lw;
 
578
        lbound.y = leader->u.coord.y;
 
579
        lbound = resize_leaf(leader,lbound);
 
580
        if (leader->u.out.size > 0) {           /* in-edge leaves */
 
581
                n = leader->u.out.list[0]->head;
 
582
                j = leader->u.order + 1;
 
583
                for (e = agfstin(g,n); e; e = agnxtin(g,e)) {
 
584
                        if ((e->tail != leader) && (UF_find(e->tail) == leader)) {
 
585
                                lbound = place_leaf(e->tail,lbound,j++);
 
586
                                unmerge_oneway(e);
 
587
                                elist_append(e,e->head->u.in);
 
588
                        }
 
589
                }
 
590
        }
 
591
        else {                                                  /* out edge leaves */
 
592
                n = leader->u.in.list[0]->tail;
 
593
                j = leader->u.order + 1;
 
594
                for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
 
595
                        if ((e->head != leader) && (UF_find(e->head) == leader)) {
 
596
                                lbound = place_leaf(e->head,lbound,j++);
 
597
                                unmerge_oneway(e);
 
598
                                elist_append(e,e->tail->u.out);
 
599
                        }
 
600
                }
 
601
        }
 
602
}
 
603
 
 
604
int ports_eq(edge_t *e,edge_t *f)
 
605
{
 
606
        return (
 
607
                   (e->u.head_port.defined == f->u.head_port.defined)
 
608
                && ( ((e->u.head_port.p.x == f->u.head_port.p.x) &&
 
609
                         (e->u.head_port.p.y == f->u.head_port.p.y))
 
610
                        || (e->u.head_port.defined == FALSE))
 
611
                && ( ((e->u.tail_port.p.x == f->u.tail_port.p.x) &&
 
612
                         (e->u.tail_port.p.y == f->u.tail_port.p.y))
 
613
                        || (e->u.tail_port.defined == FALSE))
 
614
        );
 
615
}
 
616
 
 
617
void expand_leaves(graph_t* g)
 
618
{
 
619
        int             i,d;
 
620
        node_t  *n;
 
621
        edge_t  *e,*f;
 
622
 
 
623
        make_leafslots(g);
 
624
        for (n = g->u.nlist; n; n = n->u.next) {
 
625
                if (n->u.inleaf) do_leaves(g,n->u.inleaf);
 
626
                if (n->u.outleaf) do_leaves(g,n->u.outleaf);
 
627
                if (n->u.other.list) for (i = 0; (e = n->u.other.list[i]); i++) {
 
628
                        if ((d = e->head->u.rank - e->head->u.rank) == 0) continue;
 
629
                        f = e->u.to_orig;
 
630
                        if (ports_eq(e,f) == FALSE) {
 
631
                                zapinlist(&(n->u.other),e);
 
632
                                if (d == 1) fast_edge(e);
 
633
                                /*else unitize(e); ### */
 
634
                                i--;
 
635
                        }
 
636
                }
 
637
        }
 
638
}
 
639
 
 
640
void compress_graph(graph_t* g)
 
641
{
 
642
        char            *str;
 
643
        double          x;
 
644
        point           p;
 
645
 
 
646
        p = g->u.drawing->size;
 
647
        if ((str = agget(g,"ratio")) == NULL) return;
 
648
        if (strcmp(str,"compress")) return;
 
649
        if (p.x * p.y <= 1) return;
 
650
        contain_nodes(g);
 
651
        if (g->u.left_to_right == FALSE) x = p.x; else x = p.y;
 
652
        make_aux_edge(g->u.ln,g->u.rn,(int)x,1000);
 
653
}
 
654
 
 
655
void make_lrvn(graph_t* g)
 
656
{
 
657
        node_t          *ln,*rn;
 
658
 
 
659
        if (g->u.ln) return;
 
660
        ln = virtual_node(g->root); ln->u.node_type = SLACKNODE;
 
661
        rn = virtual_node(g->root); rn->u.node_type = SLACKNODE;
 
662
        g->u.ln = ln; g->u.rn = rn;
 
663
}
 
664
 
 
665
/* contain_nodes: make left and right bounding box virtual nodes,
 
666
 *              constrain interior nodes
 
667
 */
 
668
void contain_nodes(graph_t* g)
 
669
{
 
670
        int                     r;
 
671
        node_t          *ln,*rn,*v;
 
672
 
 
673
        make_lrvn(g); ln = g->u.ln; rn = g->u.rn;
 
674
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
675
                if (g->u.rank[r].n == 0) continue;
 
676
                v = g->u.rank[r].v[0];
 
677
                if (v == NULL) {
 
678
                        fprintf(stderr,"contain_nodes clust %s rank %d missing node\n",g->name,r);
 
679
                        continue;
 
680
                }
 
681
                make_aux_edge(ln,v,v->u.lw + CL_OFFSET,0);
 
682
                v = g->u.rank[r].v[g->u.rank[r].n - 1];
 
683
                make_aux_edge(v,rn,v->u.rw + CL_OFFSET,0);
 
684
        }
 
685
}
 
686
 
 
687
/* set g->drawing->size to a reasonable default.
 
688
 * returns a boolean to indicate if drawing is to
 
689
 * be scaled and filled */
 
690
int idealsize(graph_t* g, double minallowed)
 
691
{
 
692
        double          xf,yf,f,R;
 
693
        point           b,relpage,margin;
 
694
 
 
695
        /* try for one page */
 
696
        relpage = g->u.drawing->page;
 
697
        if (relpage.x == 0) return FALSE;                               /* no page was specified */
 
698
        margin = g->u.drawing->margin;
 
699
        relpage = sub_points(relpage,margin);
 
700
        relpage = sub_points(relpage,margin);
 
701
        b.x = g->u.bb.UR.x; b.y = g->u.bb.UR.y;
 
702
        xf = (double)relpage.x / b.x;
 
703
        yf = (double)relpage.y / b.y;
 
704
        if ((xf >= 1.0) && (yf >= 1.0)) return FALSE;   /* fits on one page */
 
705
 
 
706
        f = MIN(xf,yf);
 
707
        xf = yf = MAX(f,minallowed);
 
708
 
 
709
        R = ceil((xf * b.x)/relpage.x);
 
710
        xf = ((R * relpage.x) / b.x);
 
711
        R = ceil((yf * b.y)/relpage.y);
 
712
        yf = ((R * relpage.y) / b.y);
 
713
        g->u.drawing->size.x = b.x * xf;
 
714
        g->u.drawing->size.y = b.y * yf;
 
715
        return TRUE;
 
716
}
 
717
 
 
718
/*
 
719
 * recursively compute cluster ht requirements.  assumes subg->u.ht1 and ht2
 
720
 * are computed from primitive nodes only.  updates ht1 and ht2 to reflect
 
721
 * cluster nesting and labels.  also maintains global rank ht1 and ht2.
 
722
 */
 
723
static void
 
724
clust_ht(Agraph_t *g)
 
725
{
 
726
        int     c, ht1, ht2;
 
727
        graph_t *subg;
 
728
        rank_t  *rank = g->root->u.rank;
 
729
 
 
730
        ht1 = g->u.ht1;
 
731
        ht2 = g->u.ht2;
 
732
 
 
733
        /* account for sub-clusters */
 
734
        for (c = 1; c <= g->u.n_cluster; c++) {
 
735
                subg = g->u.clust[c];
 
736
                clust_ht(subg);
 
737
                if (subg->u.maxrank == g->u.maxrank)
 
738
                        ht1 = MAX(ht1,subg->u.ht1 + CL_OFFSET);
 
739
                if (subg->u.minrank == g->u.minrank)
 
740
                        ht2 = MAX(ht2,subg->u.ht2 + CL_OFFSET);
 
741
        }
 
742
 
 
743
        /* account for a possible cluster label */
 
744
        ht1 += g->u.border[BOTTOM_IX].y;
 
745
        ht2 += g->u.border[TOP_IX].y;
 
746
        g->u.ht1 = ht1;
 
747
        g->u.ht2 = ht2;
 
748
 
 
749
        /* update the global ranks */
 
750
        if (g != g->root) {
 
751
                rank[g->u.minrank].ht2 = MAX(rank[g->u.minrank].ht2,ht2);
 
752
                rank[g->u.maxrank].ht1 = MAX(rank[g->u.maxrank].ht1,ht1);
 
753
        }
 
754
}