← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dotneato/dotgen/ns.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/ns.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
 * Network Simplex Algorithm for Ranking Nodes of a DAG
 
14
 */
 
15
 
 
16
#include "dot.h"
 
17
 
 
18
#ifdef DMALLOC
 
19
#include "dmalloc.h"
 
20
#endif
 
21
 
 
22
static int init_graph(graph_t *);
 
23
 
 
24
#define LENGTH(e)               ((e)->head->u.rank - (e)->tail->u.rank)
 
25
#define SLACK(e)                (LENGTH(e) - (e)->u.minlen)
 
26
#define SEQ(a,b,c)              (((a) <= (b)) && ((b) <= (c)))
 
27
#define TREE_EDGE(e)    (e->u.tree_index >= 0)
 
28
 
 
29
static graph_t  *G;
 
30
static int              N_nodes,N_edges;
 
31
static int              Minrank,Maxrank;
 
32
static int              S_i;            /* search index for enter_edge */
 
33
static int              Search_size;
 
34
#define SEARCHSIZE 30
 
35
static nlist_t  Tree_node;
 
36
static elist    Tree_edge;
 
37
 
 
38
void add_tree_edge(edge_t* e)
 
39
{
 
40
        node_t  *n;
 
41
        if (TREE_EDGE(e)) abort();
 
42
        e->u.tree_index = Tree_edge.size;
 
43
        Tree_edge.list[Tree_edge.size++] = e;
 
44
        if (e->tail->u.mark == FALSE) Tree_node.list[Tree_node.size++] = e->tail;
 
45
        if (e->head->u.mark == FALSE) Tree_node.list[Tree_node.size++] = e->head;
 
46
        n = e->tail;
 
47
        n->u.mark = TRUE;
 
48
        n->u.tree_out.list[n->u.tree_out.size++] = e;
 
49
        n->u.tree_out.list[n->u.tree_out.size] = NULL;
 
50
        if (n->u.out.list[n->u.tree_out.size-1] == 0) abort();
 
51
        n = e->head;
 
52
        n->u.mark = TRUE;
 
53
        n->u.tree_in.list[n->u.tree_in.size++] = e;
 
54
        n->u.tree_in.list[n->u.tree_in.size] = NULL;
 
55
        if (n->u.in.list[n->u.tree_in.size-1] == 0) abort();
 
56
}
 
57
 
 
58
void exchange_tree_edges(edge_t *e,edge_t *f)
 
59
{
 
60
        int             i,j;
 
61
        node_t  *n;
 
62
 
 
63
        f->u.tree_index = e->u.tree_index;
 
64
        Tree_edge.list[e->u.tree_index] = f;
 
65
        e->u.tree_index = -1;
 
66
 
 
67
        n = e->tail;
 
68
        i = --(n->u.tree_out.size);
 
69
        for (j = 0; j <= i; j++) if (n->u.tree_out.list[j] == e) break;
 
70
        n->u.tree_out.list[j] = n->u.tree_out.list[i];
 
71
        n->u.tree_out.list[i] = NULL;
 
72
        n = e->head;
 
73
        i = --(n->u.tree_in.size);
 
74
        for (j = 0; j <= i; j++) if (n->u.tree_in.list[j] == e) break;
 
75
        n->u.tree_in.list[j] = n->u.tree_in.list[i];
 
76
        n->u.tree_in.list[i] = NULL;
 
77
 
 
78
        n = f->tail;
 
79
        n->u.tree_out.list[n->u.tree_out.size++] = f;
 
80
        n->u.tree_out.list[n->u.tree_out.size] = NULL;
 
81
        n = f->head;
 
82
        n->u.tree_in.list[n->u.tree_in.size++] = f;
 
83
        n->u.tree_in.list[n->u.tree_in.size] = NULL;
 
84
}
 
85
 
 
86
void init_rank(void)
 
