Graphviz 13.1.0~dev.20250626.0830
Loading...
Searching...
No Matches
flat.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#include <assert.h>
12#include <dotgen/dot.h>
13#include <stdbool.h>
14#include <stddef.h>
15#include <util/alloc.h>
16#include <util/gv_math.h>
17
18static node_t *make_vn_slot(graph_t * g, int r, int pos)
19{
20 int i;
21 node_t *n;
22
23 assert(GD_rank(g)[r].av == GD_rank(g)[r].v);
24 GD_rank(g)[r].av = gv_recalloc(GD_rank(g)[r].av, GD_rank(g)[r].n + 1,
25 GD_rank(g)[r].n + 2, sizeof(node_t *));
26 GD_rank(g)[r].v = GD_rank(g)[r].av;
27 node_t **const v = GD_rank(g)[r].v;
28 for (i = GD_rank(g)[r].n; i > pos; i--) {
29 v[i] = v[i - 1];
30 ND_order(v[i])++;
31 }
32 n = v[pos] = virtual_node(g);
33 ND_order(n) = pos;
34 ND_rank(n) = r;
35 v[++(GD_rank(g)[r].n)] = NULL;
36 return v[pos];
37}
38
39#define HLB 0 /* hard left bound */
40#define HRB 1 /* hard right bound */
41#define SLB 2 /* soft left bound */
42#define SRB 3 /* soft right bound */
43
44static void findlr(node_t * u, node_t * v, int *lp, int *rp)
45{
46 int l, r;
47 l = ND_order(u);
48 r = ND_order(v);
49 if (l > r) {
50 SWAP(&l, &r);
51 }
52 *lp = l;
53 *rp = r;
54}
55
56static void setbounds(node_t * v, int *bounds, int lpos, int rpos)
57{
58 int i, l, r, ord;
59 edge_t *f;
60
61 if (ND_node_type(v) == VIRTUAL) {
62 ord = ND_order(v);
63 if (ND_in(v).size == 0) { /* flat */
64 assert(ND_out(v).size == 2);
65 findlr(aghead(ND_out(v).list[0]), aghead(ND_out(v).list[1]), &l,
66 &r);
67 /* the other flat edge could be to the left or right */
68 if (r <= lpos)
69 bounds[SLB] = bounds[HLB] = ord;
70 else if (l >= rpos)
71 bounds[SRB] = bounds[HRB] = ord;
72 /* could be spanning this one */
73 else if (l < lpos && r > rpos); // ignore
74 /* must have intersecting ranges */
75 else {
76 if (l < lpos || (l == lpos && r < rpos))
77 bounds[SLB] = ord;
78 if (r > rpos || (r == rpos && l > lpos))
79 bounds[SRB] = ord;
80 }
81 } else { /* forward */
82 bool onleft, onright;
83 onleft = onright = false;
84 for (i = 0; (f = ND_out(v).list[i]); i++) {
85 if (ND_order(aghead(f)) <= lpos) {
86 onleft = true;
87 continue;
88 }
89 if (ND_order(aghead(f)) >= rpos) {
90 onright = true;
91 continue;
92 }
93 }
94 if (onleft && !onright)
95 bounds[HLB] = ord + 1;
96 if (onright && !onleft)
97 bounds[HRB] = ord - 1;
98 }
99 }
100}
101
102static int flat_limits(graph_t * g, edge_t * e)
103{
104 int lnode, rnode, r, bounds[4], lpos, rpos, pos;
105 node_t **rank;
106
107 r = ND_rank(agtail(e)) - 1;
108 rank = GD_rank(g)[r].v;
109 lnode = 0;
110 rnode = GD_rank(g)[r].n - 1;
111 bounds[HLB] = bounds[SLB] = lnode - 1;
112 bounds[HRB] = bounds[SRB] = rnode + 1;
113 findlr(agtail(e), aghead(e), &lpos, &rpos);
114 while (lnode <= rnode) {
115 setbounds(rank[lnode], bounds, lpos, rpos);
116 if (lnode != rnode)
117 setbounds(rank[rnode], bounds, lpos, rpos);
118 lnode++;
119 rnode--;
120 if (bounds[HRB] - bounds[HLB] <= 1)
121 break;
122 }
123 if (bounds[HLB] <= bounds[HRB])
124 pos = (bounds[HLB] + bounds[HRB] + 1) / 2;
125 else
126 pos = (bounds[SLB] + bounds[SRB] + 1) / 2;
127 return pos;
128}
129
130/* Create virtual node representing edge label between
131 * actual ends of edge e.
132 * This node is characterized by being virtual and having a non-NULL
133 * ND_alg pointing to e.
134 */
135static void
137{
138 int r, place;
139 double ypos, h2;
140 graph_t *g;
141 node_t *n, *vn;
142 edge_t *ve;
143 pointf dimen;
144
145 if (ED_label(e) == NULL)
146 return;
147 g = dot_root(agtail(e));
148 r = ND_rank(agtail(e));
149
150 place = flat_limits(g, e);
151 /* grab ypos = LL.y of label box before make_vn_slot() */
152 if ((n = GD_rank(g)[r - 1].v[0]))
153 ypos = ND_coord(n).y - GD_rank(g)[r - 1].ht1;
154 else {
155 n = GD_rank(g)[r].v[0];
156 ypos = ND_coord(n).y + GD_rank(g)[r].ht2 + GD_ranksep(g);
157 }
158 vn = make_vn_slot(g, r - 1, place);
159 dimen = ED_label(e)->dimen;
160 if (GD_flip(g)) {
161 SWAP(&dimen.x, &dimen.y);
162 }
163 ND_ht(vn) = dimen.y;
164 h2 = ND_ht(vn) / 2;
165 ND_lw(vn) = ND_rw(vn) = dimen.x / 2;
166 ND_label(vn) = ED_label(e);
167 ND_coord(vn).y = ypos + h2;
168 ve = virtual_edge(vn, agtail(e), e); /* was NULL? */
169 ED_tail_port(ve).p.x = -ND_lw(vn);
170 ED_head_port(ve).p.x = ND_rw(agtail(e));
172 ve = virtual_edge(vn, aghead(e), e);
173 ED_tail_port(ve).p.x = ND_rw(vn);
174 ED_head_port(ve).p.x = ND_lw(aghead(e));
176 /* another assumed symmetry of ht1/ht2 of a label node */
177 if (GD_rank(g)[r - 1].ht1 < h2)
178 GD_rank(g)[r - 1].ht1 = h2;
179 if (GD_rank(g)[r - 1].ht2 < h2)
180 GD_rank(g)[r - 1].ht2 = h2;
181 ND_alg(vn) = e;
182}
183
184static void abomination(graph_t * g)
185{
186 int r;
187
188 assert(GD_minrank(g) == 0);
189 /* 3 = one for new rank, one for sentinel, one for off-by-one */
190 r = GD_maxrank(g) + 3;
191 rank_t *rptr = gv_recalloc(GD_rank(g), GD_maxrank(g) + 1, r,
192 sizeof(rank_t));
193 GD_rank(g) = rptr + 1;
194 for (r = GD_maxrank(g); r >= 0; r--)
195 GD_rank(g)[r] = GD_rank(g)[r - 1];
196 GD_rank(g)[r].n = GD_rank(g)[r].an = 0;
197 GD_rank(g)[r].v = GD_rank(g)[r].av = gv_calloc(2, sizeof(node_t *));
198 GD_rank(g)[r].flat = NULL;
199 GD_rank(g)[r].ht1 = GD_rank(g)[r].ht2 = 1;
200 GD_rank(g)[r].pht1 = GD_rank(g)[r].pht2 = 1;
201 GD_minrank(g)--;
202}
203
204/* Check if tn and hn are adjacent.
205 * If so, set adjacent bit on all related edges.
206 * Assume e is flat.
207 */
208static void
210{
211 node_t* tn = agtail(e);
212 node_t* hn = aghead(e);
213 int i, lo, hi;
214 node_t* n;
215 rank_t *rank;
216
217 if (ND_order(tn) < ND_order(hn)) {
218 lo = ND_order(tn);
219 hi = ND_order(hn);
220 }
221 else {
222 lo = ND_order(hn);
223 hi = ND_order(tn);
224 }
225 rank = &GD_rank(dot_root(tn))[ND_rank(tn)];
226 for (i = lo + 1; i < hi; i++) {
227 n = rank->v[i];
228 if ((ND_node_type(n) == VIRTUAL && ND_label(n)) ||
229 ND_node_type(n) == NORMAL)
230 break;
231 }
232 if (i == hi) { /* adjacent edge */
233 do {
234 ED_adjacent(e) = 1;
235 e = ED_to_virt(e);
236 } while (e);
237 }
238}
239
240/* Process flat edges.
241 * First, mark flat edges as having adjacent endpoints or not.
242 *
243 * Second, if there are edge labels, nodes are placed on ranks 0,2,4,...
244 * If we have a labeled flat edge on rank 0, add a rank -1.
245 *
246 * Finally, create label information. Add a virtual label node in the
247 * previous rank for each labeled, non-adjacent flat edge. If this is
248 * done for any edge, return true, so that main code will reset y coords.
249 * For labeled adjacent flat edges, store label width in representative edge.
250 * FIX: We should take into account any extra height needed for the latter
251 * labels.
252 *
253 * We leave equivalent flat edges in ND_other. Their ED_virt field should
254 * still point to the class representative.
255 */
256int
258{
259 int i;
260 bool reset = false;
261 node_t *n;
262 edge_t *e;
263
264 for (n = GD_nlist(g); n; n = ND_next(n)) {
265 if (ND_flat_out(n).list) {
266 for (size_t j = 0; (e = ND_flat_out(n).list[j]); j++) {
268 }
269 }
270 for (size_t j = 0; j < ND_other(n).size; j++) {
271 e = ND_other(n).list[j];
272 if (ND_rank(aghead(e)) == ND_rank(agtail(e)))
274 }
275 }
276
277 if (GD_rank(g)[0].flat || GD_n_cluster(g) > 0) {
278 bool found = false;
279 for (i = 0; (n = GD_rank(g)[0].v[i]); i++) {
280 for (size_t j = 0; (e = ND_flat_in(n).list[j]); j++) {
281 if (ED_label(e) && !ED_adjacent(e)) {
282 abomination(g);
283 found = true;
284 break;
285 }
286 }
287 if (found)
288 break;
289 }
290 }
291
293 for (n = GD_nlist(g); n; n = ND_next(n)) {
294 /* if n is the tail of any flat edge, one will be in flat_out */
295 if (ND_flat_out(n).list) {
296 for (i = 0; (e = ND_flat_out(n).list[i]); i++) {
297 if (ED_label(e)) {
298 if (ED_adjacent(e)) {
299 ED_dist(e) = GD_flip(g) ? ED_label(e)->dimen.y : ED_label(e)->dimen.x;
300 }
301 else {
302 reset = true;
303 flat_node(e);
304 }
305 }
306 }
307 /* look for other flat edges with labels */
308 for (size_t j = 0; j < ND_other(n).size; j++) {
309 edge_t* le;
310 e = ND_other(n).list[j];
311 if (ND_rank(agtail(e)) != ND_rank(aghead(e))) continue;
312 if (agtail(e) == aghead(e)) continue; /* skip loops */
313 le = e;
314 while (ED_to_virt(le)) le = ED_to_virt(le);
316 if (ED_label(e)) {
317 if (ED_adjacent(e)) {
318 const double lw = GD_flip(g) ? ED_label(e)->dimen.y : ED_label(e)->dimen.x;
319 ED_dist(le) = MAX(lw,ED_dist(le));
320 }
321 else {
322 reset = true;
323 flat_node(e);
324 }
325 }
326 }
327 }
328 }
329 if (reset) {
332 }
333 return reset;
334}
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
Definition alloc.h:73
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define NORMAL
Definition const.h:24
#define FLATORDER
Definition const.h:28
#define VIRTUAL
Definition const.h:25
Agraph_t * dot_root(void *p)
Definition dotinit.c:525
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition fastgr.c:169
void checkLabelOrder(graph_t *g)
Definition mincross.c:342
void rec_reset_vlists(Agraph_t *)
Definition mincross.c:994
void rec_save_vlists(Agraph_t *)
Definition mincross.c:984
Agnode_t * virtual_node(Agraph_t *)
Definition fastgr.c:199
#define le
Definition edges.h:25
static void flat_node(edge_t *e)
Definition flat.c:136
static int flat_limits(graph_t *g, edge_t *e)
Definition flat.c:102
#define HLB
Definition flat.c:39
int flat_edges(graph_t *g)
Definition flat.c:257
static void checkFlatAdjacent(edge_t *e)
Definition flat.c:209
static void abomination(graph_t *g)
Definition flat.c:184
#define HRB
Definition flat.c:40
static node_t * make_vn_slot(graph_t *g, int r, int pos)
Definition flat.c:18
#define SRB
Definition flat.c:42
#define SLB
Definition flat.c:41
static void findlr(node_t *u, node_t *v, int *lp, int *rp)
Definition flat.c:44
static void setbounds(node_t *v, int *bounds, int lpos, int rpos)
Definition flat.c:56
node NULL
Definition grammar.y:181
#define ED_dist(e)
Definition types.h:602
#define agtail(e)
Definition cgraph.h:988
#define ED_edge_type(e)
Definition types.h:582
#define ED_adjacent(e)
Definition types.h:584
#define aghead(e)
Definition cgraph.h:989
#define ED_head_port(e)
Definition types.h:588
#define ED_label(e)
Definition types.h:589
#define ED_tail_port(e)
Definition types.h:597
#define ED_to_virt(e)
Definition types.h:599
#define GD_minrank(g)
Definition types.h:384
#define GD_maxrank(g)
Definition types.h:382
#define GD_rank(g)
Definition types.h:395
#define GD_nlist(g)
Definition types.h:393
#define GD_n_cluster(g)
Definition types.h:389
#define GD_flip(g)
Definition types.h:378
#define GD_ranksep(g)
Definition types.h:397
#define ND_rank(n)
Definition types.h:523
#define ND_ht(n)
Definition types.h:500
#define ND_next(n)
Definition types.h:510
#define ND_other(n)
Definition types.h:514
#define ND_label(n)
Definition types.h:502
#define ND_alg(n)
Definition types.h:484
#define ND_flat_out(n)
Definition types.h:493
#define ND_rw(n)
Definition types.h:525
#define ND_node_type(n)
Definition types.h:511
#define ND_lw(n)
Definition types.h:506
#define ND_order(n)
Definition types.h:513
#define ND_flat_in(n)
Definition types.h:492
#define ND_coord(n)
Definition types.h:490
#define ND_in(n)
Definition types.h:501
#define ND_out(n)
Definition types.h:515
Arithmetic helper functions.
#define SWAP(a, b)
Definition gv_math.h:131
int rank(graph_t *g, int balance, int maxiter)
Definition ns.c:1063
void reset(sgraph *G)
Definition sgraph.c:29
graph or subgraph
Definition cgraph.h:424
double x
Definition geom.h:29
double y
Definition geom.h:29
int n
Definition types.h:201
#define MAX(a, b)
Definition write.c:32