← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dotneato/dotgen/fastgr.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/fastgr.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
#include "dot.h"                  
 
13
 
 
14
#ifdef DMALLOC
 
15
#include "dmalloc.h"
 
16
#endif
 
17
 
 
18
/*
 
19
 * operations on the fast internal graph.
 
20
 */
 
21
 
 
22
static edge_t* ffe(node_t *u, elist uL, node_t *v, elist vL)
 
23
{
 
24
        int             i;
 
25
        edge_t  *e;
 
26
 
 
27
        if (uL.size < vL.size) {
 
28
                for (i = 0; (e = uL.list[i]); i++)
 
29
                        if (e->head == v) break;
 
30
        }
 
31
        else {
 
32
                for (i = 0; (e = vL.list[i]); i++)
 
33
                        if (e->tail == u) break;
 
34
        }
 
35
        return e;
 
36
}
 
37
 
 
38
edge_t* find_fast_edge(node_t *u,node_t *v)
 
39
{
 
40
        return ffe(u,u->u.out,v,v->u.in);
 
41
}
 
42
 
 
43
node_t* find_fast_node(graph_t *g, node_t *n)
 
44
{
 
45
        node_t          *v;
 
46
        for (v = g->u.nlist; v; v = v->u.next)
 
47
                if (v == n) break;
 
48
        return v;
 
49
}
 
50
 
 
51
edge_t* find_flat_edge(node_t *u, node_t *v)
 
52
{
 
53
        return ffe(u,u->u.flat_out,v,v->u.flat_in);
 
54
}
 
55
 
 
56
/* safe_list_append - append e to list L only if e not already a member */
 
57
void safe_list_append(edge_t *e, elist *L)
 
58
{
 
59
        int             i;
 
60
 
 
61
        for (i = 0; i < L->size; i++) if (e == L->list[i]) return;
 
62
        elist_append(e,(*L));
 
63
}
 
64
 
 
65
edge_t*
 
66
fast_edge(edge_t *e)
 
67
{
 
68
#ifdef DEBUG
 
69
        int             i;
 
70
        edge_t  *f;
 
71
        for (i = 0; (f = e->tail->u.out.list[i]); i++) {
 
72
                if (e == f) {fprintf(stderr,"duplicate fast edge\n"); return;}
 
73
                assert (e->head != f->head);
 
74
        }
 
75
        for (i = 0; (f = e->head->u.in.list[i]); i++) {
 
76
                if (e == f) {fprintf(stderr,"duplicate fast edge\n"); return;}
 
77
                assert (e->tail != f->tail);
 
78
        }
 
79
#endif
 
80
        elist_append(e,e->tail->u.out);
 
81
        elist_append(e,e->head->u.in);
 
82
        return e;
 
83
}
 
84
 
 
85
/* zapinlist - remove e from list and fill hole with last member of list */
 
86
void zapinlist(elist *L, edge_t *e)
 
87
{
 
88
        int     i;
 
89
 
 
90
        for (i = 0; i < L->size; i++) {
 
91
                if (L->list[i] == e) {
 
92
                        L->size--;
 
93
                        L->list[i] = L->list[L->size];
 
94
                        L->list[L->size] = NULL;
 
95
                        break;
 
96
                }
 
97
        }
 
98
}
 
99
 
 
100
/* disconnects e from graph */
 
101
void delete_fast_edge(edge_t *e)
 
102
{
 
103
        assert(e != NULL);
 
104
        zapinlist(&(e->tail->u.out),e);
 
105
        zapinlist(&(e->head->u.in),e);
 
106
}
 
107
 
 
108
void safe_delete_fast_edge(edge_t *e)
 
109
{
 
110
        int             i;
 
111
        edge_t  *f;
 
112
 
 
113
        assert(e != NULL);
 
114
        for (i = 0; (f = e->tail->u.out.list[i]); i++)
 
115
                if (f == e) zapinlist(&(e->tail->u.out),e);
 
116
        for (i = 0; (f = e->head->u.in.list[i]); i++)
 
117
                if (f == e) zapinlist(&(e->head->u.in),e);
 
118
}
 
119
 
 
120
void other_edge(edge_t *e)
 
121
{
 
122
        elist_append(e,e->tail->u.other);
 
123
}
 
