Graphviz 13.1.1~dev.20250701.1401
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
38DEFINE_LIST(edge_set, edge_t *)
39
40
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 edge_set_append(track, L->list[i]);
46 }
47 L->list[i] = NULL;
48 }
49 L->size = 0;
50}
51
63static int edge_ptr_cmp(const edge_t **a, const edge_t **b) {
64 const uintptr_t addr_a = (uintptr_t)*a;
65 const uintptr_t addr_b = (uintptr_t)*b;
66 if (addr_a < addr_b) {
67 return -1;
68 }
69 if (addr_a > addr_b) {
70 return 1;
71 }
72 return 0;
73}
74
75static void
77{
78 edge_t *e, *f;
79
80 edge_set_t to_free = {0};
81
82 for (size_t c = 0; c < GD_comp(g).size; c++) {
83 GD_nlist(g) = GD_comp(g).list[c];
84 for (node_t *n = GD_nlist(g), *next, *prev = NULL; n; n = next) {
85 next = ND_next(n);
86 // out edges are owning, so only track their removal
87 renewlist(&ND_in(n), NULL);
88 renewlist(&ND_out(n), &to_free);
89 ND_mark(n) = false;
90 // If this is a slack node, it exists _only_ in the component lists
91 // that we are about to drop. Remove and deallocate slack nodes now to
92 // avoid leaking these.
93 if (ND_node_type(n) == SLACKNODE) {
94 if (prev == NULL) {
95 GD_comp(g).list[c] = next;
96 GD_nlist(g) = next;
97 } else {
98 ND_next(prev) = next;
99 }
100 if (next != NULL) {
101 ND_prev(next) = prev;
102 }
103 free_list(ND_in(n));
104 free_list(ND_out(n));
105 free(n->base.data);
106 free(n);
107 } else {
108 prev = n;
109 }
110 }
111 }
112 for (node_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
113 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
114 f = ED_to_virt(e);
115 /* Null out any other references to f to make sure we don't
116 * handle it a second time. For example, parallel multiedges
117 * share a virtual edge.
118 */
119 if (f && e != ED_to_orig(f)) {
120 ED_to_virt(e) = NULL;
121 }
122 }
123 }
124 for (node_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
125 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
126 f = ED_to_virt(e);
127 if (f && ED_to_orig(f) == e) {
128 edge_set_append(&to_free, f);
129 ED_to_virt(e) = NULL;
130 }
131 }
132 }
133
134 // free all the edges we removed
135 // XXX: Accruing all the pointers, including duplicates, and then sorting to
136 // avoid duplicate frees is suboptimal. If this turns out to be a
137 // performance problem, replace `edge_set_t` with a proper set.
138 edge_set_sort(&to_free, edge_ptr_cmp);
139 edge_t *previous = NULL;
140 for (size_t i = 0; i < edge_set_size(&to_free); ++i) {
141 edge_t *const current = edge_set_get(&to_free, i);
142 if (current != previous) {
143 free(current->base.data);
144 free(current);
145 }
146 previous = current;
147 }
148 edge_set_free(&to_free);
149
150 free(GD_comp(g).list);
151 GD_comp(g).list = NULL;
152 GD_comp(g).size = 0;
153}
154
155/* When there are edge labels, extra ranks are reserved here for the virtual
156 * nodes of the labels. This is done by doubling the input edge lengths.
157 * The input rank separation is adjusted to compensate.
158 */
159static void
161{
162 node_t *n;
163 edge_t *e;
164
165 if (GD_has_labels(g) & EDGE_LABEL) {
166 for (n = agfstnode(g); n; n = agnxtnode(g, n))
167 for (e = agfstout(g, n); e; e = agnxtout(g, e))
168 ED_minlen(e) *= 2;
169 GD_ranksep(g) = (GD_ranksep(g) + 1) / 2;
170 }
171}
172
173/* Merge the nodes of a min, max, or same rank set. */
174static void
175collapse_rankset(graph_t * g, graph_t * subg, int kind)
176{
177 node_t *u, *v;
178
179 u = v = agfstnode(subg);
180 if (u) {
181 ND_ranktype(u) = kind;
182 while ((v = agnxtnode(subg, v))) {
183 UF_union(u, v);
184 ND_ranktype(v) = ND_ranktype(u);
185 }
186 switch (kind) {
187 case MINRANK:
188 case SOURCERANK:
189 if (GD_minset(g) == NULL)
190 GD_minset(g) = u;
191 else
192 GD_minset(g) = UF_union(GD_minset(g), u);
193 break;
194 case MAXRANK:
195 case SINKRANK:
196 if (GD_maxset(g) == NULL)
197 GD_maxset(g) = u;
198 else
199 GD_maxset(g) = UF_union(GD_maxset(g), u);
200 break;
201 }
202 switch (kind) {
203 case SOURCERANK:
204 ND_ranktype(GD_minset(g)) = kind;
205 break;
206 case SINKRANK:
207 ND_ranktype(GD_maxset(g)) = kind;
208 break;
209 }
210 }
211}
212
213static int
215{
216 static char *name[] = { "same", "min", "source", "max", "sink", NULL };
217 static int class[] =
219 int val;
220
221 if (is_cluster(g))
222 return CLUSTER;
223 val = maptoken(agget(g, "rank"), name, class);
224 GD_set_type(g) = val;
225 return val;
226}
227
228static int
230{
231 int cno;
232 cno = ++(GD_n_cluster(g));
233 GD_clust(g) = gv_recalloc(GD_clust(g), GD_n_cluster(g), cno + 1,
234 sizeof(graph_t*));
235 GD_clust(g)[cno] = subg;
236 do_graph_label(subg);
237 return cno;
238}
239
240static void
242{
243 node_t *n, *nn;
244 edge_t *e;
245 int i;
246
247 /* enforce that a node is in at most one cluster at this level */
248 for (n = agfstnode(g); n; n = nn) {
249 nn = agnxtnode(g, n);
250 if (ND_ranktype(n)) {
251 agdelete(g, n);
252 continue;
253 }
254 for (i = 1; i < GD_n_cluster(par); i++)
255 if (agcontains(GD_clust(par)[i], n))
256 break;
257 if (i < GD_n_cluster(par))
258 agdelete(g, n);
259 ND_clust(n) = NULL;
260 }
261
262 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
263 for (e = agfstout(dot_root(g), n); e; e = agnxtout(dot_root(g), e)) {
264 if (agcontains(g, aghead(e)))
265 agsubedge(g,e,1);
266 }
267 }
268}
269
270void
272{
273 node_t *n, *leader = NULL;
274 GD_minrank(g) = INT_MAX;
275 GD_maxrank(g) = -1;
276 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
277 if (GD_maxrank(g) < ND_rank(n))
278 GD_maxrank(g) = ND_rank(n);
279 if (GD_minrank(g) > ND_rank(n))
280 GD_minrank(g) = ND_rank(n);
281 if (leader == NULL)
282 leader = n;
283 else {
284 if (ND_rank(n) < ND_rank(leader))
285 leader = n;
286 }
287 }
288 GD_leader(g) = leader;
289}
290
291static void
293{
294 node_t *leader, *n;
295 int maxrank = 0;
296
297 /* find number of ranks and select a leader */
298 leader = NULL;
299 for (n = GD_nlist(clust); n; n = ND_next(n)) {
300 if (ND_rank(n) == 0 && ND_node_type(n) == NORMAL)
301 leader = n;
302 if (maxrank < ND_rank(n))
303 maxrank = ND_rank(n);
304 }
305 assert(leader != NULL);
306 GD_leader(clust) = leader;
307
308 for (n = agfstnode(clust); n; n = agnxtnode(clust, n)) {
309 assert(ND_UF_size(n) <= 1 || n == leader);
310 UF_union(n, leader);
311 ND_ranktype(n) = CLUSTER;
312 }
313}
314
315/*
316 * A cluster is collapsed in three steps.
317 * 1) The nodes of the cluster are ranked locally.
318 * 2) The cluster is collapsed into one node on the least rank.
319 * 3) In class1(), any inter-cluster edges are converted using
320 * the "virtual node + 2 edges" trick.
321 */
322static void
324{
325 if (GD_parent(subg)) {
326 return;
327 }
328 GD_parent(subg) = g;
329 node_induce(g, subg);
330 if (agfstnode(subg) == NULL)
331 return;
332 make_new_cluster(g, subg);
333 if (CL_type == LOCAL) {
334 dot1_rank(subg);
335 cluster_leader(subg);
336 } else
337 dot_scan_ranks(subg);
338}
339
340/* Execute union commands for "same rank" subgraphs and clusters. */
341static void
343{
344 int c;
345 graph_t *subg;
346
347 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
348 c = rank_set_class(subg);
349 if (c) {
350 if ((c == CLUSTER) && CL_type == LOCAL)
351 collapse_cluster(rg, subg);
352 else
353 collapse_rankset(rg, subg, c);
354 }
355 else collapse_sets(rg, subg);
356
357 }
358}
359
360static void
362{
363 graph_t *subg;
364 for (subg = agfstsubg(dot_root(g)); subg; subg = agnxtsubg(subg)) {
365 if (GD_set_type(subg) == CLUSTER)
366 collapse_cluster(g, subg);
367 }
368}
369
370static void
372{
373 int c;
374
375 GD_minrank(g) += ND_rank(GD_leader(g));
376 GD_maxrank(g) += ND_rank(GD_leader(g));
377 for (c = 1; c <= GD_n_cluster(g); c++)
378 set_minmax(GD_clust(g)[c]);
379}
380
381/* To ensure that min and max rank nodes always have the intended rank
382 * assignment, reverse any incompatible edges.
383 */
384static point
386{
387 node_t *n;
388 edge_t *e;
389 point slen;
390
391 slen.x = slen.y = 0;
392 if ((GD_maxset(g) == NULL) && (GD_minset(g) == NULL))
393 return slen;
394 if (GD_minset(g) != NULL)
395 GD_minset(g) = UF_find(GD_minset(g));
396 if (GD_maxset(g) != NULL)
397 GD_maxset(g) = UF_find(GD_maxset(g));
398
399 if ((n = GD_maxset(g))) {
400 slen.y = (ND_ranktype(GD_maxset(g)) == SINKRANK);
401 while ((e = ND_out(n).list[0])) {
402 assert(aghead(e) == UF_find(aghead(e)));
403 reverse_edge(e);
404 }
405 }
406 if ((n = GD_minset(g))) {
407 slen.x = (ND_ranktype(GD_minset(g)) == SOURCERANK);
408 while ((e = ND_in(n).list[0])) {
409 assert(agtail(e) == UF_find(agtail(e)));
410 reverse_edge(e);
411 }
412 }
413 return slen;
414}
415
416static int
418{
419 node_t *n;
420 edge_t *e = 0;
421
422 if ((GD_maxset(g)) || (GD_minset(g))) {
423 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
424 if (n != UF_find(n))
425 continue;
426 if ((ND_out(n).size == 0) && GD_maxset(g) && (n != GD_maxset(g))) {
427 e = virtual_edge(n, GD_maxset(g), NULL);
428 ED_minlen(e) = slen.y;
429 ED_weight(e) = 0;
430 }
431 if ((ND_in(n).size == 0) && GD_minset(g) && (n != GD_minset(g))) {
432 e = virtual_edge(GD_minset(g), n, NULL);
433 ED_minlen(e) = slen.x;
434 ED_weight(e) = 0;
435 }
436 }
437 }
438 return (e != 0);
439}
440
441/* Run the network simplex algorithm on each component. */
442void rank1(graph_t * g)
443{
444 int maxiter = INT_MAX;
445 char *s;
446
447 if ((s = agget(g, "nslimit1")))
448 maxiter = scale_clamp(agnnodes(g), atof(s));
449 for (size_t c = 0; c < GD_comp(g).size; c++) {
450 GD_nlist(g) = GD_comp(g).list[c];
451 rank(g, (GD_n_cluster(g) == 0 ? 1 : 0), maxiter); /* TB balance */
452 }
453}
454
455/*
456 * Assigns ranks of non-leader nodes.
457 * Expands same, min, max rank sets.
458 * Leaf sets and clusters remain merged.
459 * Sets minrank and maxrank appropriately.
460 */
461static void expand_ranksets(graph_t *g) {
462 int c;
463 node_t *n, *leader;
464
465 if ((n = agfstnode(g))) {
466 GD_minrank(g) = INT_MAX;
467 GD_maxrank(g) = -1;
468 while (n) {
469 leader = UF_find(n);
470 /* The following works because ND_rank(n) == 0 if n is not in a
471 * cluster, and ND_rank(n) = the local rank offset if n is in
472 * a cluster. */
473 if (leader != n)
474 ND_rank(n) += ND_rank(leader);
475
476 if (GD_maxrank(g) < ND_rank(n))
477 GD_maxrank(g) = ND_rank(n);
478 if (GD_minrank(g) > ND_rank(n))
479 GD_minrank(g) = ND_rank(n);
480
481 if (ND_ranktype(n) && ND_ranktype(n) != LEAFSET)
482 UF_singleton(n);
483 n = agnxtnode(g, n);
484 }
485 if (g == dot_root(g)) {
486 if (CL_type == LOCAL) {
487 for (c = 1; c <= GD_n_cluster(g); c++)
488 set_minmax(GD_clust(g)[c]);
489 } else {
490 find_clusters(g);
491 }
492 }
493 } else {
494 GD_minrank(g) = GD_maxrank(g) = 0;
495 }
496}
497
498static void dot1_rank(graph_t *g)
499{
500 point p;
502
503 collapse_sets(g,g);
504 class1(g);
505 p = minmax_edges(g);
506 decompose(g, 0);
507 acyclic(g);
508 if (minmax_edges2(g, p))
509 decompose(g, 0);
510
511 rank1(g);
512
514 cleanup1(g);
515}
516
518 if (mapbool(agget(g, "newrank"))) {
519 GD_flags(g) |= NEW_RANK;
520 dot2_rank(g);
521 }
522 else
523 dot1_rank(g);
524 if (Verbose)
525 fprintf (stderr, "Maxrank = %d, minrank = %d\n", GD_maxrank(g), GD_minrank(g));
526}
527
529{
530 return is_a_cluster(g); // from utils.c
531}
532
533/* new ranking code:
534 * Allows more constraints
535 * Copy of level.c in dotgen2
536 * Many of the utility functions are simpler or gone with
537 * cgraph library.
538 */
539#define BACKWARD_PENALTY 1000
540#define STRONG_CLUSTER_WEIGHT 1000
541#define NORANK 6
542#define ROOT "\177root"
543#define TOPNODE "\177top"
544#define BOTNODE "\177bot"
545
546/* hops is not used in dot, so we overload it to
547 * contain the index of the connected component
548 */
549#define ND_comp(n) ND_hops(n)
550
551static void set_parent(graph_t* g, graph_t* p)
552{
553 GD_parent(g) = p;
554 make_new_cluster(p, g);
555 node_induce(p, g);
556}
557
558static bool is_empty(graph_t *g) {
559 return !agfstnode(g);
560}
561
563{
564 char *str = agget(g, "compact");
565 return mapbool(str);
566}
567
568static int rankset_kind(graph_t * g)
569{
570 char *str = agget(g, "rank");
571
572 if (str && str[0]) {
573 if (!strcmp(str, "min"))
574 return MINRANK;
575 if (!strcmp(str, "source"))
576 return SOURCERANK;
577 if (!strcmp(str, "max"))
578 return MAXRANK;
579 if (!strcmp(str, "sink"))
580 return SINKRANK;
581 if (!strcmp(str, "same"))
582 return SAMERANK;
583 }
584 return NORANK;
585}
586
587static bool is_nonconstraint(edge_t * e)
588{
589 char *constr;
590
591 if (E_constr && (constr = agxget(e, E_constr))) {
592 if (constr[0] && !mapbool(constr))
593 return true;
594 }
595 return false;
596}
597
598static node_t *find(node_t * n)
599{
600 node_t *set;
601 if ((set = ND_set(n))) {
602 if (set != n)
603 set = ND_set(n) = find(set);
604 } else
605 set = ND_set(n) = n;
606 return set;
607}
608
609static node_t *union_one(node_t * leader, node_t * n)
610{
611 if (n)
612 return (ND_set(find(n)) = find(leader));
613 else
614 return leader;
615}
616
618{
619 node_t *n, *leader;
620
621 n = agfstnode(g);
622 if (!n)
623 return n;
624 leader = find(n);
625 while ((n = agnxtnode(g, n)))
626 union_one(leader, n);
627 return leader;
628}
629
630static void compile_samerank(graph_t * ug, graph_t * parent_clust)
631{
632 graph_t *s; /* subgraph being scanned */
633 graph_t *clust; /* cluster that contains the rankset */
634 node_t *n, *leader;
635
636 if (is_empty(ug))
637 return;
638 if (is_a_cluster(ug)) {
639 clust = ug;
640 if (parent_clust) {
641 GD_level(ug) = GD_level(parent_clust) + 1;
642 set_parent(ug, parent_clust);
643 }
644 else
645 GD_level(ug) = 0;
646 } else
647 clust = parent_clust;
648
649 /* process subgraphs of this subgraph */
650 for (s = agfstsubg(ug); s; s = agnxtsubg(s))
651 compile_samerank(s, clust);
652
653 /* process this subgraph as a cluster */
654 if (is_a_cluster(ug)) {
655 for (n = agfstnode(ug); n; n = agnxtnode(ug, n)) {
656 if (ND_clust(n) == 0)
657 ND_clust(n) = ug;
658#ifdef DEBUG
659 fprintf(stderr, "(%s) %s %p\n", agnameof(ug), agnameof(n),
660 ND_clust(n));
661#endif
662 }
663 }
664
665 /* process this subgraph as a rankset */
666 switch (rankset_kind(ug)) {
667 case SOURCERANK: // fall through
668 case MINRANK:
669 leader = union_all(ug);
670 if (clust != NULL) {
671 GD_minrep(clust) = union_one(leader, GD_minrep(clust));
672 }
673 break;
674 case SINKRANK: // fall through
675 case MAXRANK:
676 leader = union_all(ug);
677 if (clust != NULL) {
678 GD_maxrep(clust) = union_one(leader, GD_maxrep(clust));
679 }
680 break;
681 case SAMERANK:
682 leader = union_all(ug);
683 /* do we need to record these ranksets? */
684 break;
685 case NORANK:
686 break;
687 default: /* unrecognized - warn and do nothing */
688 agwarningf("%s has unrecognized rank=%s", agnameof(ug),
689 agget(ug, "rank"));
690 }
691
692 /* a cluster may become degenerate */
693 if (is_a_cluster(ug) && GD_minrep(ug)) {
694 if (GD_minrep(ug) == GD_maxrep(ug)) {
695 node_t *up = union_all(ug);
696 GD_minrep(ug) = up;
697 GD_maxrep(ug) = up;
698 }
699 }
700}
701
702static graph_t *dot_lca(graph_t * c0, graph_t * c1)
703{
704 while (c0 != c1) {
705 if (GD_level(c0) >= GD_level(c1))
706 c0 = GD_parent(c0);
707 else
708 c1 = GD_parent(c1);
709 }
710 return c0;
711}
712
714{
715 graph_t *par, *ct, *ch;
716 ct = ND_clust(agtail(e));
717 ch = ND_clust(aghead(e));
718 if (ct == ch)
719 return true;
720 par = dot_lca(ct, ch);
721 if (par == ct || par == ch)
722 return true;
723 return false;
724}
725
727static node_t* makeXnode (graph_t* G, char* name)
728{
729 node_t *n = agnode(G, name, 1);
730 alloc_elist(4, ND_in(n));
731 alloc_elist(4, ND_out(n));
732 if (Last_node) {
733 ND_prev(n) = Last_node;
734 ND_next(Last_node) = n;
735 } else {
736 ND_prev(n) = NULL;
737 GD_nlist(G) = n;
738 }
739 Last_node = n;
740 ND_next(n) = NULL;
741
742 return n;
743}
744
745static void compile_nodes(graph_t * g, graph_t * Xg)
746{
747 /* build variables */
748 node_t *n;
749
750 Last_node = NULL;
751 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
752 if (find(n) == n)
753 ND_rep(n) = makeXnode (Xg, agnameof(n));
754 }
755 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
756 if (ND_rep(n) == 0)
757 ND_rep(n) = ND_rep(find(n));
758 }
759}
760
761static void merge(edge_t * e, int minlen, int weight)
762{
763 ED_minlen(e) = MAX(ED_minlen(e), minlen);
764 ED_weight(e) += weight;
765}
766
767static void strong(graph_t * g, node_t * t, node_t * h, edge_t * orig)
768{
769 edge_t *e;
770 if ((e = agfindedge(g, t, h)) ||
771 (e = agfindedge(g, h, t)) || (e = agedge(g, t, h, 0, 1)))
772 merge(e, ED_minlen(orig), ED_weight(orig));
773 else
774 agerrorf("ranking: failure to create strong constraint edge between nodes %s and %s\n",
775 agnameof(t), agnameof(h));
776}
777
778static void weak(graph_t * g, node_t * t, node_t * h, edge_t * orig)
779{
780 node_t *v;
781 edge_t *e, *f;
782 static int id;
783 char buf[100];
784
785 for (e = agfstin(g, t); e; e = agnxtin(g, e)) {
786 /* merge with existing weak edge (e,f) */
787 v = agtail(e);
788 if ((f = agfstout(g, v)) && (aghead(f) == h)) {
789 return;
790 }
791 }
792 if (!e) {
793 snprintf(buf, sizeof(buf), "_weak_%d", id++);
794 v = makeXnode(g, buf);
795 e = agedge(g, v, t, 0, 1);
796 f = agedge(g, v, h, 0, 1);
797 }
798 ED_minlen(e) = MAX(ED_minlen(e), 0); /* effectively a nop */
800 ED_minlen(f) = MAX(ED_minlen(f), ED_minlen(orig));
801 ED_weight(f) += ED_weight(orig);
802}
803
804static void compile_edges(graph_t * ug, graph_t * Xg)
805{
806 node_t *n;
807 edge_t *e;
808 node_t *Xt, *Xh;
809 graph_t *tc, *hc;
810
811 /* build edge constraints */
812 for (n = agfstnode(ug); n; n = agnxtnode(ug, n)) {
813 Xt = ND_rep(n);
814 for (e = agfstout(ug, n); e; e = agnxtout(ug, e)) {
815 if (is_nonconstraint(e))
816 continue;
817 Xh = ND_rep(find(aghead(e)));
818 if (Xt == Xh)
819 continue;
820
821 tc = ND_clust(agtail(e));
822 hc = ND_clust(aghead(e));
823
824 if (is_internal_to_cluster(e)) {
825 graph_t *clust_tail = ND_clust(agtail(e));
826 graph_t *clust_head = ND_clust(aghead(e));
827 /* determine if graph requires reversed edge */
828 if ((clust_tail != NULL && find(agtail(e)) == GD_maxrep(clust_tail))
829 || (clust_head != NULL && find(aghead(e)) == GD_minrep(clust_head))) {
830 node_t *temp = Xt;
831 Xt = Xh;
832 Xh = temp;
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:67
bool mapbool(const char *p)
Definition utils.c:337
node_t * UF_union(node_t *u, node_t *v)
Definition utils.c:110
node_t * UF_find(node_t *n)
Definition utils.c:100
int maptoken(char *p, char **name, int *val)
Definition utils.c:311
void UF_singleton(node_t *u)
Definition utils.c:138
bool is_a_cluster(Agraph_t *g)
Definition utils.c:692
#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:525
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:23
static attrs_t * L
Definition gmlparse.c:94
void free(void *)
edge
Definition gmlparse.y:239
#define SIZE_MAX
Definition gmlscan.c:347
node NULL
Definition grammar.y:181
int agnedges(Agraph_t *g)
Definition graph.c:163
int agnnodes(Agraph_t *g)
Definition graph.c:157
char * agget(void *obj, char *name)
Definition attr.c:462
char * agxget(void *obj, Agsym_t *sym)
Definition attr.c:472
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:273
#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
$2 u p prev
Definition htmlparse.y:297
textitem scanner parser str
Definition htmlparse.y:224
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
#define DEFINE_LIST(name, type)
Definition list.h:22
#define delta
Definition maze.c:136
int rank(graph_t *g, int balance, int maxiter)
Definition ns.c:1063
int rank2(graph_t *g, int balance, int maxiter, int search_size)
Definition ns.c:984
#define BOTNODE
Definition rank.c:544
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:229
static bool is_internal_to_cluster(edge_t *e)
Definition rank.c:713
static void compile_samerank(graph_t *ug, graph_t *parent_clust)
Definition rank.c:630
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:804
#define STRONG_CLUSTER_WEIGHT
Definition rank.c:540
void dot_scan_ranks(graph_t *g)
Definition rank.c:271
#define ND_comp(n)
Definition rank.c:549
static graph_t * dot_lca(graph_t *c0, graph_t *c1)
Definition rank.c:702
static void expand_ranksets(graph_t *g)
Definition rank.c:461
void rank1(graph_t *g)
Definition rank.c:442
static int connect_components(graph_t *g)
Definition rank.c:1024
static void node_induce(graph_t *par, graph_t *g)
Definition rank.c:241
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:323
static void cleanup1(graph_t *g)
Definition rank.c:76
static int rankset_kind(graph_t *g)
Definition rank.c:568
#define BACKWARD_PENALTY
Definition rank.c:539
static bool is_empty(graph_t *g)
Definition rank.c:558
static void merge(edge_t *e, int minlen, int weight)
Definition rank.c:761
#define TOPNODE
Definition rank.c:543
static int minmax_edges2(graph_t *g, point slen)
Definition rank.c:417
void dot_rank(graph_t *g)
Definition rank.c:517
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:175
bool is_cluster(graph_t *g)
Definition rank.c:528
#define ROOT
Definition rank.c:542
static point minmax_edges(graph_t *g)
Definition rank.c:385
static node_t * union_one(node_t *leader, node_t *n)
Definition rank.c:609
int infosizes[]
Definition rank.c:1067
static int edge_ptr_cmp(const edge_t **a, const edge_t **b)
Definition rank.c:63
static void find_clusters(graph_t *g)
Definition rank.c:361
static void collapse_sets(graph_t *rg, graph_t *g)
Definition rank.c:342
static bool is_nonconstraint(edge_t *e)
Definition rank.c:587
static void strong(graph_t *g, node_t *t, node_t *h, edge_t *orig)
Definition rank.c:767
static void set_parent(graph_t *g, graph_t *p)
Definition rank.c:551
static node_t * Last_node
Definition rank.c:726
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:598
static node_t * makeXnode(graph_t *G, char *name)
Definition rank.c:727
static void renewlist(elist *L, edge_set_t *track)
Definition rank.c:42
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:498
static void compile_nodes(graph_t *g, graph_t *Xg)
Definition rank.c:745
static bool is_a_strong_cluster(graph_t *g)
Definition rank.c:562
#define NORANK
Definition rank.c:541
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:778
static int rank_set_class(graph_t *g)
Definition rank.c:214
static void cluster_leader(graph_t *clust)
Definition rank.c:292
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:160
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:617
static void set_minmax(graph_t *g)
Definition rank.c:371
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:89
#define MAX(a, b)
Definition write.c:32