← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dotneato/dotgen/flat.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/flat.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
#include        "dot.h"
 
13
 
 
14
#ifdef DMALLOC
 
15
#include "dmalloc.h"
 
16
#endif
 
17
 
 
18
node_t  *
 
19
make_vn_slot(graph_t *g, int r, int pos)
 
20
{
 
21
        int             i;
 
22
        node_t  **v,*n;
 
23
 
 
24
        v = g->u.rank[r].v = ALLOC(g->u.rank[r].n+2,g->u.rank[r].v,node_t*);
 
25
        for (i = g->u.rank[r].n; i > pos; i--) {
 
26
                v[i] = v[i-1];
 
27
                v[i]->u.order++;
 
28
        }
 
29
        n = v[pos] = virtual_node(g);
 
30
        n->u.order = pos;       n->u.rank = r;
 
31
        v[++(g->u.rank[r].n)] = NULL;
 
32
        return v[pos];
 
33
}
 
34
 
 
35
#define         HLB     0               /* hard left bound */
 
36
#define         HRB             1               /* hard right bound */
 
37
#define         SLB             2               /* soft left bound */
 
38
#define         SRB             3               /* soft right bound */
 
39
 
 
40
void findlr(node_t *u, node_t *v, int *lp, int *rp)
 
41
{
 
42
        int             l,r;
 
43
        l = u->u.order; r = v->u.order;
 
44
        if (l > r) {int t = l; l = r; r = t;}
 
45
        *lp = l; *rp = r;
 
46
}
 
47
 
 
48
void setbounds(node_t *v, int *bounds,int lpos, int rpos)
 
49
{
 
50
        int             i, l,r,ord;
 
51
        edge_t  *f;
 
52
 
 
53
        if (v->u.node_type == VIRTUAL) {
 
54
                ord = v->u.order;
 
55
                if (v->u.in.size == 0) {        /* flat */
 
56
                        assert(v->u.out.size == 2);
 
57
                        findlr(v->u.out.list[0]->head,v->u.out.list[1]->head,&l,&r);
 
58
                                /* the other flat edge could be to the left or right */
 
59
                        if (r <= lpos) bounds[SLB] = bounds[HLB] = ord;
 
60
                        else if (l >= rpos) bounds[SRB] = bounds[HRB] = ord;
 
61
                                /* could be spanning this one */
 
62
                        else if ((l < lpos) && (r > rpos)) ; /* ignore */
 
63
                                /* must have intersecting ranges */
 
64
                        else {
 
65
                                if ((l < lpos) || ((l == lpos) && (r < rpos)))
 
66
                                        bounds[SLB] = ord;
 
67
                                if ((r > rpos) || ((r == rpos) && (l > lpos)))
 
68
                                        bounds[SRB] = ord;
 
69
                        }
 
70
                }
 
71
                else {                                          /* forward */
 
72
                        boolean         onleft,onright;
 
73
                        onleft = onright = FALSE;
 
74
                        for (i = 0; (f = v->u.out.list[i]); i++) {
 
75
                                if (f->head->u.order <= lpos) {onleft = TRUE; continue;}
 
76
                                if (f->head->u.order >= rpos) {onright = TRUE; continue;}
 
77
                        }
 
78
                        if (onleft && (onright == FALSE)) bounds[HLB] = ord + 1;
 
79
                        if (onright && (onleft == FALSE)) bounds[HRB] = ord - 1;
 
80
                }
 
81
        }
 
82
}
 
83
 
 
84
int flat_limits(graph_t* g, edge_t* e)
 
85
{
 
86
        int                     lnode,rnode,r,bounds[4],lpos,rpos,pos;
 
87
        node_t          **rank;
 
88
 
 
89
        r = e->tail->u.rank - 1;
 
90
        rank = g->u.rank[r].v;
 
91
        lnode = 0;
 
92
        rnode = g->u.rank[r].n - 1;
 
93
        bounds[HLB] = bounds[SLB] = lnode - 1;
 
94
        bounds[HRB] = bounds[SRB] = rnode + 1;
 
95
        findlr(e->tail,e->head,&lpos,&rpos);
 
96
        while (lnode <= rnode) {
 
97
                setbounds(rank[lnode],bounds,lpos,rpos);
 
98
                if (lnode != rnode)
 
99
                        setbounds(rank[rnode],bounds,lpos,rpos);
 
100
                lnode++; rnode--;
 
101
                if (bounds[HRB] - bounds[HLB] <= 1) break;
 
102
        }
 
103
        if (bounds[HLB] <= bounds[HRB])
 
104
                pos = (bounds[HLB] + bounds[HRB] + 1) / 2;
 
105
        else
 
106
                pos = (bounds[SLB] + bounds[SRB] + 1) / 2;
 
107
        return pos;
 
108
}
 
