← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dotneato/dotgen/mincross.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/mincross.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
 * dot_mincross(g) takes a ranked graphs, and finds an ordering
 
14
 * that avoids edge crossings.  clusters are expanded.
 
15
 * N.B. the rank structure is global (not allocated per cluster)
 
16
 * because mincross may compare nodes in different clusters.
 
17
 */
 
18
 
 
19
#include "dot.h"
 
20
 
 
21
#ifdef DMALLOC
 
22
#include "dmalloc.h"
 
23
#endif
 
24
 
 
25
#define MARK(v)                 ((v)->u.mark)
 
26
#define saveorder(v)    ((v)->u.coord.x)
 
27
#define flatindex(v)    ((v)->u.low)
 
28
 
 
29
        /* forward declarations */
 
30
static boolean medians(graph_t *g, int r0, int r1);
 
31
static int nodeposcmpf(node_t **n0, node_t **n1);
 
32
static int edgeidcmpf(edge_t **e0, edge_t **e1);
 
33
static void flat_breakcycles(graph_t* g);
 
34
static void flat_reorder(graph_t* g);
 
35
static void flat_search(graph_t* g, node_t* v);
 
36
static void init_mincross(graph_t* g);
 
37
static void merge2(graph_t* g);
 
38
static void init_mccomp(graph_t* g, int c);
 
39
static void cleanup2(graph_t* g, int nc);
 
40
static int mincross_clust(graph_t *par, graph_t *g);
 
41
static int mincross(graph_t *g, int startpass, int endpass);
 
42
static void init_mincross(graph_t* g);
 
43
static void mincross_step(graph_t* g, int pass);
 
44
static void mincross_options(graph_t* g);
 
45
static void save_best(graph_t* g);
 
46
static void restore_best(graph_t* g);
 
47
static adjmatrix_t* new_matrix(int i, int j);
 
48
static void free_matrix(adjmatrix_t* p);
 
49
 
 
50
        /* mincross parameters */
 
51
static int      MinQuit;
 
52
static double   Convergence;
 
53
 
 
54
static graph_t  *Root;
 
55
static int              GlobalMinRank,GlobalMaxRank;
 
56
static edge_t   **TE_list;
 
57
static int              *TI_list;
 
58
static boolean  ReMincross;
 
59
 
 
60
void dot_mincross(graph_t* g)
 
61
{
 
62
        int             c,nc;
 
63
        char    *s;
 
64
 
 
65
        init_mincross(g);
 
66
 
 
67
        for (nc = c = 0; c < g->u.comp.size; c++) {
 
68
                init_mccomp(g,c);
 
69
                nc += mincross(g,0,2);
 
70
        }
 
71
 
 
72
        merge2(g);
 
73
 
 
74
        /* run mincross on contents of each cluster */
 
75
        for (c = 1; c <= g->u.n_cluster; c++) {
 
76
                nc += mincross_clust(g,g->u.clust[c]);
 
77
#ifdef DEBUG
 
78
                check_vlists(g->u.clust[c]);
 
79
                check_order();
 
80
#endif
 
81
        }
 
82
 
 
83
        if ((g->u.n_cluster > 0) && (!(s = agget(g,"remincross")) || (mapbool(s)))) {
 
84
                mark_lowclusters(g);
 
85
                ReMincross = TRUE;
 
86
                nc = mincross(g,2,2);
 
87
#ifdef DEBUG
 
88
                for (c = 1; c <= g->u.n_cluster; c++)
 
89
                        check_vlists(g->u.clust[c]);
 
90
#endif
 
91
        }
 
92
        cleanup2(g,nc);
 
93
}
 
94
 
 
95
static adjmatrix_t* new_matrix(int i, int j)
 
96
{
 
97
        adjmatrix_t     *rv = NEW(adjmatrix_t);
 
98
        rv->nrows = i; rv->ncols = j;
 
99
        rv->data = N_NEW(i*j,char);
 
100
        return rv;
 
101
}
 
102
 
 
103
static void free_matrix(adjmatrix_t* p)
 
104
{
 
105
        if (p) {free(p->data); free(p);}
 
106
}
 
107
#define ELT(M,i,j)              (M->data[((i)*M->ncols)+(j)])
 
108
 
 
109
static void init_mccomp(graph_t* g, int c)
 
110
{
 
111
        int             r;
 
112
 
 
113
        g->u.nlist = g->u.comp.list[c];
 
114
        if (c > 0) {
 
115
                for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
116
                        g->u.rank[r].v = g->u.rank[r].v + g->u.rank[r].n;
 
117
                        g->u.rank[r].n = 0;
 
118
                }
 
119
        }
 
120
}
 
121
 
 
122
static int mincross_clust(graph_t *par, graph_t *g)
 
123
{
 
124
        int             c,nc;
 
125
 
 
126
        expand_cluster(g);
 
127
        ordered_edges(g);
 
128
        flat_breakcycles(g);
 
129
        flat_reorder(g);
 
130
        nc = mincross(g,2,2);
 
131
        
 
132
        for (c = 1; c <= g->u.n_cluster; c++)
 
133
                nc += mincross_clust(g,g->u.clust[c]);
 
134
 
 
135
        save_vlist(g);
 
136
        return nc;
 
137
}
 
138
 
 
139
static int mincross(graph_t *g, int startpass, int endpass)
 
140
{
 
141
        int             maxthispass,iter,trying,pass;
 
142
        int             cur_cross,best_cross;
 
143
 
 
144
        if (startpass > 1) {
 
145
                cur_cross = best_cross = ncross(g);
 
146
                save_best(g);
 
147
        }
 
148
        else cur_cross = best_cross = MAXINT;
 
149
        for (pass = startpass; pass <= endpass; pass++) {
 
150
                if (pass <= 1) {
 
151
                        maxthispass = MIN(4,MaxIter);
 
152
                        if (g == g->root) build_ranks(g,pass);
 
153
                        if (pass == 0) flat_breakcycles(g);
 
154
                        flat_reorder(g);
 
155
 
 
156
                        if ((cur_cross = ncross(g)) <= best_cross) {
 
157
                                save_best(g);
 
158
                                best_cross = cur_cross;
 
159
                        }
 
160
                        trying = 0;
 
161
                }
 
162
                else {
 
163
                        maxthispass = MaxIter;
 
164
                        if (cur_cross > best_cross) restore_best(g);
 
165
                        cur_cross = best_cross;
 
166
                }
 
167
                trying = 0;
 
168
                for (iter = 0; iter < maxthispass; iter++) {
 
169
                        if (Verbose) fprintf(stderr,"mincross: pass %d iter %d trying %d cur_cross %d best_cross %d\n",pass,iter,trying,cur_cross,best_cross);
 
170
                        if (trying++ >= MinQuit) break;
 
171
                        if (cur_cross == 0) break;
 
172
                        mincross_step(g,iter);
 
173
                        if ((cur_cross = ncross(g)) <= best_cross) {
 
174
                                save_best(g);
 
175
                                if (cur_cross < Convergence*best_cross) trying = 0;
 
176
                                best_cross = cur_cross;
 
177
                        }
 
178
                }
 
179
                if (cur_cross == 0) break;
 
180
        }
 
181
        if (cur_cross > best_cross) restore_best(g);
 
182
        if (best_cross > 0) {transpose(g,FALSE); best_cross= ncross(g);}
 
183
        return best_cross;
 
184
}
 
