Graphviz 13.0.0~dev.20250511.0440
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)
92 && (ND_node_type(to) == NORMAL))
93 other_edge(orig);
94 return;
95 }
96 }
97 u = from;
98 for (r = ND_rank(from); r < ND_rank(to); r++) {
99 if (r < ND_rank(to) - 1)
100 v = clone_vn(dot_root(from), aghead(ve));
101 else
102 v = to;
103 e = virtual_edge(u, v, orig);
104 ED_edge_type(e) = type;
105 u = v;
106 ED_count(ve)--;
107 ve = ND_out(aghead(ve)).list[0];
108 }
109 } else {
110 if (ND_rank(to) - ND_rank(from) == 1) {
111 if ((ve = find_fast_edge(from, to)) && (ports_eq(orig, ve))) {
112 /*ED_to_orig(ve) = orig; */
113 ED_to_virt(orig) = ve;
114 ED_edge_type(ve) = type;
115 ED_count(ve)++;
116 if ((ND_node_type(from) == NORMAL)
117 && (ND_node_type(to) == NORMAL))
118 other_edge(orig);
119 } else {
120 ED_to_virt(orig) = NULL;
121 ve = virtual_edge(from, to, orig);
122 ED_edge_type(ve) = type;
123 }
124 }
125 if (ND_rank(to) - ND_rank(from) > 1) {
126 if (agtail(ve) != from) {
127 ED_to_virt(orig) = NULL;
128 e = ED_to_virt(orig) = virtual_edge(from, aghead(ve), orig);
130 } else
131 e = ve;
132 while (ND_rank(aghead(e)) != ND_rank(to))
133 e = ND_out(aghead(e)).list[0];
134 if (aghead(e) != to) {
135 ve = e;
136 e = virtual_edge(agtail(e), to, orig);
137 ED_edge_type(e) = type;
139 }
140 }
141 }
142}
143
144static void make_interclust_chain(node_t * from, node_t * to, edge_t * orig) {
145 int newtype;
146 node_t *u, *v;
147
148 u = map_interclust_node(from);
149 v = map_interclust_node(to);
150 if ((u == from) && (v == to))
151 newtype = VIRTUAL;
152 else
153 newtype = CLUSTER_EDGE;
154 map_path(u, v, orig, ED_to_virt(orig), newtype);
155}
156
157/*
158 * attach and install edges between clusters.
159 * essentially, class2() for interclust edges.
160 */
161static void interclexp(graph_t * subg)
162{
163 graph_t *g;
164 node_t *n;
165 edge_t *e, *prev, *next;
166
167 g = dot_root(subg);
168 for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
169
170 /* N.B. n may be in a sub-cluster of subg */
171 prev = NULL;
172 for (e = agfstedge(g, n); e; e = next) {
173 next = agnxtedge(g, e, n);
174 if (agcontains(subg, e))
175 continue;
176
177 /* canonicalize edge */
178 e = AGMKOUT(e);
179 /* short/flat multi edges */
180 if (mergeable(prev, e)) {
181 if (ND_rank(agtail(e)) == ND_rank(aghead(e)))
182 ED_to_virt(e) = prev;
183 else
184 ED_to_virt(e) = NULL;
185 if (ED_to_virt(prev) == NULL)
186 continue; /* internal edge */
187 ED_to_virt(e) = NULL;
188 merge_chain(subg, e, ED_to_virt(prev), false);
190 continue;
191 }
192
193 /* flat edges */
194 if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
195 edge_t* fe;
196 if ((fe = find_flat_edge(agtail(e), aghead(e))) == NULL) {
197 flat_edge(g, e);
198 prev = e;
199 } else if (e != fe) {
201 if (!ED_to_virt(e)) merge_oneway(e, fe);
202 }
203 continue;
204 }
205
206 /* forward edges */
207 if (ND_rank(aghead(e)) > ND_rank(agtail(e))) {
209 prev = e;
210 continue;
211 }
212
213 /* backward edges */
214 else {
215/*
216I think that make_interclust_chain should create call other_edge(e) anyway
217 if (agcontains(subg,agtail(e))
218 && agfindedge(g,aghead(e),agtail(e))) other_edge(e);
219*/
221 prev = e;
222 }
223 }
224 }
225}
226
227static void
229{
230 int i, d, r, pos, ipos;
231 node_t *v;
232 graph_t *root;
233
234 assert(GD_minrank(subg) <= GD_maxrank(subg) && "corrupted rank bounds");
235
236 root = dot_root(subg);
237 if (GD_minrank(subg) > 0)
238 GD_rank(root)[GD_minrank(subg) - 1].valid = false;
239 for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
240 d = GD_rank(subg)[r].n;
241 ipos = pos = ND_order(GD_rankleader(subg)[r]);
242 make_slots(root, r, pos, d);
243 for (i = 0; i < GD_rank(subg)[r].n; i++) {
244 v = GD_rank(root)[r].v[pos] = GD_rank(subg)[r].v[i];
245 ND_order(v) = pos++;
246 /* real nodes automatically have v->root = root graph */
247 if (ND_node_type(v) == VIRTUAL)
248 v->root = agroot(root);
249 delete_fast_node(subg, v);
250 fast_node(root, v);
251 }
252 GD_rank(subg)[r].v = GD_rank(root)[r].v + ipos;
253 GD_rank(root)[r].valid = false;
254 }
255 if (r < GD_maxrank(root))
256 GD_rank(root)[r].valid = false;
257 GD_expanded(subg) = true;
258}
259
260static void
262{
263 int r;
264 node_t *v;
265 edge_t *e;
266
267 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
268 v = GD_rankleader(g)[r];
269
270 /* remove the entire chain */
271 while ((e = ND_out(v).list[0])) {
273 free(e->base.data);
274 free(e);
275 }
276 while ((e = ND_in(v).list[0])) {
278 free(e);
279 }
281 free(ND_in(v).list);
282 free(ND_out(v).list);
283 free(v->base.data);
284 free(v);
285 GD_rankleader(g)[r] = NULL;
286 }
287}
288
289/* delete virtual nodes of a cluster, and install real nodes or sub-clusters */
291 /* build internal structure of the cluster */
292 class2(subg);
293 GD_comp(subg).size = 1;
294 GD_comp(subg).list[0] = GD_nlist(subg);
295 allocate_ranks(subg);
296 ints_t scratch = {0};
297 const int rc = build_ranks(subg, 0, &scratch);
298 ints_free(&scratch);
299 if (rc != 0) {
300 return rc;
301 }
302 merge_ranks(subg);
303
304 /* build external structure of the cluster */
305 interclexp(subg);
306 remove_rankleaders(subg);
307 return 0;
308}
309
310/* this function marks every node in <g> with its top-level cluster under <g> */
312{
313 int c;
314 node_t *n, *nn, *vn;
315 edge_t *orig, *e;
316 graph_t *clust;
317
318 /* remove sub-clusters below this level */
319 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
320 if (ND_ranktype(n) == CLUSTER)
321 UF_singleton(n);
322 ND_clust(n) = NULL;
323 }
324
325 for (c = 1; c <= GD_n_cluster(g); c++) {
326 clust = GD_clust(g)[c];
327 for (n = agfstnode(clust); n; n = nn) {
328 nn = agnxtnode(clust,n);
329 if (ND_ranktype(n) != NORMAL) {
331 "%s was already in a rankset, deleted from cluster %s\n",
332 agnameof(n), agnameof(g));
333 agdelete(clust,n);
334 continue;
335 }
336 UF_setname(n, GD_leader(clust));
337 ND_clust(n) = clust;
338 ND_ranktype(n) = CLUSTER;
339
340 /* here we mark the vnodes of edges in the cluster */
341 for (orig = agfstout(clust, n); orig;
342 orig = agnxtout(clust, orig)) {
343 if ((e = ED_to_virt(orig))) {
344 while (e && ND_node_type(vn =aghead(e)) == VIRTUAL) {
345 ND_clust(vn) = clust;
346 e = ND_out(aghead(e)).list[0];
347 /* trouble if concentrators and clusters are mixed */
348 }
349 }
350 }
351 }
352 }
353}
354
356{
357 int r;
358 node_t *v, *prev, *rl;
359 edge_t *e;
360
361 prev = NULL;
362 GD_rankleader(subg) = gv_calloc(GD_maxrank(subg) + 2, sizeof(node_t*));
363 for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
364 v = GD_rankleader(subg)[r] = virtual_node(g);
365 ND_rank(v) = r;
366 ND_ranktype(v) = CLUSTER;
367 ND_clust(v) = subg;
368 if (prev) {
369 e = virtual_edge(prev, v, NULL);
370 ED_xpenalty(e) *= CL_CROSS;
371 }
372 prev = v;
373 }
374
375 /* set the counts on virtual edges of the cluster skeleton */
376 for (v = agfstnode(subg); v; v = agnxtnode(subg, v)) {
377 rl = GD_rankleader(subg)[ND_rank(v)];
378 ND_UF_size(rl)++;
379 for (e = agfstout(subg, v); e; e = agnxtout(subg, e)) {
380 for (r = ND_rank(agtail(e)); r < ND_rank(aghead(e)); r++) {
381 ED_count(ND_out(rl).list[0])++;
382 }
383 }
384 }
385 for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
386 rl = GD_rankleader(subg)[r];
387 if (ND_UF_size(rl) > 1)
388 ND_UF_size(rl)--;
389 }
390}
391
392int install_cluster(graph_t *g, node_t *n, int pass, node_queue_t *q) {
393 int r;
394 graph_t *clust;
395
396 clust = ND_clust(n);
397 if (GD_installed(clust) != pass + 1) {
398 for (r = GD_minrank(clust); r <= GD_maxrank(clust); r++) {
399 const int rc = install_in_rank(g, GD_rankleader(clust)[r]);
400 if (rc != 0) {
401 return rc;
402 }
403 }
404 for (r = GD_minrank(clust); r <= GD_maxrank(clust); r++)
405 enqueue_neighbors(q, GD_rankleader(clust)[r], pass);
406 GD_installed(clust) = pass + 1;
407 }
408 return 0;
409}
410
411static void mark_lowcluster_basic(Agraph_t * g);
413{
414 Agnode_t *n, *vn;
415 Agedge_t *orig, *e;
416
417 /* first, zap any previous cluster labelings */
418 for (n = agfstnode(root); n; n = agnxtnode(root, n)) {
419 ND_clust(n) = NULL;
420 for (orig = agfstout(root, n); orig; orig = agnxtout(root, orig)) {
421 if ((e = ED_to_virt(orig))) {
422 while (e && (ND_node_type(vn = aghead(e))) == VIRTUAL) {
423 ND_clust(vn) = NULL;
424 e = ND_out(aghead(e)).list[0];
425 }
426 }
427 }
428 }
429
430 /* do the recursion */
432}
433
435{
436 Agraph_t *clust;
437 Agnode_t *n, *vn;
438 Agedge_t *orig, *e;
439 int c;
440
441 for (c = 1; c <= GD_n_cluster(g); c++) {
442 clust = GD_clust(g)[c];
444 }
445 /* see what belongs to this graph that wasn't already marked */
446 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
447 if (ND_clust(n) == NULL)
448 ND_clust(n) = g;
449 for (orig = agfstout(g, n); orig; orig = agnxtout(g, orig)) {
450 if ((e = ED_to_virt(orig))) {
451 while (e && (ND_node_type(vn = aghead(e))) == VIRTUAL) {
452 if (ND_clust(vn) == NULL)
453 ND_clust(vn) = g;
454 e = ND_out(aghead(e)).list[0];
455 }
456 }
457 }
458 }
459}
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:134
void class2(graph_t *g)
Definition class2.c:159
bool mergeable(edge_t *e, edge_t *f)
Definition class2.c:154
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:534
void other_edge(Agedge_t *)
Definition fastgr.c:115
void delete_fast_node(Agraph_t *, Agnode_t *)
Definition fastgr.c:189
int build_ranks(Agraph_t *, int, ints_t *)
Definition mincross.c:1250
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition fastgr.c:170
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:1326
void allocate_ranks(Agraph_t *)
Definition mincross.c:1174
void flat_edge(Agraph_t *, Agedge_t *)
Definition fastgr.c:215
void fast_node(Agraph_t *, Agnode_t *)
Definition fastgr.c:175
void delete_fast_edge(Agedge_t *)
Definition fastgr.c:108
void merge_oneway(Agedge_t *, Agedge_t *)
Definition fastgr.c:289
int install_in_rank(Agraph_t *, Agnode_t *)
Definition mincross.c:1202
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:200
expr procedure type
Definition exparse.y:206
void free(void *)
node NULL
Definition grammar.y:163
#define AGMKOUT(e)
Definition cgraph.h:980
#define ED_xpenalty(e)
Definition types.h:601
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:24
#define ED_count(e)
Definition types.h:580
#define agtail(e)
Definition cgraph.h:986
#define ED_edge_type(e)
Definition types.h:582
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition edge.c:94
#define aghead(e)
Definition cgraph.h:987
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:39
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition edge.c:85
#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:47
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:40
#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:434
static void merge_ranks(graph_t *subg)
Definition cluster.c:228
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:392
static void remove_rankleaders(graph_t *g)
Definition cluster.c:261
static void interclexp(graph_t *subg)
Definition cluster.c:161
int expand_cluster(graph_t *subg)
Definition cluster.c:290
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:412
void build_skeleton(graph_t *g, graph_t *subg)
Definition cluster.c:355
void mark_clusters(graph_t *g)
Definition cluster.c:311
static void make_interclust_chain(node_t *from, node_t *to, edge_t *orig)
Definition cluster.c:144
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