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 * dot_mincross(g) takes a ranked graphs, and finds an ordering
17 * that avoids edge crossings. clusters are expanded.
18 * N.B. the rank structure is global (not allocated per cluster)
19 * because mincross may compare nodes in different clusters.
20 */
21
22#include "dot.h"
23
24/* #define DEBUG */
25#define MARK(v) (ND_mark(v))
26#define saveorder(v) (ND_coord(v)).x
27#define flatindex(v) ND_low(v)
28
29 /* forward declarations */
30static boolean medians(graph_t * g, int r0, int r1);
31static int nodeposcmpf(node_t ** n0, node_t ** n1);
32static int edgeidcmpf(edge_t ** e0, edge_t ** e1);
33static void flat_breakcycles(graph_t * g);
34static void flat_reorder(graph_t * g);
35static void flat_search(graph_t * g, node_t * v);
36static void init_mincross(graph_t * g);
37static void merge2(graph_t * g);
38static void init_mccomp(graph_t * g, int c);
39static void cleanup2(graph_t * g, int nc);
40static int mincross_clust(graph_t * par, graph_t * g, int);
41static int mincross(graph_t * g, int startpass, int endpass, int);
42static void mincross_step(graph_t * g, int pass);
43static void mincross_options(graph_t * g);
44static void save_best(graph_t * g);
45static void restore_best(graph_t * g);
46static adjmatrix_t *new_matrix(int i, int j);
47static void free_matrix(adjmatrix_t * p);
48static int ordercmpf(int *i0, int *i1);
49#ifdef DEBUG
50#if DEBUG > 1
51static int gd_minrank(Agraph_t *g) {return GD_minrank(g);}
52static int gd_maxrank(Agraph_t *g) {return GD_maxrank(g);}
53static rank_t *gd_rank(Agraph_t *g, int r) {return &GD_rank(g)[r];}
54static int nd_order(Agnode_t *v) { return ND_order(v); }
55#endif
56void check_rs(graph_t * g, int null_ok);
57void check_order(void);
58void check_vlists(graph_t * g);
59void node_in_root_vlist(node_t * n);
60#endif
61
62
63 /* mincross parameters */
64static int MinQuit;
65static double Convergence;
66
67static graph_t *Root;
68static int GlobalMinRank, GlobalMaxRank;
69static edge_t **TE_list;
70static int *TI_list;
71static boolean ReMincross;
72
73#if DEBUG > 1
74static void indent(graph_t* g)
75{
76 if (g->parent) {
77 fprintf (stderr, " ");
78 indent(g->parent);
79 }
80}
81
82static char* nname(node_t* v)
83{
84 static char buf[1000];
85 if (ND_node_type(v)) {
86 if (ND_ranktype(v) == CLUSTER)
87 sprintf (buf, "v%s_%p", agnameof(ND_clust(v)), v);
88 else
89 sprintf (buf, "v_%p", v);
90 } else
91 sprintf (buf, "%s", agnameof(v));
92 return buf;
93}
94static void dumpg (graph_t* g)
95{
96 int j, i, r;
97 node_t* v;
98 edge_t* e;
99
100 fprintf (stderr, "digraph A {\n");
101 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
102 fprintf (stderr, " subgraph {rank=same ");
103 for (i = 0; i < GD_rank(g)[r].n; i++) {
104 v = GD_rank(g)[r].v[i];
105 if (i > 0)
106 fprintf (stderr, " -> %s", nname(v));
107 else
108 fprintf (stderr, "%s", nname(v));
109 }
110 if (i > 1) fprintf (stderr, " [style=invis]}\n");
111 else fprintf (stderr, " }\n");
112 }
113 for (r = GD_minrank(g); r < GD_maxrank(g); r++) {
114 for (i = 0; i < GD_rank(g)[r].n; i++) {
115 v = GD_rank(g)[r].v[i];
116 for (j = 0; (e = ND_out(v).list[j]); j++) {
117 fprintf (stderr, "%s -> ", nname(v));
118 fprintf (stderr, "%s\n", nname(aghead(e)));
119 }
120 }
121 }
122 fprintf (stderr, "}\n");
123}
124static void dumpr (graph_t* g, int edges)
125{
126 int j, i, r;
127 node_t* v;
128 edge_t* e;
129
130 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
131 fprintf (stderr, "[%d] ", r);
132 for (i = 0; i < GD_rank(g)[r].n; i++) {
133 v = GD_rank(g)[r].v[i];
134 fprintf (stderr, "%s(%.02f,%d) ", nname(v), saveorder(v),ND_order(v));
135 }
136 fprintf (stderr, "\n");
137 }
138 if (edges == 0) return;
139 for (r = GD_minrank(g); r < GD_maxrank(g); r++) {
140 for (i = 0; i < GD_rank(g)[r].n; i++) {
141 v = GD_rank(g)[r].v[i];
142 for (j = 0; (e = ND_out(v).list[j]); j++) {
143 fprintf (stderr, "%s -> ", nname(v));
144 fprintf (stderr, "%s\n", nname(aghead(e)));
145 }
146 }
147 }
148}
149#endif
150
151typedef struct {
152 Agrec_t h;
153 int x, lo, hi;
154 Agnode_t* np;
155} info_t;
156
157#define ND_x(n) (((info_t*)AGDATA(n))->x)
158#define ND_lo(n) (((info_t*)AGDATA(n))->lo)
159#define ND_hi(n) (((info_t*)AGDATA(n))->hi)
160#define ND_np(n) (((info_t*)AGDATA(n))->np)
161#define ND_idx(n) (ND_order(ND_np(n)))
162
163static void
164emptyComp (graph_t* sg)
165{
166 Agnode_t* n;
167 Agnode_t* nxt;
168
169 for (n = agfstnode(sg); n; n = nxt) {
170 nxt = agnxtnode (sg, n);
171 agdelnode(sg,n);
172 }
173}
174
175#define isBackedge(e) (ND_idx(aghead(e)) > ND_idx(agtail(e)))
176
177static Agnode_t*
178findSource (Agraph_t* g, Agraph_t* sg)
179{
180 Agnode_t* n;
181
182 for (n = agfstnode(sg); n; n = agnxtnode(sg, n))
183 if (agdegree(g,n,1,0) == 0) return n;
184 return NULL;
185}
186
187static int
188topsort (Agraph_t* g, Agraph_t* sg, Agnode_t** arr)
189{
190 Agnode_t* n;
191 Agedge_t* e;
192 Agedge_t* nxte;
193 int cnt = 0;
194
195 while ((n = findSource(g, sg))) {
196 arr[cnt++] = ND_np(n);
197 agdelnode(sg, n);
198 for (e = agfstout(g, n); e; e = nxte) {
199 nxte = agnxtout(g, e);
200 agdeledge(g, e);
201 }
202 }
203 return cnt;
204}
205
206static int
207getComp (graph_t* g, node_t* n, graph_t* comp, int* indices)
208{
209 int backedge = 0;
210 Agedge_t* e;
211
212 ND_x(n) = 1;
213 indices[agnnodes(comp)] = ND_idx(n);
214 agsubnode(comp, n, 1);
215 for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
216 if (isBackedge(e)) backedge++;
217 if (!ND_x(aghead(e)))
218 backedge += getComp(g, aghead(e), comp, indices);
219 }
220 for (e = agfstin(g,n); e; e = agnxtin(g,e)) {
221 if (isBackedge(e)) backedge++;
222 if (!ND_x(agtail(e)))
223 backedge += getComp(g, agtail(e), comp, indices);
224 }
225 return backedge;
226}
227
228/* fixLabelOrder:
229 * For each pair of nodes (labels), we add an edge
230 */
231static void
232fixLabelOrder (graph_t* g, rank_t* rk)
233{
234 int cnt, haveBackedge = FALSE;
235 Agnode_t** arr;
236 int* indices;
237 Agraph_t* sg;
238 Agnode_t* n;
239 Agnode_t* nxtp;
240 Agnode_t* v;
241
242 for (n = agfstnode(g); n; n = nxtp) {
243 v = nxtp = agnxtnode(g, n);
244 for (; v; v = agnxtnode(g, v)) {
245 if (ND_hi(v) <= ND_lo(n)) {
246 haveBackedge = TRUE;
247 agedge(g, v, n, NULL, 1);
248 }
249 else if (ND_hi(n) <= ND_lo(v)) {
250 agedge(g, n, v, NULL, 1);
251 }
252 }
253 }
254 if (!haveBackedge) return;
255
256 sg = agsubg(g, "comp", 1);
257 arr = N_NEW(agnnodes(g), Agnode_t*);
258 indices = N_NEW(agnnodes(g), int);
259
260 for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
261 if (ND_x(n) || (agdegree(g,n,1,1) == 0)) continue;
262 if (getComp(g, n, sg, indices)) {
263 int i, sz = agnnodes(sg);
264 cnt = topsort (g, sg, arr);
265 assert (cnt == sz);
266 qsort(indices, cnt, sizeof(int), (qsort_cmpf)ordercmpf);
267 for (i = 0; i < sz; i++) {
268 ND_order(arr[i]) = indices[i];
269 rk->v[indices[i]] = arr[i];
270 }
271 }
272 emptyComp(sg);
273 }
274 free (arr);
275}
276
277/* checkLabelOrder:
278 * Check that the ordering of labels for flat edges is consistent.
279 * This is necessary because dot_position will attempt to force the label
280 * to be between the edge's vertices. This can lead to an infeasible problem.
281 *
282 * We check each rank for any flat edge labels (as dummy nodes) and create a
283 * graph with a node for each label. If the graph contains more than 1 node, we
284 * call fixLabelOrder to see if there really is a problem and, if so, fix it.
285 */
286void
287checkLabelOrder (graph_t* g)
288{
289 int j, r, lo, hi;
290 graph_t* lg = NULL;
291 char buf[BUFSIZ];
292 rank_t* rk;
293 Agnode_t* u;
294 Agnode_t* n;
295 Agedge_t* e;
296
297 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
298 rk = GD_rank(g)+r;
299 for (j = 0; j < rk->n; j++) {
300 u = rk->v[j];
301 if ((e = (edge_t*)ND_alg(u))) {
302 if (!lg) lg = agopen ("lg", Agstrictdirected, 0);
303 sprintf (buf, "%d", j);
304 n = agnode(lg, buf, 1);
305 agbindrec(n, "info", sizeof(info_t), 1);
306 lo = ND_order(aghead(ND_out(u).list[0]));
307 hi = ND_order(aghead(ND_out(u).list[1]));
308 if (lo > hi) {
309 int tmp;
310 tmp = lo;
311 lo = hi;
312 hi = tmp;
313 }
314 ND_lo(n) = lo;
315 ND_hi(n) = hi;
316 ND_np(n) = u;
317 }
318 }
319 if (lg) {
320 if (agnnodes(lg) > 1) fixLabelOrder (lg, rk);
321 agclose(lg);
322 lg = NULL;
323 }
324 }
325}
326
327/* dot_mincross:
328 * Minimize edge crossings
329 * Note that nodes are not placed into GD_rank(g) until mincross()
330 * is called.
331 */
332void dot_mincross(graph_t * g, int doBalance)
333{
334 int c, nc;
335 char *s;
336
337 init_mincross(g);
338
339 for (nc = c = 0; c < GD_comp(g).size; c++) {
340 init_mccomp(g, c);
341 nc += mincross(g, 0, 2, doBalance);
342 }
343
344 merge2(g);
345
346 /* run mincross on contents of each cluster */
347 for (c = 1; c <= GD_n_cluster(g); c++) {
348 nc += mincross_clust(g, GD_clust(g)[c], doBalance);
349#ifdef DEBUG
350 check_vlists(GD_clust(g)[c]);
351 check_order();
352#endif
353 }
354
355 if ((GD_n_cluster(g) > 0)
356 && (!(s = agget(g, "remincross")) || (mapbool(s)))) {
357 mark_lowclusters(g);
358 ReMincross = TRUE;
359 nc = mincross(g, 2, 2, doBalance);
360#ifdef DEBUG
361 for (c = 1; c <= GD_n_cluster(g); c++)
362 check_vlists(GD_clust(g)[c]);
363#endif
364 }
365 cleanup2(g, nc);
366}
367
368static adjmatrix_t *new_matrix(int i, int j)
369{
370 adjmatrix_t *rv = NEW(adjmatrix_t);
371 rv->nrows = i;
372 rv->ncols = j;
373 rv->data = N_NEW(i * j, char);
374 return rv;
375}
376
377static void free_matrix(adjmatrix_t * p)
378{
379 if (p) {
380 free(p->data);
381 free(p);
382 }
383}
384
385#define ELT(M,i,j) (M->data[((i)*M->ncols)+(j)])
386
387static void init_mccomp(graph_t * g, int c)
388{
389 int r;
390
391 GD_nlist(g) = GD_comp(g).list[c];
392 if (c > 0) {
393 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
394 GD_rank(g)[r].v = GD_rank(g)[r].v + GD_rank(g)[r].n;
395 GD_rank(g)[r].n = 0;
396 }
397 }
398}
399
400static int betweenclust(edge_t * e)
401{
402 while (ED_to_orig(e))
403 e = ED_to_orig(e);
404 return (ND_clust(agtail(e)) != ND_clust(aghead(e)));
405}
406
407static void do_ordering_node (graph_t * g, node_t* n, int outflag)
408{
409 int i, ne;
410 node_t *u, *v;
411 edge_t *e, *f, *fe;
412 edge_t **sortlist = TE_list;
413
414 if (ND_clust(n))
415 return;
416 if (outflag) {
417 for (i = ne = 0; (e = ND_out(n).list[i]); i++)
418 if (!betweenclust(e))
419 sortlist[ne++] = e;
420 } else {
421 for (i = ne = 0; (e = ND_in(n).list[i]); i++)
422 if (!betweenclust(e))
423 sortlist[ne++] = e;
424 }
425 if (ne <= 1)
426 return;
427 /* write null terminator at end of list.
428 requires +1 in TE_list alloccation */
429 sortlist[ne] = 0;
430 qsort(sortlist, ne, sizeof(sortlist[0]), (qsort_cmpf) edgeidcmpf);
431 for (ne = 1; (f = sortlist[ne]); ne++) {
432 e = sortlist[ne - 1];
433 if (outflag) {
434 u = aghead(e);
435 v = aghead(f);
436 } else {
437 u = agtail(e);
438 v = agtail(f);
439 }
440 if (find_flat_edge(u, v))
441 return;
442 fe = new_virtual_edge(u, v, NULL);
443 ED_edge_type(fe) = FLATORDER;
444 flat_edge(g, fe);
445 }
446}
447
448static void do_ordering(graph_t * g, int outflag)
449{
450 /* Order all nodes in graph */
451 node_t *n;
452
453 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
454 do_ordering_node (g, n, outflag);
455 }
456}
457
458static void do_ordering_for_nodes(graph_t * g)
459{
460 /* Order nodes which have the "ordered" attribute */
461 node_t *n;
462 const char *ordering;
463
464 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
465 if ((ordering = late_string(n, N_ordering, NULL))) {
466 if (streq(ordering, "out"))
467 do_ordering_node(g, n, TRUE);
468 else if (streq(ordering, "in"))
469 do_ordering_node(g, n, FALSE);
470 else if (ordering[0])
471 agerr(AGERR, "ordering '%s' not recognized for node '%s'.\n", ordering, agnameof(n));
472 }
473 }
474}
475
476/* ordered_edges:
477 * handle case where graph specifies edge ordering
478 * If the graph does not have an ordering attribute, we then
479 * check for nodes having the attribute.
480 * Note that, in this implementation, the value of G_ordering
481 * dominates the value of N_ordering.
482 */
483static void ordered_edges(graph_t * g)
484{
485 char *ordering;
486
487 if (!G_ordering && !N_ordering)
488 return;
489 if ((ordering = late_string(g, G_ordering, NULL))) {
490 if (streq(ordering, "out"))
491 do_ordering(g, TRUE);
492 else if (streq(ordering, "in"))
493 do_ordering(g, FALSE);
494 else if (ordering[0])
495 agerr(AGERR, "ordering '%s' not recognized.\n", ordering);
496 }
497 else
498 {
499 graph_t *subg;
500
501 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
502 /* clusters are processed by separate calls to ordered_edges */
503 if (!is_cluster(subg))
504 ordered_edges(subg);
505 }
506 if (N_ordering) do_ordering_for_nodes (g);
507 }
508}
509
510static int mincross_clust(graph_t * par, graph_t * g, int doBalance)
511{
512 int c, nc;
513
514 expand_cluster(g);
515 ordered_edges(g);
516 flat_breakcycles(g);
517 flat_reorder(g);
518 nc = mincross(g, 2, 2, doBalance);
519
520 for (c = 1; c <= GD_n_cluster(g); c++)
521 nc += mincross_clust(g, GD_clust(g)[c], doBalance);
522
523 save_vlist(g);
524 return nc;
525}
526
527static int left2right(graph_t * g, node_t * v, node_t * w)
528{
529 adjmatrix_t *M;
530 int rv;
531
532 /* CLUSTER indicates orig nodes of clusters, and vnodes of skeletons */
533 if (ReMincross == FALSE) {
534 if ((ND_clust(v) != ND_clust(w)) && (ND_clust(v)) && (ND_clust(w))) {
535 /* the following allows cluster skeletons to be swapped */
536 if ((ND_ranktype(v) == CLUSTER)
537 && (ND_node_type(v) == VIRTUAL))
538 return FALSE;
539 if ((ND_ranktype(w) == CLUSTER)
540 && (ND_node_type(w) == VIRTUAL))
541 return FALSE;
542 return TRUE;
543 /*return ((ND_ranktype(v) != CLUSTER) && (ND_ranktype(w) != CLUSTER)); */
544 }
545 } else {
546 if ((ND_clust(v)) != (ND_clust(w)))
547 return TRUE;
548 }
549 M = GD_rank(g)[ND_rank(v)].flat;
550 if (M == NULL)
551 rv = FALSE;
552 else {
553 if (GD_flip(g)) {
554 node_t *t = v;
555 v = w;
556 w = t;
557 }
558 rv = ELT(M, flatindex(v), flatindex(w));
559 }
560 return rv;
561}
562
563static int in_cross(node_t * v, node_t * w)
564{
565 register edge_t **e1, **e2;
566 register int inv, cross = 0, t;
567
568 for (e2 = ND_in(w).list; *e2; e2++) {
569 register int cnt = ED_xpenalty(*e2);
570
571 inv = ND_order((agtail(*e2)));
572
573 for (e1 = ND_in(v).list; *e1; e1++) {
574 t = ND_order(agtail(*e1)) - inv;
575 if ((t > 0)
576 || ((t == 0)
577 && ( ED_tail_port(*e1).p.x > ED_tail_port(*e2).p.x)))
578 cross += ED_xpenalty(*e1) * cnt;
579 }
580 }
581 return cross;
582}
583
584static int out_cross(node_t * v, node_t * w)
585{
586 register edge_t **e1, **e2;
587 register int inv, cross = 0, t;
588
589 for (e2 = ND_out(w).list; *e2; e2++) {
590 register int cnt = ED_xpenalty(*e2);
591 inv = ND_order(aghead(*e2));
592
593 for (e1 = ND_out(v).list; *e1; e1++) {
594 t = ND_order(aghead(*e1)) - inv;
595 if ((t > 0)
596 || ((t == 0)
597 && ((ED_head_port(*e1)).p.x > (ED_head_port(*e2)).p.x)))
598 cross += ((ED_xpenalty(*e1)) * cnt);
599 }
600 }
601 return cross;
602
603}
604
605static void exchange(node_t * v, node_t * w)
606{
607 int vi, wi, r;
608
609 r = ND_rank(v);
610 vi = ND_order(v);
611 wi = ND_order(w);
612 ND_order(v) = wi;
613 GD_rank(Root)[r].v[wi] = v;
614 ND_order(w) = vi;
615 GD_rank(Root)[r].v[vi] = w;
616}
617
618static void balanceNodes(graph_t * g, int r, node_t * v, node_t * w)
619{
620 node_t *s; /* separator node */
621 int sepIndex = 0;
622 int nullType; /* type of null nodes */
623 int cntDummy = 0, cntOri = 0;
624 int k = 0, m = 0, k1 = 0, m1 = 0, i = 0;
625
626 /* we only consider v and w of different types */
627 if (ND_node_type(v) == ND_node_type(w))
628 return;
629
630 /* count the number of dummy and original nodes */
631 for (i = 0; i < GD_rank(g)[r].n; i++) {
632 if (ND_node_type(GD_rank(g)[r].v[i]) == NORMAL)
633 cntOri++;
634 else
635 cntDummy++;
636 }
637
638 if (cntOri < cntDummy) {
639 if (ND_node_type(v) == NORMAL)
640 s = v;
641 else
642 s = w;
643 } else {
644 if (ND_node_type(v) == NORMAL)
645 s = w;
646 else
647 s = v;
648 }
649
650 /* get the separator node index */
651 for (i = 0; i < GD_rank(g)[r].n; i++) {
652 if (GD_rank(g)[r].v[i] == s)
653 sepIndex = i;
654 }
655
656 nullType = (ND_node_type(s) == NORMAL) ? VIRTUAL : NORMAL;
657
658 /* count the number of null nodes to the left and
659 * right of the separator node
660 */
661 for (i = sepIndex - 1; i >= 0; i--) {
662 if (ND_node_type(GD_rank(g)[r].v[i]) == nullType)
663 k++;
664 else
665 break;
666 }
667
668 for (i = sepIndex + 1; i < GD_rank(g)[r].n; i++) {
669 if (ND_node_type(GD_rank(g)[r].v[i]) == nullType)
670 m++;
671 else
672 break;
673 }
674
675 /* now exchange v,w and calculate the same counts */
676
677 exchange(v, w);
678
679 /* get the separator node index */
680 for (i = 0; i < GD_rank(g)[r].n; i++) {
681 if (GD_rank(g)[r].v[i] == s)
682 sepIndex = i;
683 }
684
685 /* count the number of null nodes to the left and
686 * right of the separator node
687 */
688 for (i = sepIndex - 1; i >= 0; i--) {
689 if (ND_node_type(GD_rank(g)[r].v[i]) == nullType)
690 k1++;
691 else
692 break;
693 }
694
695 for (i = sepIndex + 1; i < GD_rank(g)[r].n; i++) {
696 if (ND_node_type(GD_rank(g)[r].v[i]) == nullType)
697 m1++;
698 else
699 break;
700 }
701
702 if (abs(k1 - m1) > abs(k - m)) {
703 exchange(v, w); //revert to the original ordering
704 }
705}
706
707static int balance(graph_t * g)
708{
709 int i, c0, c1, rv;
710 node_t *v, *w;
711 int r;
712
713 rv = 0;
714
715 for (r = GD_maxrank(g); r >= GD_minrank(g); r--) {
716
717 GD_rank(g)[r].candidate = FALSE;
718 for (i = 0; i < GD_rank(g)[r].n - 1; i++) {
719 v = GD_rank(g)[r].v[i];
720 w = GD_rank(g)[r].v[i + 1];
721 assert(ND_order(v) < ND_order(w));
722 if (left2right(g, v, w))
723 continue;
724 c0 = c1 = 0;
725 if (r > 0) {
726 c0 += in_cross(v, w);
727 c1 += in_cross(w, v);
728 }
729
730 if (GD_rank(g)[r + 1].n > 0) {
731 c0 += out_cross(v, w);
732 c1 += out_cross(w, v);
733 }
734#if 0
735 if ((c1 < c0) || ((c0 > 0) && reverse && (c1 == c0))) {
736 exchange(v, w);
737 rv += (c0 - c1);
738 GD_rank(Root)[r].valid = FALSE;
739 GD_rank(g)[r].candidate = TRUE;
740
741 if (r > GD_minrank(g)) {
742 GD_rank(Root)[r - 1].valid = FALSE;
743 GD_rank(g)[r - 1].candidate = TRUE;
744 }
745 if (r < GD_maxrank(g)) {
746 GD_rank(Root)[r + 1].valid = FALSE;
747 GD_rank(g)[r + 1].candidate = TRUE;
748 }
749 }
750#endif
751
752 if (c1 <= c0) {
753 balanceNodes(g, r, v, w);
754 }
755 }
756 }
757 return rv;
758}
759
760static int transpose_step(graph_t * g, int r, int reverse)
761{
762 int i, c0, c1, rv;
763 node_t *v, *w;
764
765 rv = 0;
766 GD_rank(g)[r].candidate = FALSE;
767 for (i = 0; i < GD_rank(g)[r].n - 1; i++) {
768 v = GD_rank(g)[r].v[i];
769 w = GD_rank(g)[r].v[i + 1];
770 assert(ND_order(v) < ND_order(w));
771 if (left2right(g, v, w))
772 continue;
773 c0 = c1 = 0;
774 if (r > 0) {
775 c0 += in_cross(v, w);
776 c1 += in_cross(w, v);
777 }
778 if (GD_rank(g)[r + 1].n > 0) {
779 c0 += out_cross(v, w);
780 c1 += out_cross(w, v);
781 }
782 if ((c1 < c0) || ((c0 > 0) && reverse && (c1 == c0))) {
783 exchange(v, w);
784 rv += (c0 - c1);
785 GD_rank(Root)[r].valid = FALSE;
786 GD_rank(g)[r].candidate = TRUE;
787
788 if (r > GD_minrank(g)) {
789 GD_rank(Root)[r - 1].valid = FALSE;
790 GD_rank(g)[r - 1].candidate = TRUE;
791 }
792 if (r < GD_maxrank(g)) {
793 GD_rank(Root)[r + 1].valid = FALSE;
794 GD_rank(g)[r + 1].candidate = TRUE;
795 }
796 }
797 }
798 return rv;
799}
800
801static void transpose(graph_t * g, int reverse)
802{
803 int r, delta;
804
805 for (r = GD_minrank(g); r <= GD_maxrank(g); r++)
806 GD_rank(g)[r].candidate = TRUE;
807 do {
808 delta = 0;
809#ifdef NOTDEF
810 /* don't run both the upward and downward passes- they cancel.
811 i tried making it depend on whether an odd or even pass,
812 but that didn't help. */
813 for (r = GD_maxrank(g); r >= GD_minrank(g); r--)
814 if (GD_rank(g)[r].candidate)
815 delta += transpose_step(g, r, reverse);
816#endif
817 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
818 if (GD_rank(g)[r].candidate) {
819 delta += transpose_step(g, r, reverse);
820 }
821 }
822 /*} while (delta > ncross(g)*(1.0 - Convergence)); */
823 } while (delta >= 1);
824}
825
826static int mincross(graph_t * g, int startpass, int endpass, int doBalance)
827{
828 int maxthispass, iter, trying, pass;
829 int cur_cross, best_cross;
830
831 if (startpass > 1) {
832 cur_cross = best_cross = ncross(g);
833 save_best(g);
834 } else
835 cur_cross = best_cross = INT_MAX;
836 for (pass = startpass; pass <= endpass; pass++) {
837 if (pass <= 1) {
838 maxthispass = MIN(4, MaxIter);
839 if (g == dot_root(g))
840 build_ranks(g, pass);
841 if (pass == 0)
842 flat_breakcycles(g);
843 flat_reorder(g);
844
845 if ((cur_cross = ncross(g)) <= best_cross) {
846 save_best(g);
847 best_cross = cur_cross;
848 }
849 trying = 0;
850 } else {
851 maxthispass = MaxIter;
852 if (cur_cross > best_cross)
853 restore_best(g);
854 cur_cross = best_cross;
855 }
856 trying = 0;
857 for (iter = 0; iter < maxthispass; iter++) {
858 if (Verbose)
859 fprintf(stderr,
860 "mincross: pass %d iter %d trying %d cur_cross %d best_cross %d\n",
861 pass, iter, trying, cur_cross, best_cross);
862 if (trying++ >= MinQuit)
863 break;
864 if (cur_cross == 0)
865 break;
866 mincross_step(g, iter);
867 if ((cur_cross = ncross(g)) <= best_cross) {
868 save_best(g);
869 if (cur_cross < Convergence * best_cross)
870 trying = 0;
871 best_cross = cur_cross;
872 }
873 }
874 if (cur_cross == 0)
875 break;
876 }
877 if (cur_cross > best_cross)
878 restore_best(g);
879 if (best_cross > 0) {
880 transpose(g, FALSE);
881 best_cross = ncross(g);
882 }
883 if (doBalance) {
884 for (iter = 0; iter < maxthispass; iter++)
885 balance(g);
886 }
887
888 return best_cross;
889}
890
891static void restore_best(graph_t * g)
892{
893 node_t *n;
894 int i, r;
895
896 /* for (n = GD_nlist(g); n; n = ND_next(n)) */
897 /* ND_order(n) = saveorder(n); */
898 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
899 for (i = 0; i < GD_rank(g)[r].n; i++) {
900 n = GD_rank(g)[r].v[i];
901 ND_order(n) = saveorder(n);
902 }
903 }
904 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
905 GD_rank(Root)[r].valid = FALSE;
906 qsort(GD_rank(g)[r].v, GD_rank(g)[r].n, sizeof(GD_rank(g)[0].v[0]),
907 (qsort_cmpf) nodeposcmpf);
908 }
909}
910
911static void save_best(graph_t * g)
912{
913 node_t *n;
914 /* for (n = GD_nlist(g); n; n = ND_next(n)) */
915 /* saveorder(n) = ND_order(n); */
916 int i, r;
917 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
918 for (i = 0; i < GD_rank(g)[r].n; i++) {
919 n = GD_rank(g)[r].v[i];
920 saveorder(n) = ND_order(n);
921 }
922 }
923}
924
925/* merges the connected components of g */
926static void merge_components(graph_t * g)
927{
928 int c;
929 node_t *u, *v;
930
931 if (GD_comp(g).size <= 1)
932 return;
933 u = NULL;
934 for (c = 0; c < GD_comp(g).size; c++) {
935 v = GD_comp(g).list[c];
936 if (u)
937 ND_next(u) = v;
938 ND_prev(v) = u;
939 while (ND_next(v)) {
940 v = ND_next(v);
941 }
942 u = v;
943 }
944 GD_comp(g).size = 1;
945 GD_nlist(g) = GD_comp(g).list[0];
946 GD_minrank(g) = GlobalMinRank;
947 GD_maxrank(g) = GlobalMaxRank;
948}
949
950/* merge connected components, create globally consistent rank lists */
951static void merge2(graph_t * g)
952{
953 int i, r;
954 node_t *v;
955
956 /* merge the components and rank limits */
957 merge_components(g);
958
959 /* install complete ranks */
960 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
961 GD_rank(g)[r].n = GD_rank(g)[r].an;
962 GD_rank(g)[r].v = GD_rank(g)[r].av;
963 for (i = 0; i < GD_rank(g)[r].n; i++) {
964 v = GD_rank(g)[r].v[i];
965 if (v == NULL) {
966 if (Verbose)
967 fprintf(stderr,
968 "merge2: graph %s, rank %d has only %d < %d nodes\n",
969 agnameof(g), r, i, GD_rank(g)[r].n);
970 GD_rank(g)[r].n = i;
971 break;
972 }
973 ND_order(v) = i;
974 }
975 }
976}
977
978static void cleanup2(graph_t * g, int nc)
979{
980 int i, j, r, c;
981 node_t *v;
982 edge_t *e;
983
984 if (TI_list) {
985 free(TI_list);
986 TI_list = NULL;
987 }
988 if (TE_list) {
989 free(TE_list);
990 TE_list = NULL;
991 }
992 /* fix vlists of clusters */
993 for (c = 1; c <= GD_n_cluster(g); c++)
994 rec_reset_vlists(GD_clust(g)[c]);
995
996 /* remove node temporary edges for ordering nodes */
997 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
998 for (i = 0; i < GD_rank(g)[r].n; i++) {
999 v = GD_rank(g)[r].v[i];
1000 ND_order(v) = i;
1001 if (ND_flat_out(v).list) {
1002 for (j = 0; (e = ND_flat_out(v).list[j]); j++)
1003 if (ED_edge_type(e) == FLATORDER) {
1004 delete_flat_edge(e);
1005 free(e->base.data);
1006 free(e);
1007 j--;
1008 }
1009 }
1010 }
1011 free_matrix(GD_rank(g)[r].flat);
1012 }
1013 if (Verbose)
1014 fprintf(stderr, "mincross %s: %d crossings, %.2f secs.\n",
1015 agnameof(g), nc, elapsed_sec());
1016}
1017
1018static node_t *neighbor(node_t * v, int dir)
1019{
1020 node_t *rv;
1021
1022 rv = NULL;
1023assert(v);
1024 if (dir < 0) {
1025 if (ND_order(v) > 0)
1026 rv = GD_rank(Root)[ND_rank(v)].v[ND_order(v) - 1];
1027 } else
1028 rv = GD_rank(Root)[ND_rank(v)].v[ND_order(v) + 1];
1029assert((rv == 0) || (ND_order(rv)-ND_order(v))*dir > 0);
1030 return rv;
1031}
1032
1033static int is_a_normal_node_of(graph_t * g, node_t * v)
1034{
1035 return ((ND_node_type(v) == NORMAL) && agcontains(g, v));
1036}
1037
1038static int is_a_vnode_of_an_edge_of(graph_t * g, node_t * v)
1039{
1040 if ((ND_node_type(v) == VIRTUAL)
1041 && (ND_in(v).size == 1) && (ND_out(v).size == 1)) {
1042 edge_t *e = ND_out(v).list[0];
1043 while (ED_edge_type(e) != NORMAL)
1044 e = ED_to_orig(e);
1045 if (agcontains(g, e))
1046 return TRUE;
1047 }
1048 return FALSE;
1049}
1050
1051static int inside_cluster(graph_t * g, node_t * v)
1052{
1053 return (is_a_normal_node_of(g, v) | is_a_vnode_of_an_edge_of(g, v));
1054}
1055
1056static node_t *furthestnode(graph_t * g, node_t * v, int dir)
1057{
1058 node_t *u, *rv;
1059
1060 rv = u = v;
1061 while ((u = neighbor(u, dir))) {
1062 if (is_a_normal_node_of(g, u))
1063 rv = u;
1064 else if (is_a_vnode_of_an_edge_of(g, u))
1065 rv = u;
1066 }
1067 return rv;
1068}
1069
1070void save_vlist(graph_t * g)
1071{
1072 int r;
1073
1074 if (GD_rankleader(g))
1075 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1076 GD_rankleader(g)[r] = GD_rank(g)[r].v[0];
1077 }
1078}
1079
1080void rec_save_vlists(graph_t * g)
1081{
1082 int c;
1083
1084 save_vlist(g);
1085 for (c = 1; c <= GD_n_cluster(g); c++)
1086 rec_save_vlists(GD_clust(g)[c]);
1087}
1088
1089
1090void rec_reset_vlists(graph_t * g)
1091{
1092 int r, c;
1093 node_t *u, *v, *w;
1094
1095 /* fix vlists of sub-clusters */
1096 for (c = 1; c <= GD_n_cluster(g); c++)
1097 rec_reset_vlists(GD_clust(g)[c]);
1098
1099 if (GD_rankleader(g))
1100 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1101 v = GD_rankleader(g)[r];
1102#ifdef DEBUG
1103 node_in_root_vlist(v);
1104#endif
1105 u = furthestnode(g, v, -1);
1106 w = furthestnode(g, v, 1);
1107 GD_rankleader(g)[r] = u;
1108#ifdef DEBUG
1109 assert(GD_rank(dot_root(g))[r].v[ND_order(u)] == u);
1110#endif
1111 GD_rank(g)[r].v = GD_rank(dot_root(g))[r].v + ND_order(u);
1112 GD_rank(g)[r].n = ND_order(w) - ND_order(u) + 1;
1113 }
1114}
1115
1116/* realFillRanks:
1117 * The structures in crossing minimization and positioning require
1118 * that clusters have some node on each rank. This function recursively
1119 * guarantees this property. It takes into account nodes and edges in
1120 * a cluster, the latter causing dummy nodes for intervening ranks.
1121 * For any rank without node, we create a real node of small size. This
1122 * is stored in the subgraph sg, for easy removal later.
1123 *
1124 * I believe it is not necessary to do this for the root graph, as these
1125 * are laid out one component at a time and these will necessarily have a
1126 * node on each rank from source to sink levels.
1127 */
1128static Agraph_t*
1129realFillRanks (Agraph_t* g, int rnks[], int rnks_sz, Agraph_t* sg)
1130{
1131 int i, c;
1132 Agedge_t* e;
1133 Agnode_t* n;
1134
1135 for (c = 1; c <= GD_n_cluster(g); c++)
1136 sg = realFillRanks (GD_clust(g)[c], rnks, rnks_sz, sg);
1137
1138 if (dot_root(g) == g)
1139 return sg;
1140 memset (rnks, 0, sizeof(int)*rnks_sz);
1141 for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
1142 rnks[ND_rank(n)] = 1;
1143 for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
1144 for (i = ND_rank(n)+1; i <= ND_rank(aghead(e)); i++)
1145 rnks[i] = 1;
1146 }
1147 }
1148 for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
1149 if (rnks[i] == 0) {
1150 if (!sg) {
1151 sg = agsubg (dot_root(g), "_new_rank", 1);
1152 }
1153 n = agnode (sg, NULL, 1);
1154 agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE);
1155 ND_rank(n) = i;
1156 ND_lw(n) = ND_rw(n) = 0.5;
1157 ND_ht(n) = 1;
1158 ND_UF_size(n) = 1;
1159 alloc_elist(4, ND_in(n));
1160 alloc_elist(4, ND_out(n));
1161 agsubnode (g, n, 1);
1162 }
1163 }
1164 return sg;
1165}
1166
1167static void
1168fillRanks (Agraph_t* g)
1169{
1170 Agraph_t* sg;
1171 int rnks_sz = GD_maxrank(g) + 2;
1172 int* rnks = N_NEW(rnks_sz, int);
1173 sg = realFillRanks (g, rnks, rnks_sz, NULL);
1174 free (rnks);
1175}
1176
1177static void init_mincross(graph_t * g)
1178{
1179 int size;
1180
1181 if (Verbose)
1182 start_timer();
1183
1184 ReMincross = FALSE;
1185 Root = g;
1186 /* alloc +1 for the null terminator usage in do_ordering() */
1187 /* also, the +1 avoids attempts to alloc 0 sizes, something
1188 that efence complains about */
1189 size = agnedges(dot_root(g)) + 1;
1190 TE_list = N_NEW(size, edge_t *);
1191 TI_list = N_NEW(size, int);
1192 mincross_options(g);
1193 if (GD_flags(g) & NEW_RANK)
1194 fillRanks (g);
1195 class2(g);
1196 decompose(g, 1);
1197 allocate_ranks(g);
1198 ordered_edges(g);
1199 GlobalMinRank = GD_minrank(g);
1200 GlobalMaxRank = GD_maxrank(g);
1201}
1202
1203void flat_rev(Agraph_t * g, Agedge_t * e)
1204{
1205 int j;
1206 Agedge_t *rev;
1207
1208 if (!ND_flat_out(aghead(e)).list)
1209 rev = NULL;
1210 else
1211 for (j = 0; (rev = ND_flat_out(aghead(e)).list[j]); j++)
1212 if (aghead(rev) == agtail(e))
1213 break;
1214 if (rev) {
1215 merge_oneway(e, rev);
1216 if (ED_to_virt(e) == 0)
1217 ED_to_virt(e) = rev;
1218 if ((ED_edge_type(rev) == FLATORDER)
1219 && (ED_to_orig(rev) == 0))
1220 ED_to_orig(rev) = e;
1221 elist_append(e, ND_other(agtail(e)));
1222 } else {
1223 rev = new_virtual_edge(aghead(e), agtail(e), e);
1224 if (ED_edge_type(e) == FLATORDER)
1225 ED_edge_type(rev) = FLATORDER;
1226 else
1227 ED_edge_type(rev) = REVERSED;
1228 ED_label(rev) = ED_label(e);
1229 flat_edge(g, rev);
1230 }
1231}
1232
1233static void flat_search(graph_t * g, node_t * v)
1234{
1235 int i;
1236 boolean hascl;
1237 edge_t *e;
1238 adjmatrix_t *M = GD_rank(g)[ND_rank(v)].flat;
1239
1240 ND_mark(v) = TRUE;
1241 ND_onstack(v) = TRUE;
1242 hascl = (GD_n_cluster(dot_root(g)) > 0);
1243 if (ND_flat_out(v).list)
1244 for (i = 0; (e = ND_flat_out(v).list[i]); i++) {
1245 if (hascl
1246 && NOT(agcontains(g, agtail(e)) && agcontains(g, aghead(e))))
1247 continue;
1248 if (ED_weight(e) == 0)
1249 continue;
1250 if (ND_onstack(aghead(e)) == TRUE) {
1251 assert(flatindex(aghead(e)) < M->nrows);
1252 assert(flatindex(agtail(e)) < M->ncols);
1253 ELT(M, flatindex(aghead(e)), flatindex(agtail(e))) = 1;
1254 delete_flat_edge(e);
1255 i--;
1256 if (ED_edge_type(e) == FLATORDER)
1257 continue;
1258 flat_rev(g, e);
1259 } else {
1260 assert(flatindex(aghead(e)) < M->nrows);
1261 assert(flatindex(agtail(e)) < M->ncols);
1262 ELT(M, flatindex(agtail(e)), flatindex(aghead(e))) = 1;
1263 if (ND_mark(aghead(e)) == FALSE)
1264 flat_search(g, aghead(e));
1265 }
1266 }
1267 ND_onstack(v) = FALSE;
1268}
1269
1270static void flat_breakcycles(graph_t * g)
1271{
1272 int i, r, flat;
1273 node_t *v;
1274
1275 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1276 flat = 0;
1277 for (i = 0; i < GD_rank(g)[r].n; i++) {
1278 v = GD_rank(g)[r].v[i];
1279 ND_mark(v) = ND_onstack(v) = FALSE;
1280 flatindex(v) = i;
1281 if ((ND_flat_out(v).size > 0) && (flat == 0)) {
1282 GD_rank(g)[r].flat =
1283 new_matrix(GD_rank(g)[r].n, GD_rank(g)[r].n);
1284 flat = 1;
1285 }
1286 }
1287 if (flat) {
1288 for (i = 0; i < GD_rank(g)[r].n; i++) {
1289 v = GD_rank(g)[r].v[i];
1290 if (ND_mark(v) == FALSE)
1291 flat_search(g, v);
1292 }
1293 }
1294 }
1295}
1296
1297/* allocate_ranks:
1298 * Allocate rank structure, determining number of nodes per rank.
1299 * Note that no nodes are put into the structure yet.
1300 */
1301void allocate_ranks(graph_t * g)
1302{
1303 int r, low, high, *cn;
1304 node_t *n;
1305 edge_t *e;
1306
1307 cn = N_NEW(GD_maxrank(g) + 2, int); /* must be 0 based, not GD_minrank */
1308 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1309 cn[ND_rank(n)]++;
1310 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1311 low = ND_rank(agtail(e));
1312 high = ND_rank(aghead(e));
1313 if (low > high) {
1314 int t = low;
1315 low = high;
1316 high = t;
1317 }
1318 for (r = low + 1; r < high; r++)
1319 cn[r]++;
1320 }
1321 }
1322 GD_rank(g) = N_NEW(GD_maxrank(g) + 2, rank_t);
1323 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1324 GD_rank(g)[r].an = GD_rank(g)[r].n = cn[r];
1325 GD_rank(g)[r].av = GD_rank(g)[r].v = N_NEW(cn[r] + 1, node_t *);
1326 }
1327 free(cn);
1328}
1329
1330/* install a node at the current right end of its rank */
1331void install_in_rank(graph_t * g, node_t * n)
1332{
1333 int i, r;
1334
1335 r = ND_rank(n);
1336 i = GD_rank(g)[r].n;
1337 if (GD_rank(g)[r].an <= 0) {
1338 agerr(AGERR, "install_in_rank, line %d: %s %s rank %d i = %d an = 0\n",
1339 __LINE__, agnameof(g), agnameof(n), r, i);
1340 return;
1341 }
1342
1343 GD_rank(g)[r].v[i] = n;
1344 ND_order(n) = i;
1345 GD_rank(g)[r].n++;
1346 assert(GD_rank(g)[r].n <= GD_rank(g)[r].an);
1347#ifdef DEBUG
1348 {
1349 node_t *v;
1350
1351 for (v = GD_nlist(g); v; v = ND_next(v))
1352 if (v == n)
1353 break;
1354 assert(v != NULL);
1355 }
1356#endif
1357 if (ND_order(n) > GD_rank(Root)[r].an) {
1358 agerr(AGERR, "install_in_rank, line %d: ND_order(%s) [%d] > GD_rank(Root)[%d].an [%d]\n",
1359 __LINE__, agnameof(n), ND_order(n), r, GD_rank(Root)[r].an);
1360 return;
1361 }
1362 if ((r < GD_minrank(g)) || (r > GD_maxrank(g))) {
1363 agerr(AGERR, "install_in_rank, line %d: rank %d not in rank range [%d,%d]\n",
1364 __LINE__, r, GD_minrank(g), GD_maxrank(g));
1365 return;
1366 }
1367 if (GD_rank(g)[r].v + ND_order(n) >
1368 GD_rank(g)[r].av + GD_rank(Root)[r].an) {
1369 agerr(AGERR, "install_in_rank, line %d: GD_rank(g)[%d].v + ND_order(%s) [%d] > GD_rank(g)[%d].av + GD_rank(Root)[%d].an [%d]\n",
1370 __LINE__, r, agnameof(n),GD_rank(g)[r].v + ND_order(n), r, r, GD_rank(g)[r].av+GD_rank(Root)[r].an);
1371 return;
1372 }
1373}
1374
1375/* install nodes in ranks. the initial ordering ensure that series-parallel
1376 * graphs such as trees are drawn with no crossings. it tries searching
1377 * in- and out-edges and takes the better of the two initial orderings.
1378 */
1379void build_ranks(graph_t * g, int pass)
1380{
1381 int i, j;
1382 node_t *n, *n0;
1383 edge_t **otheredges;
1384 nodequeue *q;
1385
1386 q = new_queue(GD_n_nodes(g));
1387 for (n = GD_nlist(g); n; n = ND_next(n))
1388 MARK(n) = FALSE;
1389
1390#ifdef DEBUG
1391 {
1392 edge_t *e;
1393 for (n = GD_nlist(g); n; n = ND_next(n)) {
1394 for (i = 0; (e = ND_out(n).list[i]); i++)
1395 assert(MARK(aghead(e)) == FALSE);
1396 for (i = 0; (e = ND_in(n).list[i]); i++)
1397 assert(MARK(agtail(e)) == FALSE);
1398 }
1399 }
1400#endif
1401
1402 for (i = GD_minrank(g); i <= GD_maxrank(g); i++)
1403 GD_rank(g)[i].n = 0;
1404
1405 for (n = GD_nlist(g); n; n = ND_next(n)) {
1406 otheredges = ((pass == 0) ? ND_in(n).list : ND_out(n).list);
1407 if (otheredges[0] != NULL)
1408 continue;
1409 if (MARK(n) == FALSE) {
1410 MARK(n) = TRUE;
1411 enqueue(q, n);
1412 while ((n0 = dequeue(q))) {
1413 if (ND_ranktype(n0) != CLUSTER) {
1414 install_in_rank(g, n0);
1415 enqueue_neighbors(q, n0, pass);
1416 } else {
1417 install_cluster(g, n0, pass, q);
1418 }
1419 }
1420 }
1421 }
1422 if (dequeue(q))
1423 agerr(AGERR, "surprise\n");
1424 for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
1425 GD_rank(Root)[i].valid = FALSE;
1426 if (GD_flip(g) && (GD_rank(g)[i].n > 0)) {
1427 int n, ndiv2;
1428 node_t **vlist = GD_rank(g)[i].v;
1429 n = GD_rank(g)[i].n - 1;
1430 ndiv2 = n / 2;
1431 for (j = 0; j <= ndiv2; j++)
1432 exchange(vlist[j], vlist[n - j]);
1433 }
1434 }
1435
1436 if ((g == dot_root(g)) && ncross(g) > 0)
1437 transpose(g, FALSE);
1438 free_queue(q);
1439}
1440
1441void enqueue_neighbors(nodequeue * q, node_t * n0, int pass)
1442{
1443 int i;
1444 edge_t *e;
1445
1446 if (pass == 0) {
1447 for (i = 0; i < ND_out(n0).size; i++) {
1448 e = ND_out(n0).list[i];
1449 if ((MARK(aghead(e))) == FALSE) {
1450 MARK(aghead(e)) = TRUE;
1451 enqueue(q, aghead(e));
1452 }
1453 }
1454 } else {
1455 for (i = 0; i < ND_in(n0).size; i++) {
1456 e = ND_in(n0).list[i];
1457 if ((MARK(agtail(e))) == FALSE) {
1458 MARK(agtail(e)) = TRUE;
1459 enqueue(q, agtail(e));
1460 }
1461 }
1462 }
1463}
1464
1465static int constraining_flat_edge(Agraph_t *g, Agnode_t *v, Agedge_t *e)
1466{
1467 if (ED_weight(e) == 0) return FALSE;
1468 if (!inside_cluster(g,agtail(e))) return FALSE;
1469 if (!inside_cluster(g,aghead(e))) return FALSE;
1470 return TRUE;
1471}
1472
1473
1474/* construct nodes reachable from 'here' in post-order.
1475* This is the same as doing a topological sort in reverse order.
1476*/
1477static int postorder(graph_t * g, node_t * v, node_t ** list, int r)
1478{
1479 edge_t *e;
1480 int i, cnt = 0;
1481
1482 MARK(v) = TRUE;
1483 if (ND_flat_out(v).size > 0) {
1484 for (i = 0; (e = ND_flat_out(v).list[i]); i++) {
1485 if (!constraining_flat_edge(g,v,e)) continue;
1486 if (MARK(aghead(e)) == FALSE)
1487 cnt += postorder(g, aghead(e), list + cnt, r);
1488 }
1489 }
1490 assert(ND_rank(v) == r);
1491 list[cnt++] = v;
1492 return cnt;
1493}
1494
1495static void flat_reorder(graph_t * g)
1496{
1497 int i, j, r, pos, n_search, local_in_cnt, local_out_cnt, base_order;
1498 node_t *v, **left, **right, *t;
1499 node_t **temprank = NULL;
1500 edge_t *flat_e, *e;
1501
1502 if (GD_has_flat_edges(g) == FALSE)
1503 return;
1504 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1505 if (GD_rank(g)[r].n == 0) continue;
1506 base_order = ND_order(GD_rank(g)[r].v[0]);
1507 for (i = 0; i < GD_rank(g)[r].n; i++)
1508 MARK(GD_rank(g)[r].v[i]) = FALSE;
1509 temprank = ALLOC(i + 1, temprank, node_t *);
1510 pos = 0;
1511
1512 /* construct reverse topological sort order in temprank */
1513 for (i = 0; i < GD_rank(g)[r].n; i++) {
1514 if (GD_flip(g)) v = GD_rank(g)[r].v[i];
1515 else v = GD_rank(g)[r].v[GD_rank(g)[r].n - i - 1];
1516
1517 local_in_cnt = local_out_cnt = 0;
1518 for (j = 0; j < ND_flat_in(v).size; j++) {
1519 flat_e = ND_flat_in(v).list[j];
1520 if (constraining_flat_edge(g,v,flat_e)) local_in_cnt++;
1521 }
1522 for (j = 0; j < ND_flat_out(v).size; j++) {
1523 flat_e = ND_flat_out(v).list[j];
1524 if (constraining_flat_edge(g,v,flat_e)) local_out_cnt++;
1525 }
1526 if ((local_in_cnt == 0) && (local_out_cnt == 0))
1527 temprank[pos++] = v;
1528 else {
1529 if ((MARK(v) == FALSE) && (local_in_cnt == 0)) {
1530 left = temprank + pos;
1531 n_search = postorder(g, v, left, r);
1532 pos += n_search;
1533 }
1534 }
1535 }
1536
1537 if (pos) {
1538 if (GD_flip(g) == FALSE) {
1539 left = temprank;
1540 right = temprank + pos - 1;
1541 while (left < right) {
1542 t = *left;
1543 *left = *right;
1544 *right = t;
1545 left++;
1546 right--;
1547 }
1548 }
1549 for (i = 0; i < GD_rank(g)[r].n; i++) {
1550 v = GD_rank(g)[r].v[i] = temprank[i];
1551 ND_order(v) = i + base_order;
1552 }
1553
1554 /* nonconstraint flat edges must be made LR */
1555 for (i = 0; i < GD_rank(g)[r].n; i++) {
1556 v = GD_rank(g)[r].v[i];
1557 if (ND_flat_out(v).list) {
1558 for (j = 0; (e = ND_flat_out(v).list[j]); j++) {
1559 if ( ((GD_flip(g) == FALSE) && (ND_order(aghead(e)) < ND_order(agtail(e)))) ||
1560 ( (GD_flip(g)) && (ND_order(aghead(e)) > ND_order(agtail(e)) ))) {
1561 assert(constraining_flat_edge(g,v,e) == FALSE);
1562 delete_flat_edge(e);
1563 j--;
1564 flat_rev(g, e);
1565 }
1566 }
1567 }
1568 }
1569 /* postprocess to restore intended order */
1570 }
1571 /* else do no harm! */
1572 GD_rank(Root)[r].valid = FALSE;
1573 }
1574 if (temprank)
1575 free(temprank);
1576}
1577
1578static void reorder(graph_t * g, int r, int reverse, int hasfixed)
1579{
1580 int changed = 0, nelt;
1581 boolean muststay, sawclust;
1582 node_t **vlist = GD_rank(g)[r].v;
1583 node_t **lp, **rp, **ep = vlist + GD_rank(g)[r].n;
1584
1585 for (nelt = GD_rank(g)[r].n - 1; nelt >= 0; nelt--) {
1586 lp = vlist;
1587 while (lp < ep) {
1588 /* find leftmost node that can be compared */
1589 while ((lp < ep) && (ND_mval(*lp) < 0))
1590 lp++;
1591 if (lp >= ep)
1592 break;
1593 /* find the node that can be compared */
1594 sawclust = muststay = FALSE;
1595 for (rp = lp + 1; rp < ep; rp++) {
1596 if (sawclust && ND_clust(*rp))
1597 continue; /* ### */
1598 if (left2right(g, *lp, *rp)) {
1599 muststay = TRUE;
1600 break;
1601 }
1602 if (ND_mval(*rp) >= 0)
1603 break;
1604 if (ND_clust(*rp))
1605 sawclust = TRUE; /* ### */
1606 }
1607 if (rp >= ep)
1608 break;
1609 if (muststay == FALSE) {
1610 register int p1 = (ND_mval(*lp));
1611 register int p2 = (ND_mval(*rp));
1612 if ((p1 > p2) || ((p1 == p2) && (reverse))) {
1613 exchange(*lp, *rp);
1614 changed++;
1615 }
1616 }
1617 lp = rp;
1618 }
1619 if ((hasfixed == FALSE) && (reverse == FALSE))
1620 ep--;
1621 }
1622
1623 if (changed) {
1624 GD_rank(Root)[r].valid = FALSE;
1625 if (r > 0)
1626 GD_rank(Root)[r - 1].valid = FALSE;
1627 }
1628}
1629
1630static void mincross_step(graph_t * g, int pass)
1631{
1632 int r, other, first, last, dir;
1633 int hasfixed, reverse;
1634
1635 if ((pass % 4) < 2)
1636 reverse = TRUE;
1637 else
1638 reverse = FALSE;
1639 if (pass % 2) {
1640 r = GD_maxrank(g) - 1;
1641 dir = -1;
1642 } /* up pass */
1643 else {
1644 r = 1;
1645 dir = 1;
1646 } /* down pass */
1647
1648 if (pass % 2 == 0) { /* down pass */
1649 first = GD_minrank(g) + 1;
1650 if (GD_minrank(g) > GD_minrank(Root))
1651 first--;
1652 last = GD_maxrank(g);
1653 dir = 1;
1654 } else { /* up pass */
1655 first = GD_maxrank(g) - 1;
1656 last = GD_minrank(g);
1657 if (GD_maxrank(g) < GD_maxrank(Root))
1658 first++;
1659 dir = -1;
1660 }
1661
1662 for (r = first; r != last + dir; r += dir) {
1663 other = r - dir;
1664 hasfixed = medians(g, r, other);
1665 reorder(g, r, reverse, hasfixed);
1666 }
1667 transpose(g, NOT(reverse));
1668}
1669
1670static int local_cross(elist l, int dir)
1671{
1672 int i, j, is_out;
1673 int cross = 0;
1674 edge_t *e, *f;
1675 if (dir > 0)
1676 is_out = TRUE;
1677 else
1678 is_out = FALSE;
1679 for (i = 0; (e = l.list[i]); i++) {
1680 if (is_out)
1681 for (j = i + 1; (f = l.list[j]); j++) {
1682 if ((ND_order(aghead(f)) - ND_order(aghead(e)))
1683 * (ED_tail_port(f).p.x - ED_tail_port(e).p.x) < 0)
1684 cross += ED_xpenalty(e) * ED_xpenalty(f);
1685 } else
1686 for (j = i + 1; (f = l.list[j]); j++) {
1687 if ((ND_order(agtail(f)) - ND_order(agtail(e)))
1688 * (ED_head_port(f).p.x - ED_head_port(e).p.x) < 0)
1689 cross += ED_xpenalty(e) * ED_xpenalty(f);
1690 }
1691 }
1692 return cross;
1693}
1694
1695static int rcross(graph_t * g, int r)
1696{
1697 static int *Count, C;
1698 int top, bot, cross, max, i, k;
1699 node_t **rtop, *v;
1700
1701 cross = 0;
1702 max = 0;
1703 rtop = GD_rank(g)[r].v;
1704
1705 if (C <= GD_rank(Root)[r + 1].n) {
1706 C = GD_rank(Root)[r + 1].n + 1;
1707 Count = ALLOC(C, Count, int);
1708 }
1709
1710 for (i = 0; i < GD_rank(g)[r + 1].n; i++)
1711 Count[i] = 0;
1712
1713 for (top = 0; top < GD_rank(g)[r].n; top++) {
1714 register edge_t *e;
1715 if (max > 0) {
1716 for (i = 0; (e = ND_out(rtop[top]).list[i]); i++) {
1717 for (k = ND_order(aghead(e)) + 1; k <= max; k++)
1718 cross += Count[k] * ED_xpenalty(e);
1719 }
1720 }
1721 for (i = 0; (e = ND_out(rtop[top]).list[i]); i++) {
1722 register int inv = ND_order(aghead(e));
1723 if (inv > max)
1724 max = inv;
1725 Count[inv] += ED_xpenalty(e);
1726 }
1727 }
1728 for (top = 0; top < GD_rank(g)[r].n; top++) {
1729 v = GD_rank(g)[r].v[top];
1730 if (ND_has_port(v))
1731 cross += local_cross(ND_out(v), 1);
1732 }
1733 for (bot = 0; bot < GD_rank(g)[r + 1].n; bot++) {
1734 v = GD_rank(g)[r + 1].v[bot];
1735 if (ND_has_port(v))
1736 cross += local_cross(ND_in(v), -1);
1737 }
1738 return cross;
1739}
1740
1741int ncross(graph_t * g)
1742{
1743 int r, count, nc;
1744
1745 g = Root;
1746 count = 0;
1747 for (r = GD_minrank(g); r < GD_maxrank(g); r++) {
1748 if (GD_rank(g)[r].valid)
1749 count += GD_rank(g)[r].cache_nc;
1750 else {
1751 nc = GD_rank(g)[r].cache_nc = rcross(g, r);
1752 count += nc;
1753 GD_rank(g)[r].valid = TRUE;
1754 }
1755 }
1756 return count;
1757}
1758
1759static int ordercmpf(int *i0, int *i1)
1760{
1761 return (*i0) - (*i1);
1762}
1763
1764/* flat_mval:
1765 * Calculate a mval for nodes with no in or out non-flat edges.
1766 * Assume (ND_out(n).size == 0) && (ND_in(n).size == 0)
1767 * Find flat edge a->n where a has the largest order and set
1768 * n.mval = a.mval+1, assuming a.mval is defined (>=0).
1769 * If there are no flat in edges, find flat edge n->a where a
1770 * has the smallest order and set * n.mval = a.mval-1, assuming
1771 * a.mval is > 0.
1772 * Return true if n.mval is left -1, indicating a fixed node for sorting.
1773 */
1774static int flat_mval(node_t * n)
1775{
1776 int i;
1777 edge_t *e, **fl;
1778 node_t *nn;
1779
1780 if (ND_flat_in(n).size > 0) {
1781 fl = ND_flat_in(n).list;
1782 nn = agtail(fl[0]);
1783 for (i = 1; (e = fl[i]); i++)
1784 if (ND_order(agtail(e)) > ND_order(nn))
1785 nn = agtail(e);
1786 if (ND_mval(nn) >= 0) {
1787 ND_mval(n) = ND_mval(nn) + 1;
1788 return FALSE;
1789 }
1790 } else if (ND_flat_out(n).size > 0) {
1791 fl = ND_flat_out(n).list;
1792 nn = aghead(fl[0]);
1793 for (i = 1; (e = fl[i]); i++)
1794 if (ND_order(aghead(e)) < ND_order(nn))
1795 nn = aghead(e);
1796 if (ND_mval(nn) > 0) {
1797 ND_mval(n) = ND_mval(nn) - 1;
1798 return FALSE;
1799 }
1800 }
1801 return TRUE;
1802}
1803
1804#define VAL(node,port) (MC_SCALE * ND_order(node) + (port).order)
1805
1806static boolean medians(graph_t * g, int r0, int r1)
1807{
1808 int i, j, j0, lm, rm, lspan, rspan, *list;
1809 node_t *n, **v;
1810 edge_t *e;
1811 boolean hasfixed = FALSE;
1812
1813 list = TI_list;
1814 v = GD_rank(g)[r0].v;
1815 for (i = 0; i < GD_rank(g)[r0].n; i++) {
1816 n = v[i];
1817 j = 0;
1818 if (r1 > r0)
1819 for (j0 = 0; (e = ND_out(n).list[j0]); j0++) {
1820 if (ED_xpenalty(e) > 0)
1821 list[j++] = VAL(aghead(e), ED_head_port(e));
1822 } else
1823 for (j0 = 0; (e = ND_in(n).list[j0]); j0++) {
1824 if (ED_xpenalty(e) > 0)
1825 list[j++] = VAL(agtail(e), ED_tail_port(e));
1826 }
1827 switch (j) {
1828 case 0:
1829 ND_mval(n) = -1;
1830 break;
1831 case 1:
1832 ND_mval(n) = list[0];
1833 break;
1834 case 2:
1835 ND_mval(n) = (list[0] + list[1]) / 2;
1836 break;
1837 default:
1838 qsort(list, j, sizeof(int), (qsort_cmpf) ordercmpf);
1839 if (j % 2)
1840 ND_mval(n) = list[j / 2];
1841 else {
1842 /* weighted median */
1843 rm = j / 2;
1844 lm = rm - 1;
1845 rspan = list[j - 1] - list[rm];
1846 lspan = list[lm] - list[0];
1847 if (lspan == rspan)
1848 ND_mval(n) = (list[lm] + list[rm]) / 2;
1849 else {
1850 double w = list[lm] * (double)rspan + list[rm] * (double)lspan;
1851 ND_mval(n) = w / (lspan + rspan);
1852 }
1853 }
1854 }
1855 }
1856 for (i = 0; i < GD_rank(g)[r0].n; i++) {
1857 n = v[i];
1858 if ((ND_out(n).size == 0) && (ND_in(n).size == 0))
1859 hasfixed |= flat_mval(n);
1860 }
1861 return hasfixed;
1862}
1863
1864static int nodeposcmpf(node_t ** n0, node_t ** n1)
1865{
1866 return (ND_order(*n0) - ND_order(*n1));
1867}
1868
1869static int edgeidcmpf(edge_t ** e0, edge_t ** e1)
1870{
1871 return (AGSEQ(*e0) - AGSEQ(*e1));
1872}
1873
1874/* following code deals with weights of edges of "virtual" nodes */
1875#define ORDINARY 0
1876#define SINGLETON 1
1877#define VIRTUALNODE 2
1878#define NTYPES 3
1879
1880#define C_EE 1
1881#define C_VS 2
1882#define C_SS 2
1883#define C_VV 4
1884
1885static int table[NTYPES][NTYPES] = {
1886 /* ordinary */ {C_EE, C_EE, C_EE},
1887 /* singleton */ {C_EE, C_SS, C_VS},
1888 /* virtual */ {C_EE, C_VS, C_VV}
1889};
1890
1891static int endpoint_class(node_t * n)
1892{
1893 if (ND_node_type(n) == VIRTUAL)
1894 return VIRTUALNODE;
1895 if (ND_weight_class(n) <= 1)
1896 return SINGLETON;
1897 return ORDINARY;
1898}
1899
1900void virtual_weight(edge_t * e)
1901{
1902 int t;
1903 t = table[endpoint_class(agtail(e))][endpoint_class(aghead(e))];
1904 ED_weight(e) *= t;
1905}
1906
1907#ifdef DEBUG
1908void check_rs(graph_t * g, int null_ok)
1909{
1910 int i, r;
1911 node_t *v, *prev;
1912
1913 fprintf(stderr, "\n\n%s:\n", agnameof(g));
1914 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1915 fprintf(stderr, "%d: ", r);
1916 prev = NULL;
1917 for (i = 0; i < GD_rank(g)[r].n; i++) {
1918 v = GD_rank(g)[r].v[i];
1919 if (v == NULL) {
1920 fprintf(stderr, "NULL\t");
1921 if (null_ok == FALSE)
1922 abort();
1923 } else {
1924 fprintf(stderr, "%s(%f)\t", agnameof(v), ND_mval(v));
1925 assert(ND_rank(v) == r);
1926 assert(v != prev);
1927 prev = v;
1928 }
1929 }
1930 fprintf(stderr, "\n");
1931 }
1932}
1933
1934void check_order(void)
1935{
1936 int i, r;
1937 node_t *v;
1938 graph_t *g = Root;
1939
1940 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1941 assert(GD_rank(g)[r].v[GD_rank(g)[r].n] == NULL);
1942 for (i = 0; (v = GD_rank(g)[r].v[i]); i++) {
1943 assert(ND_rank(v) == r);
1944 assert(ND_order(v) == i);
1945 }
1946 }
1947}
1948#endif
1949
1950static void mincross_options(graph_t * g)
1951{
1952 char *p;
1953 double f;
1954
1955 /* set default values */
1956 MinQuit = 8;
1957 MaxIter = 24;
1958 Convergence = .995;
1959
1960 p = agget(g, "mclimit");
1961 if (p && ((f = atof(p)) > 0.0)) {
1962 MinQuit = MAX(1, MinQuit * f);
1963 MaxIter = MAX(1, MaxIter * f);
1964 }
1965}
1966
1967#ifdef DEBUG
1968void check_exchange(node_t * v, node_t * w)
1969{
1970 int i, r;
1971 node_t *u;
1972
1973 if ((ND_clust(v) == NULL) && (ND_clust(w) == NULL))
1974 return;
1975 assert((ND_clust(v) == NULL) || (ND_clust(w) == NULL));
1976 assert(ND_rank(v) == ND_rank(w));
1977 assert(ND_order(v) < ND_order(w));
1978 r = ND_rank(v);
1979
1980 for (i = ND_order(v) + 1; i < ND_order(w); i++) {
1981 u = GD_rank(dot_root(v))[r].v[i];
1982 if (ND_clust(u))
1983 abort();
1984 }
1985}
1986
1987void check_vlists(graph_t * g)
1988{
1989 int c, i, j, r;
1990 node_t *u;
1991
1992 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1993 for (i = 0; i < GD_rank(g)[r].n; i++) {
1994 u = GD_rank(g)[r].v[i];
1995 j = ND_order(u);
1996 assert(GD_rank(Root)[r].v[j] == u);
1997 }
1998 if (GD_rankleader(g)) {
1999 u = GD_rankleader(g)[r];
2000 j = ND_order(u);
2001 assert(GD_rank(Root)[r].v[j] == u);
2002 }
2003 }
2004 for (c = 1; c <= GD_n_cluster(g); c++)
2005 check_vlists(GD_clust(g)[c]);
2006}
2007
2008void node_in_root_vlist(node_t * n)
2009{
2010 node_t **vptr;
2011
2012 for (vptr = GD_rank(Root)[ND_rank(n)].v; *vptr; vptr++)
2013 if (*vptr == n)
2014 break;
2015 if (*vptr == 0)
2016 abort();
2017}
2018#endif /* DEBUG code */
2019