185
 
 
186
static void restore_best(graph_t* g)
 
187
{
 
188
        node_t  *n;
 
189
        int             r;
 
190
        
 
191
        for (n = g->u.nlist; n; n = n->u.next) n->u.order = saveorder(n);
 
192
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
193
                g->u.rank[r].valid = FALSE;
 
194
                qsort(g->u.rank[r].v,g->u.rank[r].n,sizeof(g->u.rank[0].v[0]),(qsort_cmpf)nodeposcmpf);
 
195
        }
 
196
}
 
197
 
 
198
static void save_best(graph_t* g)
 
199
{
 
200
        node_t  *n;
 
201
        for (n = g->u.nlist; n; n = n->u.next) saveorder(n) = n->u.order;
 
202
}
 
203
 
 
204
/* merge connected components, create globally consistent rank lists */
 
205
static void merge2(graph_t* g)
 
206
{
 
207
        int             i,r;
 
208
        node_t  *v;
 
209
 
 
210
        /* merge the components and rank limits */
 
211
        merge_components(g);
 
212
 
 
213
        /* install complete ranks */
 
214
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
215
                g->u.rank[r].n = g->u.rank[r].an;
 
216
                g->u.rank[r].v = g->u.rank[r].av;
 
217
                for (i = 0; i < g->u.rank[r].n; i++) {
 
218
                        v = g->u.rank[r].v[i];
 
219
                        if (v == NULL) {
 
220
                                if (Verbose) fprintf(stderr,"merge2: graph %s, rank %d has only %d < %d nodes\n",g->name,r,i,g->u.rank[r].n);
 
221
                                        g->u.rank[r].n = i;
 
222
                                        break;
 
223
                        }
 
224
                        v->u.order = i;
 
225
                }
 
226
        }
 
227
}
 
228
 
 
229
static void cleanup2(graph_t* g, int nc)
 
230
{
 
231
        int             i,j,r,c;
 
232
        node_t  *v;
 
233
        edge_t  *e;
 
234
 
 
235
        free(TI_list); free(TE_list);
 
236
        /* fix vlists of clusters */
 
237
        for (c = 1; c <= g->u.n_cluster; c++)
 
238
                rec_reset_vlists(g->u.clust[c]);
 
239
 
 
240
        /* remove node temporary edges for ordering nodes */
 
241
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
242
                for (i = 0; i < g->u.rank[r].n; i++) {
 
243
                        v = g->u.rank[r].v[i];
 
244
                        v->u.order = i;
 
245
                        if (v->u.flat_out.list) {
 
246
                                for (j = 0; (e = v->u.flat_out.list[j]); j++)
 
247
                                if (e->u.edge_type == FLATORDER) {
 
248
                                        delete_flat_edge(e);
 
249
                                        free(e);
 
250
                                        j--;
 
251
                                }
 
252
                        }
 
253
                }
 
254
                free_matrix(g->u.rank[r].flat);
 
255
        }
 
256
        if (Verbose) fprintf(stderr,"mincross %s: %d crossings, %.2f secs.\n",
 
257
                g->name,nc,elapsed_sec());
 
258
}
 
259
 
 
260
static node_t* neighbor(node_t* v, int dir)
 
261
{
 
262
        node_t          *rv;
 
263
 
 
264
        rv = NULL;
 
265
        if (dir < 0) {
 
266
                if (v->u.order > 0) rv = Root->u.rank[v->u.rank].v[v->u.order - 1];
 
267
        }
 
268
        else rv = Root->u.rank[v->u.rank].v[v->u.order + 1];
 
269
        return rv;
 
270
}
 
271
 
 
272
int inside_cluster(graph_t* g, node_t* v)
 
273
{
 
274
        return (is_a_normal_node_of(g,v) | is_a_vnode_of_an_edge_of(g,v));
 
275
}
 
276
 
 
277
int is_a_normal_node_of(graph_t* g, node_t* v)
 
278
{
 
279
        return ((v->u.node_type == NORMAL) && agcontains(g,v));
 
280
}
 
281
 
 
282
int is_a_vnode_of_an_edge_of(graph_t* g, node_t* v)
 
283
{
 
284
        if ((v->u.node_type == VIRTUAL)
 
285
                && (v->u.in.size == 1) && (v->u.out.size == 1) )  {
 
286
                        edge_t  *e = v->u.out.list[0];
 
287
                        while (e->u.edge_type != NORMAL) e = e->u.to_orig;
 
288
                        if (agcontains(g,e)) return TRUE;
 
289
        }
 
290
        return FALSE;
 
291
}
 
292
 
 
293
static node_t   *furthestnode(graph_t* g, node_t* v, int dir)
 
294
{
 
295
        node_t  *u,*rv;
 
296
 
 
297
        rv = u = v;
 
298
        while ((u = neighbor(u,dir))) {
 
299
                if (is_a_normal_node_of(g,u)) rv = u;
 
300
                else if (is_a_vnode_of_an_edge_of(g,u)) rv = u;
 
301
        }
 
302
        return rv;
 
303
}
 
304
 
 
305
void save_vlist(graph_t* g)
 
306
{
 
307
        int             r;
 
308
 
 
309
        if (g->u.rankleader)
 
310
                for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
311
                        g->u.rankleader[r] = g->u.rank[r].v[0];
 
312
                }
 
313
}
 
314
 
 
315
void rec_save_vlists(graph_t* g)
 
316
{
 
317
        int             c;
 
318
 
 
319
        save_vlist(g);
 
320
        for (c = 1; c <= g->u.n_cluster; c++)
 
321
                rec_save_vlists(g->u.clust[c]);
 
322
}
 
323
 
 
324
 
 
325
void rec_reset_vlists(graph_t* g)
 
326
{
 
327
        int             r,c;
 
328
        node_t  *u,*v,*w;
 
329
 
 
330
        /* fix vlists of sub-clusters */
 
331
        for (c = 1; c <= g->u.n_cluster; c++)
 
332
                rec_reset_vlists(g->u.clust[c]);
 
333
        
 
334
        if (g->u.rankleader)
 
335
                for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
336
                        v = g->u.rankleader[r];
 
337
#ifdef DEBUG
 
338
                        assert(node_in_root_vlist(v));
 
339
#endif
 
340
                        u = furthestnode(g,v,-1);
 
341
                        w = furthestnode(g,v, 1);
 
342
                        g->u.rankleader[r] = u;
 
343
#ifdef DEBUG
 
344
                        assert(g->root->u.rank[r].v[u->u.order] == u);
 
345
#endif
 
346
                        g->u.rank[r].v = g->root->u.rank[r].v + u->u.order;
 
347
                        g->u.rank[r].n = w->u.order - u->u.order + 1;
 
348
                }
 
349
}
 
350
 
 
351
static void init_mincross(graph_t* g)
 
