← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dotneato/dotgen/conc.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/conc.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
 *      build edge_t concentrators for parallel edges with a common endpoint
 
14
 */
 
15
 
 
16
#include        "dot.h"
 
17
 
 
18
#ifdef DMALLOC
 
19
#include "dmalloc.h"
 
20
#endif
 
21
 
 
22
#define         UP              0
 
23
#define         DOWN    1
 
24
 
 
25
static boolean
 
26
samedir(edge_t *e,edge_t *f)
 
27
{
 
28
        edge_t  *e0,*f0;
 
29
 
 
30
        for (e0 = e; e0->u.edge_type != NORMAL; e0 = e0->u.to_orig);
 
31
        for (f0 = f; f0->u.edge_type != NORMAL; f0 = f0->u.to_orig);
 
32
        return ((f0->tail->u.rank - f0->head->u.rank)
 
33
                *(e0->tail->u.rank - e0->head->u.rank) > 0);
 
34
}
 
35
 
 
36
boolean
 
37
downcandidate(node_t* v)
 
38
{
 
39
        return ((v->u.node_type == VIRTUAL) && (v->u.in.size == 1) && (v->u.out.size == 1) &&(v->u.label == NULL));
 
40
}
 
41
 
 
42
boolean
 
43
bothdowncandidates(node_t *u, node_t *v)
 
44
{
 
45
        edge_t  *e,*f;
 
46
        e = u->u.in.list[0];
 
47
        f = v->u.in.list[0];
 
48
        if (downcandidate(v) && (e->tail == f->tail)) {
 
49
                return samedir(e,f) && (portcmp(e->u.tail_port,f->u.tail_port)==0);
 
50
        }
 
51
        return FALSE;
 
52
}
 
53
 
 
54
boolean
 
55
upcandidate(node_t* v)
 
56
{
 
57
        return ((v->u.node_type == VIRTUAL) && (v->u.out.size == 1) && (v->u.in.size == 1) && (v->u.label == NULL));
 
58
}
 
59
 
 
60
boolean
 
61
bothupcandidates(node_t *u, node_t *v)
 
62
{
 
63
        edge_t  *e,*f;
 
64
        e = u->u.out.list[0];
 
65
        f = v->u.out.list[0];
 
66
        if (upcandidate(v) && (e->head == f->head)) {
 
67
                return samedir(e,f) && (portcmp(e->u.head_port,f->u.head_port)==0);
 
68
        }
 
69
        return FALSE;
 
70
}
 
71
 
 
72
void mergevirtual(graph_t *g, int r, int lpos, int rpos, int dir)
 
73
{
 
74
        int             i,k;
 
75
        node_t  *left,*right;
 
76
        edge_t  *e,*f,*e0;
 
77
 
 
78
        left = g->u.rank[r].v[lpos];
 
79
        /* merge all right nodes into the leftmost one */
 
80
        for (i = lpos + 1; i <= rpos; i++) {
 
81
                right = g->u.rank[r].v[i];
 
82
                if (dir == DOWN) {
 
83
                        while ((e = right->u.out.list[0])) {
 
84
                                for (k = 0; (f = left->u.out.list[k]); k++)
 
85
                                        if (f->head == e->head) break;
 
86
                                if (f == NULL) f = virtual_edge(left,e->head,e);
 
87
                                while ((e0 = right->u.in.list[0])) {
 
88
                                        merge_oneway(e0,f);
 
89
                                        /*f->u.weight += e0->u.weight;*/
 
90
                                        delete_fast_edge(e0);
 
91
                                }
 
92
                                delete_fast_edge(e);
 
93
                        }
 
94
                }
 
95
                else {
 
96
                        while ((e = right->u.in.list[0])) {
 
97
                                for (k = 0; (f = left->u.in.list[k]); k++)
 
98
                                        if (f->tail == e->tail) break;
 
99
                                if (f == NULL) f = virtual_edge(e->tail,left,e);
 
100
                                while ((e0 = right->u.out.list[0])) {
 
101
                                        merge_oneway(e0,f);
 
102
                                        delete_fast_edge(e0);
 
103
                                }
 
104
                                delete_fast_edge(e);
 
105
                        }
 
106
                }
 
107
                assert(right->u.in.size + right->u.out.size == 0);
 
108
                delete_fast_node(g,right);
 
109
        }
 
110
        k = lpos + 1;
 
111
        i = rpos + 1;
 
112
        while (i < g->u.rank[r].n) {
 
113
                node_t  *n;
 
114
                n = g->u.rank[r].v[k] = g->u.rank[r].v[i];
 
115
                n->u.order = k;
 
116
                k++; i++;
 
117
        }
 
118
        g->u.rank[r].n = k;
 
119
        g->u.rank[r].v[k] = NULL;
 
120
}
 