87
{
 
88
        int                     i,ctr;
 
89
        queue           *Q;
 
90
        node_t          *v;
 
91
        edge_t          *e;
 
92
 
 
93
        Q = new_queue(N_nodes);
 
94
        ctr = 0;
 
95
 
 
96
        for (v = G->u.nlist; v; v = v->u.next) {
 
97
                if (v->u.priority == 0) enqueue(Q,v);
 
98
        }
 
99
 
 
100
        while ((v = dequeue(Q))) {
 
101
                v->u.rank = 0;
 
102
                ctr++;
 
103
                for (i = 0; (e = v->u.in.list[i]); i++)
 
104
                        v->u.rank = MAX(v->u.rank,e->tail->u.rank + e->u.minlen);
 
105
                for (i = 0; (e = v->u.out.list[i]); i++) {
 
106
                        if (--(e->head->u.priority) <= 0) enqueue(Q,e->head);
 
107
                }
 
108
        }
 
109
        if (ctr != N_nodes) {
 
110
                fprintf(stderr,"trouble in init_rank\n");
 
111
                for (v = G->u.nlist; v; v = v->u.next)
 
112
                        if (v->u.priority)
 
113
                                fprintf(stderr,"\t%s %d\n",v->name,v->u.priority);
 
114
        }
 
115
        free_queue(Q);
 
116
}
 
117
 
 
118
node_t *
 
119
incident(edge_t* e)
 
120
{
 
121
        if (e->tail->u.mark) {
 
122
                if (e->head->u.mark == FALSE)
 
123
                        return e->tail;
 
124
        }
 
125
        else {
 
126
                if (e->head->u.mark)
 
127
                        return e->head;
 
128
        }
 
129
        return NULL;
 
130
}
 
131
 
 
132
edge_t *
 
133
leave_edge (void)
 
134
{
 
135
        edge_t                  *f,*rv = NULL;
 
136
        int                             j,cnt = 0;
 
137
 
 
138
        j = S_i;
 
139
        while (S_i < Tree_edge.size) {
 
140
                if ((f = Tree_edge.list[S_i])->u.cutvalue < 0) {
 
141
                        if (rv) {
 
142
                                if (rv->u.cutvalue > f->u.cutvalue) rv = f;
 
143
                        }
 
144
                        else rv = Tree_edge.list[S_i];
 
145
                        if (++cnt >= Search_size) return rv;
 
146
                }
 
147
                S_i++;
 
148
        }
 
149
        if (j > 0) {
 
150
                S_i = 0;
 
151
                while (S_i < j) {
 
152
                        if ((f = Tree_edge.list[S_i])->u.cutvalue < 0) {
 
153
                                if (rv) {
 
154
                                        if (rv->u.cutvalue > f->u.cutvalue) rv = f;
 
155
                                }
 
156
                                else rv = Tree_edge.list[S_i];
 
157
                                if (++cnt >= Search_size) return rv;
 
158
                        }
 
159
                        S_i++;
 
160
                }
 
161
        }
 
162
        return rv;
 
163
}
 
164
 
 
165
static edge_t   *Enter;
 
166
static int              Low,Lim,Slack;
 
167
 
 
168
void dfs_enter_outedge(node_t* v)
 
169
{
 
170
        int             i,slack;
 
171
        edge_t  *e;
 
172
 
 
173
        for (i = 0; (e = v->u.out.list[i]); i++) {
 
174
                if (TREE_EDGE(e) == FALSE) {
 
175
                        if (!SEQ(Low,e->head->u.lim,Lim)) {
 
176
                                slack = SLACK(e);
 
177
                                if ((slack < Slack) || (Enter == NULL)) {
 
178
                                        Enter = e;
 
179
                                        Slack = slack;
 
180
                                }
 
181
                        }
 
182
                }
 
183
                else if (e->head->u.lim < v->u.lim) dfs_enter_outedge(e->head);
 
184
        }
 
185
        for (i = 0; (e = v->u.tree_in.list[i]) && (Slack > 0); i++)
 
186
                if (e->tail->u.lim < v->u.lim) dfs_enter_outedge(e->tail);
 
187
}
 
188
 
 
189
void dfs_enter_inedge(node_t* v)
 
190
{
 
191
        int             i,slack;
 
192
        edge_t  *e;
 
193
 
 
194
        for (i = 0; (e = v->u.in.list[i]); i++) {
 
195
                if (TREE_EDGE(e) == FALSE) {
 
196
                        if (!SEQ(Low,e->tail->u.lim,Lim)) {
 
197
                                slack = SLACK(e);
 
198
                                if ((slack < Slack) || (Enter == NULL)) {
 
199
                                        Enter = e;
 
200
                                        Slack = slack;
 
201
                                }
 
202
                        }
 
203
                }
 
204
                else if (e->tail->u.lim < v->u.lim) dfs_enter_inedge(e->tail);
 
205
        }
 
206
        for (i = 0; (e = v->u.tree_out.list[i]) && (Slack > 0); i++)
 
207
                if (e->head->u.lim < v->u.lim) dfs_enter_inedge(e->head);
 
208
}
 