352
{
 
353
        if (Verbose) start_timer();
 
354
 
 
355
        ReMincross = FALSE;
 
356
        Root = g;
 
357
        TE_list = N_NEW(agnedges(g->root),edge_t*);
 
358
        TI_list = N_NEW(agnedges(g->root),int);
 
359
 
 
360
        mincross_options(g);
 
361
        class2(g);
 
362
        decompose(g,1);
 
363
        allocate_ranks(g);
 
364
        ordered_edges(g);
 
365
        GlobalMinRank = g->u.minrank; GlobalMaxRank = g->u.maxrank;
 
366
}
 
367
 
 
368
static void flat_search(graph_t* g, node_t* v)
 
369
{
 
370
        int             i,j;
 
371
        boolean hascl;
 
372
        edge_t  *e,*rev;
 
373
        adjmatrix_t     *M = g->u.rank[v->u.rank].flat;
 
374
 
 
375
        v->u.mark = TRUE;
 
376
        v->u.onstack = TRUE;
 
377
        hascl = (g->root->u.n_cluster > 0);
 
378
        if (v->u.flat_out.list) for (i = 0; (e = v->u.flat_out.list[i]); i++) {
 
379
                if (hascl && NOT(agcontains(g,e->tail) && agcontains(g,e->head)))
 
380
                        continue;
 
381
                if (e->u.weight == 0) continue;
 
382
                if (e->head->u.onstack == TRUE)  {
 
383
                        assert(flatindex(e->head) < M->nrows);
 
384
                        assert(flatindex(e->tail) < M->ncols);
 
385
                        ELT(M,flatindex(e->head),flatindex(e->tail)) = 1;
 
386
                        delete_flat_edge(e);
 
387
                        i--;
 
388
                        if (e->u.edge_type == FLATORDER) continue;
 
389
                        for (j = 0; (rev = e->head->u.flat_out.list[j]); j++)
 
390
                                if (rev->head == e->tail) break;
 
391
                        if (rev) {
 
392
                                merge_oneway(e,rev);
 
393
                                elist_append(e,e->tail->u.other);
 
394
                        }
 
395
                        else {
 
396
                                rev = new_virtual_edge(e->head,e->tail,e);
 
397
                                rev->u.edge_type = REVERSED;
 
398
                                flat_edge(g,rev);
 
399
                        }
 
400
                }
 
401
                else {
 
402
                        assert(flatindex(e->head) < M->nrows);
 
403
                        assert(flatindex(e->tail) < M->ncols);
 
404
                        ELT(M,flatindex(e->tail),flatindex(e->head)) = 1;
 
405
                        if (e->head->u.mark == FALSE) flat_search(g,e->head);
 
406
                }
 
407
        }
 
408
        v->u.onstack = FALSE;
 
409
}
 
410
 
 
411
static void flat_breakcycles(graph_t* g)
 
412
{
 
413
        int             i,r,flat;
 
414
        node_t  *v;
 
415
 
 
416
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
417
                flat = 0;
 
418
                for (i = 0; i < g->u.rank[r].n; i++) {
 
419
                        v = g->u.rank[r].v[i];
 
420
                        v->u.mark = v->u.onstack = FALSE;
 
421
                        flatindex(v) = i;
 
422
                        if ((v->u.flat_out.size > 0) && (flat == 0)) {
 
423
                                g->u.rank[r].flat = new_matrix(g->u.rank[r].n,g->u.rank[r].n);
 
424
                                flat = 1;
 
425
                        }
 
426
                }
 
427
                if (flat) {
 
428
                        for (i = 0; i < g->u.rank[r].n; i++) {
 
429
                                v = g->u.rank[r].v[i];
 
430
                                if (v->u.mark == FALSE) flat_search(g,v);
 
431
                        }
 
432
                }
 
433
        }
 
434
}
 
435
 
 
436
int left2right(graph_t *g, node_t *v, node_t *w)
 
437
{
 
438
        adjmatrix_t     *M;
 
439
        int                     rv;
 
440
 
 
441
        /* CLUSTER indicates orig nodes of clusters, and vnodes of skeletons */
 
442
        if (ReMincross == FALSE) {
 
443
                if ((v->u.clust != w->u.clust) && (v->u.clust) && (w->u.clust)) {
 
444
                        /* the following allows cluster skeletons to be swapped */
 
445
                        if ((v->u.ranktype == CLUSTER) && (v->u.node_type == VIRTUAL)) return FALSE;
 
446
                        if ((w->u.ranktype == CLUSTER) && (w->u.node_type == VIRTUAL)) return FALSE;
 
447
                        return TRUE;
 
448
                        /*return ((v->u.ranktype != CLUSTER) && (w->u.ranktype != CLUSTER));*/
 
449
                }
 
450
        }
 
451
        else {
 
452
                if ((v->u.clust) != (w->u.clust)) return TRUE;
 
453
        }
 
454
        M = g->u.rank[v->u.rank].flat;
 
455
        if (M == NULL) rv = FALSE;
 
456
        else {
 
457
                if (g->u.left_to_right) {node_t *t = v; v = w; w = t;}
 
458
                rv = ELT(M,flatindex(v),flatindex(w));
 
459
        }
 
460
        return rv;
 
461
}
 
462
 
 
463
static void clust_count_ranks(graph_t* g, int* count)
 
464
{
 
465
        node_t          *n;
 
466
        edge_t          *e;
 
467
        int                     low,high,j;
 
468
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
469
                assert (n->u.UF_size > 0);
 
470
                count[n->u.rank] += n->u.UF_size;
 
471
                for (e = agfstout(g->root,n); e; e = agnxtout(g->root,e)) {
 
472
                        low = e->tail->u.rank; high = e->head->u.rank;
 
473
                        if (low > high) {int t = low; low = high; high = t;}
 
474
                        assert(low <= high);
 
475
                        for (j = low + 1; j <= high - 1; j++) count[j] += e->u.xpenalty;
 
476
                }
 
477
        }
 
478
}
 
479
 
 
480
/* should combine with previous, just need to count rankleaders */
 
481
static void count_ranks(graph_t* g, int** c0)
 
482
{
 
483
        static int      *count;
 
484
        int                     c;
 
485
        node_t          *n;
 
486
        edge_t          *e;
 
487
        int                     low,high,i,j;
 
488
 
 
489
        count = ALLOC(Root->u.maxrank+1,count,int);
 
490
        for (c = 0; c <= g->u.maxrank; c++) count[c] = 0;
 
491
 
 
492
        for (c = 0; c < g->u.comp.size; c++) {
 
493
                for (n = g->u.comp.list[c]; n; n = n->u.next) {
 
494
                        assert (n->u.UF_size > 0);
 
495
                        count[n->u.rank] += n->u.UF_size;
 
496
                        for (i = 0; (e = n->u.out.list[i]); i++) {
 
497
                                low = e->tail->u.rank; high = e->head->u.rank;
 
498
                                assert(low < high);
 
499
                                for (j = low + 1; j <= high - 1; j++) count[j] += e->u.xpenalty;
 
500
                        }
 
501
                }
 
502
        }
 
503
        for (c = 1; c <= g->u.n_cluster; c++)
 
504
                clust_count_ranks(g->u.clust[c],count);
 
505
        *c0 = count;
 
506
}
 
507
 
 
508
/* allocates ranks, with enough space for all nodes expanded */
 
509
void allocate_ranks(graph_t* g)
 
