← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dotneato/dotgen/rank.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/rank.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
 * Rank the nodes of a directed graph, subject to user-defined
 
14
 * sets of nodes to be kept on the same, min, or max rank.
 
15
 * The temporary acyclic fast graph is constructed and ranked
 
16
 * by a network-simplex technique.  Then ranks are propagated
 
17
 * to non-leader nodes and temporary edges are deleted.
 
18
 * Leaf nodes and top-level clusters are left collapsed, though.
 
19
 * Assigns global minrank and maxrank of graph and all clusters.
 
20
 *
 
21
 * TODO: safety code.  must not be in two clusters at same level.
 
22
 *  must not be in same/min/max/rank and a cluster at the same time.
 
23
 *  watch out for interactions between leaves and clusters.
 
24
 */
 
25
 
 
26
#include        "dot.h"
 
27
 
 
28
#ifdef DMALLOC
 
29
#include "dmalloc.h"
 
30
#endif
 
31
 
 
32
void dot_rank(graph_t* g)
 
33
{
 
34
        edgelabel_ranks(g);
 
35
        collapse_sets(g);
 
36
        /*collapse_leaves(g);*/
 
37
        class1(g);
 
38
        minmax_edges(g);
 
39
        decompose(g,0);
 
40
        acyclic(g);
 
41
        rank1(g);
 
42
        expand_ranksets(g);
 
43
        cleanup1(g);
 
44
}
 
45
 
 
46
/* When there are edge labels, extra ranks are reserved here for the virtual
 
47
 * nodes of the labels.  This is done by doubling the input edge lengths.
 
48
 * The input rank separation is adjusted to compensate.
 
49
 */
 
50
void edgelabel_ranks(graph_t* g)
 
51
{
 
52
        node_t          *n;
 
53
        edge_t          *e;
 
54
 
 
55
        if (g->u.has_edge_labels) {
 
56
                for (n = agfstnode(g); n; n = agnxtnode(g,n))
 
57
                        for (e = agfstout(g,n); e; e = agnxtout(g,e))
 
58
                                e->u.minlen *= 2;
 
59
                g->u.ranksep = (g->u.ranksep  + 1) / 2;
 
60
        }
 
61
}
 
62
 
 
63
/* Run the network simplex algorithm on each component. */
 
64
void rank1(graph_t* g)
 
65
{
 
66
        int                     maxiter = MAXINT;
 
67
        int                     c;
 
68
        char            *s;
 
69
 
 
70
        if ((s = agget(g,"nslimit1")))
 
71
                maxiter = atof(s) * agnnodes(g);
 
72
        for (c = 0; c < g->u.comp.size; c++) {
 
73
                g->u.nlist = g->u.comp.list[c];
 
74
                rank(g,TRUE,maxiter);
 
75
        }
 
76
}
 
77
 
 
78
int is_cluster(graph_t* g)
 
79
{
 
80
        return (strncmp(g->name,"cluster",7) == 0);
 
81
}
 
82
 
 
83
int rank_set_class(graph_t* g)
 
84
{
 
85
        static char     *name[] = {"same","min","source","max","sink",NULL};
 
86
        static int      class[] = {SAMERANK,MINRANK,SOURCERANK,MAXRANK,SINKRANK,0};
 
87
        int             val;
 
88
 
 
89
        if (is_cluster(g)) return CLUSTER;
 
90
        val = maptoken(agget(g,"rank"),name,class);
 
91
        g->u.set_type = val;
 
92
        return val;
 
93
}
 
94
 
 
95
/* Execute union commands for "same rank" subgraphs and clusters. */
 
96
void collapse_sets(graph_t* g)
 
97
{
 
98
        int                     c;
 
99
        graph_t         *mg,*subg;
 
100
        node_t          *mn,*n;
 
101
        edge_t          *me;
 
102
 
 
103
        mg = g->meta_node->graph;
 
104
        for (me = agfstout(mg,g->meta_node); me; me = agnxtout(mg,me)) {
 
105
                mn = me->head;
 
106
                subg = agusergraph(mn);
 
107
 
 
108
                c = rank_set_class(subg);
 
109
                if (c) {
 
110
                        if ((c == CLUSTER) && CL_type == LOCAL) collapse_cluster(g,subg);
 
111
                        else collapse_rankset(g,subg,c);
 
112
                }
 
113
 
 
114
                /* mark nodes with ordered edges so their leaves are not collapsed */
 
115
                if (agget(subg,"ordering"))
 
116
                        for (n = agfstnode(subg); n; n = agnxtnode(subg,n)) n->u.order = 1;
 
117
        }
 
118
}
 
