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