← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dag/uvcross.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:
dag/uvcross.c
 
1
#include <dag.h>
 
2
 
 
3
#ifdef DMALLOC
 
4
#include "dmalloc.h"
 
5
#endif
 
6
 
 
7
int dd_uvcross(Agnode_t *v, Agnode_t *w, int use_in, int use_out)
 
8
{
 
9
        Agedge_t        *e, *f;
 
10
        int                     v_inv,w_inv;
 
11
        int                     cross = 0;
 
12
 
 
13
        if (use_in) for (e = agfstin(w); e; e = agnxtin(e)) {
 
14
                w_inv = dd_order(e->node);
 
15
                for (f = agfstin(v); f; f = agnxtin(f)) {
 
16
                        v_inv = dd_order(f->node);
 
17
                        if (v_inv > w_inv) cross++;
 
18
                }
 
19
        }
 
20
 
 
21
        if (use_out) for (e = agfstout(w); e; e = agnxtout(e)) {
 
22
                w_inv = dd_order(e->node);
 
23
                for (f = agfstout(v); f; f = agnxtout(f)) {
 
24
                        v_inv = dd_order(f->node);
 
25
                        if (v_inv > w_inv) cross++;
 
26
                }
 
27
        }
 
28
    return cross;
 
29
}
 
30
 
 
31
#define dd_xpenalty(e) 1                /* edge crossing coefficient of e */
 
32
 
 
33
int dd_ncross(ddview_t *view)
 
34
{
 
35
        int             i, k, r, cross, max, *count;
 
36
        Agnode_t        *v;
 
37
        Agedge_t        *e;
 
38
        rank_t          *rd;
 
39
 
 
40
        cross = 0;
 
41
 
 
42
        for (r = view->config->low; r < view->config->high; r++) {
 
43
                rd = dd_rankd(view,r);
 
44
 
 
45
                k = dd_rankd(view,r+1)->n + 1;
 
46
                count = malloc(k * sizeof(count[0]));
 
47
                for (i = 0; i < k; i++) count[i] = 0;
 
48
 
 
49
                max = 0;
 
50
                for (i = 0; i < rd->n; i++) {
 
51
                        v = rd->v[i];
 
52
                        if (max > 0) {
 
53
                                for (e = agfstout(v); e; e = agnxtout(e)) {
 
54
                                        for (k = dd_order(e->node) + 1; k <= max; k++)
 
55
                                                cross += count[k] * dd_xpenalty(e);
 
56
                                }
 
57
                        }
 
58
 
 
59
                        for (e = agfstout(v); e; e = agnxtout(e)) {
 
60
                                int    inv = dd_order(e->node);
 
61
                                if (inv > max) max = inv;
 
62
                                count[inv] += dd_xpenalty(e);
 
63
                        }
 
64
                }
 
65
                free(count);
 
66
        }
 
67
        return cross;
 
68
}