119
 
 
120
/* Merge the nodes of a min, max, or same rank set. */
 
121
void collapse_rankset(graph_t *g, graph_t *subg, int kind)
 
122
{
 
123
        node_t  *u,*v;
 
124
 
 
125
        u = v = agfstnode(subg);
 
126
        if (u) {
 
127
                u->u.ranktype = kind;
 
128
                while ((v = agnxtnode(subg,v))) {
 
129
                        UF_union(u,v);
 
130
                        v->u.ranktype = u->u.ranktype;
 
131
                }
 
132
                switch (kind) {
 
133
                case MINRANK: case SOURCERANK:
 
134
                        if (g->u.minset == NULL) g->u.minset = u;
 
135
                        else g->u.minset = UF_union(g->u.minset,u);
 
136
                        break;
 
137
                case MAXRANK: case SINKRANK:
 
138
                        if (g->u.maxset == NULL) g->u.maxset = u;
 
139
                        else g->u.maxset = UF_union(g->u.maxset,u);
 
140
                        break;
 
141
                }
 
142
                switch (kind) {
 
143
                        case SOURCERANK: g->u.minset->u.ranktype = kind; break;
 
144
                        case SINKRANK: g->u.maxset->u.ranktype = kind; break;
 
145
                }
 
146
        }
 
147
}
 
148
 
 
149
node_t* merge_leaves(graph_t *g, node_t *cur, node_t *new)
 
150
{
 
151
        node_t  *rv;
 
152
 
 
153
        if (cur == NULL) rv = new;
 
154
        else {
 
155
                rv = UF_union(cur,new);
 
156
                rv->u.ht = MAX(cur->u.ht,new->u.ht);
 
157
                rv->u.lw = cur->u.lw + new->u.lw + g->u.nodesep/2;
 
158
                rv->u.rw = cur->u.rw + new->u.rw + g->u.nodesep/2;
 
159
        }
 
160
        return rv;
 
161
}
 
162
 
 
163
void potential_leaf(graph_t* g, edge_t* e, node_t* leaf)
 
164
{
 
165
        node_t          *par;
 
166
 
 
167
        if ((e->u.tail_port.p.x) || (e->u.head_port.p.x)) return;
 
168
        if ((e->u.minlen != 1) || (e->tail->u.order > 0)) return;
 
169
        par = ((leaf != e->head)? e->head : e->tail);
 
170
        leaf->u.ranktype = LEAFSET;
 
171
        if (par == e->tail) par->u.outleaf = merge_leaves(g,par->u.outleaf,leaf);
 
172
        else par->u.inleaf = merge_leaves(g,par->u.inleaf,leaf);
 
173
}
 
174
 
 
175
void collapse_leaves(graph_t* g)
 
176
{
 
177
        node_t          *n;
 
178
        edge_t          *e;
 
179
 
 
180
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
181
 
 
182
                /* consider n as a potential leaf of some other node. */
 
183
                if ((n->u.ranktype != NOCMD) || (n->u.order)) continue;
 
184
                if (agfstout(g,n) == NULL) {
 
185
                        if ((e = agfstin(g,n)) && (agnxtin(g,e) == NULL)) {
 
186
                                potential_leaf(g,e,n);
 
187
                                continue;
 
188
                        }
 
189
                }
 
190
                if (agfstin(g,n) == NULL) {
 
191
                        if ((e = agfstout(g,n)) && (agnxtout(g,e) == NULL)) {
 
192
                                potential_leaf(g,e,n);
 
193
                                continue;
 
194
                        }
 
195
                }
 
196
        }
 
197
}
 
198
 
 
199
/* To ensure that min and max rank nodes always have the intended rank
 
200
 * assignment, reverse any incompatible edges.
 
201
 */
 
202
void minmax_edges(graph_t* g)
 
