1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14
15/*
16 * Classify edges for rank assignment phase to
17 * create temporary edges.
18 */
19
20#include "dot.h"
21
22
23int nonconstraint_edge(edge_t * e)
24{
25 char *constr;
26
27 if (E_constr && (constr = agxget(e, E_constr))) {
28 if (constr[0] && mapbool(constr) == FALSE)
29 return TRUE;
30 }
31 return FALSE;
32}
33
34static void
35interclust1(graph_t * g, node_t * t, node_t * h, edge_t * e)
36{
37 node_t *v, *t0, *h0;
38 int offset, t_len, h_len, t_rank, h_rank;
39 edge_t *rt, *rh;
40
41 if (ND_clust(agtail(e)))
42 t_rank = ND_rank(agtail(e)) - ND_rank(GD_leader(ND_clust(agtail(e))));
43 else
44 t_rank = 0;
45 if (ND_clust(aghead(e)))
46 h_rank = ND_rank(aghead(e)) - ND_rank(GD_leader(ND_clust(aghead(e))));
47 else
48 h_rank = 0;
49 offset = ED_minlen(e) + t_rank - h_rank;
50 if (offset > 0) {
51 t_len = 0;
52 h_len = offset;
53 } else {
54 t_len = -offset;
55 h_len = 0;
56 }
57
58 v = virtual_node(g);
59 ND_node_type(v) = SLACKNODE;
60 t0 = UF_find(t);
61 h0 = UF_find(h);
62 rt = make_aux_edge(v, t0, t_len, CL_BACK * ED_weight(e));
63 rh = make_aux_edge(v, h0, h_len, ED_weight(e));
64 ED_to_orig(rt) = ED_to_orig(rh) = e;
65}
66void class1(graph_t * g)
67{
68 node_t *n, *t, *h;
69 edge_t *e, *rep;
70
71 mark_clusters(g);
72 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
73 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
74
75 /* skip edges already processed */
76 if (ED_to_virt(e))
77 continue;
78
79 /* skip edges that we want to ignore in this phase */
80 if (nonconstraint_edge(e))
81 continue;
82
83 t = UF_find(agtail(e));
84 h = UF_find(aghead(e));
85
86 /* skip self, flat, and intra-cluster edges */
87 if (t == h)
88 continue;
89
90
91 /* inter-cluster edges require special treatment */
92 if (ND_clust(t) || ND_clust(h)) {
93 interclust1(g, agtail(e), aghead(e), e);
94 continue;
95 }
96
97 if ((rep = find_fast_edge(t, h)))
98 merge_oneway(e, rep);
99 else
100 virtual_edge(t, h, e);
101
102#ifdef NOTDEF
103 if ((t == agtail(e)) && (h == aghead(e))) {
104 if (rep = find_fast_edge(t, h))
105 merge_oneway(e, rep);
106 else
107 virtual_edge(t, h, e);
108 } else {
109 f = agfindedge(g, t, h);
110 if (f && (ED_to_virt(f) == NULL))
111 rep = virtual_edge(t, h, f);
112 else
113 rep = find_fast_edge(t, h);
114 if (rep)
115 merge_oneway(e, rep);
116 else
117 virtual_edge(t, h, e);
118 }
119#endif
120 }
121 }
122}
123
124