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