510
{
 
511
        int             r,*cn;
 
512
 
 
513
        count_ranks(g,&cn);
 
514
        g->u.rank = N_NEW(g->u.maxrank+2,rank_t);
 
515
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
516
                g->u.rank[r].an = g->u.rank[r].n = cn[r];
 
517
                g->u.rank[r].av = g->u.rank[r].v = N_NEW(cn[r]+1,node_t*);
 
518
        }
 
519
}
 
520
 
 
521
/* install a node at the current right end of its rank */
 
522
void install_in_rank(graph_t* g, node_t* n)
 
523
{
 
524
        int             i,r;
 
525
 
 
526
        r = n->u.rank;
 
527
        i = g->u.rank[r].n;
 
528
        if (g->u.rank[r].an <= 0) {
 
529
                fprintf(stderr,"install_in_rank %s %s rank %d i = %d an = 0\n",
 
530
                        g->name,n->name,r,i);
 
531
                abort();
 
532
        }
 
533
 
 
534
        g->u.rank[r].v[i] = n;
 
535
        n->u.order = i;
 
536
        g->u.rank[r].n++;
 
537
        assert(g->u.rank[r].n <= g->u.rank[r].an);
 
538
#ifdef DEBUG
 
539
        {
 
540
                node_t          *v;
 
541
 
 
542
                for (v = g->u.nlist; v; v = v->u.next)
 
543
                        if (v == n) break;
 
544
                assert(v != NULL);
 
545
        }
 
546
#endif
 
547
        if (n->u.order > Root->u.rank[r].an) abort();
 
548
        if ((r < g->u.minrank) || (r > g->u.maxrank)) abort();
 
549
        if (g->u.rank[r].v + n->u.order > g->u.rank[r].av + Root->u.rank[r].an) abort();
 
550
}
 
551
 
 
552
/*      install nodes in ranks. the initial ordering ensure that series-parallel
 
553
 *      graphs such as trees are drawn with no crossings.  it tries searching
 
554
 *      in- and out-edges and takes the better of the two initial orderings.
 
555
 */
 
556
void build_ranks(graph_t* g, int pass)
 
557
{
 
558
        int             i,j;
 
559
        node_t  *n,*n0;
 
560
        edge_t  **otheredges;
 
561
        queue   *q;
 
562
        
 
563
 
 
564
        q = new_queue(g->u.n_nodes);
 
565
        for (n = g->u.nlist; n; n = n->u.next) MARK(n) = FALSE;
 
566
 
 
567
#ifdef DEBUG
 
568
        {
 
569
        edge_t  *e;
 
570
        for (n = g->u.nlist; n; n = n->u.next) {
 
571
                for (i = 0; (e = n->u.out.list[i]); i++) 
 
572
                        assert(MARK(e->head) == FALSE);
 
573
                for (i = 0; (e = n->u.in.list[i]); i++) 
 
574
                        assert(MARK(e->tail) == FALSE);
 
575
        }
 
576
        }
 
577
#endif
 
578
 
 
579
        for (i = g->u.minrank; i <= g->u.maxrank; i++) g->u.rank[i].n = 0;
 
580
 
 
581
        for (n = g->u.nlist; n; n = n->u.next) {
 
582
                otheredges = ((pass == 0)? n->u.in.list : n->u.out.list);
 
583
                if (otheredges[0] != NULL) continue;
 
584
                if (MARK(n) == FALSE) {
 
585
                        MARK(n) = TRUE;
 
586
                        enqueue(q,n);
 
587
                        while ((n0 = dequeue(q))) {
 
588
                                if (n0->u.ranktype != CLUSTER) {
 
589
                                        install_in_rank(g,n0);
 
590
                                        enqueue_neighbors(q,n0,pass);
 
591
                                }
 
592
                                else {
 
593
                                        install_cluster(g,n0,pass,q);
 
594
                                }
 
595
                        }
 
596
                }
 
597
        }
 
598
        if (dequeue(q)) fprintf(stderr,"surprise\n");
 
599
        for (i = g->u.minrank; i <= g->u.maxrank; i++) {
 
600
                g->u.rank[i].valid = FALSE;
 
601
                if (g->u.left_to_right && (g->u.rank[i].n > 0)) {
 
602
                        int             n,ndiv2;
 
603
                        node_t  **vlist = g->u.rank[i].v;
 
604
                        n = g->u.rank[i].n - 1;  ndiv2 = n / 2;
 
605
                        for (j = 0; j <= ndiv2; j++)
 
606
                                exchange(vlist[j],vlist[n - j]);
 
607
                }
 
608
        }
 
609
 
 
610
        if ((g == g->root) && ncross(g) > 0) transpose(g,FALSE);
 
611
        free_queue(q);
 
612
}
 
613
 
 
614
void enqueue_neighbors(queue* q, node_t* n0, int pass)
 
615
{
 
616
        int             i;
 
617
        edge_t  *e;
 
618
 
 
619
        if (pass == 0) {
 
620
                for (i = 0; i < n0->u.out.size ; i++) {
 
621
                        e = n0->u.out.list[i];
 
622
                        if ((MARK(e->head)) == FALSE) {
 
623
                                MARK(e->head) = TRUE;
 
624
                                enqueue(q,e->head);
 
625
                        }
 
626
                }
 
627
        }
 
628
        else {
 
629
                for (i = 0; i < n0->u.in.size ; i++) {
 
630
                        e = n0->u.in.list[i];
 
631
                        if ((MARK(e->tail)) == FALSE) {
 
632
                                MARK(e->tail) = TRUE;
 
633
                                enqueue(q,e->tail);
 
634
                        }
 
635
                }
 
636
        }
 
637
}
 
638
 
 
639
/* construct nodes reachable from 'here' in post-order.
 
640
 * This is the same as doing a topological sort in reverse order.
 
641
 */
 
642
static int postorder(graph_t *g, node_t *v, node_t **list)
 
643
{
 
644
    edge_t      *e;
 
645
        int             i,cnt = 0;
 
646
 
 
647
        MARK(v) = TRUE;
 
648
        if (v->u.flat_out.size > 0) {
 
649
                for (i = 0; (e = v->u.flat_out.list[i]); i++) {
 
650
                        if ((e->head->u.node_type == NORMAL) &
 
651
                                (NOT(agcontains(g,e->head)))) continue;
 
652
                        if (e->head->u.clust != e->tail->u.clust) continue;
 
653
 
 
654
                        if (MARK(e->head) == FALSE)
 
655
                                cnt += postorder(g,e->head,list+cnt);
 
656
                }
 
657
        }
 
658
    list[cnt++] = v;
 
659
        return cnt;
 
660
}
 
661
 
 
662
static void flat_reorder(graph_t* g)
 
