← Back to branch summary

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

« back to all changes in this revision

Viewing changes to dotneato/dotgen/class1.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/class1.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
 * Classify edges for rank assignment phase to
 
14
 * create temporary edges.
 
15
 */
 
16
 
 
17
#include "dot.h"
 
18
 
 
19
#ifdef DMALLOC
 
20
#include "dmalloc.h"
 
21
#endif
 
22
 
 
23
int nonconstraint_edge(edge_t* e)
 
24
{
 
25
        char    *constr;
 
26
 
 
27
        if (E_constr && (constr = agxget(e,E_constr->index))) {
 
28
                if (constr[0] && mapbool(constr) == FALSE) return TRUE;
 
29
        }
 
30
        return FALSE;
 
31
}
 
32
 
 
33
void class1(graph_t* g)
 
34
{
 
35
        node_t  *n,*t,*h;
 
36
        edge_t  *e,*rep;
 
37
 
 
38
        mark_clusters(g);
 
39
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
40
                for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
 
41
 
 
42
                                /* skip edges already processed */
 
43
                        if (e->u.to_virt) continue;
 
44
 
 
45
                                /* skip edges that we want to ignore in this phase */
 
46
                        if (nonconstraint_edge(e)) continue;
 
47
 
 
48
                        t = UF_find(e->tail);
 
49
                        h = UF_find(e->head);
 
50
 
 
51
                                /* skip self, flat, and intra-cluster edges */
 
52
                        if (t == h) continue;
 
53
 
 
54
 
 
55
                                /* inter-cluster edges require special treatment */
 
56
                        if (t->u.clust || h->u.clust) {
 
57
                                interclust1(g,e->tail,e->head,e);
 
58
                                continue;
 
59
                        }
 
60
 
 
61
                        if ((rep = find_fast_edge(t,h))) merge_oneway(e,rep);
 
62
                        else virtual_edge(t,h,e);
 
63
 
 
64
#ifdef NOTDEF
 
65
                        if ((t == e->tail) && (h == e->head)) {
 
66
                        if (rep = find_fast_edge(t,h)) merge_oneway(e,rep);
 
67
                        else virtual_edge(t,h,e);
 
68
                        }
 
69
                        else {
 
70
                                f = agfindedge(g,t,h);
 
71
                                if (f && (f->u.to_virt == NULL)) rep = virtual_edge(t,h,f);
 
72
                                else rep = find_fast_edge(t,h);
 
73
                                if (rep) merge_oneway(e,rep);
 
74
                                else virtual_edge(t,h,e);
 
75
                        }
 
76
#endif
 
77
                }
 
78
        }
 
79
}
 
80
 
 
81
void interclust1(graph_t *g, node_t *t, node_t *h, edge_t *e)
 
82
{
 
83
        node_t          *v,*t0,*h0;
 
84
        int                     offset,t_len,h_len,t_rank,h_rank;
 
85
        edge_t          *rt,*rh;
 
86
 
 
87
        if (e->tail->u.clust)
 
88
                t_rank = e->tail->u.rank - e->tail->u.clust->u.leader->u.rank;
 
89
        else t_rank = 0;
 
90
        if (e->head->u.clust)
 
91
                h_rank = e->head->u.rank - e->head->u.clust->u.leader->u.rank;
 
92
        else h_rank = 0;
 
93
        offset = e->u.minlen + t_rank - h_rank;
 
94
        if (offset > 0) {t_len = 0; h_len = offset;}
 
95
        else {t_len = -offset; h_len = 0;}
 
96
 
 
97
        v = virtual_node(g);
 
98
        v->u.node_type = SLACKNODE;
 
99
        t0 = UF_find(t); h0 = UF_find(h);
 
100
        rt = make_aux_edge(v,t0,t_len,CL_BACK*e->u.weight);
 
101
        rh = make_aux_edge(v,h0,h_len,e->u.weight);
 
102
        rt->u.to_orig = rh->u.to_orig = e;
 
103
}