Graphviz 13.1.0~dev.20250626.0830
Loading...
Searching...
No Matches
cluster.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
17static node_t*
19{
20 node_t *rv;
21
22 if (ND_clust(n) == NULL || GD_expanded(ND_clust(n)))
23 rv = n;
24 else
25 rv = GD_rankleader(ND_clust(n))[ND_rank(n)];
26 return rv;
27}
28
29/* make d slots starting at position pos (where 1 already exists) */
30static void
31make_slots(graph_t * root, int r, int pos, int d)
32{
33 int i;
34 node_t *v, **vlist;
35 vlist = GD_rank(root)[r].v;
36 if (d <= 0) {
37 for (i = pos - d + 1; i < GD_rank(root)[r].n; i++) {
38 v = vlist[i];
39 ND_order(v) = i + d - 1;
40 vlist[ND_order(v)] = v;
41 }
42 for (i = GD_rank(root)[r].n + d - 1; i < GD_rank(root)[r].n; i++)
43 vlist[i] = NULL;
44 } else {
45/*assert(ND_rank(root)[r].n + d - 1 <= ND_rank(root)[r].an);*/
46 for (i = GD_rank(root)[r].n - 1; i > pos; i--) {
47 v = vlist[i];
48 ND_order(v) = i + d - 1;
49 vlist[ND_order(v)] = v;
50 }
51 for (i = pos + 1; i < pos + d; i++)
52 vlist[i] = NULL;
53 }
54 GD_rank(root)[r].n += d - 1;
55}
56
57static node_t*
59{
60 node_t *rv;
61 int r;
62
63 r = ND_rank(vn);
64 make_slots(g, r, ND_order(vn), 2);
65 rv = virtual_node(g);
66 ND_lw(rv) = ND_lw(vn);
67 ND_rw(rv) = ND_rw(vn);
68 ND_rank(rv) = ND_rank(vn);
69 ND_order(rv) = ND_order(vn) + 1;
70 GD_rank(g)[r].v[ND_order(rv)] = rv;
71 return rv;
72}
73
74static void
75map_path(node_t * from, node_t * to, edge_t * orig, edge_t * ve, int type)
76{
77 int r;
78 node_t *u, *v;
79 edge_t *e;
80
81 assert(ND_rank(from) < ND_rank(to));
82
83 if (agtail(ve) == from && aghead(ve) == to)
84 return;
85
86 if (ED_count(ve) > 1) {
87 ED_to_virt(orig) = NULL;
88 if (ND_rank(to) - ND_rank(from) == 1) {
89 if ((e = find_fast_edge(from, to)) && ports_eq(orig, e)) {
90 merge_oneway(orig, e);
91 if (ND_node_type(from) == NORMAL && ND_node_type(to) == NORMAL)
92 other_edge(orig);
93 return;
94 }
95 }
96 u = from;
97 for (r = ND_rank(from); r < ND_rank(to); r++) {
98 if (r < ND_rank(to) - 1)
99 v = clone_vn(dot_root(from), aghead(ve));
100 else
101 v = to;
102 e = virtual_edge(u, v, orig);
103 ED_edge_type(e) = type;
104 u = v;
105 ED_count(ve)--;
106 ve = ND_out(aghead(ve)).list[0];
107 }
108 } else {
109 if (ND_rank(to) - ND_rank(from) == 1) {
110 if ((ve = find_fast_edge(from, to)) && ports_eq(orig, ve)) {
111 /*ED_to_orig(ve) = orig; */
112 ED_to_virt(orig) = ve;
113 ED_edge_type(ve) = type;
114 ED_count(ve)++;
115 if (ND_node_type(from) == NORMAL && ND_node_type(to) == NORMAL)
116 other_edge(orig);
117 } else {
118 ED_to_virt(orig) = NULL;
119 ve = virtual_edge(from, to, orig);
120 ED_edge_type(ve) = type;
121 }
122 }
123 if (ND_rank(to) - ND_rank(from) > 1) {
124 if (agtail(ve) != from) {
125 ED_to_virt(orig) = NULL;
126 e = ED_to_virt(orig) = virtual_edge(from, aghead(ve), orig);
128 } else
129 e = ve;
130 while (ND_rank(aghead(e)) != ND_rank(to))
131 e = ND_out(aghead(e)).list[0];
132 if (aghead(e) != to) {
133 ve = e;
134 e = virtual_edge(agtail(e), to, orig);
135 ED_edge_type(e) = type;
137 }
138 }
139 }
140}
141
142static void make_interclust_chain(node_t * from, node_t * to, edge_t * orig) {
143 int newtype;
144 node_t *u, *v;
145
146 u = map_interclust_node(from);
147 v = map_interclust_node(to);
148 if (u == from && v == to)
149 newtype = VIRTUAL;
150 else
151 newtype = CLUSTER_EDGE;
152 map_path(u, v, orig, ED_to_virt(orig), newtype);
153}
154
155/*
156 * attach and install edges between clusters.
157 * essentially, class2() for interclust edges.
158 */
159static void interclexp(graph_t * subg)
160{
161 edge_t *next;
162
163 graph_t *const g = dot_root(subg);
164 for (node_t *n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
165
166 /* N.B. n may be in a sub-cluster of subg */
167 edge_t *prev = NULL;
168 for (edge_t *e = agfstedge(g, n); e; e = next) {
169 next = agnxtedge(g, e, n);
170 if (agcontains(subg, e))
171 continue;
172
173 /* canonicalize edge */
174 e = AGMKOUT(e);
175 /* short/flat multi edges */
176 if (mergeable(prev, e)) {
177 if (ND_rank(agtail(e)) == ND_rank(aghead(e)))
178 ED_to_virt(e) = prev;
179 else
180 ED_to_virt(e) = NULL;
181 if (ED_to_virt(prev) == NULL)
182 continue; /* internal edge */
183 ED_to_virt(e) = NULL;
184 merge_chain(subg, e, ED_to_virt(prev), false);
186 continue;
187 }
188
189 /* flat edges */
190 if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
191 edge_t* fe;
192 if ((fe = find_flat_edge(agtail(e), aghead(e))) == NULL) {
193 if (!ED_to_virt(e)) {
194 flat_edge(g, e);
195 }
196 prev = e;
197 } else if (e != fe) {
199 if (!ED_to_virt(e)) merge_oneway(e, fe);
200 }
201 continue;
202 }
203
204 /* forward edges */
205 if (ND_rank(aghead(e)) > ND_rank(agtail(e))) {
207 prev = e;
208 continue;
209 }
210
211 /* backward edges */
213 prev = e;
214 }
215 }
216}
217
218static void
220{
221 int i, d, r, pos, ipos;
222 node_t *v;
223 graph_t *root;
224
225 assert(GD_minrank(subg) <= GD_maxrank(subg) && "corrupted rank bounds");
226
227 root = dot_root(subg);
228 if (GD_minrank(subg) > 0)
229 GD_rank(root)[GD_minrank(subg) - 1].valid = false;
230 for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
231 d = GD_rank(subg)[r].n;
232 ipos = pos = ND_order(GD_rankleader(subg)[r]);
233 make_slots(root, r, pos, d);
234 for (i = 0; i < GD_rank(subg)[r].n; i++) {
235 v = GD_rank(root)[r].v[pos] = GD_rank(subg)[r].v[i];
236 ND_order(v) = pos++;
237 /* real nodes automatically have v->root = root graph */
238 if (ND_node_type(v) == VIRTUAL)
239 v->root = agroot(root);
240 delete_fast_node(subg, v);
241 fast_node(root, v);
242 }
243 GD_rank(subg)[r].v = GD_rank(root)[r].v + ipos;
244 GD_rank(root)[r].valid = false;
245 }
246 if (r < GD_maxrank(root))
247 GD_rank(root)[r].valid = false;
248 GD_expanded(subg) = true;
249}
250
251static void
253{
254 int r;
255 node_t *v;
256 edge_t *e;
257
258 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
259 v = GD_rankleader(g)[r];
260
261 /* remove the entire chain */
262 while ((e = ND_out(v).list[0])) {
264 free(e->base.data);
265 free(e);
266 }
267 while ((e = ND_in(v).list[0])) {
269 free(e);
270 }
272 free(ND_in(v).list);
273 free(ND_out(v).list);
274 free(v->base.data);
275 free(v);
276 GD_rankleader(g)[r] = NULL;
277 }
278}
279
280/* delete virtual nodes of a cluster, and install real nodes or sub-clusters */
282 /* build internal structure of the cluster */
283 class2(subg);
284 GD_comp(subg).size = 1;
285 GD_comp(subg).list[0] = GD_nlist(subg);
286 allocate_ranks(subg);
287 ints_t scratch = {0};
288 const int rc = build_ranks(subg, 0, &scratch);
289 ints_free(&scratch);
290 if (rc != 0) {
291 return rc;
292 }
293 merge_ranks(subg);
294
295 /* build external structure of the cluster */
296 interclexp(subg);
297 remove_rankleaders(subg);
298 return 0;
299}
300
301/* this function marks every node in <g> with its top-level cluster under <g> */
303{
304 int c;
305 node_t *n, *nn, *vn;
306 edge_t *orig, *e;
307 graph_t *clust;
308
309 /* remove sub-clusters below this level */
310 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
311 if (ND_ranktype(n) == CLUSTER)
312 UF_singleton(n);
313 ND_clust(n) = NULL;
314 }
315
316 for (c = 1; c <= GD_n_cluster(g); c++) {
317 clust = GD_clust(g)[c];
318 for (n = agfstnode(clust); n; n = nn) {
319 nn = agnxtnode(clust,n);
320 if (ND_ranktype(n) != NORMAL) {
322 "%s was already in a rankset, deleted from cluster %s\n",
323 agnameof(n), agnameof(g));
324 agdelete(clust,n);
325 continue;
326 }
327 UF_setname(n, GD_leader(clust));
328 ND_clust(n) = clust;
329 ND_ranktype(n) = CLUSTER;
330
331 /* here we mark the vnodes of edges in the cluster */
332 for (orig = agfstout(clust, n); orig;
333 orig = agnxtout(clust, orig)) {
334 if ((e = ED_to_virt(orig))) {
335 while (e && ND_node_type(vn =aghead(e)) == VIRTUAL) {
336 ND_clust(vn) = clust;
337 e = ND_out(aghead(e)).list[0];
338 /* trouble if concentrators and clusters are mixed */
339 }
340 }
341 }
342 }
343 }
344}
345
347{
348 int r;
349 node_t *v, *prev, *rl;
350 edge_t *e;
351
352 prev = NULL;
353 GD_rankleader(subg) = gv_calloc(GD_maxrank(subg) + 2, sizeof(node_t*));
354 for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
355 v = GD_rankleader(subg)[r] = virtual_node(g);
356 ND_rank(v) = r;
357 ND_ranktype(v) = CLUSTER;
358 ND_clust(v) = subg;
359 if (prev) {
360 e = virtual_edge(prev, v, NULL);
361 ED_xpenalty(e) *= CL_CROSS;
362 }
363 prev = v;
364 }
365
366 /* set the counts on virtual edges of the cluster skeleton */
367 for (v = agfstnode(subg); v; v = agnxtnode(subg, v)) {
368 rl = GD_rankleader(subg)[ND_rank(v)];
369 ND_UF_size(rl)++;
370 for (e = agfstout(subg, v); e; e = agnxtout(subg, e)) {
371 for (r = ND_rank(agtail(e)); r < ND_rank(aghead(e)); r++) {
372 ED_count(ND_out(rl).list[0])++;
373 }
374 }
375 }
376 for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
377 rl = GD_rankleader(subg)[r];
378 if (ND_UF_size(rl) > 1)
379 ND_UF_size(rl)--;
380 }
381}
382
383int install_cluster(graph_t *g, node_t *n, int pass, node_queue_t *q) {
384 int r;
385 graph_t *clust;
386
387 clust = ND_clust(n);
388 if (GD_installed(clust) != pass + 1) {
389 for (r = GD_minrank(clust); r <= GD_maxrank(clust); r++) {
390 const int rc = install_in_rank(g, GD_rankleader(clust)[r]);
391 if (rc != 0) {
392 return rc;
393 }
394 }
395 for (r = GD_minrank(clust); r <= GD_maxrank(clust); r++)
396 enqueue_neighbors(q, GD_rankleader(clust)[r], pass);
397 GD_installed(clust) = pass + 1;
398 }
399 return 0;
400}
401
402static void mark_lowcluster_basic(Agraph_t * g);
404{
405 Agnode_t *n, *vn;
406 Agedge_t *orig, *e;
407
408 /* first, zap any previous cluster labelings */
409 for (n = agfstnode(root); n; n = agnxtnode(root, n)) {
410 ND_clust(n) = NULL;
411 for (orig = agfstout(root, n); orig; orig = agnxtout(root, orig)) {
412 if ((e = ED_to_virt(orig))) {
413 while (e && (ND_node_type(vn = aghead(e))) == VIRTUAL) {
414 ND_clust(vn) = NULL;
415 e = ND_out(aghead(e)).list[0];
416 }
417 }
418 }
419 }
420
421 /* do the recursion */
423}
424
426{
427 Agraph_t *clust;
428 Agnode_t *n, *vn;
429 Agedge_t *orig, *e;
430 int c;
431
432 for (c = 1; c <= GD_n_cluster(g); c++) {
433 clust = GD_clust(g)[c];
435 }
436 /* see what belongs to this graph that wasn't already marked */
437 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
438 if (ND_clust(n) == NULL)
439 ND_clust(n) = g;
440 for (orig = agfstout(g, n); orig; orig = agnxtout(g, orig)) {
441 if ((e = ED_to_virt(orig))) {
442 while (e && (ND_node_type(vn = aghead(e))) == VIRTUAL) {
443 if (ND_clust(vn) == NULL)
444 ND_clust(vn) = g;
445 e = ND_out(aghead(e)).list[0];
446 }
447 }
448 }
449 }
450}
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
void merge_chain(graph_t *g, edge_t *e, edge_t *f, bool update_count)
Definition class2.c:132
void class2(graph_t *g)
Definition class2.c:157
bool mergeable(edge_t *e, edge_t *f)
Definition class2.c:152
void UF_setname(node_t *u, node_t *v)
Definition utils.c:145
void UF_singleton(node_t *u)
Definition utils.c:138
#define NORMAL
Definition const.h:24
#define VIRTUAL
Definition const.h:25
#define CLUSTER_EDGE
Definition const.h:29
#define CLUSTER
Definition const.h:40
#define CL_CROSS
Definition const.h:153
Agraph_t * dot_root(void *p)
Definition dotinit.c:525
void other_edge(Agedge_t *)
Definition fastgr.c:115
void delete_fast_node(Agraph_t *, Agnode_t *)
Definition fastgr.c:188
int build_ranks(Agraph_t *, int, ints_t *)
Definition mincross.c:1273
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition fastgr.c:169
void safe_other_edge(Agedge_t *)
Definition fastgr.c:120
void enqueue_neighbors(node_queue_t *q, node_t *n0, int pass)
Definition mincross.c:1349
void allocate_ranks(Agraph_t *)
Definition mincross.c:1197
void flat_edge(Agraph_t *, Agedge_t *)
Definition fastgr.c:214
void fast_node(Agraph_t *, Agnode_t *)
Definition fastgr.c:174
void delete_fast_edge(Agedge_t *)
Definition fastgr.c:108
void merge_oneway(Agedge_t *, Agedge_t *)
Definition fastgr.c:288
int install_in_rank(Agraph_t *, Agnode_t *)
Definition mincross.c:1225
int ports_eq(edge_t *, edge_t *)
Definition position.c:1008
Agedge_t * find_flat_edge(Agnode_t *, Agnode_t *)
Definition fastgr.c:54
Agedge_t * find_fast_edge(Agnode_t *, Agnode_t *)
Definition fastgr.c:41
Agnode_t * virtual_node(Agraph_t *)
Definition fastgr.c:199
expr procedure type
Definition exparse.y:206
void free(void *)
node NULL
Definition grammar.y:181
#define AGMKOUT(e)
Definition cgraph.h:982
#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
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition edge.c:96
#define aghead(e)
Definition cgraph.h:989
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition edge.c:87
#define ED_to_virt(e)
Definition types.h:599
void agwarningf(const char *fmt,...)
Definition agerror.c:173
#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_installed(g)
Definition types.h:373
#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_expanded(g)
Definition types.h:364
#define GD_leader(g)
Definition types.h:375
#define GD_comp(g)
Definition types.h:362
#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_clust(n)
Definition types.h:489
#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_UF_size(n)
Definition types.h:487
#define ND_ranktype(n)
Definition types.h:524
#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 agdelete(Agraph_t *g, void *obj)
deletes object. Equivalent to agclose, agdelnode, and agdeledge for obj being a graph,...
Definition obj.c:20
int agcontains(Agraph_t *, void *obj)
returns non-zero if obj is a member of (sub)graph
Definition obj.c:233
Agraph_t * agroot(void *obj)
Definition obj.c:168
$2 u p prev
Definition htmlparse.y:297
static void mark_lowcluster_basic(Agraph_t *g)
Definition cluster.c:425
static void merge_ranks(graph_t *subg)
Definition cluster.c:219
static void map_path(node_t *from, node_t *to, edge_t *orig, edge_t *ve, int type)
Definition cluster.c:75
static void make_slots(graph_t *root, int r, int pos, int d)
Definition cluster.c:31
int install_cluster(graph_t *g, node_t *n, int pass, node_queue_t *q)
Definition cluster.c:383
static void remove_rankleaders(graph_t *g)
Definition cluster.c:252
static void interclexp(graph_t *subg)
Definition cluster.c:159
int expand_cluster(graph_t *subg)
Definition cluster.c:281
static node_t * clone_vn(graph_t *g, node_t *vn)
Definition cluster.c:58
static node_t * map_interclust_node(node_t *n)
Definition cluster.c:18
void mark_lowclusters(Agraph_t *root)
Definition cluster.c:403
void build_skeleton(graph_t *g, graph_t *subg)
Definition cluster.c:346
void mark_clusters(graph_t *g)
Definition cluster.c:302
static void make_interclust_chain(node_t *from, node_t *to, edge_t *orig)
Definition cluster.c:142
Agobj_t base
Definition cgraph.h:269
Agraph_t * root
Definition cgraph.h:261
Agobj_t base
Definition cgraph.h:260
Agrec_t * data
stores programmer-defined data, access with AGDATA
Definition cgraph.h:212
graph or subgraph
Definition cgraph.h:424