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