209
 
 
210
edge_t *
 
211
enter_edge(edge_t* e)
 
212
{
 
213
        node_t  *v;
 
214
        int             outsearch;
 
215
 
 
216
        /* v is the down node */
 
217
        if (e->tail->u.lim < e->head->u.lim) {v = e->tail; outsearch = FALSE;}
 
218
        else {v = e->head;outsearch = TRUE;}
 
219
        Enter = NULL;
 
220
        Slack = MAXINT;
 
221
        Low = v->u.low;
 
222
        Lim = v->u.lim;
 
223
        if (outsearch) dfs_enter_outedge(v);
 
224
        else dfs_enter_inedge(v);
 
225
        return Enter;
 
226
}
 
227
 
 
228
int treesearch(node_t* v)
 
229
{
 
230
        int             i;
 
231
        edge_t  *e;
 
232
 
 
233
        for (i = 0; (e = v->u.out.list[i]); i++) {
 
234
                if ((e->head->u.mark == FALSE) && (SLACK(e) == 0)) {
 
235
                        add_tree_edge(e);
 
236
                        if ((Tree_edge.size == N_nodes-1) || treesearch(e->head)) return TRUE;
 
237
                }
 
238
        }
 
239
        for (i = 0; (e = v->u.in.list[i]); i++) {
 
240
                if ((e->tail->u.mark == FALSE) && (SLACK(e) == 0)) {
 
241
                        add_tree_edge(e);
 
242
                        if ((Tree_edge.size == N_nodes-1) || treesearch(e->tail)) return TRUE;
 
243
                }
 
244
        }
 
245
        return FALSE;
 
246
}
 
247
 
 
248
int
 
249
tight_tree(void)
 
250
{
 
251
        int             i;
 
252
        node_t  *n;
 
253
 
 
254
        for (n = G->u.nlist; n; n = n->u.next) {
 
255
                n->u.mark = FALSE;
 
256
                n->u.tree_in.list[0] = n->u.tree_out.list[0] = NULL;
 
257
                n->u.tree_in.size = n->u.tree_out.size = 0;
 
258
        }
 
259
        for (i = 0; i < Tree_edge.size; i++) Tree_edge.list[i]->u.tree_index = -1;
 
260
 
 
261
        Tree_node.size = Tree_edge.size = 0;
 
262
        for (n = G->u.nlist; n && (Tree_edge.size == 0); n = n->u.next) treesearch(n);
 
263
        return Tree_node.size;
 
264
}
 
265
 
 
266
void init_cutvalues(void)
 
267
{
 
268
        dfs_range(G->u.nlist,NULL,1);
 
269
        dfs_cutval(G->u.nlist,NULL);
 
270
}
 
271
 
 
272
void feasible_tree(void)
 
273
{
 
274
        int                     i,delta;
 
275
        node_t          *n;
 
276
        edge_t          *e,*f;
 
277
 
 
278
        if (N_nodes <= 1) return;
 
279
        while (tight_tree() < N_nodes) {
 
280
                e = NULL;
 
281
                for (n = G->u.nlist; n; n = n->u.next) {
 
282
                        for (i = 0; (f = n->u.out.list[i]); i++) {
 
283
                                if ((TREE_EDGE(f) == FALSE) && incident(f) && ((e == NULL)
 
284
                                        || (SLACK(f) < SLACK(e)))) e = f;
 
285
                        }
 
286
                }
 
287
                if (e) {
 
288
                        delta = SLACK(e);
 
289
                        if (delta) {
 
290
                                if (incident(e) == e->head) delta = -delta;
 
291
                                for (i = 0; i < Tree_node.size; i++)
 
292
                                        Tree_node.list[i]->u.rank += delta;
 
293
                        }
 
294
                }
 
295
                else {
 
296
#ifdef DEBUG
 
297
                        fprintf(stderr,"not in tight tree:\n");
 
298
                        for (n = G->u.nlist; n; n = n->u.next) {
 
299
                                for (i = 0; i < Tree_node.size; i++)
 
300
                                        if (Tree_node.list[i] == n) break;
 
301
                                if (i >= Tree_node.size) fprintf(stderr,"\t%s\n",n->name);
 
302
                        }
 
303
#endif
 
304
                        abort();
 
305
                }
 
306
        }
 
307
        init_cutvalues();
 
308
}
 
