Graphviz 16.1.3~dev.20261121.1645
Loading...
Searching...
No Matches
rank.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 v2.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/org/documents/epl-2.0/EPL-2.0.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11/*
12 * Rank the nodes of a directed graph, subject to user-defined
13 * sets of nodes to be kept on the same, min, or max rank.
14 * The temporary acyclic fast graph is constructed and ranked
15 * by a network-simplex technique. Then ranks are propagated
16 * to non-leader nodes and temporary edges are deleted.
17 * Leaf nodes and top-level clusters are left collapsed, though.
18 * Assigns global minrank and maxrank of graph and all clusters.
19 *
20 * TODO: safety code. must not be in two clusters at same level.
21 * must not be in same/min/max/rank and a cluster at the same time.
22 * watch out for interactions between leaves and clusters.
23 */
24
25#include "config.h"
26
27#include <common/utils.h>
28#include <dotgen/dot.h>
29#include <limits.h>
30#include <stdbool.h>
31#include <stdint.h>
32#include <stdlib.h>
33#include <util/alloc.h>
34#include <util/gv_math.h>
35#include <util/list.h>
36#include <util/streq.h>
37
38static void dot1_rank(graph_t *g);
39static void dot2_rank(graph_t *g);
40
41typedef LIST(edge_t *) edge_set_t;
42
45static void renewlist(elist *L, edge_set_t *track) {
46 for (size_t i = L->size; i != SIZE_MAX; i--) {
47 if (track != NULL && L->list[i] != NULL) {
48 LIST_APPEND(track, L->list[i]);
49 }
50 L->list[i] = NULL;
51 }
52 L->size = 0;
53}
54
66static int edge_ptr_cmp(const void *x, const void *y) {
67 const edge_t *const *a = x;
68 const edge_t *const *b = y;
69 const uintptr_t addr_a = (uintptr_t)*a;
70 const uintptr_t addr_b = (uintptr_t)*b;
71 if (addr_a < addr_b) {
72 return -1;
73 }
74 if (addr_a > addr_b) {
75 return 1;
76 }
77 return 0;
78}
79
80static void cleanup1(graph_t *g) {
81 edge_t *e, *f;
82
83 edge_set_t to_free = {0};
84
85 for (size_t c = 0; c < GD_comp(g).size; c++) {
86 GD_nlist(g) = GD_comp(g).list[c];
87 for (node_t *n = GD_nlist(g), *next, *prev = NULL; n; n = next) {
88 next = ND_next(n);
89 // out edges are owning, so only track their removal
90 renewlist(&ND_in(n), NULL);
91 renewlist(&ND_out(n), &to_free);
92 ND_mark(n) = false;
93 // If this is a slack node, it exists _only_ in the component lists
94 // that we are about to drop. Remove and deallocate slack nodes now to
95 // avoid leaking these.
96 if (ND_node_type(n) == SLACKNODE) {
97 if (prev == NULL) {
98 GD_comp(g).list[c] = next;
99 GD_nlist(g) = next;
100 } else {
101 ND_next(prev) = next;
102 }
103 if (next != NULL) {
104 ND_prev(next) = prev;
105 }
106 free_list(ND_in(n));
107 free_list(ND_out(n));
108 free(n->base.data);
109 free(n);
110 } else {
111 prev = n;
112 }
113 }
114 }
115 for (node_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
116 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
117 f = ED_to_virt(e);
118 /* Null out any other references to f to make sure we don't
119 * handle it a second time. For example, parallel multiedges
120 * share a virtual edge.
121 */
122 if (f && e != ED_to_orig(f)) {
123 ED_to_virt(e) = NULL;
124 }
125 }
126 }
127 for (node_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
128 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
129 f = ED_to_virt(e);
130 if (f && ED_to_orig(f) == e) {
131 LIST_APPEND(&to_free, f);
132 ED_to_virt(e) = NULL;
133 }
134 }
135 }
136
137 // free all the edges we removed
138 // XXX: Accruing all the pointers, including duplicates, and then sorting to
139 // avoid duplicate frees is suboptimal. If this turns out to be a
140 // performance problem, replace `edge_set_t` with a proper set.
141 LIST_SORT(&to_free, edge_ptr_cmp);
142 edge_t *previous = NULL;
143 for (size_t i = 0; i < LIST_SIZE(&to_free); ++i) {
144 edge_t *const current = LIST_GET(&to_free, i);
145 if (current != previous) {
146 if (previous != NULL) {
147 free(previous->base.data);
148 }
149 free(previous);
150 previous = current;
151 }
152 }
153 if (previous != NULL) {
154 free(previous->base.data);
155 }
156 free(previous);
157 LIST_FREE(&to_free);
158
159 free(GD_comp(g).list);
160 GD_comp(g).list = NULL;
161 GD_comp(g).size = 0;
162}
163
164/* When there are edge labels, extra ranks are reserved here for the virtual
165 * nodes of the labels. This is done by doubling the input edge lengths.
166 * The input rank separation is adjusted to compensate.
167 */
168static void edgelabel_ranks(graph_t *g) {
169 node_t *n;
170 edge_t *e;
171
172 if (GD_has_labels(g) & EDGE_LABEL) {
173 for (n = agfstnode(g); n; n = agnxtnode(g, n))
174 for (e = agfstout(g, n); e; e = agnxtout(g, e))
175 ED_minlen(e) *= 2;
176 GD_ranksep(g) = (GD_ranksep(g) + 1) / 2;
177 }
178}
179
180/* Merge the nodes of a min, max, or same rank set. */
181static void collapse_rankset(graph_t *g, graph_t *subg, char kind) {
182 node_t *u, *v;
183
184 u = v = agfstnode(subg);
185 if (u) {
186 ND_ranktype(u) = kind;
187 while ((v = agnxtnode(subg, v))) {
188 UF_union(u, v);
189 ND_ranktype(v) = ND_ranktype(u);
190 }
191 switch (kind) {
192 case MINRANK:
193 case SOURCERANK:
194 if (GD_minset(g) == NULL)
195 GD_minset(g) = u;
196 else
197 GD_minset(g) = UF_union(GD_minset(g), u);
198 break;
199 case MAXRANK:
200 case SINKRANK:
201 if (GD_maxset(g) == NULL)
202 GD_maxset(g) = u;
203 else
204 GD_maxset(g) = UF_union(GD_maxset(g), u);
205 break;
206 default:
207 break;
208 }
209 if (kind == SOURCERANK) {
210 ND_ranktype(GD_minset(g)) = kind;
211 } else if (kind == SINKRANK) {
212 ND_ranktype(GD_maxset(g)) = kind;
213 }
214 }
215}
216
217static char rankset_kind(graph_t *g);
218
219static char rank_set_class(graph_t *g) {
220
221 if (is_a_cluster(g))
222 return CLUSTER;
223 const char val = rankset_kind(g);
224 GD_set_type(g) = val;
225 return val;
226}
227
228static int make_new_cluster(graph_t *g, graph_t *subg) {
229 int cno;
230 cno = ++(GD_n_cluster(g));
231 GD_clust(g) =
232 gv_recalloc(GD_clust(g), GD_n_cluster(g), cno + 1, sizeof(graph_t *));
233 GD_clust(g)[cno] = subg;
234 do_graph_label(subg);
235 return cno;
236}
237
238static void node_induce(graph_t *par, graph_t *g) {
239 node_t *n, *nn;
240 edge_t *e;
241 int i;
242
243 /* enforce that a node is in at most one cluster at this level */
244 for (n = agfstnode(g); n; n = nn) {
245 nn = agnxtnode(g, n);
246 if (ND_ranktype(n)) {
247 agdelete(g, n);
248 continue;
249 }
250 for (i = 1; i < GD_n_cluster(par); i++)
251 if (agcontains(GD_clust(par)[i], n))
252 break;
253 if (i < GD_n_cluster(par))
254 agdelete(g, n);
255 ND_clust(n) = NULL;
256 }
257
258 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
259 for (e = agfstout(dot_root(g), n); e; e = agnxtout(dot_root(g), e)) {
260 if (agcontains(g, aghead(e)))
261 agsubedge(g, e, 1);
262 }
263 }
264}
265
267 node_t *n, *leader = NULL;
268 GD_minrank(g) = INT_MAX;
269 GD_maxrank(g) = -1;
270 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
271 if (GD_maxrank(g) < ND_rank(n))
272 GD_maxrank(g) = ND_rank(n);
273 if (GD_minrank(g) > ND_rank(n))
274 GD_minrank(g) = ND_rank(n);
275 if (leader == NULL)
276 leader = n;
277 else {
278 if (ND_rank(n) < ND_rank(leader))
279 leader = n;
280 }
281 }
282 GD_leader(g) = leader;
283}
284
285static void cluster_leader(graph_t *clust) {
286 node_t *leader, *n;
287 int maxrank = 0;
288
289 /* find number of ranks and select a leader */
290 leader = NULL;
291 for (n = GD_nlist(clust); n; n = ND_next(n)) {
292 if (ND_rank(n) == 0 && ND_node_type(n) == NORMAL)
293 leader = n;
294 if (maxrank < ND_rank(n))
295 maxrank = ND_rank(n);
296 }
297 assert(leader != NULL);
298 GD_leader(clust) = leader;
299
300 for (n = agfstnode(clust); n; n = agnxtnode(clust, n)) {
301 assert(ND_UF_size(n) <= 1 || n == leader);
302 UF_union(n, leader);
303 ND_ranktype(n) = CLUSTER;
304 }
305}
306
307/*
308 * A cluster is collapsed in three steps.
309 * 1) The nodes of the cluster are ranked locally.
310 * 2) The cluster is collapsed into one node on the least rank.
311 * 3) In class1(), any inter-cluster edges are converted using
312 * the "virtual node + 2 edges" trick.
313 */
314static void collapse_cluster(graph_t *g, graph_t *subg) {
315 if (GD_parent(subg)) {
316 return;
317 }
318 GD_parent(subg) = g;
319 node_induce(g, subg);
320 if (agfstnode(subg) == NULL)
321 return;
322 make_new_cluster(g, subg);
323 if (CL_type == LOCAL) {
324 dot1_rank(subg);
325 cluster_leader(subg);
326 } else
327 dot_scan_ranks(subg);
328}
329
330/* Execute union commands for "same rank" subgraphs and clusters. */
331static void collapse_sets(graph_t *rg, graph_t *g) {
332 graph_t *subg;
333
334 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
335 const char c = rank_set_class(subg);
336 if (c) {
337 if (c == CLUSTER && CL_type == LOCAL)
338 collapse_cluster(rg, subg);
339 else
340 collapse_rankset(rg, subg, c);
341 } else
342 collapse_sets(rg, subg);
343 }
344}
345
346static void find_clusters(graph_t *g) {
347 graph_t *subg;
348 for (subg = agfstsubg(dot_root(g)); subg; subg = agnxtsubg(subg)) {
349 if (GD_set_type(subg) == CLUSTER)
350 collapse_cluster(g, subg);
351 }
352}
353
354static void set_minmax(graph_t *g) {
355 int c;
356
357 GD_minrank(g) += ND_rank(GD_leader(g));
358 GD_maxrank(g) += ND_rank(GD_leader(g));
359 for (c = 1; c <= GD_n_cluster(g); c++)
360 set_minmax(GD_clust(g)[c]);
361}
362
363/* To ensure that min and max rank nodes always have the intended rank
364 * assignment, reverse any incompatible edges.
365 */
367 node_t *n;
368 edge_t *e;
369 point slen;
370
371 slen.x = slen.y = 0;
372 if (GD_maxset(g) == NULL && GD_minset(g) == NULL)
373 return slen;
374 if (GD_minset(g) != NULL)
375 GD_minset(g) = UF_find(GD_minset(g));
376 if (GD_maxset(g) != NULL)
377 GD_maxset(g) = UF_find(GD_maxset(g));
378
379 if ((n = GD_maxset(g))) {
380 slen.y = ND_ranktype(GD_maxset(g)) == SINKRANK;
381 while ((e = ND_out(n).list[0])) {
382 assert(aghead(e) == UF_find(aghead(e)));
383 reverse_edge(e);
384 }
385 }
386 if ((n = GD_minset(g))) {
387 slen.x = ND_ranktype(GD_minset(g)) == SOURCERANK;
388 while ((e = ND_in(n).list[0])) {
389 assert(agtail(e) == UF_find(agtail(e)));
390 reverse_edge(e);
391 }
392 }
393 return slen;
394}
395
396static int minmax_edges2(graph_t *g, point slen) {
397 node_t *n;
398 edge_t *e = 0;
399
400 if (GD_maxset(g) || GD_minset(g)) {
401 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
402 if (n != UF_find(n))
403 continue;
404 if (ND_out(n).size == 0 && GD_maxset(g) && n != GD_maxset(g)) {
405 e = virtual_edge(n, GD_maxset(g), NULL);
406 ED_minlen(e) = slen.y;
407 ED_weight(e) = 0;
408 }
409 if (ND_in(n).size == 0 && GD_minset(g) && n != GD_minset(g)) {
410 e = virtual_edge(GD_minset(g), n, NULL);
411 ED_minlen(e) = slen.x;
412 ED_weight(e) = 0;
413 }
414 }
415 }
416 return e != 0;
417}
418
419/* Run the network simplex algorithm on each component. */
420void rank1(graph_t *g) {
421 int maxiter = INT_MAX;
422 char *s;
423
424 if ((s = agget(g, "nslimit1")))
425 maxiter = scale_clamp(agnnodes(g), atof(s));
426 for (size_t c = 0; c < GD_comp(g).size; c++) {
427 GD_nlist(g) = GD_comp(g).list[c];
428 rank(g, GD_n_cluster(g) == 0 ? 1 : 0, maxiter); // TB balance
429 }
430}
431
432/*
433 * Assigns ranks of non-leader nodes.
434 * Expands same, min, max rank sets.
435 * Leaf sets and clusters remain merged.
436 * Sets minrank and maxrank appropriately.
437 */
438static void expand_ranksets(graph_t *g) {
439 int c;
440 node_t *n, *leader;
441
442 if ((n = agfstnode(g))) {
443 GD_minrank(g) = INT_MAX;
444 GD_maxrank(g) = -1;
445 while (n) {
446 leader = UF_find(n);
447 /* The following works because ND_rank(n) == 0 if n is not in a
448 * cluster, and ND_rank(n) = the local rank offset if n is in
449 * a cluster. */
450 if (leader != n)
451 ND_rank(n) += ND_rank(leader);
452
453 if (GD_maxrank(g) < ND_rank(n))
454 GD_maxrank(g) = ND_rank(n);
455 if (GD_minrank(g) > ND_rank(n))
456 GD_minrank(g) = ND_rank(n);
457
458 if (ND_ranktype(n) && ND_ranktype(n) != LEAFSET)
459 UF_singleton(n);
460 n = agnxtnode(g, n);
461 }
462 if (g == dot_root(g)) {
463 if (CL_type == LOCAL) {
464 for (c = 1; c <= GD_n_cluster(g); c++)
465 set_minmax(GD_clust(g)[c]);
466 } else {
467 find_clusters(g);
468 }
469 }
470 } else {
471 GD_minrank(g) = GD_maxrank(g) = 0;
472 }
473}
474
475static void dot1_rank(graph_t *g) {
476 point p;
478
479 collapse_sets(g, g);
480 class1(g);
481 p = minmax_edges(g);
482 decompose(g, 0);
483 acyclic(g);
484 if (minmax_edges2(g, p))
485 decompose(g, 0);
486
487 rank1(g);
488
490 cleanup1(g);
491}
492
494 if (mapbool(agget(g, "newrank"))) {
495 GD_flags(g) |= NEW_RANK;
496 dot2_rank(g);
497 } else
498 dot1_rank(g);
499 if (Verbose)
500 fprintf(stderr, "Maxrank = %d, minrank = %d\n", GD_maxrank(g),
501 GD_minrank(g));
502}
503
504/* new ranking code:
505 * Allows more constraints
506 * Copy of level.c in dotgen2
507 * Many of the utility functions are simpler or gone with
508 * cgraph library.
509 */
510#define ROOT "\177root"
511
512/* hops is not used in dot, so we overload it to
513 * contain the index of the connected component
514 */
515#define ND_comp(n) ND_hops(n)
516
517static void set_parent(graph_t *g, graph_t *p) {
518 GD_parent(g) = p;
519 make_new_cluster(p, g);
520 node_induce(p, g);
521}
522
523static bool is_empty(graph_t *g) { return !agfstnode(g); }
524
525static char rankset_kind(graph_t *g) {
526 const char *const str = agget(g, "rank");
527
528 if (str) {
529 if (streq(str, "min"))
530 return MINRANK;
531 if (streq(str, "source"))
532 return SOURCERANK;
533 if (streq(str, "max"))
534 return MAXRANK;
535 if (streq(str, "sink"))
536 return SINKRANK;
537 if (streq(str, "same"))
538 return SAMERANK;
539 }
540 return NOCMD;
541}
542
543static bool is_nonconstraint(edge_t *e) {
544 char *constr;
545
546 if (E_constr && (constr = agxget(e, E_constr))) {
547 if (constr[0] && !mapbool(constr))
548 return true;
549 }
550 return false;
551}
552
553static node_t *find(node_t *n) {
554 node_t *set;
555 if ((set = ND_set(n))) {
556 if (set != n)
557 set = ND_set(n) = find(set);
558 } else
559 set = ND_set(n) = n;
560 return set;
561}
562
563static node_t *union_one(node_t *leader, node_t *n) {
564 if (n)
565 return (ND_set(find(n)) = find(leader));
566 else
567 return leader;
568}
569
571 node_t *n, *leader;
572
573 n = agfstnode(g);
574 if (!n)
575 return n;
576 leader = find(n);
577 while ((n = agnxtnode(g, n)))
578 union_one(leader, n);
579 return leader;
580}
581
582static void compile_samerank(graph_t *ug, graph_t *parent_clust) {
583 graph_t *s; /* subgraph being scanned */
584 graph_t *clust; /* cluster that contains the rankset */
585 node_t *n, *leader;
586
587 if (is_empty(ug))
588 return;
589 if (is_a_cluster(ug)) {
590 clust = ug;
591 if (parent_clust) {
592 GD_level(ug) = GD_level(parent_clust) + 1;
593 set_parent(ug, parent_clust);
594 } else
595 GD_level(ug) = 0;
596 } else
597 clust = parent_clust;
598
599 /* process subgraphs of this subgraph */
600 for (s = agfstsubg(ug); s; s = agnxtsubg(s))
601 compile_samerank(s, clust);
602
603 /* process this subgraph as a cluster */
604 if (is_a_cluster(ug)) {
605 for (n = agfstnode(ug); n; n = agnxtnode(ug, n)) {
606 if (ND_clust(n) == 0)
607 ND_clust(n) = ug;
608#ifdef DEBUG
609 fprintf(stderr, "(%s) %s %p\n", agnameof(ug), agnameof(n), ND_clust(n));
610#endif
611 }
612 }
613
614 /* process this subgraph as a rankset */
615 switch (rankset_kind(ug)) {
616 case SOURCERANK: // fall through
617 case MINRANK:
618 leader = union_all(ug);
619 if (clust != NULL) {
620 GD_minrep(clust) = union_one(leader, GD_minrep(clust));
621 }
622 break;
623 case SINKRANK: // fall through
624 case MAXRANK:
625 leader = union_all(ug);
626 if (clust != NULL) {
627 GD_maxrep(clust) = union_one(leader, GD_maxrep(clust));
628 }
629 break;
630 case SAMERANK:
631 leader = union_all(ug);
632 /* do we need to record these ranksets? */
633 break;
634 case NOCMD:
635 break;
636 default: /* unrecognized - warn and do nothing */
637 agwarningf("%s has unrecognized rank=%s", agnameof(ug), agget(ug, "rank"));
638 }
639
640 /* a cluster may become degenerate */
641 if (is_a_cluster(ug) && GD_minrep(ug)) {
642 if (GD_minrep(ug) == GD_maxrep(ug)) {
643 node_t *up = union_all(ug);
644 GD_minrep(ug) = up;
645 GD_maxrep(ug) = up;
646 }
647 }
648}
649
650static graph_t *dot_lca(graph_t *c0, graph_t *c1) {
651 while (c0 != c1) {
652 if (GD_level(c0) >= GD_level(c1))
653 c0 = GD_parent(c0);
654 else
655 c1 = GD_parent(c1);
656 }
657 return c0;
658}
659
661 graph_t *par, *ct, *ch;
662 ct = ND_clust(agtail(e));
663 ch = ND_clust(aghead(e));
664 if (ct == ch)
665 return true;
666 par = dot_lca(ct, ch);
667 if (par == ct || par == ch)
668 return true;
669 return false;
670}
671
673static node_t *makeXnode(graph_t *G, char *name) {
674 node_t *n = agnode(G, name, 1);
675 alloc_elist(4, ND_in(n));
676 alloc_elist(4, ND_out(n));
677 if (Last_node) {
678 ND_prev(n) = Last_node;
679 ND_next(Last_node) = n;
680 } else {
681 ND_prev(n) = NULL;
682 GD_nlist(G) = n;
683 }
684 Last_node = n;
685 ND_next(n) = NULL;
686
687 return n;
688}
689
690static void compile_nodes(graph_t *g, graph_t *Xg) {
691 /* build variables */
692 node_t *n;
693
694 Last_node = NULL;
695 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
696 if (find(n) == n)
697 ND_rep(n) = makeXnode(Xg, agnameof(n));
698 }
699 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
700 if (ND_rep(n) == 0)
701 ND_rep(n) = ND_rep(find(n));
702 }
703}
704
705static void merge(edge_t *e, int minlen, int weight) {
706 ED_minlen(e) = MAX(ED_minlen(e), minlen);
707 ED_weight(e) += weight;
708}
709
710static void strong(graph_t *g, node_t *t, node_t *h, edge_t *orig) {
711 edge_t *e;
712 if ((e = agfindedge(g, t, h)) || (e = agfindedge(g, h, t)) ||
713 (e = agedge(g, t, h, 0, 1)))
714 merge(e, ED_minlen(orig), ED_weight(orig));
715 else
716 agerrorf("ranking: failure to create strong constraint edge between nodes "
717 "%s and %s\n",
718 agnameof(t), agnameof(h));
719}
720
721static void compile_edges(graph_t *ug, graph_t *Xg) {
722 node_t *n;
723 edge_t *e;
724 node_t *Xt, *Xh;
725
726 /* build edge constraints */
727 for (n = agfstnode(ug); n; n = agnxtnode(ug, n)) {
728 Xt = ND_rep(n);
729 for (e = agfstout(ug, n); e; e = agnxtout(ug, e)) {
730 if (is_nonconstraint(e))
731 continue;
732 Xh = ND_rep(find(aghead(e)));
733 if (Xt == Xh)
734 continue;
735
736 if (is_internal_to_cluster(e)) {
737 graph_t *clust_tail = ND_clust(agtail(e));
738 graph_t *clust_head = ND_clust(aghead(e));
739 /* determine if graph requires reversed edge */
740 if ((clust_tail != NULL && find(agtail(e)) == GD_maxrep(clust_tail)) ||
741 (clust_head != NULL && find(aghead(e)) == GD_minrep(clust_head))) {
742 SWAP(&Xt, &Xh);
743 }
744 }
745 strong(Xg, Xt, Xh, e);
746 }
747 }
748}
749
750static void reverse_edge2(graph_t *g, edge_t *e) {
751 edge_t *rev;
752
753 rev = agfindedge(g, aghead(e), agtail(e));
754 if (!rev)
755 rev = agedge(g, aghead(e), agtail(e), 0, 1);
756 merge(rev, ED_minlen(e), ED_weight(e));
757 agdelete(g, e);
758}
759
760static void dfs(graph_t *g, node_t *v) {
761 edge_t *e, *f;
762 node_t *w;
763
764 if (ND_mark(v))
765 return;
766 ND_mark(v) = true;
767 ND_onstack(v) = true;
768 for (e = agfstout(g, v); e; e = f) {
769 f = agnxtout(g, e);
770 w = aghead(e);
771 if (ND_onstack(w))
772 reverse_edge2(g, e);
773 else {
774 if (!ND_mark(w))
775 dfs(g, w);
776 }
777 }
778 ND_onstack(v) = false;
779}
780
781static void break_cycles(graph_t *g) {
782 node_t *n;
783
784 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
785 ND_mark(n) = false;
786 ND_onstack(n) = false;
787 }
788 for (n = agfstnode(g); n; n = agnxtnode(g, n))
789 dfs(g, n);
790}
791
792/* This will only be called with the root graph or a cluster
793 * which are guaranteed to contain nodes. Thus, leader will be
794 * set.
795 */
796static void setMinMax(graph_t *g, int doRoot) {
797 int c, v;
798 node_t *n;
799 node_t *leader = NULL;
800
801 /* Do child clusters */
802 for (c = 1; c <= GD_n_cluster(g); c++)
803 setMinMax(GD_clust(g)[c], 0);
804
805 if (!GD_parent(g) && !doRoot) // root graph
806 return;
807
808 GD_minrank(g) = INT_MAX;
809 GD_maxrank(g) = -1;
810 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
811 v = ND_rank(n);
812 if (GD_maxrank(g) < v)
813 GD_maxrank(g) = v;
814 if (GD_minrank(g) > v) {
815 GD_minrank(g) = v;
816 leader = n;
817 }
818 }
819 GD_leader(g) = leader;
820}
821
822/* Store node rank information in original graph.
823 * Set rank bounds in graph and clusters
824 * Free added data structures.
825 *
826 * rank2 is called with balance=1, which ensures that minrank=0
827 */
828static void readout_levels(graph_t *g, graph_t *Xg, int ncc) {
829 node_t *n;
830 node_t *xn;
831 int *minrk = NULL;
832 int doRoot = 0;
833
834 GD_minrank(g) = INT_MAX;
835 GD_maxrank(g) = -1;
836 if (ncc > 1) {
837 int i;
838 minrk = gv_calloc(ncc + 1, sizeof(int));
839 for (i = 1; i <= ncc; i++)
840 minrk[i] = INT_MAX;
841 }
842 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
843 xn = ND_rep(find(n));
844 ND_rank(n) = ND_rank(xn);
845 if (GD_maxrank(g) < ND_rank(n))
846 GD_maxrank(g) = ND_rank(n);
847 if (GD_minrank(g) > ND_rank(n))
848 GD_minrank(g) = ND_rank(n);
849 if (minrk) {
850 ND_comp(n) = ND_comp(xn);
851 minrk[ND_comp(n)] = MIN(minrk[ND_comp(n)], ND_rank(n));
852 }
853 }
854 if (minrk) {
855 for (n = agfstnode(g); n; n = agnxtnode(g, n))
856 ND_rank(n) -= minrk[ND_comp(n)];
857 /* Non-uniform shifting, so recompute maxrank/minrank of root graph */
858 doRoot = 1;
859 } else if (GD_minrank(g) > 0) { /* should never happen */
860 int delta = GD_minrank(g);
861 for (n = agfstnode(g); n; n = agnxtnode(g, n))
862 ND_rank(n) -= delta;
863 GD_minrank(g) -= delta;
864 GD_maxrank(g) -= delta;
865 }
866
867 setMinMax(g, doRoot);
868
869 /* release fastgraph memory from Xg */
870 for (n = agfstnode(Xg); n; n = agnxtnode(Xg, n)) {
871 free_list(ND_in(n));
872 free_list(ND_out(n));
873 }
874
875 free(ND_alg(agfstnode(g)));
876 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
877 ND_alg(n) = NULL;
878 }
879 free(minrk);
880}
881
882static void dfscc(graph_t *g, node_t *n, int cc) {
883 edge_t *e;
884 if (ND_comp(n) == 0) {
885 ND_comp(n) = cc;
886 for (e = agfstout(g, n); e; e = agnxtout(g, e))
887 dfscc(g, aghead(e), cc);
888 for (e = agfstin(g, n); e; e = agnxtin(g, e))
889 dfscc(g, agtail(e), cc);
890 }
891}
892
894 int cc = 0;
895 node_t *n;
896
897 for (n = agfstnode(g); n; n = agnxtnode(g, n))
898 ND_comp(n) = 0;
899 for (n = agfstnode(g); n; n = agnxtnode(g, n))
900 if (ND_comp(n) == 0)
901 dfscc(g, n, ++cc);
902 if (cc > 1) {
903 node_t *root = makeXnode(g, ROOT);
904 int ncc = 1;
905 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
906 if (ND_comp(n) == ncc) {
907 (void)agedge(g, root, n, 0, 1);
908 ncc++;
909 }
910 }
911 }
912 return (cc);
913}
914
915static void add_fast_edges(graph_t *g) {
916 node_t *n;
917 edge_t *e;
918 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
919 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
920 elist_append(e, ND_out(n));
921 elist_append(e, ND_in(aghead(e)));
922 }
923 }
924}
925
926static void my_init_graph(Agraph_t *g, Agobj_t *graph, void *arg) {
927 int *sz = arg;
928 (void)g;
929 agbindrec(graph, "level graph rec", sz[0], true);
930}
931static void my_init_node(Agraph_t *g, Agobj_t *node, void *arg) {
932 int *sz = arg;
933 (void)g;
934 agbindrec(node, "level node rec", sz[1], true);
935}
936static void my_init_edge(Agraph_t *g, Agobj_t *edge, void *arg) {
937 int *sz = arg;
938 (void)g;
939 agbindrec(edge, "level edge rec", sz[2], true);
940}
942 {my_init_graph, 0, 0}, {my_init_node, 0, 0}, {my_init_edge, 0, 0}};
943
944int infosizes[] = {sizeof(Agraphinfo_t), sizeof(Agnodeinfo_t),
945 sizeof(Agedgeinfo_t)};
946
948 int ssize;
949 int ncc, maxiter = INT_MAX;
950 char *s;
951 graph_t *Xg;
952
953 Last_node = NULL;
954 Xg = agopen("level assignment constraints", Agstrictdirected, 0);
955 agbindrec(Xg, "level graph rec", sizeof(Agraphinfo_t), true);
957
959
960 if ((s = agget(g, "nslimit1")))
961 maxiter = scale_clamp(agnnodes(g), atof(s));
962 else
963 maxiter = INT_MAX;
964
965 compile_samerank(g, 0);
966 compile_nodes(g, Xg);
967 compile_edges(g, Xg);
968 break_cycles(Xg);
969 ncc = connect_components(Xg);
970 add_fast_edges(Xg);
971
972 if ((s = agget(g, "searchsize")))
973 ssize = atoi(s);
974 else
975 ssize = -1;
976 rank2(Xg, 1, maxiter, ssize);
977 readout_levels(g, Xg, ncc);
978#ifdef DEBUG
979 fprintf(stderr, "Xg %d nodes %d edges\n", agnnodes(Xg), agnedges(Xg));
980#endif
981 agclose(Xg);
982}
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 MIN(a, b)
Definition arith.h:28
#define MAX(a, b)
Definition arith.h:33
void class1(graph_t *g)
Definition class1.c:63
bool mapbool(const char *p)
Definition utils.c:321
node_t * UF_union(node_t *u, node_t *v)
Definition utils.c:115
node_t * UF_find(node_t *n)
Definition utils.c:106
void UF_singleton(node_t *u)
Definition utils.c:142
bool is_a_cluster(Agraph_t *g)
Definition utils.c:645
#define NOCMD
Definition const.h:33
#define NORMAL
Definition const.h:24
#define MINRANK
Definition const.h:35
#define SOURCERANK
Definition const.h:36
#define LOCAL
Definition const.h:43
#define EDGE_LABEL
Definition const.h:167
#define NEW_RANK
Definition const.h:243
#define SLACKNODE
Definition const.h:26
#define CLUSTER
Definition const.h:40
#define SAMERANK
Definition const.h:34
#define SINKRANK
Definition const.h:38
#define MAXRANK
Definition const.h:37
#define LEAFSET
Definition const.h:39
static Dtdisc_t constr
Definition constraint.c:54
void decompose(graph_t *g, int pass)
Definition decomp.c:108
Agraph_t * dot_root(void *p)
Definition dotinit.c:483
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition fastgr.c:170
#define G
Definition gdefs.h:7
int CL_type
Definition globals.h:61
Agsym_t * E_constr
Definition globals.h:85
static bool Verbose
Definition gml2gv.c:26
static attrs_t * L
Definition gmlparse.c:94
void free(void *)
edge
Definition gmlparse.y:246
#define SIZE_MAX
Definition gmlscan.c:347
node NULL
Definition grammar.y:181
int agnedges(Agraph_t *g)
Definition graph.c:169
int agnnodes(Agraph_t *g)
Definition graph.c:163
char * agget(void *obj, char *name)
Definition attr.c:447
char * agxget(void *obj, Agsym_t *sym)
Definition attr.c:457
void agpushdisc(Agraph_t *g, Agcbdisc_t *disc, void *state)
Definition obj.c:204
#define ED_to_orig(e)
Definition types.h:598
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition edge.c:234
#define ED_minlen(e)
Definition types.h:592
Agedge_t * agsubedge(Agraph_t *g, Agedge_t *e, int createflag)
Definition edge.c:323
Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition edge.c:70
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:28
#define agtail(e)
Definition cgraph.h:982
#define ED_weight(e)
Definition types.h:603
#define agfindedge(g, t, h)
Definition types.h:609
#define aghead(e)
Definition cgraph.h:983
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:42
Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition edge.c:57
#define ED_to_virt(e)
Definition types.h:599
void agwarningf(const char *fmt,...)
Definition agerror.c:175
void agerrorf(const char *fmt,...)
Definition agerror.c:167
#define GD_minrank(g)
Definition types.h:384
#define GD_maxrank(g)
Definition types.h:382
#define GD_maxset(g)
Definition types.h:383
#define GD_maxrep(g)
Definition types.h:387
#define GD_has_labels(g)
Definition types.h:368
#define GD_clust(g)
Definition types.h:360
#define GD_minrep(g)
Definition types.h:386
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Definition graph.c:97
#define GD_flags(g)
Definition types.h:365
#define GD_parent(g)
Definition types.h:351
#define GD_nlist(g)
Definition types.h:393
Agdesc_t Agstrictdirected
strict directed. A strict graph cannot have multi-edges or self-arcs.
Definition graph.c:279
#define GD_minset(g)
Definition types.h:385
#define GD_n_cluster(g)
Definition types.h:389
Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
creates a new graph with the given name and kind
Definition graph.c:44
#define GD_level(g)
Definition types.h:352
#define GD_set_type(g)
Definition types.h:399
#define GD_leader(g)
Definition types.h:375
#define GD_comp(g)
Definition types.h:362
#define GD_ranksep(g)
Definition types.h:397
Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition node.c:143
#define ND_rank(n)
Definition types.h:523
#define ND_prev(n)
Definition types.h:521
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:50
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:43
#define ND_next(n)
Definition types.h:510
#define ND_clust(n)
Definition types.h:489
#define ND_set(n)
Definition types.h:486
#define ND_alg(n)
Definition types.h:484
#define ND_node_type(n)
Definition types.h:511
#define ND_rep(n)
Definition types.h:496
#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:145
int agdelete(Agraph_t *g, void *obj)
deletes object. Equivalent to agclose, agdelnode, and agdeledge for obj being a graph,...
Definition obj.c:22
int agcontains(Agraph_t *, void *obj)
returns non-zero if obj is a member of (sub)graph
Definition obj.c:235
void * agbindrec(void *obj, const char *name, unsigned int recsize, int move_to_front)
attaches a new record of the given size to the object
Definition rec.c:91
Agraph_t * agfstsubg(Agraph_t *g)
Definition subg.c:72
Agraph_t * agnxtsubg(Agraph_t *subg)
Definition subg.c:77
Agraph_t * graph(char *name)
Definition gv.cpp:34
Arithmetic helper functions.
static int scale_clamp(int original, double scale)
scale up or down a non-negative integer, clamping to [0, INT_MAX]
Definition gv_math.h:75
#define SWAP(a, b)
Definition gv_math.h:133
$2 prev
Definition htmlparse.y:291
textitem scanner parser str
Definition htmlparse.y:218
void do_graph_label(graph_t *sg)
Set characteristics of graph label if it exists.
Definition input.c:828
#define ND_onstack(n)
Definition acyclic.c:31
#define ND_mark(n)
Definition acyclic.c:30
void acyclic(graph_t *g)
Definition acyclic.c:58
void reverse_edge(edge_t *e)
Definition acyclic.c:22
type-generic dynamically expanding list
#define LIST_APPEND(list,...)
Definition list.h:151
#define LIST(type)
Definition list.h:66
#define LIST_SIZE(list)
Definition list.h:92
#define LIST_FREE(list)
Definition list.h:413
#define LIST_SORT(list, cmp)
Definition list.h:381
#define LIST_GET(list, index)
Definition list.h:197
#define delta
Definition maze.c:138
int rank(graph_t *g, int balance, int maxiter)
Definition ns.c:1104
int rank2(graph_t *g, int balance, int maxiter, int search_size)
Definition ns.c:1024
static void dfscc(graph_t *g, node_t *n, int cc)
Definition rank.c:882
static int make_new_cluster(graph_t *g, graph_t *subg)
Definition rank.c:228
static bool is_internal_to_cluster(edge_t *e)
Definition rank.c:660
static void compile_samerank(graph_t *ug, graph_t *parent_clust)
Definition rank.c:582
static char rankset_kind(graph_t *g)
Definition rank.c:525
static void compile_edges(graph_t *ug, graph_t *Xg)
Definition rank.c:721
void dot_scan_ranks(graph_t *g)
Definition rank.c:266
#define ND_comp(n)
Definition rank.c:515
static graph_t * dot_lca(graph_t *c0, graph_t *c1)
Definition rank.c:650
static char rank_set_class(graph_t *g)
Definition rank.c:219
static void expand_ranksets(graph_t *g)
Definition rank.c:438
void rank1(graph_t *g)
Definition rank.c:420
static int connect_components(graph_t *g)
Definition rank.c:893
static void node_induce(graph_t *par, graph_t *g)
Definition rank.c:238
static void readout_levels(graph_t *g, graph_t *Xg, int ncc)
Definition rank.c:828
static void setMinMax(graph_t *g, int doRoot)
Definition rank.c:796
static void collapse_cluster(graph_t *g, graph_t *subg)
Definition rank.c:314
static void cleanup1(graph_t *g)
Definition rank.c:80
static bool is_empty(graph_t *g)
Definition rank.c:523
static void merge(edge_t *e, int minlen, int weight)
Definition rank.c:705
static int minmax_edges2(graph_t *g, point slen)
Definition rank.c:396
void dot_rank(graph_t *g)
Definition rank.c:493
static int edge_ptr_cmp(const void *x, const void *y)
Definition rank.c:66
static void dfs(graph_t *g, node_t *v)
Definition rank.c:760
#define ROOT
Definition rank.c:510
static point minmax_edges(graph_t *g)
Definition rank.c:366
static node_t * union_one(node_t *leader, node_t *n)
Definition rank.c:563
int infosizes[]
Definition rank.c:944
static void find_clusters(graph_t *g)
Definition rank.c:346
static void collapse_sets(graph_t *rg, graph_t *g)
Definition rank.c:331
static bool is_nonconstraint(edge_t *e)
Definition rank.c:543
static void strong(graph_t *g, node_t *t, node_t *h, edge_t *orig)
Definition rank.c:710
static void set_parent(graph_t *g, graph_t *p)
Definition rank.c:517
static node_t * Last_node
Definition rank.c:672
static void my_init_graph(Agraph_t *g, Agobj_t *graph, void *arg)
Definition rank.c:926
static node_t * find(node_t *n)
Definition rank.c:553
static node_t * makeXnode(graph_t *G, char *name)
Definition rank.c:673
static void reverse_edge2(graph_t *g, edge_t *e)
Definition rank.c:750
static Agcbdisc_t mydisc
Definition rank.c:941
static void add_fast_edges(graph_t *g)
Definition rank.c:915
static void break_cycles(graph_t *g)
Definition rank.c:781
static void dot1_rank(graph_t *g)
Definition rank.c:475
static void compile_nodes(graph_t *g, graph_t *Xg)
Definition rank.c:690
static void dot2_rank(graph_t *g)
Definition rank.c:947
static void collapse_rankset(graph_t *g, graph_t *subg, char kind)
Definition rank.c:181
static void cluster_leader(graph_t *clust)
Definition rank.c:285
static void my_init_node(Agraph_t *g, Agobj_t *node, void *arg)
Definition rank.c:931
static void edgelabel_ranks(graph_t *g)
Definition rank.c:168
static void my_init_edge(Agraph_t *g, Agobj_t *edge, void *arg)
Definition rank.c:936
static node_t * union_all(graph_t *g)
Definition rank.c:570
static void set_minmax(graph_t *g)
Definition rank.c:354
static bool streq(const char *a, const char *b)
are a and b equal?
Definition streq.h:11
client event callbacks, used in Agcbstack_s
Definition cgraph.h:387
Agobj_t base
Definition cgraph.h:269
a generic header of Agraph_s, Agnode_s and Agedge_s
Definition cgraph.h:210
Agrec_t * data
stores programmer-defined data, access with AGDATA
Definition cgraph.h:212
graph or subgraph
Definition cgraph.h:424
Definition types.h:251
Definition geom.h:27
int y
Definition geom.h:27
int x
Definition geom.h:27
#define free_list(L)
Definition types.h:272
#define elist_append(item, L)
Definition types.h:261
#define alloc_elist(n, L)
Definition types.h:267
Definition grammar.c:90