663
{
 
664
        int             i,j,r,pos,n_search,local_in_cnt, local_out_cnt;
 
665
        node_t  *v,**left,**right,*t;
 
666
        node_t  **temprank = NULL;
 
667
        edge_t  *flat_e;
 
668
 
 
669
        if (g->u.has_flat_edges == FALSE) return;
 
670
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
671
                for (i = 0; i < g->u.rank[r].n; i++) MARK(g->u.rank[r].v[i]) = FALSE;
 
672
                temprank = ALLOC(i+1,temprank,node_t*);
 
673
                pos = 0;
 
674
                for (i = 0; i < g->u.rank[r].n; i++) {
 
675
                        v = g->u.rank[r].v[i];
 
676
 
 
677
                        local_in_cnt = local_out_cnt = 0;
 
678
                        for (j = 0; j < v->u.flat_in.size; j++) {
 
679
                                flat_e = v->u.flat_in.list[j];
 
680
                                if (inside_cluster(g,flat_e->tail)) local_in_cnt++;
 
681
                        }
 
682
                        for (j = 0; j < v->u.flat_out.size; j++) {
 
683
                                flat_e = v->u.flat_out.list[j];
 
684
                                if (inside_cluster(g,flat_e->head)) local_out_cnt++;
 
685
                        }
 
686
                        if ((local_in_cnt == 0) && (local_out_cnt == 0))
 
687
                                temprank[pos++] = v;
 
688
                        else {
 
689
                                if ((MARK(v) == FALSE) && (local_in_cnt == 0)) {
 
690
                                        left = temprank + pos;
 
691
                                        n_search = postorder(g,v,left);
 
692
                                        if (g->u.left_to_right == FALSE) {
 
693
                                                right = left + n_search - 1;
 
694
                                                while (left < right) {
 
695
                                                        t = *left; *left = *right; *right = t;
 
696
                                                        left++; right--;
 
697
                                                }
 
698
                                        }
 
699
                                        pos += n_search;
 
700
                                }
 
701
                        }
 
702
                }
 
703
                for (i = 0; i < g->u.rank[r].n; i++){
 
704
                        v = g->u.rank[r].v[i] = temprank[i];
 
705
                        v->u.order = i + (g->u.rank[r].v - Root->u.rank[r].v);
 
706
                }
 
707
                g->u.rank[r].valid = FALSE;
 
708
        }
 
709
        if (temprank) free(temprank);
 
710
}
 
711
 
 
712
static void mincross_step(graph_t* g, int pass)
 
713
{
 
714
        int             r,other,first,last,dir;
 
715
        int             hasfixed,reverse;
 
716
 
 
717
        if ((pass % 4) < 2) reverse = TRUE; else reverse = FALSE;
 
718
        if (pass % 2)   { r = g->u.maxrank - 1; dir = -1; }      /* up pass */
 
719
        else                    { r = 1; dir = 1; }                             /* down pass */
 
720
 
 
721
        if (pass % 2 == 0) {            /* down pass */
 
722
                first = g->u.minrank + 1;
 
723
                if (g->u.minrank > Root->u.minrank) first--;
 
724
                last = g->u.maxrank;
 
725
                dir = 1;
 
726
        }
 
727
        else {                                          /* up pass */
 
728
                first = g->u.maxrank - 1;
 
729
                last = g->u.minrank;
 
730
                if (g->u.maxrank < Root->u.maxrank) first++;
 
731
                dir = -1;
 
732
        }
 
733
 
 
734
        for (r = first; r != last + dir; r += dir) {
 
735
                other = r - dir;
 
736
                hasfixed = medians(g,r,other);
 
737
                reorder(g,r,reverse,hasfixed);
 
738
        }
 
739
        transpose(g,NOT(reverse));
 
740
}
 
741
 
 
742
void transpose(graph_t* g, int reverse)
 
743
{
 
744
        int             r,delta;
 
745
 
 
746
        for (r = g->u.minrank; r <= g->u.maxrank; r++)
 
747
                g->u.rank[r].candidate = TRUE;
 
748
        do {
 
749
                delta = 0;
 
750
#ifdef NOTDEF
 
751
                /* don't run both the upward and downward passes- they cancel. 
 
752
                   i tried making it depend on whether an odd or even pass, 
 
753
                   but that didn't help. */
 
754
                for (r = g->u.maxrank; r >= g->u.minrank; r--)
 
755
                        if (g->u.rank[r].candidate) delta += transpose_step(g,r,reverse);
 
756
#endif
 
757
                for (r = g->u.minrank; r <= g->u.maxrank; r++)
 
758
                        if (g->u.rank[r].candidate) delta += transpose_step(g,r,reverse);
 
759
        /*} while (delta > ncross(g)*(1.0 - Convergence));*/
 
760
        } while (delta >= 1);
 
761
}
 
762
 
 
763
int local_cross(elist l, int dir)
 
764
{
 
765
        int             i,j,is_out;
 
766
        int             cross = 0;
 
767
        edge_t  *e,*f;
 
768
        if (dir > 0) is_out = TRUE; else is_out = FALSE;
 
769
        for (i = 0; (e = l.list[i]); i++) {
 
770
                if (is_out) for (j = i+1; (f = l.list[j]); j++)  {
 
771
                        if ((f->head->u.order - e->head->u.order) * (f->u.tail_port.p.x - e->u.tail_port.p.x) < 0)
 
772
                                        cross += e->u.xpenalty * f->u.xpenalty;
 
773
                }
 
774
                else for (j = i+1; (f = l.list[j]); j++)  {
 
775
                        if ((f->tail->u.order - e->tail->u.order) * (f->u.head_port.p.x - e->u.head_port.p.x) < 0)
 
776
                                        cross += e->u.xpenalty * f->u.xpenalty;
 
777
                }
 
778
        }
 
779
        return cross;
 
780
}
 
781
 
 
782
int rcross(graph_t* g, int r)
 
783
{
 
784
        static int *Count,C;
 
785
        int             top,bot,cross,max,i,k;
 
786
        node_t  **rtop,*v;
 
787
 
 
788
        cross = 0;
 
789
        max = 0;
 
790
        rtop = g->u.rank[r].v;
 
791
 
 
792
        if (C <= Root->u.rank[r+1].n) {
 
793
                C = Root->u.rank[r+1].n + 1;
 
794
                Count = ALLOC(C,Count,int);
 
795
        }
 
796
 
 
797
        for (i = 0; i < g->u.rank[r+1].n; i++) Count[i] = 0;
 
798
 
 
799
        for (top = 0; top < g->u.rank[r].n; top++) {
 
800
                register edge_t *e;
 
801
                if (max > 0) {
 
802
                        for (i = 0; (e = rtop[top]->u.out.list[i]); i++) {
 
803
                                for (k = e->head->u.order + 1; k <= max; k++)
 
804
                                        cross += Count[k] * e->u.xpenalty;
 
805
                        }
 
806
                }
 
807
                for (i = 0; (e = rtop[top]->u.out.list[i]); i++) {
 
808
                        register int    inv = e->head->u.order;
 
809
                        if (inv > max) max = inv;
 
810
                        Count[inv] += e->u.xpenalty;
 
811
                }
 
812
        }
 
813
        for (top = 0; top < g->u.rank[r].n; top++) {
 
814
                v = g->u.rank[r].v[top];
 
815
                if (v->u.has_port) cross += local_cross(v->u.out,1);
 
816
        }
 
817
        for (bot = 0; bot < g->u.rank[r+1].n; bot++) {
 
818
                v = g->u.rank[r+1].v[bot];
 
819
                if (v->u.has_port) cross += local_cross(v->u.in,-1);
 
820
        }
 
821
        return cross;
 
822
}
 
