42#define MARK(v) (ND_mark(v))
43#define saveorder(v) (ND_coord(v)).x
44#define flatindex(v) ((size_t)ND_low(v))
49static int edgeidcmpf(
const void *,
const void *);
67static int ordercmpf(
const void *,
const void *);
68static int64_t
ncross(ints_t *scratch);
76void check_rs(
graph_t * g,
int null_ok);
77void check_order(
void);
79void node_in_root_vlist(
node_t * n);
93#if defined(DEBUG) && DEBUG > 1
97 fprintf (stderr,
" ");
102static char* nname(
node_t* v)
104 static char buf[1000];
109 snprintf(buf,
sizeof(buf),
"v_%p", v);
111 snprintf(buf,
sizeof(buf),
"%s",
agnameof(v));
120 fprintf (stderr,
"digraph A {\n");
122 fprintf (stderr,
" subgraph {rank=same ");
123 for (i = 0; i <
GD_rank(g)[r].n; i++) {
126 fprintf (stderr,
" -> %s", nname(v));
128 fprintf (stderr,
"%s", nname(v));
130 if (i > 1) fprintf (stderr,
" [style=invis]}\n");
131 else fprintf (stderr,
" }\n");
134 for (i = 0; i <
GD_rank(g)[r].n; 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)));
142 fprintf (stderr,
"}\n");
144static void dumpr (
graph_t* g,
int edges)
151 fprintf (stderr,
"[%d] ", r);
152 for (i = 0; i <
GD_rank(g)[r].n; i++) {
156 fprintf (stderr,
"\n");
158 if (edges == 0)
return;
160 for (i = 0; i <
GD_rank(g)[r].n; 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)));
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)))
195#define isBackedge(e) (ND_idx(aghead(e)) > ND_idx(agtail(e)))
203 if (
agdegree(g,n,1,0) == 0)
return n;
218 for (e =
agfstout(g, n); e; e = nxte) {
255 bool haveBackedge =
false;
273 if (!haveBackedge)
return;
275 sg =
agsubg(g,
"comp", 1);
281 if (
getComp(g, n, sg, indices)) {
286 for (i = 0; i < sz; i++) {
288 rk->
v[indices[i]] = arr[i];
319 for (j = 0; j < rk->
n; j++) {
373 ints_t scratch = {0};
376 for (nc = 0, comp = 0; comp <
GD_comp(g).size; comp++) {
378 const int64_t mc =
mincross(g, 0, &scratch);
405 const int64_t mc =
mincross(g, 2, &scratch);
437#define ELT(M,i,j) (M->data[((i)*M->ncols)+(j)])
467 for (i = ne = 0; (e =
ND_out(n).list[i]); i++)
471 for (i = ne = 0; (e =
ND_in(n).list[i]); i++)
480 qsort(sortlist, ne,
sizeof(sortlist[0]),
edgeidcmpf);
481 for (ne = 1; (f = sortlist[ne]); ne++) {
482 e = sortlist[ne - 1];
511 const char *ordering;
515 if (
streq(ordering,
"out"))
517 else if (
streq(ordering,
"in"))
519 else if (ordering[0])
520 agerrorf(
"ordering '%s' not recognized for node '%s'.\n", ordering,
agnameof(n));
539 if (
streq(ordering,
"out"))
541 else if (
streq(ordering,
"in"))
543 else if (ordering[0])
544 agerrorf(
"ordering '%s' not recognized.\n", ordering);
568 int64_t nc =
mincross(g, 2, scratch);
616 for (e2 =
ND_in(w).list; *e2; e2++) {
621 for (e1 =
ND_in(v).list; *e1; e1++) {
633 int inv,
cross = 0, t;
635 for (e2 =
ND_out(w).list; *e2; e2++) {
639 for (e1 =
ND_out(v).list; *e1; e1++) {
667 GD_rank(g)[r].candidate =
false;
668 for (i = 0; i <
GD_rank(g)[r].n - 1; i++) {
684 if (c1 < c0 || (c0 > 0 && reverse && c1 == c0)) {
688 GD_rank(g)[r].candidate =
true;
692 GD_rank(g)[r - 1].candidate =
true;
696 GD_rank(g)[r + 1].candidate =
true;
708 GD_rank(g)[r].candidate =
true;
717 }
while (
delta >= 1);
721 const int endpass = 2;
722 int maxthispass = 0, iter, trying, pass;
723 int64_t cur_cross, best_cross;
726 cur_cross = best_cross =
ncross(scratch);
729 cur_cross = best_cross = INT64_MAX;
730 for (pass = startpass; pass <= endpass; pass++) {
741 if ((cur_cross =
ncross(scratch)) <= best_cross) {
743 best_cross = cur_cross;
747 if (cur_cross > best_cross)
749 cur_cross = best_cross;
752 for (iter = 0; iter < maxthispass; iter++) {
755 "mincross: pass %d iter %d trying %d cur_cross %" PRId64
" best_cross %"
757 pass, iter, trying, cur_cross, best_cross);
763 if ((cur_cross =
ncross(scratch)) <= best_cross) {
767 best_cross = cur_cross;
773 if (cur_cross > best_cross)
775 if (best_cross > 0) {
777 best_cross =
ncross(scratch);
789 for (i = 0; i <
GD_rank(g)[r].n; i++) {
806 for (i = 0; i <
GD_rank(g)[r].n; i++) {
821 for (
size_t c = 0; c <
GD_comp(g).size; c++) {
850 for (i = 0; i <
GD_rank(g)[r].n; i++) {
855 "merge2: graph %s, rank %d has only %d < %d nodes\n",
884 for (i = 0; i <
GD_rank(g)[r].n; i++) {
900 fprintf(stderr,
"mincross %s: %" PRId64
" crossings, %.2f secs.\n",
982 node_in_root_vlist(v);
1019 memset (rnks, 0,
sizeof(
int)*rnks_sz);
1050 int *rnks =
gv_calloc(rnks_sz,
sizeof(
int));
1149 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1161 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1189 for (r = low + 1; r < high; r++)
1208 agerrorf(
"install_in_rank, line %d: %s %s rank %d i = %d an = 0\n",
1228 agerrorf(
"install_in_rank, line %d: ND_order(%s) [%d] > GD_rank(Root)[%d].an [%d]\n",
1233 agerrorf(
"install_in_rank, line %d: rank %d not in rank range [%d,%d]\n",
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",
1254 node_queue_t q = {0};
1262 for (i = 0; (e =
ND_out(n).list[i]); i++)
1264 for (i = 0; (e =
ND_in(n).list[i]); i++)
1273 const bool walkbackwards = g !=
agroot(g);
1276 if (walkbackwards) {
1284 otheredges = pass == 0 ?
ND_in(n).list :
ND_out(n).list;
1285 if (otheredges[0] !=
NULL)
1289 node_queue_push_back(&q, n);
1290 while (!node_queue_is_empty(&q)) {
1291 node_t *n0 = node_queue_pop_front(&q);
1294 node_queue_free(&q);
1301 node_queue_free(&q);
1308 assert(node_queue_is_empty(&q));
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]);
1322 node_queue_free(&q);
1330 for (
size_t i = 0; i <
ND_out(n0).size; i++) {
1334 node_queue_push_back(q,
aghead(e));
1338 for (
size_t i = 0; i <
ND_in(n0).size; i++) {
1339 e =
ND_in(n0).list[i];
1342 node_queue_push_back(q,
agtail(e));
1376 nodes_append(list, v);
1381 int i, r, local_in_cnt, local_out_cnt, base_order;
1383 nodes_t temprank = {0};
1389 if (
GD_rank(g)[r].n == 0)
continue;
1391 for (i = 0; i <
GD_rank(g)[r].n; i++)
1393 nodes_clear(&temprank);
1396 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1400 local_in_cnt = local_out_cnt = 0;
1401 for (
size_t j = 0; j <
ND_flat_in(v).size; j++) {
1405 for (
size_t j = 0; j <
ND_flat_out(v).size; j++) {
1409 if ((local_in_cnt == 0) && (local_out_cnt == 0))
1410 nodes_append(&temprank, v);
1412 if (!
MARK(v) && local_in_cnt == 0) {
1418 if (nodes_size(&temprank) > 0) {
1420 nodes_reverse(&temprank);
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);
1428 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1431 for (
size_t j = 0; (e =
ND_flat_out(v).list[j]); j++) {
1447 nodes_free(&temprank);
1452 int changed = 0, nelt;
1456 for (nelt =
GD_rank(g)[r].n - 1; nelt >= 0; nelt--) {
1460 while (lp < ep &&
ND_mval(*lp) < 0)
1465 bool sawclust =
false;
1466 bool muststay =
false;
1467 for (rp = lp + 1; rp < ep; rp++) {
1482 const double p1 =
ND_mval(*lp);
1483 const double p2 =
ND_mval(*rp);
1484 if (p1 > p2 || (p1 >= p2 && reverse)) {
1491 if (!hasfixed && !reverse)
1504 int r, other, first,
last, dir;
1506 bool reverse = pass % 4 < 2;
1508 if (pass % 2 == 0) {
1522 for (r = first; r !=
last + dir; r += dir) {
1524 bool hasfixed =
medians(g, r, other);
1525 reorder(g, r, reverse, hasfixed);
1535 bool is_out = dir > 0;
1536 for (i = 0; (e = l.
list[i]); i++) {
1538 for (j = i + 1; (f = l.
list[j]); j++) {
1543 for (j = i + 1; (f = l.
list[j]); j++) {
1553 int top, bot, max, i, k;
1566 for (i = 0; (e =
ND_out(rtop[
top]).list[i]); i++) {
1568 cross += ints_size(Count) <= (size_t)k
1573 for (i = 0; (e =
ND_out(rtop[
top]).list[i]); i++) {
1577 const size_t inv_z = (size_t)inv;
1578 if (ints_size(Count) <= inv_z) {
1579 ints_resize(Count, inv_z + 1, 0);
1581 ints_set(Count, inv_z, ints_get(Count, inv_z) +
ED_xpenalty(e));
1589 for (bot = 0; bot <
GD_rank(g)[r + 1].n; bot++) {
1598 assert(scratch !=
NULL);
1605 count +=
GD_rank(g)[r].cache_nc;
1607 const int64_t nc =
GD_rank(g)[r].cache_nc =
rcross(g, r, scratch);
1646 for (i = 1; (e = fl[i]); i++)
1656 for (i = 1; (e = fl[i]); i++)
1667#define VAL(node,port) (MC_SCALE * ND_order(node) + (port).order)
1671 int i, j0, lspan, rspan, *list;
1674 bool hasfixed =
false;
1678 for (i = 0; i <
GD_rank(g)[r0].n; i++) {
1682 for (j0 = 0; (e =
ND_out(n).list[j0]); j0++) {
1686 for (j0 = 0; (e =
ND_in(n).list[j0]); j0++) {
1698 ND_mval(n) = (list[0] + list[1]) / 2;
1708 rspan = list[j - 1] - list[
rm];
1709 lspan = list[lm] - list[0];
1713 double w = list[lm] * (double)rspan + list[
rm] * (
double)lspan;
1714 ND_mval(n) = w / (lspan + rspan);
1719 for (i = 0; i <
GD_rank(g)[r0].n; i++) {
1721 if ((
ND_out(n).size == 0) && (
ND_in(n).size == 0))
1732#pragma GCC diagnostic push
1733#pragma GCC diagnostic ignored "-Wcast-qual"
1738#pragma GCC diagnostic pop
1754#pragma GCC diagnostic push
1755#pragma GCC diagnostic ignored "-Wcast-qual"
1760#pragma GCC diagnostic pop
1774#define VIRTUALNODE 2
1805 agerrorf(
"overflow when calculating virtual weight of edge\n");
1813void check_rs(
graph_t * g,
int null_ok)
1818 fprintf(stderr,
"\n\n%s:\n",
agnameof(g));
1820 fprintf(stderr,
"%d: ", r);
1822 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1825 fprintf(stderr,
"NULL\t");
1835 fprintf(stderr,
"\n");
1839void check_order(
void)
1847 for (i = 0; (v =
GD_rank(g)[r].v[i]); i++) {
1864 p =
agget(g,
"mclimit");
1865 if (p && (f = atof(p)) > 0.0) {
1897 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1912void node_in_root_vlist(
node_t * n)
static agxbuf last
last message
static void agxbfree(agxbuf *xb)
free any malloced resources
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
static WUR char * agxbuse(agxbuf *xb)
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
abstract graph C library, Cgraph API
#define exchange(h, i, j)
bool mapbool(const char *p)
char * late_string(void *obj, attrsym_t *attr, char *defaultValue)
void decompose(graph_t *g, int pass)
Agraph_t * dot_root(void *p)
bool is_cluster(Agraph_t *)
void flat_edge(Agraph_t *, Agedge_t *)
void merge_oneway(Agedge_t *, Agedge_t *)
Agedge_t * new_virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Agedge_t * find_flat_edge(Agnode_t *, Agnode_t *)
void delete_flat_edge(Agedge_t *)
static NORETURN void graphviz_exit(int status)
static int cnt(Dict_t *d, Dtlink_t **set)
int agnedges(Agraph_t *g)
int agdegree(Agraph_t *g, Agnode_t *n, int in, int out)
int agnnodes(Agraph_t *g)
char * agget(void *obj, char *name)
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
int agdeledge(Agraph_t *g, Agedge_t *arg_e)
Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
void agwarningf(const char *fmt,...)
void agerrorf(const char *fmt,...)
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
#define GD_has_flat_edges(g)
Agdesc_t Agstrictdirected
strict directed. A strict graph cannot have multi-edges or self-arcs.
Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
creates a new graph with the given name and kind
Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Agnode_t * agfstnode(Agraph_t *g)
Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
int agdelnode(Agraph_t *g, Agnode_t *arg_n)
removes a node from a graph or subgraph.
#define ND_weight_class(n)
char * agnameof(void *)
returns a string descriptor for the object.
int agcontains(Agraph_t *, void *obj)
returns non-zero if obj is a member of (sub)graph
Agraph_t * agroot(void *obj)
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
Agraph_t * agfstsubg(Agraph_t *g)
Agraph_t * agnxtsubg(Agraph_t *subg)
Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
static void indent(int ix)
Arithmetic helper functions.
static double cross(double *u, double *v)
static Agedge_t * top(edge_stack_t *sp)
int install_cluster(graph_t *g, node_t *n, int pass, node_queue_t *q)
int expand_cluster(graph_t *subg)
void mark_lowclusters(Agraph_t *root)
#define DEFINE_LIST(name, type)
#define neighbor(t, i, edim, elist)
static int betweenclust(edge_t *e)
int build_ranks(graph_t *g, int pass, ints_t *scratch)
static void free_matrix(adjmatrix_t *p)
static bool flat_mval(node_t *n)
static int64_t mincross(graph_t *g, int startpass, ints_t *scratch)
static bool inside_cluster(graph_t *g, node_t *v)
static int64_t rcross(graph_t *g, int r, ints_t *Count)
static void init_mccomp(graph_t *g, size_t c)
static void mincross_step(graph_t *g, int pass)
static int topsort(Agraph_t *g, Agraph_t *sg, Agnode_t **arr)
static bool medians(graph_t *g, int r0, int r1)
static void reorder(graph_t *g, int r, bool reverse, bool hasfixed)
static int edgeidcmpf(const void *, const void *)
static void flat_breakcycles(graph_t *g)
static void cleanup2(graph_t *g, int64_t nc)
static bool is_a_normal_node_of(graph_t *g, node_t *v)
static void save_best(graph_t *g)
static void init_mincross(graph_t *g)
static int64_t transpose_step(graph_t *g, int r, bool reverse)
static void fixLabelOrder(graph_t *g, rank_t *rk)
void virtual_weight(edge_t *e)
static void merge2(graph_t *g)
static node_t * furthestnode(graph_t *g, node_t *v, int dir)
static int out_cross(node_t *v, node_t *w)
static int ordercmpf(const void *, const void *)
void enqueue_neighbors(node_queue_t *q, node_t *n0, int pass)
static void do_ordering(graph_t *g, bool outflag)
void checkLabelOrder(graph_t *g)
static int64_t mincross_clust(graph_t *g, ints_t *scratch)
static const double Convergence
static adjmatrix_t * new_matrix(size_t i, size_t j)
static Agraph_t * realFillRanks(Agraph_t *g, int rnks[], int rnks_sz, Agraph_t *sg)
static Agnode_t * findSource(Agraph_t *g, Agraph_t *sg)
void rec_save_vlists(graph_t *g)
static void do_ordering_node(graph_t *g, node_t *n, bool outflag)
static int64_t in_cross(node_t *v, node_t *w)
static void flat_search(graph_t *g, node_t *v)
static int64_t ncross(ints_t *scratch)
static void ordered_edges(graph_t *g)
static void transpose(graph_t *g, bool reverse)
void rec_reset_vlists(graph_t *g)
static void merge_components(graph_t *g)
int dot_mincross(graph_t *g)
static void mincross_options(graph_t *g)
static int endpoint_class(node_t *n)
static int getComp(graph_t *g, node_t *n, graph_t *comp, int *indices)
static bool left2right(graph_t *g, node_t *v, node_t *w)
static int local_cross(elist l, int dir)
static void flat_reorder(graph_t *g)
static void flat_rev(Agraph_t *g, Agedge_t *e)
static void emptyComp(graph_t *sg)
static bool is_a_vnode_of_an_edge_of(graph_t *g, node_t *v)
static void fillRanks(Agraph_t *g)
static void do_ordering_for_nodes(graph_t *g)
static void postorder(graph_t *g, node_t *v, nodes_t *list, int r)
void allocate_ranks(graph_t *g)
static int table[NTYPES][NTYPES]
static void restore_best(graph_t *g)
static bool constraining_flat_edge(Agraph_t *g, Agedge_t *e)
static int nodeposcmpf(const void *, const void *)
void save_vlist(graph_t *g)
int install_in_rank(graph_t *g, node_t *n)
static bool streq(const char *a, const char *b)
are a and b equal?
Agrec_t * data
stores programmer-defined data, access with AGDATA
implementation of Agrec_t
#define elist_append(item, L)
#define alloc_elist(n, L)