← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/graphviz/jaunty

« back to all changes in this revision

Viewing changes to dag/config.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:
dag/config.c
 
1
#include <dag.h>
 
2
 
 
3
#ifdef DMALLOC
 
4
#include "dmalloc.h"
 
5
#endif
 
6
 
 
7
/* maintains ranked graph configurations */
 
8
 
 
9
rank_t *dd_rankd(ddview_t *view, int absrank)
 
10
{
 
11
        if ((absrank < view->config->low) || (absrank > view->config->high))
 
12
                return NILrank;
 
13
        return view->config->r[absrank - view->config->low];
 
14
}
 
15
 
 
16
Agnode_t *dd_relnode(ddview_t *view, Agnode_t *n, int offset)
 
17
{
 
18
        rank_t          *rd;
 
19
        int                     r,pos;
 
20
 
 
21
        r = dd_rank(n);
 
22
        pos = dd_order(n) + offset;
 
23
        if (pos < 0) return NILnode;
 
24
 
 
25
        rd = dd_rankd(view,r);
 
26
        if (pos >= rd->n) return NILnode;
 
27
        return rd->v[pos];
 
28
}
 
29
 
 
30
Agnode_t *dd_right(ddview_t *view, Agnode_t *n)
 
31
{
 
32
        return dd_relnode(view,n,1);
 
33
}
 
34
 
 
35
Agnode_t *dd_left(ddview_t *view, Agnode_t *n)
 
36
{
 
37
        return dd_relnode(view,n,-1);
 
38
}
 
39
 
 
40
Agnode_t *dd_rightmost(ddview_t *view, int r)
 
41
{
 
42
        rank_t          *rd;
 
43
 
 
44
        rd = dd_rankd(view,r);
 
45
        if ((rd == NILrank) || (rd->n == 0))
 
46
                return NILnode;
 
47
        return rd->v[rd->n - 1];
 
48
}
 
49
 
 
50
Agnode_t *dd_leftmost(ddview_t *view, int r)
 
51
{
 
52
        rank_t          *rd;
 
53
 
 
54
        rd = dd_rankd(view,r);
 
55
        if ((rd == NILrank) || (rd->n == 0))
 
56
                return NILnode;
 
57
        return rd->v[0];
 
58
}
 
59
 
 
60
static void extend_config(ddview_t *view, int low, int high)
 
61
{
 
62
        int                     i,osize,nsize,o_nbytes,n_nbytes;
 
63
        config_t        *config;
 
64
        rank_t          **list;
 
65
 
 
66
        config = view->config;
 
67
        if (config->r) {
 
68
                osize = (config->high - config->low + 1);
 
69
                o_nbytes = osize * sizeof(config->r[0]);
 
70
                nsize = (high - low + 1);
 
71
                n_nbytes = nsize * sizeof(config->r[0]);
 
72
 
 
73
                list = config->r = agrealloc(view->layout,config->r,o_nbytes,n_nbytes);
 
74
                if (low < config->low) {
 
75
                        for (i = osize - 1; i >= 0; i--)
 
76
                                list[i + (nsize - osize)] = list[i];
 
77
                        for (i = 0; i < (nsize - osize); i++)
 
78
                                list[i] = agalloc(view->layout,sizeof(rank_t));
 
79
                }
 
80
                else {
 
81
                        for (i = osize; i < nsize; i++)
 
82
                                list[i] = agalloc(view->layout,sizeof(rank_t));
 
83
                }
 
84
        }
 
85
        else {
 
86
                nsize = high - low + 1;
 
87
                n_nbytes = nsize * sizeof(config->r[0]);
 
88
                config->r = agalloc(view->layout,n_nbytes);
 
89
                for (i = 0; i < nsize; i++)
 
90
                        config->r[i] = agalloc(view->layout,sizeof(rank_t));
 
91
        }
 
92
        config->low = low;
 
93
        config->high = high;
 
94
}
 
95
 
 
96
rank_t *dd_extendrank(ddview_t *view, int r)
 