823
 
 
824
int ncross(graph_t* g)
 
825
{
 
826
        int             r,count,nc;
 
827
 
 
828
        g = Root;
 
829
        count = 0;
 
830
        for (r = g->u.minrank; r < g->u.maxrank; r++) {
 
831
                if (g->u.rank[r].valid) count += g->u.rank[r].cache_nc;
 
832
                else
 
833
                {
 
834
                        nc = g->u.rank[r].cache_nc = rcross(g,r);
 
835
                        count += nc;
 
836
                        g->u.rank[r].valid = TRUE;
 
837
                }
 
838
        }
 
839
        return count;
 
840
}
 
841
 
 
842
int ordercmpf(int *i0, int *i1)
 
843
{
 
844
        return (*i0) - (*i1);
 
845
}
 
846
 
 
847
int out_cross(node_t *v, node_t *w)
 
848
{
 
849
        register edge_t **e1,**e2;
 
850
        register int    inv, cross = 0,t;
 
851
 
 
852
        for (e2 = w->u.out.list; *e2; e2++) {
 
853
        register int cnt = (*e2)->u.xpenalty;
 
854
                inv = ((*e2)->head)->u.order;
 
855
 
 
856
        for (e1 = v->u.out.list; *e1; e1++) {
 
857
                        t = ((*e1)->head)->u.order - inv;
 
858
                        if ((t > 0)
 
859
                                || ((t == 0) && ((*e1)->u.head_port.p.x > (*e2)->u.head_port.p.x)))
 
860
                                        cross += (*e1)->u.xpenalty * cnt;
 
861
                }
 
862
    }
 
863
    return cross;
 
864
 
 
865
}
 
866
 
 
867
int in_cross(node_t *v,node_t *w)
 
868
{
 
869
        register edge_t **e1,**e2;
 
870
        register int    inv, cross = 0, t;
 
871
 
 
872
        for (e2 = w->u.in.list; *e2; e2++) {
 
873
        register int cnt = (*e2)->u.xpenalty;
 
874
                inv = ((*e2)->tail)->u.order;
 
875
 
 
876
        for (e1 = v->u.in.list; *e1; e1++) {
 
877
                        t = ((*e1)->tail)->u.order - inv;
 
878
                        if ((t > 0)
 
879
                                || ((t == 0) && ((*e1)->u.tail_port.p.x > (*e2)->u.tail_port.p.x)))
 
880
                                        cross += (*e1)->u.xpenalty * cnt;
 
881
                }
 
882
    }
 
883
    return cross;
 
884
}
 
885
 
 
886
#define VAL(node,port) (MC_SCALE * (node)->u.order + (port).order)
 
887
 
 
888
static boolean medians(graph_t *g, int r0, int r1)
 
889
{
 
890
        int             i,j,lm,rm,lspan,rspan,*list;
 
891
        node_t  *n,**v;
 
892
        edge_t  *e;
 
893
        boolean hasfixed = FALSE;
 
894
 
 
895
        list = TI_list;
 
896
        v = g->u.rank[r0].v;
 
897
        for (i = 0; i < g->u.rank[r0].n; i++) {
 
898
                n = v[i];
 
899
                if (r1 > r0) for (j = 0; (e = n->u.out.list[j]); j++)
 
900
                        list[j] = VAL(e->head,e->u.head_port);
 
901
                else for (j = 0; (e = n->u.in.list[j]); j++)
 
902
                        list[j] = VAL(e->tail,e->u.tail_port);
 
903
                switch(j) {
 
904
                        case 0:
 
905
                                n->u.mval = -1;
 
906
                                break;
 
907
                        case 1:
 
908
                                n->u.mval = list[0];
 
909
                                break;
 
910
                        case 2:
 
911
                                n->u.mval = (list[0] + list[1])/2;
 
912
                                break;
 
913
                        default:
 
914
                                qsort(list,j,sizeof(int),(qsort_cmpf)ordercmpf);
 
915
                                if (j % 2) n->u.mval = list[j/2];
 
916
                                else {
 
917
                                        /* weighted median */
 
918
                                        rm = j/2;
 
919
                                        lm = rm - 1;
 
920
                                        rspan = list[j-1] - list[rm];
 
921
                                        lspan = list[lm] - list[0];
 
922
                                        if (lspan == rspan)
 
923
                                                n->u.mval = (list[lm] + list[rm])/2;
 
924
                                        else {
 
925
                                                int w = list[lm]*rspan + list[rm]*lspan;
 
926
                                                n->u.mval = w / (lspan + rspan);
 
927
                                        }
 
928
                                }
 
929
                }
 
930
        }
 
931
        for (i = 0; i < g->u.rank[r0].n; i++) {
 
932
                n = v[i];
 
933
                if ((n->u.out.size == 0) && (n->u.in.size == 0))
 
934
                        hasfixed |= flat_mval(n);
 
935
        }
 
936
        return hasfixed;
 
937
}
 
938
 
 
939
int transpose_step(graph_t* g, int r, int reverse)
 
940
{
 
941
        int             i,c0,c1,rv;
 
942
        node_t  *v,*w;
 
943
 
 
944
        rv = 0;
 
945
        g->u.rank[r].candidate = FALSE;
 
946
        for (i = 0; i < g->u.rank[r].n - 1; i++) {
 
947
                v = g->u.rank[r].v[i];
 
948
                w = g->u.rank[r].v[i+1];
 
949
                assert (v->u.order < w->u.order);
 
950
                if (left2right(g,v,w)) continue;
 
951
                c0 = c1 = 0;
 
952
                if (r > 0) {
 
953
                        c0 += in_cross(v,w);
 
954
                        c1 += in_cross(w,v);
 
955
                }
 
956
                if (g->u.rank[r+1].n > 0) {
 
957
                        c0 += out_cross(v,w);
 
958
                        c1 += out_cross(w,v);
 
959
                }
 
960
                if ((c1 < c0) || ((c0 > 0) && reverse && (c1 == c0))) {
 
961
                        exchange(v,w);
 
962
                        rv += (c0 - c1);
 
963
                        g->u.rank[r].valid = FALSE;
 
964
                        g->u.rank[r].candidate = TRUE;
 
965
 
 
966
                        if (r > g->u.minrank) {
 
967
                                g->u.rank[r-1].valid = FALSE;
 
968
                                g->u.rank[r-1].candidate = TRUE;
 
969
                        }
 
970
                        if (r < g->u.maxrank) {
 
971
                                g->u.rank[r+1].valid = FALSE;
 
972
                                g->u.rank[r+1].candidate = TRUE;
 
973
                        }
 
974
                }
 
975
        }
 
976
        return rv;
 
977
}
 
978
 
 
979
void exchange(node_t *v, node_t *w)
 
980
{
 
981
        int             vi,wi,r;
 
982
                
 
983
        r = v->u.rank;
 
984
        vi = v->u.order;
 
985
        wi = w->u.order;
 
986
        v->u.order = wi;
 
987
        Root->u.rank[r].v[wi] = v;
 
988
        w->u.order = vi;
 
989
        Root->u.rank[r].v[vi] = w;
 
990
}
 
991
 
 
992
void reorder(graph_t *g, int r, int reverse, int hasfixed)
 