309
 
 
310
/* walk up from v to LCA(v,w), setting new cutvalues. */
 
311
node_t *
 
312
treeupdate(node_t *v, node_t *w, int cutvalue, int dir)
 
313
{
 
314
        edge_t  *e;
 
315
        int             d;
 
316
 
 
317
        while (!SEQ(v->u.low,w->u.lim,v->u.lim)) {
 
318
                e = v->u.par;
 
319
                if (v == e->tail) d = dir; else d = NOT(dir);
 
320
                if (d) e->u.cutvalue += cutvalue; else e->u.cutvalue -= cutvalue;
 
321
                if (e->tail->u.lim > e->head->u.lim) v = e->tail; else v = e->head;
 
322
        }
 
323
        return v;
 
324
}
 
325
 
 
326
void rerank(node_t* v, int delta)
 
327
{
 
328
        int             i;
 
329
        edge_t  *e;
 
330
 
 
331
        v->u.rank -= delta;
 
332
        for (i = 0; (e = v->u.tree_out.list[i]); i++) 
 
333
                if (e != v->u.par) rerank(e->head,delta);
 
334
        for (i = 0; (e = v->u.tree_in.list[i]); i++) 
 
335
                if (e != v->u.par) rerank(e->tail,delta);
 
336
}
 
337
 
 
338
/* e is the tree edge that is leaving and f is the nontree edge that
 
339
 * is entering.  compute new cut values, ranks, and exchange e and f.
 
340
 */
 
341
void update(edge_t *e, edge_t *f)
 
342
{
 
343
        int             cutvalue,delta;
 
344
        node_t  *lca;
 
345
 
 
346
        delta = SLACK(f);
 
347
        /* "for (v = in nodes in tail side of e) do v->u.rank -= delta;" */
 
348
        if (delta > 0) {
 
349
                int s;
 
350
                s = e->tail->u.tree_in.size + e->tail->u.tree_out.size;
 
351
                if (s == 1) rerank(e->tail,delta);
 
352
                else {
 
353
                        s = e->head->u.tree_in.size + e->head->u.tree_out.size;
 
354
                        if (s == 1) rerank(e->head,-delta);
 
355
                        else {
 
356
                                if (e->tail->u.lim < e->head->u.lim) rerank(e->tail,delta);
 
357
                                else rerank(e->head,-delta);
 
358
                        }
 
359
                }
 
360
        }
 
361
 
 
362
        cutvalue = e->u.cutvalue;
 
363
        lca = treeupdate(f->tail,f->head,cutvalue,1);
 
364
        if (treeupdate(f->head,f->tail,cutvalue,0) != lca) abort();
 
365
        f->u.cutvalue = -cutvalue;
 
366
        e->u.cutvalue = 0;
 
367
        exchange_tree_edges(e,f);
 
368
        dfs_range(lca,lca->u.par,lca->u.low);
 
369
}
 
370
 
 
371
void scan_result(void)
 
372
{
 
373
        node_t  *n;
 
374
 
 
375
        Minrank = MAXINT;
 
376
        Maxrank = -MAXINT;
 
377
        for (n = G->u.nlist; n; n = n->u.next) {
 
378
                if (n->u.node_type == NORMAL) {
 
379
                        Minrank = MIN(Minrank,n->u.rank);
 
380
                        Maxrank = MAX(Maxrank,n->u.rank);
 
381
                }
 
382
        }
 
383
}
 
384
 
 
385
void LR_balance(void)
 
386
{
 
387
        int             i,delta;
 
388
        node_t  *n;
 
389
        edge_t  *e,*f;
 
390
 
 
391
        for (i = 0; i < Tree_edge.size; i++) {
 
392
                e = Tree_edge.list[i];
 
393
                if (e->u.cutvalue == 0) {
 
394
                        f = enter_edge(e);
 
395
                        if (f == NULL) continue;
 
396
                        delta = SLACK(f);
 
397
                        if (delta <= 1) continue;
 
398
                        if (e->tail->u.lim < e->head->u.lim) rerank(e->tail,delta/2);
 
399
                        else rerank(e->head,-delta/2);
 
400
                }
 
401
        }
 
402
        for (n = G->u.nlist; n; n = n->u.next) {
 
403
                free_list(n->u.tree_in);
 
404
                free_list(n->u.tree_out);
 
405
                n->u.mark = FALSE;
 
406
        }
 
407
}
 