124
 
 
125
void safe_other_edge(edge_t *e)
 
126
{
 
127
        safe_list_append(e,&(e->tail->u.other));
 
128
}
 
129
 
 
130
void delete_other_edge(edge_t *e)
 
131
{
 
132
        assert(e != NULL);
 
133
        zapinlist(&(e->tail->u.other),e);
 
134
}
 
135
 
 
136
/* orig might be an input edge, reverse of an input edge, or virtual edge */
 
137
edge_t*
 
138
new_virtual_edge(node_t *u, node_t *v, edge_t *orig)
 
139
{
 
140
        edge_t          *e;
 
141
 
 
142
        e = NEW(edge_t);
 
143
        e->tail = u;
 
144
        e->head = v;
 
145
        e->u.edge_type = VIRTUAL;
 
146
 
 
147
        if (orig) {
 
148
                e->u.count = orig->u.count;
 
149
                e->u.xpenalty = orig->u.xpenalty;
 
150
                e->u.weight = orig->u.weight;
 
151
                e->u.minlen = orig->u.minlen;
 
152
                if (e->tail == orig->tail) e->u.tail_port = orig->u.tail_port;
 
153
                else if (e->tail == orig->head) e->u.tail_port = orig->u.head_port;
 
154
                if (e->head == orig->head) e->u.head_port = orig->u.head_port;
 
155
                else if (e->head == orig->tail) e->u.head_port = orig->u.tail_port;
 
156
 
 
157
                if (orig->u.to_virt == NULL) orig->u.to_virt = e;
 
158
                e->u.to_orig = orig;
 
159
        }
 
160
        else e->u.minlen = e->u.count = e->u.xpenalty = e->u.weight = 1;
 
161
        return e;
 
162
}
 
163
 
 
164
edge_t*
 
165
virtual_edge(node_t *u, node_t *v, edge_t *orig)
 
166
{
 
167
        return fast_edge(new_virtual_edge(u,v,orig));
 
168
}
 
169
 
 
170
void fast_node(graph_t *g, Agnode_t *n)
 
171
{
 
172
 
 
173
#ifdef DEBUG
 
174
        assert (find_fast_node(g,n) == NULL);
 
175
#endif
 
176
        n->u.next = g->u.nlist;
 
177
        if (n->u.next) n->u.next->u.prev = n;
 
178
        g->u.nlist = n;
 
179
        n->u.prev = NULL;
 
180
        assert (n != n->u.next);
 
181
}
 
182
 
 
183
void fast_nodeapp(node_t *u, node_t *v)
 
184
{
 
185
        assert (u != v);
 
186
        assert (v->u.next == NULL);
 
187
        v->u.next = u->u.next;
 
188
        if (u->u.next) u->u.next->u.prev = v;
 
189
        v->u.prev = u;
 
190
        u->u.next = v;
 
191
}
 
192
 
 
193
void delete_fast_node(graph_t *g, node_t *n)
 
194
{
 
195
        assert(find_fast_node(g,n));
 
196
        if (n->u.next) n->u.next->u.prev = n->u.prev;
 
197
        if (n->u.prev) n->u.prev->u.next = n->u.next;
 
198
        else g->u.nlist = n->u.next;
 
199
}
 
200
 
 
201
node_t* virtual_node(graph_t *g)
 
202
{
 
203
        node_t          *n;
 
204
 
 
205
        n = NEW(node_t);
 
206
        n->name = "virtual";
 
207
        n->graph = g;
 
208
        n->u.node_type = VIRTUAL;
 
209
        n->u.lw = n->u.rw = 1;
 
210
        n->u.ht = 1;
 
211
        n->u.UF_size = 1;
 
212
        alloc_elist(4,n->u.in);
 
213
        alloc_elist(4,n->u.out);
 
214
        fast_node(g,n);
 
215
        g->u.n_nodes++;
 
216
        return n;
 
217
}
 
218
 
 
219
void flat_edge(graph_t *g, edge_t *e)
 
220
{
 
221
        elist_append(e,e->tail->u.flat_out);
 
222
        elist_append(e,e->head->u.flat_in);
 
223
        g->root->u.has_flat_edges = g->u.has_flat_edges = TRUE;
 
224
}
 
225
 
 
226
void delete_flat_edge(edge_t *e)
 