993
{
 
994
        int             changed = 0, nelt;
 
995
        boolean muststay,sawclust;
 
996
        node_t  **vlist = g->u.rank[r].v;
 
997
        node_t  **lp,**rp,**ep = vlist + g->u.rank[r].n;
 
998
 
 
999
        for (nelt = g->u.rank[r].n - 1; nelt >= 0; nelt--) {
 
1000
                lp = vlist;
 
1001
                while (lp  < ep) {
 
1002
                        /* find leftmost node that can be compared */
 
1003
                        while ((lp < ep) && ((*lp)->u.mval < 0)) lp++;
 
1004
                        if (lp >= ep) break;
 
1005
                        /* find the node that can be compared */
 
1006
                        sawclust = muststay = FALSE;
 
1007
                        for (rp = lp + 1; rp < ep; rp++) {
 
1008
                                if (sawclust && (*rp)->u.clust) continue;       /* ### */
 
1009
                                if (left2right(g,*lp,*rp)) { muststay = TRUE; break; }
 
1010
                                if ((*rp)->u.mval >= 0) break;
 
1011
                                if ((*rp)->u.clust) sawclust = TRUE; /* ### */
 
1012
                        }
 
1013
                        if (rp >= ep) break;
 
1014
                        if (muststay == FALSE) {
 
1015
                                register int    p1 = ((*lp)->u.mval);
 
1016
                                register int    p2 = ((*rp)->u.mval);
 
1017
                                if ((p1 > p2) || ((p1 == p2) && (reverse))) {
 
1018
                                        exchange(*lp,*rp);
 
1019
                                        changed++;
 
1020
                                }
 
1021
                        }
 
1022
                        lp = rp;
 
1023
                }
 
1024
                if ((hasfixed == FALSE) && (reverse == FALSE)) ep--;
 
1025
        }
 
1026
 
 
1027
        if (changed) {
 
1028
                g->u.rank[r].valid = FALSE;
 
1029
                if (r > 0) g->u.rank[r-1].valid = FALSE;
 
1030
        }
 
1031
}
 
1032
 
 
1033
static int nodeposcmpf(node_t **n0, node_t **n1)
 
1034
{
 
1035
        return ((*n0)->u.order - (*n1)->u.order);
 
1036
}
 
1037
 
 
1038
static int edgeidcmpf(edge_t **e0, edge_t **e1)
 
1039
{
 
1040
        return ((*e0)->id - (*e1)->id);
 
1041
}
 
1042
 
 
1043
/* following code deals with weights of edges of "virtual" nodes */
 
1044
#define ORDINARY        0
 
1045
#define SINGLETON       1
 
1046
#define VIRTUALNODE     2
 
1047
#define NTYPES          3
 
1048
 
 
1049
#define C_EE            1
 
1050
#define C_VS            2
 
1051
#define C_SS            2
 
1052
#define C_VV            4
 
1053
 
 
1054
static int table[NTYPES][NTYPES] = {
 
1055
        /* ordinary */          {C_EE, C_EE, C_EE},
 
1056
        /* singleton */         {C_EE, C_SS, C_VS},
 
1057
        /* virtual */           {C_EE, C_VS, C_VV}
 
1058
};
 
1059
 
 
1060
static int endpoint_class(node_t* n)
 
1061
{
 
1062
        if (n->u.node_type == VIRTUAL) return VIRTUALNODE;
 
1063
        if (n->u.weight_class <= 1) return SINGLETON;
 
1064
        return ORDINARY;
 
1065
}
 
1066
 
 
1067
void virtual_weight(edge_t* e)
 
1068
{
 
1069
        int t;
 
1070
        t = table[endpoint_class(e->tail)][endpoint_class(e->head)];
 
1071
        e->u.weight *= t;
 
1072
}
 
1073
 
 
1074
void ordered_edges(graph_t* g)
 
1075
{
 
1076
        char            *ordering;
 
1077
 
 
1078
        ordering = agget(g,"ordering");
 
1079
        if (ordering && streq(ordering,"out")) do_ordering(g);
 
1080
        else {
 
1081
                        /* search meta-graph to find subgraphs that may be ordered */
 
1082
                graph_t         *mg,*subg;
 
1083
                node_t          *mm,*mn;
 
1084
                edge_t          *me;
 
1085
 
 
1086
                mm = g->meta_node;
 
1087
                mg = mm->graph;
 
1088
                for (me = agfstout(mg,mm); me; me = agnxtout(mg,me)) {
 
1089
                        mn = me->head;
 
1090
                        subg = agusergraph(mn);
 
1091
                                /* clusters are processed by seperate calls to ordered_edges */
 
1092
                        if (!is_cluster(subg)) ordered_edges(subg);
 
1093
                }
 
1094
        }
 
1095
}
 
1096
 
 
1097
/* creates flat edges for ordered edges of g.
 
1098
 * follows virtual edge chains where necessary.
 
1099
 */
 
1100
void do_ordering(graph_t* g)
 
1101
{
 
1102
        int                     i,j,ri,ne,ei,nranks;
 
1103
        node_t          *n,**lpath,**rpath,*u,*v;
 
1104
        edge_t          *e,*f,*le,*re,**sortlist;
 
1105
 
 
1106
        sortlist = TE_list;
 
1107
        lpath = rpath = NULL;
 
1108
 
 
1109
        nranks = g->root->u.maxrank - g->root->u.minrank + 2;
 
1110
        lpath = N_NEW(nranks,node_t*); rpath = N_NEW(nranks,node_t*);
 
1111
 
 
1112
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
1113
                if (n->u.clust) continue;
 
1114
                le = NULL;
 
1115
 
 
1116
                        /* make a list of the forward edges */
 
1117
                for (ne = 0, e = agfstout(g,n); e; e = agnxtout(g,e)) {
 
1118
                        if (e->head->u.clust) continue;
 
1119
                        if (e->head->u.rank > e->tail->u.rank) sortlist[ne++] = e;
 
1120
                }
 
1121
 
 
1122
                if (ne == 0) continue;
 
1123
                qsort(sortlist,ne,sizeof(sortlist[0]),(qsort_cmpf)edgeidcmpf);
 
1124
                for (ei = 0; ei < ne; ei++) {
 
1125
                        e = sortlist[ei];
 
1126
                        for (re = e; re->u.to_virt; re = re->u.to_virt);
 
1127
 
 
1128
                        /* get path of right edge */
 
1129
                        ri = 0;
 
1130
                        while (ri < nranks) {
 
1131
                                rpath[ri++] = re->head;
 
1132
                                if (re->head->u.node_type == NORMAL) break;
 
1133
                                if (re->head->u.out.size != 1) break;
 
1134
                                re = re->head->u.out.list[0];
 
1135
                        }
 
1136
                        rpath[ri] = NULL;
 
1137
 
 
1138
                        if (le) {
 
1139
                                for (i = 0; i < ri; i++) {
 
1140
                                        if (lpath[i] == NULL) break;
 
1141
                                        u = lpath[i]; v = rpath[i];
 
1142
                                        f = NULL;
 
1143
                                        if ((u->u.node_type == NORMAL)
 
1144
                                                && (v->u.node_type == NORMAL)) {
 
1145
                                                        for (j = 0; (f = u->u.flat_out.list[j]); j++)
 
1146
                                                                if (f->head == v) break;
 
1147
                                        }
 
1148
                                        if (f != NULL) break;
 
1149
                                        f = new_virtual_edge(UF_find(lpath[i]),rpath[i],NULL);
 
1150
                                        f->u.edge_type = FLATORDER;
 
1151
                                        flat_edge(g,f);
 
1152
                                }
 
1153
                        }
 
1154
 
 
1155
                        le = re;
 
1156
                        for (i = 0; i <= ri; i++) lpath[i] = rpath[i];
 
1157
                }
 
1158
        }
 
