Graphviz 13.1.1~dev.20250702.1101
Loading...
Searching...
No Matches
class2.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11
12/* classify edges for mincross/nodepos/splines, using given ranks */
13
14#include <dotgen/dot.h>
15#include <stdbool.h>
16#include <stdlib.h>
17#include <util/alloc.h>
18#include <util/gv_math.h>
19
20static node_t*
22{
23 const pointf dimen = ED_label(orig)->dimen;
24 node_t *const v = virtual_node(g);
25 ND_label(v) = ED_label(orig);
26 ND_lw(v) = GD_nodesep(agroot(v));
27 if (!ED_label_ontop(orig)) {
28 if (GD_flip(agroot(g))) {
29 ND_ht(v) = dimen.x;
30 ND_rw(v) = dimen.y;
31 } else {
32 ND_ht(v) = dimen.y;
33 ND_rw(v) = dimen.x;
34 }
35 }
36 return v;
37}
38
39static void
41{
42 int width = GD_nodesep(g) / 2;
43 ND_lw(v) += width;
44 ND_rw(v) += width;
45}
46
48 node_t *const v = virtual_node(g);
49 incr_width(g, v);
50 return v;
51}
52
53static node_t *leader_of(node_t * v) {
54 graph_t *clust;
55 node_t *rv;
56
57 if (ND_ranktype(v) != CLUSTER) {
58 rv = UF_find(v);
59 } else {
60 clust = ND_clust(v);
61 rv = GD_rankleader(clust)[ND_rank(v)];
62 }
63 return rv;
64}
65
67static void
68make_chain(graph_t * g, node_t * from, node_t * to, edge_t * orig)
69{
70 int r, label_rank;
71 node_t *u, *v;
72 edge_t *e;
73
74 u = from;
75 if (ED_label(orig))
76 label_rank = (ND_rank(from) + ND_rank(to)) / 2;
77 else
78 label_rank = -1;
79 assert(ED_to_virt(orig) == NULL);
80 for (r = ND_rank(from) + 1; r <= ND_rank(to); r++) {
81 if (r < ND_rank(to)) {
82 if (r == label_rank)
83 v = label_vnode(g, orig);
84 else
85 v = plain_vnode(g);
86 ND_rank(v) = r;
87 } else
88 v = to;
89 e = virtual_edge(u, v, orig);
91 u = v;
92 }
93 assert(ED_to_virt(orig) != NULL);
94}
95
96static void
98{
99 node_t *t, *h;
100 edge_t *ve;
101
102 t = leader_of(agtail(e));
103 h = leader_of(aghead(e));
104 if (ND_rank(t) > ND_rank(h)) {
105 SWAP(&t, &h);
106 }
107 if (ND_clust(t) != ND_clust(h)) {
108 if ((ve = find_fast_edge(t, h))) {
109 merge_chain(g, e, ve, true);
110 return;
111 }
112 if (ND_rank(t) == ND_rank(h))
113 return;
114 make_chain(g, t, h, e);
115
116 /* mark as cluster edge */
117 for (ve = ED_to_virt(e); ve && ND_rank(aghead(ve)) <= ND_rank(h);
118 ve = ND_out(aghead(ve)).list[0])
120 }
121 /* else ignore intra-cluster edges at this point */
122}
123
124static bool is_cluster_edge(edge_t *e) {
125 return ND_ranktype(agtail(e)) == CLUSTER || ND_ranktype(aghead(e)) == CLUSTER;
126}
127
128void merge_chain(graph_t *g, edge_t *e, edge_t *f, bool update_count) {
129 edge_t *rep;
130 int lastrank = MAX(ND_rank(agtail(e)), ND_rank(aghead(e)));
131
132 assert(ED_to_virt(e) == NULL);
133 ED_to_virt(e) = f;
134 rep = f;
135 do {
136 /* interclust multi-edges are not counted now */
137 if (update_count)
138 ED_count(rep) += ED_count(e);
139 ED_xpenalty(rep) += ED_xpenalty(e);
140 ED_weight(rep) += ED_weight(e);
141 if (ND_rank(aghead(rep)) == lastrank)
142 break;
143 incr_width(g, aghead(rep));
144 rep = ND_out(aghead(rep)).list[0];
145 } while (rep);
146}
147
148bool mergeable(edge_t *e, edge_t *f) {
149 return e && f && agtail(e) == agtail(f) && aghead(e) == aghead(f) &&
150 ED_label(e) == ED_label(f) && ports_eq(e, f);
151}
152
154{
155 int c;
156 node_t *n, *t, *h;
157 edge_t *e, *prev, *opp;
158
159 GD_nlist(g) = NULL;
160
161 mark_clusters(g);
162 for (c = 1; c <= GD_n_cluster(g); c++)
163 build_skeleton(g, GD_clust(g)[c]);
164 for (n = agfstnode(g); n; n = agnxtnode(g, n))
165 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
166 if (ND_weight_class(aghead(e)) <= 2)
168 if (ND_weight_class(agtail(e)) <= 2)
170 }
171
172 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
173 if (ND_clust(n) == NULL && n == UF_find(n)) {
174 fast_node(g, n);
175 }
176 prev = NULL;
177 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
178
179 /* already processed */
180 if (ED_to_virt(e)) {
181 prev = e;
182 continue;
183 }
184
185 /* edges involving sub-clusters of g */
186 if (is_cluster_edge(e)) {
187 /* following is new cluster multi-edge code */
188 if (mergeable(prev, e)) {
189 if (ED_to_virt(prev)) {
190 merge_chain(g, e, ED_to_virt(prev), false);
191 other_edge(e);
192 } else if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
193 merge_oneway(e, prev);
194 other_edge(e);
195 }
196 /* else is an intra-cluster edge */
197 continue;
198 }
199 interclrep(g, e);
200 prev = e;
201 continue;
202 }
203 /* merge multi-edges */
204 if (prev && agtail(e) == agtail(prev) && aghead(e) == aghead(prev)) {
205 if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
206 merge_oneway(e, prev);
207 other_edge(e);
208 continue;
209 }
210 if (ED_label(e) == NULL && ED_label(prev) == NULL
211 && ports_eq(e, prev)) {
212 if (Concentrate)
214 else {
215 merge_chain(g, e, ED_to_virt(prev), true);
216 other_edge(e);
217 }
218 continue;
219 }
220 /* parallel edges with different labels fall through here */
221 }
222
223 /* self edges */
224 if (agtail(e) == aghead(e)) {
225 other_edge(e);
226 prev = e;
227 continue;
228 }
229
230 t = UF_find(agtail(e));
231 h = UF_find(aghead(e));
232
233 /* non-leader leaf nodes */
234 if (agtail(e) != t || aghead(e) != h) {
235 /* FIX need to merge stuff */
236 continue;
237 }
238
239
240 /* flat edges */
241 if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
242 flat_edge(g, e);
243 prev = e;
244 continue;
245 }
246
247 /* forward edges */
248 if (ND_rank(aghead(e)) > ND_rank(agtail(e))) {
249 make_chain(g, agtail(e), aghead(e), e);
250 prev = e;
251 continue;
252 }
253
254 /* backward edges */
255 else {
256 /* avoid when opp==e in undirected graph */
257 for (opp = agfstout(g, aghead(e)); opp != NULL; opp = agnxtout(g, opp)) {
258 if (aghead(opp) != agtail(e) || aghead(opp) == aghead(e) ||
259 ED_edge_type(opp) == IGNORED) {
260 continue;
261 }
262 /* shadows a forward edge */
263 if (ED_to_virt(opp) == NULL)
264 make_chain(g, agtail(opp), aghead(opp), opp);
265 if (ED_label(e) == NULL && ED_label(opp) == NULL
266 && ports_eq(e, opp)) {
267 if (Concentrate) {
269 ED_conc_opp_flag(opp) = true;
270 } else { /* see above. this is getting out of hand */
271 other_edge(e);
272 merge_chain(g, e, ED_to_virt(opp), true);
273 }
274 break;
275 }
276 }
277 if (opp != NULL) {
278 continue;
279 }
280 make_chain(g, aghead(e), agtail(e), e);
281 prev = e;
282 }
283 }
284 }
285 /* since decompose() is not called on subgraphs */
286 if (g != dot_root(g)) {
287 free(GD_comp(g).list);
288 GD_comp(g).list = gv_alloc(sizeof(node_t *));
289 GD_comp(g).list[0] = GD_nlist(g);
290 }
291}
292
Memory allocation wrappers that exit on failure.
static void * gv_alloc(size_t size)
Definition alloc.h:47
static void make_chain(graph_t *g, node_t *from, node_t *to, edge_t *orig)
create chain of dummy nodes for edge orig
Definition class2.c:68
void merge_chain(graph_t *g, edge_t *e, edge_t *f, bool update_count)
Definition class2.c:128
static void interclrep(graph_t *g, edge_t *e)
Definition class2.c:97
static node_t * leader_of(node_t *v)
Definition class2.c:53
static node_t * plain_vnode(graph_t *g)
Definition class2.c:47
static bool is_cluster_edge(edge_t *e)
Definition class2.c:124
void class2(graph_t *g)
Definition class2.c:153
bool mergeable(edge_t *e, edge_t *f)
Definition class2.c:148
static node_t * label_vnode(graph_t *g, edge_t *orig)
Definition class2.c:21
static void incr_width(graph_t *g, node_t *v)
Definition class2.c:40
node_t * UF_find(node_t *n)
Definition utils.c:100
#define IGNORED
Definition const.h:30
#define CLUSTER_EDGE
Definition const.h:29
#define CLUSTER
Definition const.h:40
Agraph_t * dot_root(void *p)
Definition dotinit.c:525
void other_edge(Agedge_t *)
Definition fastgr.c:114
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition fastgr.c:168
void virtual_weight(Agedge_t *)
Definition mincross.c:1819
void flat_edge(Agraph_t *, Agedge_t *)
Definition fastgr.c:213
void fast_node(Agraph_t *, Agnode_t *)
Definition fastgr.c:173
void merge_oneway(Agedge_t *, Agedge_t *)
Definition fastgr.c:287
int ports_eq(edge_t *, edge_t *)
Definition position.c:1008
Agedge_t * find_fast_edge(Agnode_t *, Agnode_t *)
Definition fastgr.c:41
Agnode_t * virtual_node(Agraph_t *)
Definition fastgr.c:198
bool Concentrate
Definition globals.h:59
void free(void *)
node NULL
Definition grammar.y:181
#define ED_conc_opp_flag(e)
Definition types.h:579
#define ED_label_ontop(e)
Definition types.h:591
#define ED_xpenalty(e)
Definition types.h:601
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
#define ED_count(e)
Definition types.h:580
#define agtail(e)
Definition cgraph.h:988
#define ED_edge_type(e)
Definition types.h:582
#define ED_weight(e)
Definition types.h:603
#define aghead(e)
Definition cgraph.h:989
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
#define ED_label(e)
Definition types.h:589
#define ED_to_virt(e)
Definition types.h:599
#define GD_clust(g)
Definition types.h:360
#define GD_nlist(g)
Definition types.h:393
#define GD_n_cluster(g)
Definition types.h:389
#define GD_comp(g)
Definition types.h:362
#define GD_nodesep(g)
Definition types.h:394
#define GD_flip(g)
Definition types.h:378
#define GD_rankleader(g)
Definition types.h:396
#define ND_rank(n)
Definition types.h:523
#define ND_ht(n)
Definition types.h:500
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
#define ND_clust(n)
Definition types.h:489
#define ND_label(n)
Definition types.h:502
#define ND_rw(n)
Definition types.h:525
#define ND_lw(n)
Definition types.h:506
#define ND_weight_class(n)
Definition types.h:535
#define ND_ranktype(n)
Definition types.h:524
#define ND_out(n)
Definition types.h:515
Agraph_t * agroot(void *obj)
Definition obj.c:168
Arithmetic helper functions.
#define SWAP(a, b)
Definition gv_math.h:131
$2 u p prev
Definition htmlparse.y:297
void build_skeleton(graph_t *g, graph_t *subg)
Definition cluster.c:343
void mark_clusters(graph_t *g)
Definition cluster.c:299
graph or subgraph
Definition cgraph.h:424
double x
Definition geom.h:29
double y
Definition geom.h:29
#define MAX(a, b)
Definition write.c:32