109
 
 
110
void flat_node(edge_t* e)
 
111
{
 
112
        int             r,place,ypos,h2;
 
113
        graph_t *g;
 
114
        node_t  *n,*vn;
 
115
        edge_t  *ve;
 
116
        pointf  dimen;
 
117
 
 
118
        if (e->u.label == NULL) return;
 
119
        g = e->tail->graph;
 
120
        r = e->tail->u.rank;
 
121
 
 
122
        place = flat_limits(g,e);
 
123
                /* grab ypos = LL.y of label box before make_vn_slot() */
 
124
        if ((n = g->u.rank[r - 1].v[0]))
 
125
                ypos = n->u.coord.y - g->u.rank[r - 1].ht2;
 
126
        else {
 
127
                n = g->u.rank[r].v[0];
 
128
                ypos = n->u.coord.y + g->u.rank[r].ht1 + g->u.ranksep;
 
129
        }
 
130
        vn = make_vn_slot(g,r-1,place); 
 
131
        dimen = e->u.label->dimen;
 
132
        if (g->u.left_to_right) {float f = dimen.x; dimen.x = dimen.y; dimen.y = f;}
 
133
        vn->u.ht = POINTS(dimen.y); h2 = vn->u.ht / 2;
 
134
        vn->u.lw = vn->u.rw = POINTS(dimen.x)/2;
 
135
        vn->u.label = e->u.label;
 
136
        vn->u.coord.y = ypos + h2;
 
137
        ve = virtual_edge(vn,e->tail,e);        /* was NULL? */
 
138
                ve->u.tail_port.p.x = -vn->u.lw;
 
139
                ve->u.head_port.p.x = e->tail->u.rw;
 
140
                ve->u.edge_type = FLATORDER;
 
141
        ve = virtual_edge(vn,e->head,e);
 
142
                ve->u.tail_port.p.x = vn->u.rw;
 
143
                ve->u.head_port.p.x = e->head->u.lw;
 
144
                ve->u.edge_type = FLATORDER;
 
145
        /* another assumed symmetry of ht1/ht2 of a label node */
 
146
        if (g->u.rank[r-1].ht1 < h2) g->u.rank[r-1].ht1 = h2;
 
147
        if (g->u.rank[r-1].ht2 < h2) g->u.rank[r-1].ht2 = h2;
 
148
}
 
149
 
 
150
int flat_edges(graph_t* g)
 
151
{
 
152
        int             i,j,reset = FALSE;
 
153
        node_t  *n;
 
154
        edge_t  *e;
 
155
 
 
156
        if ((g->u.rank[0].flat) || (g->u.n_cluster > 0)) {
 
157
                for (i = 0; (n = g->u.rank[0].v[i]); i++) {
 
158
                        for (j = 0; (e = n->u.flat_in.list[j]); j++) {
 
159
                                if (e->u.label) {abomination(g); break;}
 
160
                        }
 
161
                        if (e) break;
 
162
                }
 
163
        }
 
164
                        
 
165
        rec_save_vlists(g);
 
166
        for (n = g->u.nlist; n; n = n->u.next) {
 
167
                if (n->u.flat_out.list) for (i = 0; (e = n->u.flat_out.list[i]); i++) {
 
168
                        reset = TRUE;
 
169
                        flat_node(e);
 
170
                }
 
171
        }
 
172
        if (reset) rec_reset_vlists(g);
 
173
        return reset;
 
174
}
 
175
 
 
176
void abomination(graph_t* g)
 
177
{
 
178
        int             r;
 
179
        rank_t  *rptr;
 
180
 
 
181
        assert(g->u.minrank == 0);
 
182
                /* 3 = one for new rank, one for sentinel, one for off-by-one */
 
183
        r = g->u.maxrank + 3;
 
184
        rptr = ALLOC(r,g->u.rank,rank_t);
 
185
        g->u.rank = rptr + 1;
 
186
        for (r = g->u.maxrank; r >= 0; r--)
 
187
                g->u.rank[r] = g->u.rank[r-1];
 
188
        g->u.rank[r].n = g->u.rank[0].an = 0;
 
189
        g->u.rank[r].v = g->u.rank[0].av = N_NEW(2,node_t*);
 
190
        g->u.rank[r].flat = NULL;
 
191
        g->u.rank[r].ht1 = g->u.rank[r].ht2 = 1;
 
192
        g->u.rank[r].pht1 = g->u.rank[r].pht2 = 1;
 
193
        g->u.minrank--;
 
194
}