203
{
 
204
        node_t  *n;
 
205
        edge_t  *e;
 
206
        int             srclen,sinklen;
 
207
 
 
208
        srclen = sinklen = 0;
 
209
        if ((g->u.maxset == NULL) && (g->u.minset == NULL)) return;
 
210
        if ( g->u.minset != NULL ) g->u.minset = UF_find(g->u.minset);
 
211
        if ( g->u.maxset != NULL ) g->u.maxset = UF_find(g->u.maxset);
 
212
 
 
213
        if ((n = g->u.maxset)) {
 
214
                sinklen = (g->u.maxset->u.ranktype == SINKRANK);
 
215
                while ((e = n->u.out.list[0])) {
 
216
                        assert(e->head == UF_find(e->head));
 
217
                        reverse_edge(e);
 
218
                }
 
219
        }
 
220
        if ((n = g->u.minset)) {
 
221
                srclen = (g->u.minset->u.ranktype == SOURCERANK);
 
222
                while ((e = n->u.in.list[0])) {
 
223
                        assert(e->tail == UF_find(e->tail));
 
224
                        reverse_edge(e);
 
225
                }
 
226
        }
 
227
 
 
228
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
229
                if (n != UF_find(n)) continue;
 
230
                if ((n->u.out.size == 0) && g->u.maxset && (n != g->u.maxset))
 
231
                        virtual_edge(n,g->u.maxset,NULL)->u.minlen = sinklen;
 
232
                if ((n->u.in.size == 0) && g->u.minset && (n != g->u.minset))
 
233
                        virtual_edge(g->u.minset,n,NULL)->u.minlen = srclen;
 
234
        }
 
235
}
 
236
 
 
237
/*
 
238
 * A cluster is collapsed in three steps.
 
239
 * 1) The nodes of the cluster are ranked locally.
 
240
 * 2) The cluster is collapsed into one node on the least rank.
 
241
 * 3) In class1(), any inter-cluster edges are converted using
 
242
 *    the "virtual node + 2 edges" trick.
 
243
 */
 
244
void collapse_cluster(graph_t *g, graph_t *subg)
 
245
{
 
246
        node_induce(g,subg);
 
247
        if (agfstnode(subg) == NULL) return;
 
248
        make_new_cluster(g,subg);
 
249
        if (CL_type == LOCAL) {
 
250
                dot_rank(subg);
 
251
                cluster_leader(subg);
 
252
        }
 
253
        else scan_ranks(subg);
 
254
}
 
255
 
 
256
int
 
257
make_new_cluster(graph_t *g, graph_t *subg)
 
258
{
 
259
        int     cno;
 
260
        cno = ++(g->u.n_cluster);
 
261
        g->u.clust = ZALLOC(cno+1,g->u.clust,graph_t*,g->u.n_cluster);
 
262
        g->u.clust[cno] = subg;
 
263
        do_graph_label(subg);
 
264
        return cno;
 
265
}
 
266
 
 
267
void node_induce(graph_t *par, graph_t *g)
 
268
{
 
269
        node_t          *n,*nn;
 
270
        edge_t          *e;
 
271
        int                     i;
 
272
 
 
273
        /* enforce that a node is in at most one cluster at this level */
 
274
        for (n = agfstnode(g); n; n = nn) {
 
275
                nn = agnxtnode(g,n);
 
276
                if (n->u.ranktype) {agdelete(g,n); continue;}
 
277
                for (i = 1; i < par->u.n_cluster; i++)
 
278
                        if (agcontains(par->u.clust[i],n)) break;
 
279
                if (i < par->u.n_cluster) agdelete(g,n);
 
280
                n->u.clust = NULL;
 
281
        }
 
282
 
 
283
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
284
                for (e = agfstout(g->root,n); e; e = agnxtout(g->root,e)) {
 
285
                        if (agcontains(g,e->head)) aginsert(g,e);
 
286
                }
 
287
        }
 
288
}
 
289
 
 
290
void cluster_leader(graph_t* clust)
 
291
{
 
292
        node_t          *leader,*n;
 
293
        int                     maxrank = 0;
 
294
 
 
295
        /* find number of ranks and select a leader */
 
296
        leader = NULL;
 
297
        for (n = clust->u.nlist; n; n = n->u.next) {
 
298
                if ((n->u.rank == 0) && (n->u.node_type == NORMAL)) leader = n;
 
299
                if (maxrank < n->u.rank) maxrank = n->u.rank;
 
300
        }
 
301
        assert(leader != NULL);
 
302
        clust->u.leader = leader;
 
303
 
 
304
        for (n = agfstnode(clust); n; n = agnxtnode(clust,n)) {
 
305
                assert ((n->u.UF_size <= 1) || (n == leader));
 
306
                UF_union(n,leader);
 
307
                n->u.ranktype = CLUSTER;
 
308
        }
 
309
}
 
310
 
 
311
/* 
 
312
 * Assigns ranks of non-leader nodes.
 
313
 * Expands same, min, max rank sets.
 
314
 * Leaf sets and clusters remain merged.
 
315
 * Sets minrank and maxrank appropriately.
 
316
 */
 
