7
/* maintains ranked graph configurations */
9
rank_t *dd_rankd(ddview_t *view, int absrank)
11
if ((absrank < view->config->low) || (absrank > view->config->high))
13
return view->config->r[absrank - view->config->low];
16
Agnode_t *dd_relnode(ddview_t *view, Agnode_t *n, int offset)
22
pos = dd_order(n) + offset;
23
if (pos < 0) return NILnode;
25
rd = dd_rankd(view,r);
26
if (pos >= rd->n) return NILnode;
30
Agnode_t *dd_right(ddview_t *view, Agnode_t *n)
32
return dd_relnode(view,n,1);
35
Agnode_t *dd_left(ddview_t *view, Agnode_t *n)
37
return dd_relnode(view,n,-1);
40
Agnode_t *dd_rightmost(ddview_t *view, int r)
44
rd = dd_rankd(view,r);
45
if ((rd == NILrank) || (rd->n == 0))
47
return rd->v[rd->n - 1];
50
Agnode_t *dd_leftmost(ddview_t *view, int r)
54
rd = dd_rankd(view,r);
55
if ((rd == NILrank) || (rd->n == 0))
60
static void extend_config(ddview_t *view, int low, int high)
62
int i,osize,nsize,o_nbytes,n_nbytes;
66
config = view->config;
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]);
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));
81
for (i = osize; i < nsize; i++)
82
list[i] = agalloc(view->layout,sizeof(rank_t));
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));
96
rank_t *dd_extendrank(ddview_t *view, int r)
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));
105
extend_config(view,r,r);
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]));
114
void dd_install_at_right(ddview_t *view, Agnode_t *n, int r)
121
right = dd_rightmost(view,r);
122
if (right) x = dd_pos(right).x + dd_uv_sep(view,right,n);
124
rd = dd_extendrank(view,r);
127
dd_node(n)->rank = r;
128
dd_node(n)->order = slot;
130
dd_set_config_flag(n,TRUE);
131
dd_set_ycoord(view,n);
134
void dd_install_at_pos(ddview_t *view, Agnode_t *n, int r, double x)
136
Agnode_t *ln,*rn,*mv;
142
/* find where incoming node belongs */
144
for (rn = dd_leftmost(view,r); rn; rn = dd_right(view,rn)) {
145
if (x <= dd_pos(rn).x) break;
149
if (ln) slot = dd_order(ln) + 1;
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);
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);
167
void dd_exchange(ddview_t *view, Agnode_t *u, Agnode_t *v)
172
Agnode_t *cn_u, *cn_v; /* constraint vars */
173
Agedge_t *ce; /* possible LR constraint edge */
175
assert(dd_node_in_config(u));
176
assert(dd_node_in_config(v));
177
assert(dd_rank(u) == dd_rank(v));
179
rd = dd_rankd(view,dd_rank(u));
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);
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);
197
void dd_delete_constraint(ddview_t *view, Agnode_t *ln, int sys)
203
if ((c_var = nd->con[sys].n)) {
204
agdelete(view->con[sys].g,c_var);
205
nd->con[sys].n = NILnode;
207
if ((c_var = nd->con[sys].stab)) {
208
agdelete(view->con[sys].g,c_var);
209
nd->con[sys].stab = NILnode;
214
void dd_rank_delete(ddview_t *view, Agnode_t *n)
221
for (e = agfstedge(n); e; e = agnxtedge(e,n)) {
224
agdelete(view->con[XCON].g, cn);
225
dd_edge(e)->cn = NILnode;
228
dd_delete_constraint(view, n, XCON);
229
dd_invalidate_adj_mvals(n);
230
rd = dd_rankd(view,dd_rank(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);
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);
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;}
250
void dd_open_config(ddview_t *view)
254
config = agalloc(view->layout,sizeof(config_t));
257
view->config = config;
260
void dd_close_config(ddview_t *view)
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]);
270
agfree(view->layout, config->r);
271
agfree(view->layout, config);
274
Agnode_t *dd_vnode(ddview_t *view, int rank, double xpos)
278
rv = dd_open_node(view, NILnode);
279
dd_install_at_pos(view,rv,rank,xpos);