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