317
void expand_ranksets(graph_t* g)
 
318
{
 
319
        int                     c;
 
320
        node_t          *n,*leader;
 
321
 
 
322
        if ((n = agfstnode(g))) {
 
323
                g->u.minrank = MAXSHORT;
 
324
                g->u.maxrank = -1;
 
325
                while (n) {
 
326
                        leader = UF_find(n);
 
327
                        /* The following works because n->u.rank == 0 if n is not in a
 
328
                         * cluster, and n->u.rank = the local rank offset if n is in
 
329
                         * a cluster. */
 
330
                        if (leader != n) n->u.rank += leader->u.rank;
 
331
 
 
332
                        if (g->u.maxrank < n->u.rank) g->u.maxrank = n->u.rank;
 
333
                        if (g->u.minrank > n->u.rank) g->u.minrank = n->u.rank;
 
334
 
 
335
                        if (n->u.ranktype && (n->u.ranktype != LEAFSET))
 
336
                                        UF_singleton(n);
 
337
                        n = agnxtnode(g,n);
 
338
                }
 
339
                if (g == g->root) {
 
340
                        if (CL_type == LOCAL) {
 
341
                                for (c = 1; c <= g->u.n_cluster; c++)
 
342
                                        set_minmax(g->u.clust[c]);
 
343
                        }
 
344
                        else {
 
345
                                find_clusters(g);
 
346
                        }
 
347
                }
 
348
        }
 
349
        else {
 
350
                g->u.minrank = g->u.maxrank = 0;
 
351
        }
 
352
}
 
353
 
 
354
void renewlist(elist* L)
 
355
{
 
356
        int             i;
 
357
        for (i = L->size; i >= 0; i--) L->list[i] = NULL;
 
358
        L->size = 0;
 
359
}
 
360
 
 
361
void cleanup1(graph_t* g)
 
362
{
 
363
        node_t          *n;
 
364
        edge_t          *e, *f;
 
365
        int                     c;
 
366
 
 
367
        for (c = 0; c < g->u.comp.size; c++) {
 
368
                g->u.nlist = g->u.comp.list[c];
 
369
                for (n = g->u.nlist; n; n = n->u.next) {
 
370
                        renewlist(&n->u.in);
 
371
                        renewlist(&n->u.out);
 
372
                        n->u.mark = FALSE;
 
373
                }
 
374
        }
 
375
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
376
                for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
 
377
                        f = e->u.to_virt;
 
378
                        if (f && (e == f->u.to_orig)) free(f);
 
379
                        e->u.to_virt = NULL;
 
380
                }
 
381
        }
 
382
        free(g->u.comp.list);
 
383
        g->u.comp.list = NULL;
 
384
        g->u.comp.size = 0;
 
385
}
 
386
 
 
387
void set_minmax(graph_t* g)
 
388
{
 
389
        int             c;
 
390
 
 
391
        g->u.minrank += g->u.leader->u.rank;
 
392
        g->u.maxrank += g->u.leader->u.rank;
 
393
        for (c = 1; c <= g->u.n_cluster; c++) set_minmax(g->u.clust[c]);
 
394
}
 
395
 
 
396
void scan_ranks(graph_t* g)
 
397
{
 
398
        node_t          *n,*leader=NULL;
 
399
        g->u.minrank = MAXSHORT;
 
400
        g->u.maxrank = -1;
 
401
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
402
                if (g->u.maxrank < n->u.rank) g->u.maxrank = n->u.rank;
 
403
                if (g->u.minrank > n->u.rank) g->u.minrank = n->u.rank;
 
404
                if (leader == NULL) leader = n;
 
405
                else { if (n->u.rank < leader->u.rank) leader = n; }
 
406
        }
 
407
        g->u.leader = leader;
 
408
}
 
409
 
 
410
void find_clusters(graph_t* g)
 
411
{
 
412
        graph_t         *mg,*subg;
 
413
        node_t          *mn;
 
414
        edge_t          *me;
 
415
 
 
416
        mg = g->meta_node->graph;
 
417
        for (me = agfstout(mg,g->meta_node); me; me = agnxtout(mg,me)) {
 
418
                mn = me->head;
 
419
                subg = agusergraph(mn);
 
420
 
 
421
                if (subg->u.set_type == CLUSTER) collapse_cluster(g,subg);
 
422
        }
 
423
}