408
 
 
409
void TB_balance(void)
 
410
{
 
411
        node_t  *n;
 
412
        edge_t  *e;
 
413
        int             i,low,high,choice,*nrank;
 
414
        int             inweight,outweight;
 
415
 
 
416
        scan_result();
 
417
        if (Minrank != 0) {
 
418
                for (n = G->u.nlist; n; n = n->u.next) n->u.rank -= Minrank;
 
419
                Maxrank -= Minrank;
 
420
                Minrank = 0;
 
421
        }
 
422
 
 
423
        /* find nodes that are not tight and move to less populated ranks */
 
424
        nrank = N_NEW(Maxrank+1,int);
 
425
        for (i = 0; i <= Maxrank; i++) nrank[i] = 0;
 
426
        for (n = G->u.nlist; n; n = n->u.next)
 
427
                if (n->u.node_type == NORMAL) nrank[n->u.rank]++;
 
428
        for (n = G->u.nlist; n; n = n->u.next) {
 
429
                if (n->u.node_type != NORMAL) continue;
 
430
                inweight = outweight = 0;
 
431
                low = 0;
 
432
                high = Maxrank;
 
433
                for (i = 0; (e = n->u.in.list[i]); i++) {
 
434
                        inweight += e->u.weight;
 
435
                        low = MAX(low,e->tail->u.rank + e->u.minlen);
 
436
                }
 
437
                for (i = 0; (e = n->u.out.list[i]); i++) {
 
438
                        outweight += e->u.weight;
 
439
                        high = MIN(high,e->head->u.rank - e->u.minlen);
 
440
                }
 
441
                if (low < 0) low = 0;   /* vnodes can have ranks < 0 */
 
442
                if (inweight == outweight) {
 
443
                        choice = low;
 
444
                        for (i = low + 1; i <= high; i++)
 
445
                                if (nrank[i] < nrank[choice]) choice = i;
 
446
                        nrank[n->u.rank]--; nrank[choice]++;
 
447
                        n->u.rank = choice;
 
448
                }
 
449
                free_list(n->u.tree_in);
 
450
                free_list(n->u.tree_out);
 
451
                n->u.mark = FALSE;
 
452
        }
 
453
        free(nrank);
 
454
}
 
455
 
 
456
static int
 
457
init_graph(graph_t* g)
 
458
{
 
459
        int             i,feasible;
 
460
        node_t  *n;
 
461
        edge_t  *e;
 
462
 
 
463
        G = g;
 
464
        N_nodes = N_edges = S_i = 0;
 
465
        for (n = g->u.nlist; n; n = n->u.next) {
 
466
                n->u.mark = FALSE;
 
467
                N_nodes++;
 
468
                for (i = 0; (e = n->u.out.list[i]); i++) N_edges++;
 
469
        }
 
470
 
 
471
        Tree_node.list = ALLOC(N_nodes,Tree_node.list,node_t*);
 
472
        Tree_node.size = 0;
 
473
        Tree_edge.list = ALLOC(N_nodes,Tree_edge.list,edge_t*);
 
474
        Tree_edge.size = 0;
 
475
 
 
476
        feasible = TRUE;
 
477
        for (n = g->u.nlist; n; n = n->u.next) {
 
478
                n->u.priority = 0;
 
479
                for (i = 0; (e = n->u.in.list[i]); i++) {
 
480
                        n->u.priority++;
 
481
                        e->u.cutvalue = 0;
 
482
                        e->u.tree_index = -1;
 
483
                        if (feasible && (e->head->u.rank - e->tail->u.rank < e->u.minlen))
 
484
                                feasible = FALSE;
 
485
                }
 
486
                n->u.tree_in.list = N_NEW(i+1,edge_t*);
 
487
                n->u.tree_in.size = 0;
 
488
                for (i = 0; (e = n->u.out.list[i]); i++);
 
489
                n->u.tree_out.list = N_NEW(i+1,edge_t*);
 
490
                n->u.tree_out.size = 0;
 
491
        }
 
492
        return feasible;
 
493
}
 
