Graphviz 13.1.0~dev.20250626.0830
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 node_t *v;
24 pointf dimen;
25
26 dimen = ED_label(orig)->dimen;
27 v = virtual_node(g);
28 ND_label(v) = ED_label(orig);
29 ND_lw(v) = GD_nodesep(agroot(v));
30 if (!ED_label_ontop(orig)) {
31 if (GD_flip(agroot(g))) {
32 ND_ht(v) = dimen.x;
33 ND_rw(v) = dimen.y;
34 } else {
35 ND_ht(v) = dimen.y;
36 ND_rw(v) = dimen.x;
37 }
38 }
39 return v;
40}
41
42static void
44{
45 int width = GD_nodesep(g) / 2;
46 ND_lw(v) += width;
47 ND_rw(v) += width;
48}
49
51 node_t *v;
52 v = virtual_node(g);
53 incr_width(g, v);
54 return v;
55}
56
57static node_t *leader_of(node_t * v) {
58 graph_t *clust;
59 node_t *rv;
60
61 if (ND_ranktype(v) != CLUSTER) {
62 rv = UF_find(v);
63 } else {
64 clust = ND_clust(v);
65 rv = GD_rankleader(clust)[ND_rank(v)];
66 }
67 return rv;
68}
69
71static void
72make_chain(graph_t * g, node_t * from, node_t * to, edge_t * orig)
73{
74 int r, label_rank;
75 node_t *u, *v;
76 edge_t *e;
77
78 u = from;
79 if (ED_label(orig))
80 label_rank = (ND_rank(from) + ND_rank(to)) / 2;
81 else
82 label_rank = -1;
83 assert(ED_to_virt(orig) == NULL);
84 for (r = ND_rank(from) + 1; r <= ND_rank(to); r++) {
85 if (r < ND_rank(to)) {
86 if (r == label_rank)
87 v = label_vnode(g, orig);
88 else
89 v = plain_vnode(g);
90 ND_rank(v) = r;
91 } else
92 v = to;
93 e = virtual_edge(u, v, orig);
95 u = v;
96 }
97 assert(ED_to_virt(orig) != NULL);
98}
99
100static void
102{
103 node_t *t, *h;
104 edge_t *ve;
105
106 t = leader_of(agtail(e));
107 h = leader_of(aghead(e));
108 if (ND_rank(t) > ND_rank(h)) {
109 SWAP(&t, &h);
110 }
111 if (ND_clust(t) != ND_clust(h)) {
112 if ((ve = find_fast_edge(t, h))) {
113 merge_chain(g, e, ve, true);
114 return;
115 }
116 if (ND_rank(t) == ND_rank(h))
117 return;
118 make_chain(g, t, h, e);
119
120 /* mark as cluster edge */
121 for (ve = ED_to_virt(e); ve && ND_rank(aghead(ve)) <= ND_rank(h);
122 ve = ND_out(aghead(ve)).list[0])
124 }
125 /* else ignore intra-cluster edges at this point */
126}
127
128static bool is_cluster_edge(edge_t *e) {
129 return ND_ranktype(agtail(e)) == CLUSTER || ND_ranktype(aghead(e)) == CLUSTER;
130}
131
132void merge_chain(graph_t *g, edge_t *e, edge_t *f, bool update_count) {
133 edge_t *rep;
134 int lastrank = MAX(ND_rank(agtail(e)), ND_rank(aghead(e)));
135
136 assert(ED_to_virt(e) == NULL);
137 ED_to_virt(e) = f;
138 rep = f;
139 do {
140 /* interclust multi-edges are not counted now */
141 if (update_count)
142 ED_count(rep) += ED_count(e);
143 ED_xpenalty(rep) += ED_xpenalty(e);
144 ED_weight(rep) += ED_weight(e);
145 if (ND_rank(aghead(rep)) == lastrank)
146 break;
147 incr_width(g, aghead(rep));
148 rep = ND_out(aghead(rep)).list[0];
149 } while (rep);
150}
151
152bool mergeable(edge_t *e, edge_t *f) {
153 return e && f && agtail(e) == agtail(f) && aghead(e) == aghead(f) &&
154 ED_label(e) == ED_label(f) && ports_eq(e, f);
155}
156
158{
159 int c;
160 node_t *n, *t, *h;
161 edge_t *e, *prev, *opp;
162
163 GD_nlist(g) = NULL;
164
165 mark_clusters(g);
166 for (c = 1; c <= GD_n_cluster(g); c++)
167 build_skeleton(g, GD_clust(g)[c]);
168 for (n = agfstnode(g); n; n = agnxtnode(g, n))
169 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
170 if (ND_weight_class(aghead(e)) <= 2)
172 if (ND_weight_class(agtail(e)) <= 2)
174 }
175
176 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
177 if (ND_clust(n) == NULL && n == UF_find(n)) {
178 fast_node(g, n);
179 }
180 prev = NULL;
181 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
182
183 /* already processed */
184 if (ED_to_virt(e)) {
185 prev = e;
186 continue;
187 }
188
189 /* edges involving sub-clusters of g */
190 if (is_cluster_edge(e)) {
191 /* following is new cluster multi-edge code */
192 if (mergeable(prev, e)) {
193 if (ED_to_virt(prev)) {
194 merge_chain(g, e, ED_to_virt(prev), false);
195 other_edge(e);
196 } else if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
197 merge_oneway(e, prev);
198 other_edge(e);
199 }
200 /* else is an intra-cluster edge */
201 continue;
202 }
203 interclrep(g, e);
204 prev = e;
205 continue;
206 }
207 /* merge multi-edges */
208 if (prev && agtail(e) == agtail(prev) && aghead(e) == aghead(prev)) {
209 if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
210 merge_oneway(e, prev);
211 other_edge(e);
212 continue;
213 }
214 if (ED_label(e) == NULL && ED_label(prev) == NULL
215 && ports_eq(e, prev)) {
216 if (Concentrate)
218 else {
219 merge_chain(g, e, ED_to_virt(prev), true);
220 other_edge(e);
221 }
222 continue;
223 }
224 /* parallel edges with different labels fall through here */
225 }
226
227 /* self edges */
228 if (agtail(e) == aghead(e)) {
229 other_edge(e);
230 prev = e;
231 continue;
232 }
233
234 t = UF_find(agtail(e));
235 h = UF_find(aghead(e));
236
237 /* non-leader leaf nodes */
238 if (agtail(e) != t || aghead(e) != h) {
239 /* FIX need to merge stuff */
240 continue;
241 }
242
243
244 /* flat edges */
245 if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
246 flat_edge(g, e);
247 prev = e;
248 continue;
249 }
250
251 /* forward edges */
252 if (ND_rank(aghead(e)) > ND_rank(agtail(e))) {
253 make_chain(g, agtail(e), aghead(e), e);
254 prev = e;
255 continue;
256 }
257
258 /* backward edges */
259 else {
260 /* avoid when opp==e in undirected graph */
261 for (opp = agfstout(g, aghead(e)); opp != NULL; opp = agnxtout(g, opp)) {
262 if (aghead(opp) != agtail(e) || aghead(opp) == aghead(e) ||
263 ED_edge_type(opp) == IGNORED) {
264 continue;
265 }
266 /* shadows a forward edge */
267 if (ED_to_virt(opp) == NULL)
268 make_chain(g, agtail(opp), aghead(opp), opp);
269 if (ED_label(e) == NULL && ED_label(opp) == NULL
270 && ports_eq(e, opp)) {
271 if (Concentrate) {
273 ED_conc_opp_flag(opp) = true;
274 } else { /* see above. this is getting out of hand */
275 other_edge(e);
276 merge_chain(g, e, ED_to_virt(opp), true);
277 }
278 break;
279 }
280 }
281 if (opp != NULL) {
282 continue;
283 }
284 make_chain(g, aghead(e), agtail(e), e);
285 prev = e;
286 }
287 }
288 }
289 /* since decompose() is not called on subgraphs */
290 if (g != dot_root(g)) {
291 free(GD_comp(g).list);
292 GD_comp(g).list = gv_alloc(sizeof(node_t *));
293 GD_comp(g).list[0] = GD_nlist(g);
294 }
295}
296
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:72
void merge_chain(graph_t *g, edge_t *e, edge_t *f, bool update_count)
Definition class2.c:132
static void interclrep(graph_t *g, edge_t *e)
Definition class2.c:101
static node_t * leader_of(node_t *v)
Definition class2.c:57
static node_t * plain_vnode(graph_t *g)
Definition class2.c:50
static bool is_cluster_edge(edge_t *e)
Definition class2.c:128
void class2(graph_t *g)
Definition class2.c:157
bool mergeable(edge_t *e, edge_t *f)
Definition class2.c:152
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:43
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:115
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition fastgr.c:169
void virtual_weight(Agedge_t *)
Definition mincross.c:1819
void flat_edge(Agraph_t *, Agedge_t *)
Definition fastgr.c:214
void fast_node(Agraph_t *, Agnode_t *)
Definition fastgr.c:174
void merge_oneway(Agedge_t *, Agedge_t *)
Definition fastgr.c:288
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:199
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:346
void mark_clusters(graph_t *g)
Definition cluster.c:302
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