Graphviz 13.1.1~dev.20250701.1401
Loading...
Searching...
No Matches
conc.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/*
13 * build edge_t concentrators for parallel edges with a common endpoint
14 */
15
16#include <dotgen/dot.h>
17#include <stdbool.h>
18
19#define UP 0
20#define DOWN 1
21
22static bool samedir(edge_t * e, edge_t * f)
23{
24 edge_t *e0, *f0;
25
26 for (e0 = e; e0 != NULL && ED_edge_type(e0) != NORMAL; e0 = ED_to_orig(e0));
27 if (e0 == NULL)
28 return false;
29 for (f0 = f; f0 != NULL && ED_edge_type(f0) != NORMAL; f0 = ED_to_orig(f0));
30 if (f0 == NULL)
31 return false;
32 if (ED_conc_opp_flag(e0))
33 return false;
34 if (ED_conc_opp_flag(f0))
35 return false;
36 return ((ND_rank(agtail(f0)) - ND_rank(aghead(f0)))
37 * (ND_rank(agtail(e0)) - ND_rank(aghead(e0))) > 0);
38}
39
40static bool downcandidate(node_t * v)
41{
42 return ND_node_type(v) == VIRTUAL && ND_in(v).size == 1
43 && ND_out(v).size == 1 && ND_label(v) == NULL;
44}
45
46static bool bothdowncandidates(node_t * u, node_t * v)
47{
48 edge_t *e, *f;
49 e = ND_in(u).list[0];
50 f = ND_in(v).list[0];
51 if (downcandidate(v) && agtail(e) == agtail(f)) {
52 return samedir(e, f)
53 && portcmp(ED_tail_port(e), ED_tail_port(f)) == 0;
54 }
55 return false;
56}
57
58static bool upcandidate(node_t * v)
59{
60 return ND_node_type(v) == VIRTUAL && ND_out(v).size == 1
61 && ND_in(v).size == 1 && ND_label(v) == NULL;
62}
63
64static bool bothupcandidates(node_t * u, node_t * v)
65{
66 edge_t *e, *f;
67 e = ND_out(u).list[0];
68 f = ND_out(v).list[0];
69 if (upcandidate(v) && aghead(e) == aghead(f)) {
70 return samedir(e, f)
71 && portcmp(ED_head_port(e), ED_head_port(f)) == 0;
72 }
73 return false;
74}
75
76static void mergevirtual(graph_t * g, int r, int lpos, int rpos, int dir)
77{
78 int k;
79 node_t *left;
80 edge_t *e, *f, *e0;
81
82 left = GD_rank(g)[r].v[lpos];
83 /* merge all right nodes into the leftmost one */
84 for (int i = lpos + 1; i <= rpos; i++) {
85 node_t *const right = GD_rank(g)[r].v[i];
86 if (dir == DOWN) {
87 while ((e = ND_out(right).list[0])) {
88 for (k = 0; (f = ND_out(left).list[k]); k++)
89 if (aghead(f) == aghead(e))
90 break;
91 if (f == NULL)
92 f = virtual_edge(left, aghead(e), e);
93 while ((e0 = ND_in(right).list[0])) {
94 merge_oneway(e0, f);
96 }
98 }
99 } else {
100 while ((e = ND_in(right).list[0])) {
101 for (k = 0; (f = ND_in(left).list[k]); k++)
102 if (agtail(f) == agtail(e))
103 break;
104 if (f == NULL)
105 f = virtual_edge(agtail(e), left, e);
106 while ((e0 = ND_out(right).list[0])) {
107 merge_oneway(e0, f);
109 }
111 }
112 }
113 assert(ND_in(right).size + ND_out(right).size == 0);
115 }
116 k = lpos + 1;
117 for (int i = rpos + 1; i < GD_rank(g)[r].n; ++i) {
118 node_t *const n = GD_rank(g)[r].v[k] = GD_rank(g)[r].v[i];
119 ND_order(n) = k;
120 k++;
121 }
122 GD_rank(g)[r].n = k;
123 GD_rank(g)[r].v[k] = NULL;
124}
125
126static void infuse(graph_t * g, node_t * n)
127{
128 node_t *lead;
129
130 lead = GD_rankleader(g)[ND_rank(n)];
131 if (lead == NULL || ND_order(lead) > ND_order(n))
132 GD_rankleader(g)[ND_rank(n)] = n;
133}
134
135static int rebuild_vlists(graph_t * g)
136{
137 int c, i, r, maxi;
138 node_t *n, *lead;
139 edge_t *rep;
140
141 for (r = GD_minrank(g); r <= GD_maxrank(g); r++)
142 GD_rankleader(g)[r] = NULL;
144 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
145 infuse(g, n);
146 for (edge_t *e = agfstout(g, n); e; e = agnxtout(g, e)) {
147 for (rep = e; ED_to_virt(rep); rep = ED_to_virt(rep));
148 while (rep != NULL && ND_rank(aghead(rep)) < ND_rank(aghead(e))) {
149 infuse(g, aghead(rep));
150 rep = ND_out(aghead(rep)).list[0];
151 }
152 }
153 }
154
155 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
156 lead = GD_rankleader(g)[r];
157 if (lead == NULL) {
158 agerrorf("rebuild_vlists: lead is null for rank %d\n", r);
159 return -1;
160 }
161 else if (GD_rank(dot_root(g))[r].v[ND_order(lead)] != lead) {
162 agerrorf("rebuild_vlists: rank lead %s not in order %d of rank %d\n",
163 agnameof(lead), ND_order(lead), r);
164 return -1;
165 }
166 GD_rank(g)[r].v = GD_rank(dot_root(g))[r].v + ND_order(GD_rankleader(g)[r]);
167 maxi = -1;
168 for (i = 0; i < GD_rank(g)[r].n; i++) {
169 if ((n = GD_rank(g)[r].v[i]) == NULL)
170 break;
171 if (ND_node_type(n) == NORMAL) {
172 if (agcontains(g, n))
173 maxi = i;
174 else
175 break;
176 } else {
177 edge_t *e;
178 for (e = ND_in(n).list[0]; e && ED_to_orig(e);
179 e = ED_to_orig(e));
180 if (e && agcontains(g, agtail(e))
181 && agcontains(g, aghead(e)))
182 maxi = i;
183 }
184 }
185 if (maxi == -1)
186 agwarningf("degenerate concentrated rank %s,%d\n", agnameof(g),
187 r);
188 GD_rank(g)[r].n = maxi + 1;
189 }
190
191 for (c = 1; c <= GD_n_cluster(g); c++) {
192 int ret = rebuild_vlists(GD_clust(g)[c]);
193 if (ret != 0) {
194 return ret;
195 }
196 }
197 return 0;
198}
199
201{
202 int c, r, leftpos, rightpos;
203 node_t *left, *right;
204
205 if (GD_maxrank(g) - GD_minrank(g) <= 1)
206 return;
207 /* this is the downward looking pass. r is a candidate rank. */
208 for (r = 1; GD_rank(g)[r + 1].n; r++) {
209 for (leftpos = 0; leftpos < GD_rank(g)[r].n; leftpos++) {
210 left = GD_rank(g)[r].v[leftpos];
211 if (!downcandidate(left))
212 continue;
213 for (rightpos = leftpos + 1; rightpos < GD_rank(g)[r].n;
214 rightpos++) {
215 right = GD_rank(g)[r].v[rightpos];
217 break;
218 }
219 if (rightpos - leftpos > 1)
220 mergevirtual(g, r, leftpos, rightpos - 1, DOWN);
221 }
222 }
223 /* this is the corresponding upward pass */
224 while (r > 0) {
225 for (leftpos = 0; leftpos < GD_rank(g)[r].n; leftpos++) {
226 left = GD_rank(g)[r].v[leftpos];
227 if (!upcandidate(left))
228 continue;
229 for (rightpos = leftpos + 1; rightpos < GD_rank(g)[r].n;
230 rightpos++) {
231 right = GD_rank(g)[r].v[rightpos];
233 break;
234 }
235 if (rightpos - leftpos > 1)
236 mergevirtual(g, r, leftpos, rightpos - 1, UP);
237 }
238 r--;
239 }
240 for (c = 1; c <= GD_n_cluster(g); c++) {
241 if (rebuild_vlists(GD_clust(g)[c]) != 0) {
242 agerr(AGPREV, "concentrate=true may not work correctly.\n");
243 return;
244 }
245 }
246}
#define right(i)
Definition closest.c:79
#define UP
Definition conc.c:19
static int rebuild_vlists(graph_t *g)
Definition conc.c:135
#define DOWN
Definition conc.c:20
static bool bothdowncandidates(node_t *u, node_t *v)
Definition conc.c:46
static bool downcandidate(node_t *v)
Definition conc.c:40
static bool upcandidate(node_t *v)
Definition conc.c:58
static bool bothupcandidates(node_t *u, node_t *v)
Definition conc.c:64
static void infuse(graph_t *g, node_t *n)
Definition conc.c:126
void dot_concentrate(graph_t *g)
Definition conc.c:200
static bool samedir(edge_t *e, edge_t *f)
Definition conc.c:22
static void mergevirtual(graph_t *g, int r, int lpos, int rpos, int dir)
Definition conc.c:76
#define NORMAL
Definition const.h:24
#define VIRTUAL
Definition const.h:25
Agraph_t * dot_root(void *p)
Definition dotinit.c:525
void delete_fast_node(Agraph_t *, Agnode_t *)
Definition fastgr.c:187
void dot_scan_ranks(graph_t *g)
Definition rank.c:271
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition fastgr.c:168
int portcmp(port p0, port p1)
Definition dotsplines.c:132
void delete_fast_edge(Agedge_t *)
Definition fastgr.c:107
void merge_oneway(Agedge_t *, Agedge_t *)
Definition fastgr.c:287
#define left
Definition dthdr.h:12
node NULL
Definition grammar.y:181
#define ED_to_orig(e)
Definition types.h:598
#define ED_conc_opp_flag(e)
Definition types.h:579
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
#define agtail(e)
Definition cgraph.h:988
#define ED_edge_type(e)
Definition types.h:582
#define aghead(e)
Definition cgraph.h:989
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
#define ED_head_port(e)
Definition types.h:588
#define ED_tail_port(e)
Definition types.h:597
#define ED_to_virt(e)
Definition types.h:599
void agwarningf(const char *fmt,...)
Definition agerror.c:173
void agerrorf(const char *fmt,...)
Definition agerror.c:165
int agerr(agerrlevel_t level, const char *fmt,...)
Definition agerror.c:155
@ AGPREV
Definition cgraph.h:957
#define GD_minrank(g)
Definition types.h:384
#define GD_maxrank(g)
Definition types.h:382
#define GD_clust(g)
Definition types.h:360
#define GD_rank(g)
Definition types.h:395
#define GD_n_cluster(g)
Definition types.h:389
#define GD_rankleader(g)
Definition types.h:396
#define ND_rank(n)
Definition types.h:523
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_label(n)
Definition types.h:502
#define ND_node_type(n)
Definition types.h:511
#define ND_order(n)
Definition types.h:513
#define ND_in(n)
Definition types.h:501
#define ND_out(n)
Definition types.h:515
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
int agcontains(Agraph_t *, void *obj)
returns non-zero if obj is a member of (sub)graph
Definition obj.c:233
graph or subgraph
Definition cgraph.h:424