494
 
 
495
void rank(graph_t *g, int tb_mode, int maxiter)
 
496
{
 
497
        int     iter = 0,feasible;
 
498
        char    *s,*ns = "network simplex: ";
 
499
        edge_t  *e,*f;
 
500
 
 
501
        if (Verbose) start_timer();
 
502
        feasible = init_graph(g);
 
503
        if (!feasible) init_rank();
 
504
        if (maxiter <= 0) return;
 
505
 
 
506
        if ((s = agget(g,"searchsize"))) Search_size = atoi(s);
 
507
        else Search_size = SEARCHSIZE;
 
508
 
 
509
        feasible_tree();
 
510
        while ((e = leave_edge())) {
 
511
                f = enter_edge(e);
 
512
                update(e,f);
 
513
                iter++;
 
514
                if (Verbose && (iter % 100 == 0)) {
 
515
                        if (iter % 1000 == 100) fputs(ns,stderr);
 
516
                        fprintf(stderr,"%d ",iter);
 
517
                        if (iter % 1000 == 0) fputc('\n',stderr);
 
518
                        if (iter >= maxiter) break;
 
519
                }
 
520
        }
 
521
        if (tb_mode) TB_balance();
 
522
        else LR_balance();
 
523
        if (Verbose) {
 
524
                if (iter >= 100) fputc('\n',stderr);
 
525
                fprintf(stderr,"%s%d nodes %d edges %d iter %.2f sec\n",
 
526
                        ns,N_nodes,N_edges,iter,elapsed_sec());
 
527
        }
 
528
}
 
529
 
 
530
/* set cut value of f, assuming values of edges on one side were already set */
 
531
void x_cutval(edge_t* f)
 
532
{
 
533
        node_t  *v;
 
534
        edge_t  *e;
 
535
        int             i,sum,dir;
 
536
 
 
537
        /* set v to the node on the side of the edge already searched */
 
538
        if (f->tail->u.par == f) { v = f->tail; dir = 1; }
 
539
        else { v = f->head; dir = -1; }
 
540
 
 
541
        sum = 0;
 
542
        for (i = 0; (e = v->u.out.list[i]); i++) sum += x_val(e,v,dir);
 
543
        for (i = 0; (e = v->u.in.list[i]); i++) sum += x_val(e,v,dir);
 
544
        f->u.cutvalue = sum;
 
545
}
 
546
 
 
547
int x_val(edge_t* e, node_t* v, int dir)
 
548
{
 
549
        node_t  *other;
 
550
        int             d,rv,f;
 
551
 
 
552
        if (e->tail == v) other = e->head; else other = e->tail;
 
553
        if (!(SEQ(v->u.low,other->u.lim,v->u.lim))) {f = 1; rv = e->u.weight;}
 
554
        else {
 
555
                f = 0;
 
556
                if (TREE_EDGE(e)) rv = e->u.cutvalue;
 
557
                else rv = 0;
 
558
                rv -= e->u.weight;
 
559
        }
 
560
        if (dir > 0) {if (e->head == v) d = 1; else d = -1;}
 
561
        else {if (e->tail == v) d = 1; else d = -1; }
 
562
        if (f) d = -d;
 
563
        if (d < 0) rv = -rv;
 
564
        return rv;
 
565
}
 
566
 
 
567
void dfs_cutval(node_t* v, edge_t* par)
 
568
{
 
569
        int             i;
 
570
        edge_t  *e;
 
571
 
 
572
        for (i = 0; (e = v->u.tree_out.list[i]); i++)
 
573
                if (e != par) dfs_cutval(e->head,e);
 
574
        for (i = 0; (e = v->u.tree_in.list[i]); i++)
 
575
                if (e != par) dfs_cutval(e->tail,e);
 
576
        if (par) x_cutval(par);
 
577
}
 
578
 
 
579
int dfs_range(node_t* v, edge_t* par, int low)
 
580
{
 
581
        edge_t  *e;
 
582
        int             i,lim;
 
583
 
 
584
        lim = low;
 
585
        v->u.par = par;
 
586
        v->u.low = low;
 
587
        for (i = 0; (e = v->u.tree_out.list[i]); i++)
 
588
                if (e != par) lim = dfs_range(e->head,e,lim);
 
589
        for (i = 0; (e = v->u.tree_in.list[i]); i++)
 
590
                if (e != par) lim = dfs_range(e->tail,e,lim);
 
591
        v->u.lim = lim;
 
592
        return lim + 1;
 
593
}
 
