← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dotneato/dotgen/class2.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/class2.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
/* classify edges for mincross/nodepos/splines, using given ranks */
 
13
 
 
14
#include "dot.h"
 
15
 
 
16
#ifdef DMALLOC
 
17
#include "dmalloc.h"
 
18
#endif
 
19
 
 
20
void class2(graph_t* g)
 
21
{
 
22
        int             c;
 
23
        node_t  *n,*t,*h;
 
24
        edge_t  *e,*prev,*opp;
 
25
 
 
26
        g->u.nlist = NULL;
 
27
 
 
28
        g->u.n_nodes = 0;       /* new */
 
29
 
 
30
        mark_clusters(g);
 
31
        for (c = 1; c <= g->u.n_cluster; c++)
 
32
                build_skeleton(g,g->u.clust[c]);
 
33
        for (n = agfstnode(g); n; n = agnxtnode(g,n))
 
34
                for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
 
35
                        if (e->head->u.weight_class <= 2) e->head->u.weight_class++;
 
36
                        if (e->tail->u.weight_class <= 2) e->tail->u.weight_class++;
 
37
        }
 
38
 
 
39
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
40
                if ((n->u.clust == NULL) && (n == UF_find(n))) {fast_node(g,n); g->u.n_nodes++;}
 
41
                prev = NULL;
 
42
                for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
 
43
 
 
44
                                /* already processed */
 
45
                        if (e->u.to_virt) continue;
 
46
 
 
47
                                /* edges involving sub-clusters of g */
 
48
                        if (is_cluster_edge(e)) {
 
49
                                /* following is new cluster multi-edge code */
 
50
                                if (mergeable(prev,e)) {
 
51
                                        if (prev->u.to_virt) { 
 
52
                                                merge_chain(g,e,prev->u.to_virt,FALSE);
 
53
                                                other_edge(e);
 
54
                                        }
 
55
                                        else if (e->tail->u.rank == e->head->u.rank) {
 
56
                                                merge_oneway(e,prev);
 
57
                                                other_edge(e);
 
58
                                        }
 
59
                                        /* else is an intra-cluster edge */
 
60
                                        continue;
 
61
                                }
 
62
                                interclrep(g,e);
 
63
                                prev = e;
 
64
                                continue;
 
65
                        }
 
66
                                /* merge multi-edges */
 
67
                        if (prev && (e->tail == prev->tail) && (e->head == prev->head)) {
 
68
                                if (e->tail->u.rank == e->head->u.rank) {
 
69
                                        merge_oneway(e,prev);
 
70
                                        other_edge(e);
 
71
                                        continue;
 
72
                                }
 
73
                                if ((e->u.label == NULL) && (prev->u.label == NULL) && ports_eq(e,prev)) {
 
74
                                        if (Concentrate) 
 
75
                                                e->u.edge_type = IGNORED;
 
76
                                        else{
 
77
                                        merge_chain(g,e,prev->u.to_virt,TRUE);
 
78
                                        other_edge(e);
 
79
                                        }
 
80
                                        continue;
 
81
                                }
 
82
                                /* parallel edges with different labels fall through here */
 
83
                        }
 
84
 
 
85
                                /* self edges */
 
86
                        if (e->tail == e->head) {
 
87
                                other_edge(e);
 
88
                                prev = e;
 
89
                                continue;
 
90
                        }
 
91
 
 
92
                        t = UF_find(e->tail);
 
93
                        h = UF_find(e->head);
 
94
 
 
95
                                /* non-leader leaf nodes */
 
96
                        if ((e->tail != t) || (e->head != h)) {
 
97
                                        /* ### need to merge stuff */
 
98
                                continue;       
 
99
                        }
 
100
 
 
101
 
 
102
                                /* flat edges */
 
103
                        if (e->tail->u.rank == e->head->u.rank) {
 
104
                                flat_edge(g,e);
 
105
                                prev = e;
 
106
                                continue;
 
107
                        }
 
108
 
 
109
                                /* forward edges */
 
110
                        if (e->head->u.rank > e->tail->u.rank) {
 
111
                                make_chain(g,e->tail,e->head,e);
 
112
                                prev = e;
 
113
                                continue;
 
114
                        }
 
115
 
 
116
                                /* backward edges */
 
117
                        else {
 
118
                                /*other_edge(e);*/
 
119
                                if ((opp = agfindedge(g,e->head,e->tail))) {
 
120
                                        /* shadows a forward edge */
 
121
                                        if (opp->u.to_virt == NULL)
 
122
                                                make_chain(g,opp->tail,opp->head,opp);
 
123
                                        if ((e->u.label == NULL) && (opp->u.label == NULL) && ports_eq(e,opp)) {
 
124
                                                if (Concentrate) {
 
125
                                                        e->u.edge_type = IGNORED;
 
126
                                                        opp->u.conc_opp_flag = TRUE;
 
127
                                                }
 
128
                                                else{   /* see above.  this is getting out of hand */
 
129
                                                other_edge(e);
 
130
                                                merge_chain(g,e,opp->u.to_virt,TRUE);
 
131
                                                }
 
132
                                                continue;
 
133
                                        }
 
134
                                }
 
135
                                make_chain(g,e->head,e->tail,e);
 
136
                                prev = e;
 
137
                        }
 
138
                }
 
139
        }
 
140
        /* since decompose() is not called on subgraphs */
 
141
        if (g != g->root) {
 
142
                g->u.comp.list = ALLOC(1,g->u.comp.list,node_t*);
 
143
                g->u.comp.list[0] = g->u.nlist;
 
144
        }
 