1159
        if (lpath) { free(lpath); free(rpath); }
 
1160
}
 
1161
 
 
1162
/* merges the connected components of g */
 
1163
void merge_components(graph_t* g)
 
1164
{
 
1165
        int             c;
 
1166
        node_t  *u,*v;
 
1167
 
 
1168
        if (g->u.comp.size <= 1) return;
 
1169
        u = NULL;
 
1170
        for (c = 0; c < g->u.comp.size; c++) {
 
1171
                v = g->u.comp.list[c];
 
1172
                if (u) u->u.next = v;
 
1173
                v->u.prev = u;
 
1174
                while (v->u.next) {
 
1175
                        v = v->u.next;
 
1176
                }
 
1177
                u = v;
 
1178
        }
 
1179
        g->u.comp.size = 1;
 
1180
        g->u.nlist = g->u.comp.list[0];
 
1181
        g->u.minrank = GlobalMinRank;
 
1182
        g->u.maxrank = GlobalMaxRank;
 
1183
}
 
1184
 
 
1185
#ifdef DEBUG
 
1186
void check_rs(graph_t* g, int null_ok)
 
1187
{
 
1188
        int             i,r;
 
1189
        node_t  *v,*prev;
 
1190
 
 
1191
fprintf(stderr,"\n\n%s:\n",g->name);
 
1192
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
1193
fprintf(stderr,"%d: ",r);
 
1194
                prev = NULL;
 
1195
                for (i = 0; i < g->u.rank[r].n; i++) {
 
1196
                        v = g->u.rank[r].v[i];
 
1197
                        if (v == NULL) {
 
1198
fprintf(stderr,"NULL\t");
 
1199
                                if(null_ok==FALSE)abort();
 
1200
                        }
 
1201
                        else {
 
1202
fprintf(stderr,"%s\t",v->name);
 
1203
                                assert(v->u.rank == r);
 
1204
                                assert(v != prev);
 
1205
                                prev = v;
 
1206
                        }
 
1207
                }
 
1208
fprintf(stderr,"\n");
 
1209
        }
 
1210
}
 
1211
 
 
1212
void check_order(void)
 
1213
{
 
1214
        int             i,r;
 
1215
        node_t  *v;
 
1216
        graph_t *g = Root;
 
1217
 
 
1218
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
1219
                assert(g->u.rank[r].v[g->u.rank[r].n] == NULL);
 
1220
                for (i = 0; v = g->u.rank[r].v[i]; i++)
 
1221
                        assert (v->u.order == i);
 
1222
        }
 
1223
}
 
1224
#endif
 
1225
 
 
1226
static void mincross_options(graph_t* g)
 
1227
{
 
1228
        char    *p;
 
1229
        double  f;
 
1230
 
 
1231
        /* set default values */
 
1232
        MinQuit = 8;
 
1233
        MaxIter = 24;
 
1234
        Convergence = .995;
 
1235
 
 
1236
        p = agget(g,"mclimit");
 
1237
        if (p && ((f = atof(p)) > 0.0)) {
 
1238
                MinQuit = MAX(1,MinQuit * f);
 
1239
                MaxIter = MAX(1,MaxIter * f);
 
1240
        }
 
1241
}
 
1242
 
 
1243
int flat_mval(node_t* n)
 
1244
{
 
1245
        int             i;
 
1246
        edge_t  *e,**fl;
 
1247
        node_t  *nn;
 
1248
 
 
1249
        if ((n->u.in.size == 0) && (n->u.out.size == 0)) {
 
1250
                if (n->u.flat_in.size > 0) {
 
1251
                        fl = n->u.flat_in.list;
 
1252
                        nn = fl[0]->tail;
 
1253
                        for (i = 1; (e = fl[i]); i++)
 
1254
                                if (e->tail->u.order > nn->u.order) nn = e->tail;
 
1255
                        n->u.mval = nn->u.mval + 1;
 
1256
                        return FALSE;
 
1257
                }
 
1258
                else if (n->u.flat_out.size > 0) {
 
1259
                        fl = n->u.flat_out.list;
 
1260
                        nn = fl[0]->head;
 
1261
                        for (i = 1; (e = fl[i]); i++)
 
1262
                                if (e->head->u.order < nn->u.order) nn = e->head;
 
1263
                        n->u.mval = nn->u.mval - 1;
 
1264
                        return FALSE;
 
1265
                }
 
1266
        }
 
1267
        return TRUE;
 
1268
}
 
1269
 
 
1270
#ifdef DEBUG
 
1271
void check_exchange(node_t *v, node_t *w)
 
1272
{
 
1273
        int             i,r;
 
1274
        node_t  *u;
 
1275
 
 
1276
        if ((v->u.clust == NULL) && (w->u.clust == NULL)) return;
 
1277
        assert ((v->u.clust == NULL) || (w->u.clust == NULL));
 
1278
        assert(v->u.rank == w->u.rank);
 
1279
        assert(v->u.order < w->u.order);
 
1280
        r = v->u.rank;
 
1281
 
 
1282
        for (i = v->u.order + 1; i < w->u.order; i++) {
 
1283
                u = v->graph->u.rank[r].v[i];
 
1284
                if (u->u.clust) abort();
 
1285
        }
 
1286
}
 
1287
 
 
1288
void check_vlists(graph_t* g)
 
1289
{
 
1290
        int             c,i,j,r;
 
1291
        node_t  *u;
 
1292
 
 
1293
        for (r = g->u.minrank; r <= g->u.maxrank; r++) {
 
1294
                for (i = 0; i < g->u.rank[r].n; i++) {
 
1295
                        u = g->u.rank[r].v[i];
 
1296
                        j = u->u.order;
 
1297
                        assert (Root->u.rank[r].v[j] == u);
 
1298
                }
 
1299
                if (g->u.rankleader) {
 
1300
                        u = g->u.rankleader[r];
 
1301
                        j = u->u.order;
 
1302
                        assert (Root->u.rank[r].v[j] == u);
 
1303
                }
 
1304
        }
 
1305
        for (c = 1; c <= g->u.n_cluster; c++)
 
1306
                check_vlists(g->u.clust[c]);
 
1307
}
 
1308
 
 
1309
void node_in_root_vlist(node_t* n)
 
1310
{
 
1311
        node_t  **vptr;
 
1312
 
 
1313
        for (vptr = Root->u.rank[n->u.rank].v; *vptr; vptr++)
 
1314
                if (*vptr == n) break;
 
1315
        if (*vptr == 0) abort();
 
1316
}
 
1317
#endif  /* DEBUG code */