97
{
 
98
        rank_t          *rd;
 
99
        
 
100
        if ((r < view->config->low) || (r > view->config->high)) {
 
101
                if (view->config->low <= view->config->high) {
 
102
                        extend_config(view,MIN(r,view->config->low),MAX(r,view->config->high));
 
103
                }
 
104
                else {
 
105
                        extend_config(view,r,r);
 
106
                }
 
107
        }
 
108
        rd = dd_rankd(view,r);
 
109
        rd->v = agrealloc(view->layout,rd->v,(rd->n + 1) * sizeof(rd->v[0]),
 
110
                                (rd->n + 2) * sizeof(rd->v[0]));
 
111
        return rd;
 
112
}
 
113
 
 
114
void dd_install_at_right(ddview_t *view, Agnode_t *n, int r)
 
115
{
 
116
        Agnode_t        *right;
 
117
        rank_t          *rd;
 
118
        double          x;
 
119
        int                     slot;
 
120
 
 
121
        right = dd_rightmost(view,r);
 
122
        if (right) x = dd_pos(right).x + dd_uv_sep(view,right,n);
 
123
        else x = 0.0;
 
124
        rd = dd_extendrank(view,r);
 
125
        slot = rd->n++;
 
126
        rd->v[slot] = n;
 
127
        dd_node(n)->rank = r;
 
128
        dd_node(n)->order = slot;
 
129
        dd_set_x(n,x);
 
130
        dd_set_config_flag(n,TRUE);
 
131
        dd_set_ycoord(view,n);
 
132
}
 
133
 
 
134
void dd_install_at_pos(ddview_t *view, Agnode_t *n, int r, double x)
 
135
{
 
136
        Agnode_t        *ln,*rn,*mv;
 
137
        rank_t          *rd;
 
138
        int                     i,slot;
 
139
 
 
140
        dd_set_x(n,x);
 
141
 
 
142
        /* find where incoming node belongs */
 
143
        ln = NILnode;
 
144
        for (rn = dd_leftmost(view,r); rn; rn = dd_right(view,rn)) {
 
145
                if (x <= dd_pos(rn).x) break;
 
146
                else ln = rn;
 
147
        }
 
148
 
 
149
        if (ln) slot = dd_order(ln) + 1;
 
150
        else slot = 0;
 
151
 
 
152
        rd = dd_extendrank(view,r);
 
153
        for (i = rd->n - 1; i >= slot; i--) {
 
154
                mv = rd->v[i+1] = rd->v[i];
 
155
                dd_node(mv)->order = i+1;
 
156
                dd_invalidate_adj_mvals(mv);
 
157
        }
 
158
        rd->v[slot] = n;
 
159
        rd->n++;
 
160
        dd_node(n)->order = slot;
 
161
        dd_node(n)->rank = r;
 
162
        dd_invalidate_adj_mvals(n);
 
163
        dd_set_config_flag(n,TRUE);
 
164
        dd_set_ycoord(view,n);
 
165
}
 
166
 
 
167
void dd_exchange(ddview_t *view, Agnode_t *u, Agnode_t *v)
 
168
{
 
169
        rank_t          *rd;
 
170
        int                     upos,vpos;
 
171
 
 
172
        Agnode_t        *cn_u, *cn_v;   /* constraint vars */
 
173
        Agedge_t        *ce;                    /* possible LR constraint edge */
 
174
 
 
175
        assert(dd_node_in_config(u));
 
176
        assert(dd_node_in_config(v));
 
177
        assert(dd_rank(u) == dd_rank(v));
 
178
 
 
179
        rd = dd_rankd(view,dd_rank(u));
 
180
        upos = dd_order(u);
 
181
        vpos = dd_order(v);
 
182
 
 
183
        /* delete any LR constraint between these nodes */
 
184
        cn_u =  dd_node(u)->con[XCON].n;
 
185
        cn_v =  dd_node(v)->con[XCON].n;
 
186
        if (cn_u && cn_v && ((ce = agedge(cn_u,cn_v,NILstr,FALSE))))
 
187
                agdelete(view->con[XCON].g,ce);
 
188
 
 
189
        rd->v[vpos] = u; dd_node(u)->order = vpos;
 
190
        rd->v[upos] = v; dd_node(v)->order = upos;
 
191
        dd_invalidate_adj_mvals(u);
 
192
        dd_invalidate_adj_mvals(v);
 
193
        (void)agsubnode(view->dirty,u,TRUE);
 
194
        (void)agsubnode(view->dirty,v,TRUE);
 
195
}
 