145
}
 
146
 
 
147
node_t  *
 
148
label_vnode(graph_t* g, edge_t* orig)
 
149
{
 
150
        node_t          *v;
 
151
        pointf          dimen;
 
152
 
 
153
        dimen = orig->u.label->dimen;
 
154
        v = virtual_node(g);
 
155
        v->u.label = orig->u.label;
 
156
        v->u.lw = v->graph->u.nodesep;
 
157
        if (!orig->u.label_ontop) {
 
158
                if (g->u.left_to_right) {
 
159
                        v->u.ht = POINTS(dimen.x); v->u.rw = POINTS(dimen.y);
 
160
                }
 
161
                else {
 
162
                        v->u.ht = POINTS(dimen.y); v->u.rw = POINTS(dimen.x);
 
163
                }
 
164
        }
 
165
        return v;
 
166
}
 
167
 
 
168
node_t  *
 
169
plain_vnode(graph_t* g, edge_t* orig)
 
170
{
 
171
        node_t          *v;
 
172
        orig = orig;
 
173
        v = virtual_node(g);
 
174
        incr_width(g,v);
 
175
        return v;
 
176
}
 
177
 
 
178
void incr_width(graph_t* g, node_t* v)
 
179
{
 
180
        int width = g->u.nodesep / 2;
 
181
        v->u.lw += width;
 
182
        v->u.rw += width;
 
183
}
 
184
 
 
185
void make_chain(graph_t *g, node_t *from, node_t *to, edge_t *orig)
 
186
{
 
187
        int             r,label_rank;
 
188
        node_t  *u,*v;
 
189
        edge_t  *e;
 
190
 
 
191
        u = from;
 
192
        if (orig->u.label) label_rank = (from->u.rank + to->u.rank) / 2;
 
193
        else label_rank = -1;
 
194
        assert(orig->u.to_virt == NULL);
 
195
        for (r = from->u.rank + 1; r <= to->u.rank; r++) {
 
196
                if (r < to->u.rank) {
 
197
                        if (r == label_rank) v = label_vnode(g,orig);
 
198
                        else v = plain_vnode(g,orig);
 
199
                        v->u.rank = r;
 
200
                }
 
201
                else v = to;
 
202
                e = virtual_edge(u,v,orig);
 
203
                virtual_weight(e);
 
204
                u = v;
 
205
        }
 
206
        assert(orig->u.to_virt != NULL);
 
207
}
 
208
 
 
209
void merge_chain(graph_t *g, edge_t     *e, edge_t *f, int flag)
 
210
{
 
211
        edge_t          *rep;
 
212
        int                     lastrank = MAX(e->tail->u.rank,e->head->u.rank);
 
213
 
 
214
        assert(e->u.to_virt == NULL);
 
215
        e->u.to_virt = f;
 
216
        rep = f;
 
217
        do {
 
218
                        /* interclust multi-edges are not counted now */
 
219
                if (flag) rep->u.count += e->u.count;
 
220
                rep->u.xpenalty += e->u.xpenalty;
 
221
                rep->u.weight += e->u.weight;
 
222
                if (rep->head->u.rank == lastrank) break;
 
223
                incr_width(g,rep->head);
 
224
                rep = rep->head->u.out.list[0];
 
225
        } while (rep);
 
226
}
 
227
 
 
228
node_t  *
 
229
leader_of(graph_t* g, node_t* v)
 
230
{
 
231
        graph_t *clust;
 
232
        node_t  *rv;
 
233
 
 
234
        if (v->u.ranktype != CLUSTER) {
 
235
                /*assert(v == UF_find(v));  could be leaf, so comment out */
 
236
                rv = UF_find(v);
 
237
        }
 
238
        else {
 
239
                clust = v->u.clust;
 
240
                rv = clust->u.rankleader[v->u.rank];
 
241
        }
 
242
        return rv;
 
243
}
 
244
 
 
245
void interclrep(graph_t* g, edge_t* e)
 
246
{
 
247
        node_t          *t,*h;
 
248
        edge_t          *ve;
 
249
 
 
250
        t = leader_of(g,e->tail);
 
251
        h = leader_of(g,e->head);
 
252
        if (t->u.rank > h->u.rank) {node_t *t0 = t; t = h; h = t0;}
 
253
        if (t->u.clust != h->u.clust) {
 
254
                if ((ve = find_fast_edge(t,h))) {
 
255
                        merge_chain(g,e,ve,TRUE);
 
256
                        return;
 
257
                }
 
258
                if (t->u.rank == h->u.rank) return;
 
259
                make_chain(g,t,h,e);
 
260
 
 
261
                /* mark as cluster edge */
 
262
                for (ve = e->u.to_virt; ve && (ve->head->u.rank <= h->u.rank);
 
263
                        ve = ve->head->u.out.list[0]) ve->u.edge_type = CLUSTER_EDGE;
 
264
        }
 
265
        /* else ignore intra-cluster edges at this point */
 
266
}
 
267
 
 
268
int is_cluster_edge(edge_t* e)
 
269
{
 
270
        return ((e->tail->u.ranktype==CLUSTER) || (e->head->u.ranktype==CLUSTER));
 
271
}
 
272
 
 
273
int mergeable(edge_t *e, edge_t *f)
 
274
{
 
275
        if (e && f && (e->tail == f->tail) && (e->head == f->head) &&
 
276
                (e->u.label == f->u.label) && ports_eq(e,f))
 
277
                        return TRUE;
 
278
        return FALSE;
 
279
}