Graphviz  2.35.20130930.0449
cluster.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 
15 #include "dot.h"
16 
17 static node_t*
18 map_interclust_node(node_t * n)
19 {
20  node_t *rv;
21 
22 #ifndef WITH_CGRAPH
23  if ((ND_clust(n) == NULL) || (ND_clust(n)->u.expanded))
24 #else /* WITH_CGRAPH */
25  if ((ND_clust(n) == NULL) || ( GD_expanded(ND_clust(n))) )
26 #endif /* WITH_CGRAPH */
27  rv = n;
28  else
29 #ifndef WITH_CGRAPH
30  rv = ND_clust(n)->u.rankleader[ND_rank(n)];
31 #else /* WITH_CGRAPH */
32  rv = GD_rankleader(ND_clust(n))[ND_rank(n)];
33 #endif /* WITH_CGRAPH */
34  return rv;
35 }
36 
37 /* make d slots starting at position pos (where 1 already exists) */
38 static void
39 make_slots(graph_t * root, int r, int pos, int d)
40 {
41  int i;
42  node_t *v, **vlist;
43 #ifndef WITH_CGRAPH
44  vlist = ND_rank(root)[r].v;
45 #else /* WITH_CGRAPH */
46  vlist = GD_rank(root)[r].v;
47 #endif /* WITH_CGRAPH */
48  if (d <= 0) {
49 #ifndef WITH_CGRAPH
50  for (i = pos - d + 1; i < ND_rank(root)[r].n; i++) {
51 #else /* WITH_CGRAPH */
52  for (i = pos - d + 1; i < GD_rank(root)[r].n; i++) {
53 #endif /* WITH_CGRAPH */
54  v = vlist[i];
55  ND_order(v) = i + d - 1;
56  vlist[ND_order(v)] = v;
57  }
58 #ifndef WITH_CGRAPH
59  for (i = ND_rank(root)[r].n + d - 1; i < ND_rank(root)[r].n; i++)
60 #else /* WITH_CGRAPH */
61  for (i = GD_rank(root)[r].n + d - 1; i < GD_rank(root)[r].n; i++)
62 #endif /* WITH_CGRAPH */
63  vlist[i] = NULL;
64  } else {
65 /*assert(ND_rank(root)[r].n + d - 1 <= ND_rank(root)[r].an);*/
66 #ifndef WITH_CGRAPH
67  for (i = ND_rank(root)[r].n - 1; i > pos; i--) {
68 #else /* WITH_CGRAPH */
69  for (i = GD_rank(root)[r].n - 1; i > pos; i--) {
70 #endif /* WITH_CGRAPH */
71  v = vlist[i];
72  ND_order(v) = i + d - 1;
73  vlist[ND_order(v)] = v;
74  }
75  for (i = pos + 1; i < pos + d; i++)
76  vlist[i] = NULL;
77  }
78 #ifndef WITH_CGRAPH
79  ND_rank(root)[r].n += d - 1;
80 #else /* WITH_CGRAPH */
81  GD_rank(root)[r].n += d - 1;
82 #endif /* WITH_CGRAPH */
83 }
84 
85 static node_t*
86 clone_vn(graph_t * g, node_t * vn)
87 {
88  node_t *rv;
89  int r;
90 
91  r = ND_rank(vn);
92  make_slots(g, r, ND_order(vn), 2);
93  rv = virtual_node(g);
94  ND_lw(rv) = ND_lw(vn);
95  ND_rw(rv) = ND_rw(vn);
96  ND_rank(rv) = ND_rank(vn);
97  ND_order(rv) = ND_order(vn) + 1;
98  GD_rank(g)[r].v[ND_order(rv)] = rv;
99  return rv;
100 }
101 
102 static void
103 map_path(node_t * from, node_t * to, edge_t * orig, edge_t * ve, int type)
104 {
105  int r;
106  node_t *u, *v;
107  edge_t *e;
108 
109  assert(ND_rank(from) < ND_rank(to));
110 
111  if ((agtail(ve) == from) && (aghead(ve) == to))
112  return;
113 
114  if (ED_count(ve) > 1) {
115  ED_to_virt(orig) = NULL;
116  if (ND_rank(to) - ND_rank(from) == 1) {
117  if ((e = find_fast_edge(from, to)) && (ports_eq(orig, e))) {
118  merge_oneway(orig, e);
119  if ((ND_node_type(from) == NORMAL)
120  && (ND_node_type(to) == NORMAL))
121  other_edge(orig);
122  return;
123  }
124  }
125  u = from;
126  for (r = ND_rank(from); r < ND_rank(to); r++) {
127  if (r < ND_rank(to) - 1)
128  v = clone_vn(agraphof(from), aghead(ve));
129  else
130  v = to;
131  e = virtual_edge(u, v, orig);
132  ED_edge_type(e) = type;
133  u = v;
134  ED_count(ve)--;
135  ve = ND_out(aghead(ve)).list[0];
136  }
137  } else {
138  if (ND_rank(to) - ND_rank(from) == 1) {
139  if ((ve = find_fast_edge(from, to)) && (ports_eq(orig, ve))) {
140  /*ED_to_orig(ve) = orig; */
141  ED_to_virt(orig) = ve;
142  ED_edge_type(ve) = type;
143  ED_count(ve)++;
144  if ((ND_node_type(from) == NORMAL)
145  && (ND_node_type(to) == NORMAL))
146  other_edge(orig);
147  } else {
148  ED_to_virt(orig) = NULL;
149  ve = virtual_edge(from, to, orig);
150  ED_edge_type(ve) = type;
151  }
152  }
153  if (ND_rank(to) - ND_rank(from) > 1) {
154  e = ve;
155  if (agtail(ve) != from) {
156  ED_to_virt(orig) = NULL;
157  e = ED_to_virt(orig) = virtual_edge(from, aghead(ve), orig);
158  delete_fast_edge(ve);
159  } else
160  e = ve;
161  while (ND_rank(aghead(e)) != ND_rank(to))
162  e = ND_out(aghead(e)).list[0];
163  if (aghead(e) != to) {
164  ve = e;
165  e = virtual_edge(agtail(e), to, orig);
166  ED_edge_type(e) = type;
167  delete_fast_edge(ve);
168  }
169  }
170  }
171 }
172 
173 static void
174 make_interclust_chain(graph_t * g, node_t * from, node_t * to, edge_t * orig)
175 {
176  int newtype;
177  node_t *u, *v;
178 
179  u = map_interclust_node(from);
180  v = map_interclust_node(to);
181  if ((u == from) && (v == to))
182  newtype = VIRTUAL;
183  else
184  newtype = CLUSTER_EDGE;
185  map_path(u, v, orig, ED_to_virt(orig), newtype);
186 }
187 
188 /*
189  * attach and install edges between clusters.
190  * essentially, class2() for interclust edges.
191  */
192 void interclexp(graph_t * subg)
193 {
194  graph_t *g;
195  node_t *n;
196  edge_t *e, *prev, *next;
197 
198  g = agroot(subg);
199  for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
200 
201  /* N.B. n may be in a sub-cluster of subg */
202  prev = NULL;
203  for (e = agfstedge(agroot(subg), n); e; e = next) {
204  next = agnxtedge(agroot(subg), e, n);
205  if (agcontains(subg, e))
206  continue;
207 
208 #ifdef WITH_CGRAPH
209  /* canonicalize edge */
210  e = AGMKOUT(e);
211 #endif
212  /* short/flat multi edges */
213  if (mergeable(prev, e)) {
214  if (ND_rank(agtail(e)) == ND_rank(aghead(e)))
215  ED_to_virt(e) = prev;
216  else
217  ED_to_virt(e) = NULL;
218  if (ED_to_virt(prev) == NULL)
219  continue; /* internal edge */
220  merge_chain(subg, e, ED_to_virt(prev), FALSE);
221  safe_other_edge(e);
222  continue;
223  }
224 
225  /* flat edges */
226  if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
227  edge_t* fe;
228  if ((fe = find_flat_edge(agtail(e), aghead(e))) == NULL) {
229  flat_edge(g, e);
230  prev = e;
231  } else if (e != fe) {
232  safe_other_edge(e);
233  if (!ED_to_virt(e)) merge_oneway(e, fe);
234  }
235  continue;
236  }
237 
238 /* This assertion is still valid if the new ranking is not used */
239 #ifndef WITH_CGRAPH
240  assert(ED_to_virt(e) != NULL);
241 #endif
242 
243  /* forward edges */
244  if (ND_rank(aghead(e)) > ND_rank(agtail(e))) {
245  make_interclust_chain(g, agtail(e), aghead(e), e);
246  prev = e;
247  continue;
248  }
249 
250  /* backward edges */
251  else {
252 /*
253 I think that make_interclust_chain should create call other_edge(e) anyway
254  if (agcontains(subg,agtail(e))
255  && agfindedge(subg->root,aghead(e),agtail(e))) other_edge(e);
256 */
257  make_interclust_chain(g, aghead(e), agtail(e), e);
258  prev = e;
259  }
260  }
261  }
262 }
263 
264 static void
265 merge_ranks(graph_t * subg)
266 {
267  int i, d, r, pos, ipos;
268  node_t *v;
269  graph_t *root;
270 
271  root = agroot(subg);
272  if (GD_minrank(subg) > 0)
273 #ifndef WITH_CGRAPH
274  ND_rank(root)[GD_minrank(subg) - 1].valid = FALSE;
275 #else /* WITH_CGRAPH */
276  GD_rank(root)[GD_minrank(subg) - 1].valid = FALSE;
277 #endif /* WITH_CGRAPH */
278  for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
279  d = GD_rank(subg)[r].n;
280 #ifndef WITH_CGRAPH
281  ipos = pos = GD_rankleader(subg)[r]->u.order;
282 #else /* WITH_CGRAPH */
283  ipos = pos = ND_order(GD_rankleader(subg)[r]);
284 #endif /* WITH_CGRAPH */
285  make_slots(root, r, pos, d);
286  for (i = 0; i < GD_rank(subg)[r].n; i++) {
287 #ifndef WITH_CGRAPH
288  v = ND_rank(root)[r].v[pos] = GD_rank(subg)[r].v[i];
289 #else /* WITH_CGRAPH */
290  v = GD_rank(root)[r].v[pos] = GD_rank(subg)[r].v[i];
291 #endif /* WITH_CGRAPH */
292  ND_order(v) = pos++;
293 #ifndef WITH_CGRAPH
294  v->graph = subg->root;
295 #else /* WITH_CGRAPH */
296  /* real nodes automatically have v->root = root graph */
297  if (ND_node_type(v) == VIRTUAL)
298  v->root = root;
299 #endif /* WITH_CGRAPH */
300  delete_fast_node(subg, v);
301  fast_node(agroot(subg), v);
302  GD_n_nodes(agroot(subg))++;
303  }
304 #ifndef WITH_CGRAPH
305  GD_rank(subg)[r].v = ND_rank(root)[r].v + ipos;
306  ND_rank(root)[r].valid = FALSE;
307 #else /* WITH_CGRAPH */
308  GD_rank(subg)[r].v = GD_rank(root)[r].v + ipos;
309  GD_rank(root)[r].valid = FALSE;
310 #endif /* WITH_CGRAPH */
311  }
312  if (r < GD_maxrank(root))
313  GD_rank(root)[r].valid = FALSE;
314  GD_expanded(subg) = TRUE;
315 }
316 
317 static void
318 remove_rankleaders(graph_t * g)
319 {
320  int r;
321  node_t *v;
322  edge_t *e;
323 
324  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
325  v = GD_rankleader(g)[r];
326 
327  /* remove the entire chain */
328  while ((e = ND_out(v).list[0]))
329  delete_fast_edge(e);
330  while ((e = ND_in(v).list[0]))
331  delete_fast_edge(e);
332  delete_fast_node(agroot(g), v);
333  GD_rankleader(g)[r] = NULL;
334  }
335 }
336 
337 /* delete virtual nodes of a cluster, and install real nodes or sub-clusters */
339 {
340  /* build internal structure of the cluster */
341  class2(subg);
342  GD_comp(subg).size = 1;
343  GD_comp(subg).list[0] = GD_nlist(subg);
344  allocate_ranks(subg);
345  build_ranks(subg, 0);
346  merge_ranks(subg);
347 
348  /* build external structure of the cluster */
349  interclexp(subg);
350  remove_rankleaders(subg);
351 }
352 
353 /* this function marks every node in <g> with its top-level cluster under <g> */
355 {
356  int c;
357  node_t *n, *nn, *vn;
358  edge_t *orig, *e;
359  graph_t *clust;
360 
361  /* remove sub-clusters below this level */
362  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
363  if (ND_ranktype(n) == CLUSTER)
364  UF_singleton(n);
365  ND_clust(n) = NULL;
366  }
367 
368  for (c = 1; c <= GD_n_cluster(g); c++) {
369  clust = GD_clust(g)[c];
370  for (n = agfstnode(clust); n; n = nn) {
371  nn = agnxtnode(clust,n);
372  if (ND_ranktype(n) != NORMAL) {
373  agerr(AGWARN,
374  "%s was already in a rankset, deleted from cluster %s\n",
375  agnameof(n), agnameof(g));
376  agdelete(clust,n);
377  continue;
378  }
379  UF_setname(n, GD_leader(clust));
380  ND_clust(n) = clust;
381  ND_ranktype(n) = CLUSTER;
382 
383  /* here we mark the vnodes of edges in the cluster */
384  for (orig = agfstout(clust, n); orig;
385  orig = agnxtout(clust, orig)) {
386  if ((e = ED_to_virt(orig))) {
387 #ifndef WITH_CGRAPH
388  while (e && (vn = e->head)->u.node_type == VIRTUAL) {
389 #else /* WITH_CGRAPH */
390  while (e && ND_node_type(vn =aghead(e)) == VIRTUAL) {
391 #endif /* WITH_CGRAPH */
392  ND_clust(vn) = clust;
393  e = ND_out(aghead(e)).list[0];
394  /* trouble if concentrators and clusters are mixed */
395  }
396  }
397  }
398  }
399  }
400 }
401 
402 void build_skeleton(graph_t * g, graph_t * subg)
403 {
404  int r;
405  node_t *v, *prev, *rl;
406  edge_t *e;
407 
408  prev = NULL;
409  GD_rankleader(subg) = N_NEW(GD_maxrank(subg) + 2, node_t *);
410  for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
411  v = GD_rankleader(subg)[r] = virtual_node(g);
412  ND_rank(v) = r;
413  ND_ranktype(v) = CLUSTER;
414  ND_clust(v) = subg;
415  if (prev) {
416  e = virtual_edge(prev, v, NULL);
417  ED_xpenalty(e) *= CL_CROSS;
418  }
419  prev = v;
420  }
421 
422  /* set the counts on virtual edges of the cluster skeleton */
423  for (v = agfstnode(subg); v; v = agnxtnode(subg, v)) {
424  rl = GD_rankleader(subg)[ND_rank(v)];
425  ND_UF_size(rl)++;
426  for (e = agfstout(subg, v); e; e = agnxtout(subg, e)) {
427  for (r = ND_rank(agtail(e)); r < ND_rank(aghead(e)); r++) {
428  ED_count(ND_out(rl).list[0])++;
429  }
430  }
431  }
432  for (r = GD_minrank(subg); r <= GD_maxrank(subg); r++) {
433  rl = GD_rankleader(subg)[r];
434  if (ND_UF_size(rl) > 1)
435  ND_UF_size(rl)--;
436  }
437 }
438 
439 void install_cluster(graph_t * g, node_t * n, int pass, nodequeue * q)
440 {
441  int r;
442  graph_t *clust;
443 
444  clust = ND_clust(n);
445  if (GD_installed(clust) != pass + 1) {
446  for (r = GD_minrank(clust); r <= GD_maxrank(clust); r++)
447  install_in_rank(g, GD_rankleader(clust)[r]);
448  for (r = GD_minrank(clust); r <= GD_maxrank(clust); r++)
449  enqueue_neighbors(q, GD_rankleader(clust)[r], pass);
450  GD_installed(clust) = pass + 1;
451  }
452 }
453 
454 static void mark_lowcluster_basic(Agraph_t * g);
456 {
457  Agnode_t *n, *vn;
458  Agedge_t *orig, *e;
459 
460  /* first, zap any previous cluster labelings */
461  for (n = agfstnode(root); n; n = agnxtnode(root, n)) {
462  ND_clust(n) = NULL;
463  for (orig = agfstout(root, n); orig; orig = agnxtout(root, orig)) {
464  if ((e = ED_to_virt(orig))) {
465 #ifndef WITH_CGRAPH
466  while (e && (vn = e->head)->u.node_type == VIRTUAL) {
467 #else /* WITH_CGRAPH */
468  while (e && (ND_node_type(vn = aghead(e))) == VIRTUAL) {
469 #endif /* WITH_CGRAPH */
470  ND_clust(vn) = NULL;
471  e = ND_out(aghead(e)).list[0];
472  }
473  }
474  }
475  }
476 
477  /* do the recursion */
478  mark_lowcluster_basic(root);
479 }
480 
481 static void mark_lowcluster_basic(Agraph_t * g)
482 {
483  Agraph_t *clust;
484  Agnode_t *n, *vn;
485  Agedge_t *orig, *e;
486  int c;
487 
488  for (c = 1; c <= GD_n_cluster(g); c++) {
489  clust = GD_clust(g)[c];
490  mark_lowcluster_basic(clust);
491  }
492  /* see what belongs to this graph that wasn't already marked */
493  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
494  if (ND_clust(n) == NULL)
495  ND_clust(n) = g;
496  for (orig = agfstout(g, n); orig; orig = agnxtout(g, orig)) {
497  if ((e = ED_to_virt(orig))) {
498 #ifndef WITH_CGRAPH
499  while (e && (vn = e->head)->u.node_type == VIRTUAL) {
500 #else /* WITH_CGRAPH */
501  while (e && (ND_node_type(vn = aghead(e))) == VIRTUAL) {
502 #endif /* WITH_CGRAPH */
503  if (ND_clust(vn) == NULL)
504  ND_clust(vn) = g;
505  e = ND_out(aghead(e)).list[0];
506  }
507  }
508  }
509  }
510 }