196
 
 
197
void dd_delete_constraint(ddview_t *view, Agnode_t *ln, int sys)
 
198
{
 
199
        ddnode_t        *nd;
 
200
        Agnode_t        *c_var;
 
201
 
 
202
        nd = dd_node(ln);
 
203
        if ((c_var = nd->con[sys].n)) {
 
204
                agdelete(view->con[sys].g,c_var);
 
205
                nd->con[sys].n = NILnode;
 
206
        }
 
207
        if ((c_var = nd->con[sys].stab)) {
 
208
                agdelete(view->con[sys].g,c_var);
 
209
                nd->con[sys].stab = NILnode;
 
210
        }
 
211
}
 
212
 
 
213
 
 
214
void dd_rank_delete(ddview_t *view, Agnode_t *n)
 
215
{
 
216
        rank_t          *rd;
 
217
        Agnode_t        *mv, *cn;
 
218
        Agedge_t        *e;
 
219
        int                     pos,i;
 
220
 
 
221
        for (e = agfstedge(n); e; e = agnxtedge(e,n)) {
 
222
        cn = dd_edge(e)->cn;
 
223
        if (cn) {
 
224
            agdelete(view->con[XCON].g, cn);
 
225
            dd_edge(e)->cn = NILnode;
 
226
        }
 
227
        }
 
228
        dd_delete_constraint(view, n, XCON);
 
229
        dd_invalidate_adj_mvals(n);
 
230
        rd = dd_rankd(view,dd_rank(n));
 
231
        pos = dd_order(n);
 
232
        assert(rd->v[pos] == n);
 
233
        for (i = pos; i < rd->n - 1; i++) {
 
234
                mv = rd->v[i] = rd->v[i+1];
 
235
                dd_node(mv)->order = i;
 
236
                if (i == pos) agsubnode(view->dirty,mv,TRUE);
 
237
        }
 
238
        rd->v[i] = NILnode;
 
239
        rd->n--;
 
240
 
 
241
        dd_set_config_flag(n,FALSE);
 
242
        dd_node(n)->rank = -MAXINT;
 
243
        dd_fix_coord(n,FALSE);
 
244
        dd_fix_order(n,FALSE);
 
245
}
 
246
 
 
247
void    dd_set_config_flag(Agnode_t *n, ilbool val) {dd_node(n)->in_config = val;}
 
248
ilbool  dd_node_in_config(Agnode_t *n) {return dd_node(n)->in_config;}
 
249
 
 
250
void dd_open_config(ddview_t *view)
 
251
{
 
252
        config_t        *config;
 
253
 
 
254
        config = agalloc(view->layout,sizeof(config_t));
 
255
        config->low = 0;
 
256
        config->high = -1;
 
257
        view->config = config;
 
258
}
 
259
 
 
260
void dd_close_config(ddview_t *view)
 
261
{
 
262
        int                     i;
 
263
        config_t        *config;
 
264
 
 
265
        config = view->config;
 
266
        for (i = 0; i <= config->high - config->low; i++) {
 
267
                agfree(view->layout, config->r[i]->v);
 
268
                agfree(view->layout, config->r[i]);
 
269
        }
 
270
        agfree(view->layout, config->r);
 
271
        agfree(view->layout, config);
 
272
}
 
273
 
 
274
Agnode_t *dd_vnode(ddview_t *view, int rank, double xpos)
 
275
{
 
276
        Agnode_t        *rv;
 
277
 
 
278
        rv = dd_open_node(view, NILnode);
 
279
        dd_install_at_pos(view,rv,rank,xpos);
 
280
        return rv;
 
281
}