594
 
 
595
#ifdef DEBUG
 
596
void tchk(void)
 
597
{
 
598
        int             i,n_cnt,e_cnt;
 
599
        node_t  *n;
 
600
        edge_t  *e;
 
601
 
 
602
        n_cnt = 0;
 
603
        e_cnt = 0;
 
604
        for (n = G->u.nlist; n; n = n->u.next) {
 
605
                n_cnt++;
 
606
                for (i = 0; e = n->u.tree_out.list[i]; i++) {
 
607
                        e_cnt++;
 
608
                        if (SLACK(e) > 0)
 
609
                                printf("not a tight tree %x",e);
 
610
                }
 
611
        }
 
612
        if ((n_cnt != Tree_node.size)  || (e_cnt != Tree_edge.size))
 
613
                printf("something missing\n");
 
614
}
 
615
 
 
616
void check_cutvalues(void)
 
617
{
 
618
        node_t  *v;
 
619
        edge_t  *e;
 
620
        int             i,save;
 
621
 
 
622
        for (v = G->u.nlist; v; v = v->u.next) {
 
623
                for (i = 0; (e = v->u.tree_out.list[i]); i++) {
 
624
                        save = e->u.cutvalue;
 
625
                        x_cutval(e);
 
626
                        if (save != e->u.cutvalue) abort();
 
627
                }
 
628
        }
 
629
}
 
630
 
 
631
int
 
632
check_ranks(void)
 
633
{
 
634
        int             i, cost = 0;
 
635
        node_t  *n;
 
636
        edge_t  *e;
 
637
 
 
638
        for (n = G->u.nlist; n; n = n->u.next) {
 
639
                for (i = 0; (e = n->u.out.list[i]); i++) {
 
640
                        cost += (e->u.weight)*abs(LENGTH(e));
 
641
if (e->head->u.rank - e->tail->u.rank - e->u.minlen < 0) abort();
 
642
                }
 
643
        }
 
644
        fprintf(stderr,"rank cost %d\n",cost);
 
645
        return cost;
 
646
}
 
647
 
 
648
void checktree(void)
 
649
{
 
650
        int             i,n = 0,m = 0;
 
651
        node_t  *v;
 
652
        edge_t  *e;
 
653
 
 
654
        for (v = G->u.nlist; v; v = v->u.next) {
 
655
                for (i = 0; (e = v->u.tree_out.list[i]); i++) n++;
 
656
                if (i != v->u.tree_out.size) abort();
 
657
                for (i = 0; (e = v->u.tree_in.list[i]); i++) m++;
 
658
                if (i != v->u.tree_in.size) abort();
 
659
        }
 
660
        printf("%d %d %d\n",Tree_edge.size,n,m);
 
661
}
 
662
 
 
663
void check_fast_node(node_t* n)
 
664
{
 
665
        node_t  *nptr;
 
666
        nptr = n->graph->u.nlist;
 
667
        while (nptr && nptr != n) nptr = nptr->u.next;
 
668
        assert (nptr != NULL);
 
669
}
 
670
 
 
671
void checkdfs(node_t* n)
 
672
{
 
673
        int             i;
 
674
        edge_t  *e;
 
675
        node_t  *w;
 
676
 
 
677
        if (n->u.mark) return;
 
678
        n->u.mark = TRUE;
 
679
        n->u.onstack = TRUE;
 
680
        for (i = 0; (e = n->u.out.list[i]); i++) {
 
681
                w = e->head;
 
682
                if (w->u.onstack)
 
683
                        fprintf(stderr,"cycle involving %s %s\n",n->name,w->name);
 
684
                else {
 
685
                        if (w->u.mark == FALSE) checkdfs(w);
 
686
                }
 
687
        }
 
688
        n->u.onstack = FALSE;
 
689
}
 
690
 
 
691
void check_cycles(graph_t* g)
 
692
{
 
693
        node_t  *n;
 
694
        for (n = g->u.nlist; n; n = n->u.next) n->u.mark = n->u.onstack = FALSE;
 
695
        for (n = g->u.nlist; n; n = n->u.next) checkdfs(n);
 
696
}
 
697
#endif /* DEBUG */