227
{
 
228
        assert(e != NULL);
 
229
        zapinlist(&(e->tail->u.flat_out),e);
 
230
        zapinlist(&(e->head->u.flat_in),e);
 
231
}
 
232
 
 
233
#ifdef DEBUG
 
234
static char*
 
235
NAME(node_t *n)
 
236
{
 
237
        static char buf[20];
 
238
        if (n->u.node_type == NORMAL) return n->name;
 
239
        sprintf(buf,"V%x",n);
 
240
        return buf;
 
241
}
 
242
 
 
243
void fastgr(graph_t *g)
 
244
{
 
245
        int                     i,j;
 
246
        node_t          *n,*w;
 
247
        edge_t          *e,*f;
 
248
 
 
249
        for (n = g->u.nlist; n; n = n->u.next) {
 
250
                fprintf(stderr,"%s %d: (",NAME(n), n->u.rank);
 
251
                for (i = 0; e = n->u.out.list[i]; i++) {
 
252
                        fprintf(stderr," %s:%d",NAME(e->head),e->u.count);
 
253
                        w = e->head;
 
254
                        if (g == g->root) {
 
255
                                for (j = 0; f = w->u.in.list[j]; j++) if (e == f) break;
 
256
                                assert (f != NULL);
 
257
                        }
 
258
                }
 
259
                fprintf(stderr," ) (");
 
260
                for (i = 0; e = n->u.in.list[i]; i++) {
 
261
                        fprintf(stderr," %s:%d",NAME(e->tail),e->u.count);
 
262
                        w = e->tail;
 
263
                        if (g == g->root) {
 
264
                                for (j = 0; f = w->u.out.list[j]; j++) if (e == f) break;
 
265
                                assert (f != NULL);
 
266
                        }
 
267
                }
 
268
                fprintf(stderr," )\n");
 
269
        }
 
270
}
 
271
#endif
 
272
 
 
273
void merge_oneway(edge_t *e, edge_t *rep)
 
274
{
 
275
        if (rep == e->u.to_virt) {fprintf(stderr,"warning, merge_oneway glitch\n"); return;}
 
276
        assert(e->u.to_virt == NULL);
 
277
        e->u.to_virt = rep;
 
278
        basic_merge(e,rep);
 
279
}
 
280
 
 
281
void basic_merge(edge_t *e, edge_t *rep)
 
282
{
 
283
        if (rep->u.minlen < e->u.minlen)
 
284
                rep->u.minlen = e->u.minlen;
 
285
        while (rep) {
 
286
                rep->u.count += e->u.count;
 
287
                rep->u.xpenalty += e->u.xpenalty;
 
288
                rep->u.weight += e->u.weight;
 
289
                rep = rep->u.to_virt;
 
290
        }
 
291
}
 
292
 
 
293
static void unrep(edge_t *rep, edge_t *e)
 
294
{
 
295
        rep->u.count -= e->u.count;
 
296
        rep->u.xpenalty -= e->u.xpenalty;
 
297
        rep->u.weight -= e->u.weight;
 
298
}
 
299
 
 
300
void unmerge_oneway(edge_t *e)
 
301
{
 
302
        edge_t  *rep,*nextrep;
 
303
        for (rep = e->u.to_virt; rep; rep = nextrep) {
 
304
                unrep(rep,e);
 
305
                nextrep = rep->u.to_virt;
 
306
                if (rep->u.count == 0) safe_delete_fast_edge(rep);      /* free(rep)? */
 
307
 
 
308
                /* unmerge from a virtual edge chain */
 
309
                while ((rep->u.edge_type == VIRTUAL)
 
310
                && (rep->head->u.node_type == VIRTUAL)
 
311
                && (rep->head->u.out.size == 1)) {
 
312
                        rep = rep->head->u.out.list[0];
 
313
                        unrep(rep,e);
 
314
                }
 
315
        }
 
316
        e->u.to_virt = NULL;
 
317
}
 
318
 
 
319
int is_fast_node(graph_t *g, node_t *v)
 
320
{
 
321
        node_t          *n;
 
322
 
 
323
        for (n = g->u.nlist; n; n = n->u.next)
 
324
                if (v == n) return TRUE;
 
325
        return FALSE;
 
326
}