121
 
 
122
void dot_concentrate(graph_t* g)
 
123
{
 
124
        int             c,r,leftpos,rightpos;
 
125
        node_t  *left,*right;
 
126
 
 
127
        if (g->u.maxrank - g->u.minrank <= 1) return;
 
128
        /* this is the downward looking pass. r is a candidate rank. */
 
129
        for (r = 1; g->u.rank[r+1].n; r++) {
 
130
                for (leftpos = 0; leftpos < g->u.rank[r].n; leftpos++) {
 
131
                        left = g->u.rank[r].v[leftpos];
 
132
                        if (downcandidate(left) == FALSE) continue;
 
133
                        for (rightpos = leftpos + 1; rightpos < g->u.rank[r].n; rightpos++) {
 
134
                                right = g->u.rank[r].v[rightpos];
 
135
                                if (bothdowncandidates(left,right) == FALSE) break;
 
136
                        }
 
137
                        if (rightpos - leftpos > 1)
 
138
                                mergevirtual(g,r,leftpos,rightpos-1,DOWN);
 
139
                }
 
140
        }
 
141
        /* this is the corresponding upward pass */
 
142
        while (r > 0) {
 
143
                for (leftpos = 0; leftpos < g->u.rank[r].n; leftpos++) {
 
144
                        left = g->u.rank[r].v[leftpos];
 
145
                        if (upcandidate(left) == FALSE) continue;
 
146
                        for (rightpos = leftpos + 1; rightpos < g->u.rank[r].n; rightpos++) {
 
147
                                right = g->u.rank[r].v[rightpos];
 
148
                                if (bothupcandidates(left,right) == FALSE) break;
 
149
                        }
 
150
                        if (rightpos - leftpos > 1)
 
151
                                mergevirtual(g,r,leftpos,rightpos-1,UP);
 
152
                }
 
153
                r--;
 
154
        }
 
155
        for (c = 1; c <= g->u.n_cluster; c++)
 
156
                rebuild_vlists(g->u.clust[c]);
 
157
}
 
158
 
 
159
void infuse(graph_t* g, node_t* n)
 
160
{
 
161
        node_t  *lead;
 
162
 
 
163
        lead = g->u.rankleader[n->u.rank];
 
164
        if ((lead == NULL) || (lead->u.order > n->u.order))
 
165
                g->u.rankleader[n->u.rank] = n;
 
166
}
 
167
 
 
168
void rebuild_vlists(graph_t* g)
 
169
{
 
170
        int             c,i,r,maxi;
 
171
        node_t  *n,*lead;
 
172
        edge_t  *e,*rep;
 
173
 
 
174
        for (r = g->u.minrank; r <= g->u.maxrank; r++)
 
175
                g->u.rankleader[r] = NULL;
 
176
 
 
177
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
178
                infuse(g,n);
 
179
                for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
 
180
                        for (rep = e; rep->u.to_virt; rep = rep->u.to_virt);
 
181
                        while (rep->head->u.rank < e->head->u.rank) {
 
182
                                infuse(g,rep->head);
 
183
                                rep = rep->head->u.out.list[0];
 
184
                        }
 
185
                }
 
186
        }
 
187
 
 
188
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
189
                lead = g->u.rankleader[r];
 
190
                if(g->root->u.rank[r].v[lead->u.order] != lead)
 
191
                        abort();
 
192
                g->u.rank[r].v = g->root->u.rank[r].v + g->u.rankleader[r]->u.order;
 
193
                maxi = -1;
 
194
                for (i = 0; i < g->u.rank[r].n; i++) {
 
195
                        if ((n = g->u.rank[r].v[i]) == NULL) break;
 
196
                        if (n->u.node_type == NORMAL) {
 
197
                                if (agcontains(g,n)) maxi = i;
 
198
                                else break;
 
199
                        }
 
200
                        else {
 
201
                                edge_t  *e;
 
202
                                for (e = n->u.in.list[0]; e && e->u.to_orig; e = e->u.to_orig);
 
203
                                if (e && (agcontains(g,e->tail)) && agcontains(g,e->head))
 
204
                                        maxi = i;
 
205
                        }
 
206
                }
 
207
                if (maxi == -1)
 
208
                        fprintf(stderr,"warning: degenerate concentrated rank %s,%d\n",g->name,r);
 
209
                g->u.rank[r].n = maxi + 1;
 
210
        }
 
211
 
 
212
        for (c = 1; c <= g->u.n_cluster; c++)
 
213
                rebuild_vlists(g->u.clust[c]);
 
214
}