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,
" ");
103static void nname(
node_t *v, FILE *stream) {
108 fprintf(stream,
"v_%p", v);
118 fprintf (stderr,
"digraph A {\n");
120 fprintf (stderr,
" subgraph {rank=same ");
121 for (i = 0; i <
GD_rank(g)[r].n; i++) {
124 fputs(
" -> ", stderr);
127 if (i > 1) fprintf (stderr,
" [style=invis]}\n");
128 else fprintf (stderr,
" }\n");
131 for (i = 0; i <
GD_rank(g)[r].n; i++) {
133 for (j = 0; (e =
ND_out(v).list[j]); j++) {
135 fputs(
" -> ", stderr);
141 fprintf (stderr,
"}\n");
143static void dumpr (
graph_t* g,
int edges)
150 fprintf (stderr,
"[%d] ", r);
151 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++) {
164 fputs(
" -> ", stderr);
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)))
197#define isBackedge(e) (ND_idx(aghead(e)) > ND_idx(agtail(e)))
205 if (
agdegree(g,n,1,0) == 0)
return n;
220 for (e =
agfstout(g, n); e; e = nxte) {
257 bool haveBackedge =
false;
275 if (!haveBackedge)
return;
277 sg =
agsubg(g,
"comp", 1);
283 if (
getComp(g, n, sg, indices)) {
288 for (i = 0; i < sz; i++) {
290 rk->
v[indices[i]] = arr[i];
320 for (j = 0; j < rk->
n; j++) {
372 ints_t scratch = {0};
375 for (nc = 0, comp = 0; comp <
GD_comp(g).size; comp++) {
377 const int64_t mc =
mincross(g, 0, &scratch);
404 const int64_t mc =
mincross(g, 2, &scratch);
436#define ELT(M,i,j) (M->data[((i)*M->ncols)+(j)])
466 for (i = ne = 0; (e =
ND_out(n).list[i]); i++)
470 for (i = ne = 0; (e =
ND_in(n).list[i]); i++)
479 qsort(sortlist, ne,
sizeof(sortlist[0]),
edgeidcmpf);
480 for (ne = 1; (f = sortlist[ne]); ne++) {
481 e = sortlist[ne - 1];
510 const char *ordering;
514 if (
streq(ordering,
"out"))
516 else if (
streq(ordering,
"in"))
518 else if (ordering[0])
519 agerrorf(
"ordering '%s' not recognized for node '%s'.\n", ordering,
agnameof(n));
538 if (
streq(ordering,
"out"))
540 else if (
streq(ordering,
"in"))
542 else if (ordering[0])
543 agerrorf(
"ordering '%s' not recognized.\n", ordering);
567 int64_t nc =
mincross(g, 2, scratch);
615 for (e2 =
ND_in(w).list; *e2; e2++) {
620 for (e1 =
ND_in(v).list; *e1; e1++) {
632 int inv,
cross = 0, t;
634 for (e2 =
ND_out(w).list; *e2; e2++) {
638 for (e1 =
ND_out(v).list; *e1; e1++) {
666 GD_rank(g)[r].candidate =
false;
667 for (i = 0; i <
GD_rank(g)[r].n - 1; i++) {
683 if (c1 < c0 || (c0 > 0 && reverse && c1 == c0)) {
687 GD_rank(g)[r].candidate =
true;
691 GD_rank(g)[r - 1].candidate =
true;
695 GD_rank(g)[r + 1].candidate =
true;
707 GD_rank(g)[r].candidate =
true;
716 }
while (
delta >= 1);
720 const int endpass = 2;
721 int maxthispass = 0, iter, trying, pass;
722 int64_t cur_cross, best_cross;
725 cur_cross = best_cross =
ncross(scratch);
728 cur_cross = best_cross = INT64_MAX;
729 for (pass = startpass; pass <= endpass; pass++) {
740 if ((cur_cross =
ncross(scratch)) <= best_cross) {
742 best_cross = cur_cross;
746 if (cur_cross > best_cross)
748 cur_cross = best_cross;
751 for (iter = 0; iter < maxthispass; iter++) {
754 "mincross: pass %d iter %d trying %d cur_cross %" PRId64
" best_cross %"
756 pass, iter, trying, cur_cross, best_cross);
762 if ((cur_cross =
ncross(scratch)) <= best_cross) {
766 best_cross = cur_cross;
772 if (cur_cross > best_cross)
774 if (best_cross > 0) {
776 best_cross =
ncross(scratch);
788 for (i = 0; i <
GD_rank(g)[r].n; i++) {
805 for (i = 0; i <
GD_rank(g)[r].n; i++) {
820 for (
size_t c = 0; c <
GD_comp(g).size; c++) {
849 for (i = 0; i <
GD_rank(g)[r].n; i++) {
854 "merge2: graph %s, rank %d has only %d < %d nodes\n",
883 for (i = 0; i <
GD_rank(g)[r].n; i++) {
899 fprintf(stderr,
"mincross %s: %" PRId64
" crossings, %.2f secs.\n",
981 node_in_root_vlist(v);
1018 memset (rnks, 0,
sizeof(
int)*rnks_sz);
1049 int *rnks =
gv_calloc(rnks_sz,
sizeof(
int));
1148 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1160 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1188 for (r = low + 1; r < high; r++)
1207 agerrorf(
"install_in_rank, line %d: %s %s rank %d i = %d an = 0\n",
1227 agerrorf(
"install_in_rank, line %d: ND_order(%s) [%d] > GD_rank(Root)[%d].an [%d]\n",
1232 agerrorf(
"install_in_rank, line %d: rank %d not in rank range [%d,%d]\n",
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",
1253 node_queue_t q = {0};
1261 for (i = 0; (e =
ND_out(n).list[i]); i++)
1263 for (i = 0; (e =
ND_in(n).list[i]); i++)
1272 const bool walkbackwards = g !=
agroot(g);
1275 if (walkbackwards) {
1283 otheredges = pass == 0 ?
ND_in(n).list :
ND_out(n).list;
1284 if (otheredges[0] !=
NULL)
1288 node_queue_push_back(&q, n);
1289 while (!node_queue_is_empty(&q)) {
1290 node_t *n0 = node_queue_pop_front(&q);
1293 node_queue_free(&q);
1300 node_queue_free(&q);
1307 assert(node_queue_is_empty(&q));
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]);
1321 node_queue_free(&q);
1329 for (
size_t i = 0; i <
ND_out(n0).size; i++) {
1333 node_queue_push_back(q,
aghead(e));
1337 for (
size_t i = 0; i <
ND_in(n0).size; i++) {
1338 e =
ND_in(n0).list[i];
1341 node_queue_push_back(q,
agtail(e));
1375 nodes_append(list, v);
1380 int i, r, local_in_cnt, local_out_cnt, base_order;
1382 nodes_t temprank = {0};
1388 if (
GD_rank(g)[r].n == 0)
continue;
1390 for (i = 0; i <
GD_rank(g)[r].n; i++)
1392 nodes_clear(&temprank);
1395 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1399 local_in_cnt = local_out_cnt = 0;
1400 for (
size_t j = 0; j <
ND_flat_in(v).size; j++) {
1404 for (
size_t j = 0; j <
ND_flat_out(v).size; j++) {
1408 if ((local_in_cnt == 0) && (local_out_cnt == 0))
1409 nodes_append(&temprank, v);
1411 if (!
MARK(v) && local_in_cnt == 0) {
1417 if (nodes_size(&temprank) > 0) {
1419 nodes_reverse(&temprank);
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);
1427 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1430 for (
size_t j = 0; (e =
ND_flat_out(v).list[j]); j++) {
1446 nodes_free(&temprank);
1451 int changed = 0, nelt;
1455 for (nelt =
GD_rank(g)[r].n - 1; nelt >= 0; nelt--) {
1459 while (lp < ep &&
ND_mval(*lp) < 0)
1464 bool sawclust =
false;
1465 bool muststay =
false;
1466 for (rp = lp + 1; rp < ep; rp++) {
1481 const double p1 =
ND_mval(*lp);
1482 const double p2 =
ND_mval(*rp);
1483 if (p1 > p2 || (p1 >= p2 && reverse)) {
1490 if (!hasfixed && !reverse)
1503 int r, other, first,
last, dir;
1505 bool reverse = pass % 4 < 2;
1507 if (pass % 2 == 0) {
1521 for (r = first; r !=
last + dir; r += dir) {
1523 bool hasfixed =
medians(g, r, other);
1524 reorder(g, r, reverse, hasfixed);
1534 bool is_out = dir > 0;
1535 for (i = 0; (e = l.
list[i]); i++) {
1537 for (j = i + 1; (f = l.
list[j]); j++) {
1542 for (j = i + 1; (f = l.
list[j]); j++) {
1552 int top, bot, max, i, k;
1565 for (i = 0; (e =
ND_out(rtop[
top]).list[i]); i++) {
1567 cross += ints_size(Count) <= (size_t)k
1572 for (i = 0; (e =
ND_out(rtop[
top]).list[i]); i++) {
1576 const size_t inv_z = (size_t)inv;
1577 if (ints_size(Count) <= inv_z) {
1578 ints_resize(Count, inv_z + 1, 0);
1580 ints_set(Count, inv_z, ints_get(Count, inv_z) +
ED_xpenalty(e));
1588 for (bot = 0; bot <
GD_rank(g)[r + 1].n; bot++) {
1597 assert(scratch !=
NULL);
1604 count +=
GD_rank(g)[r].cache_nc;
1606 const int64_t nc =
GD_rank(g)[r].cache_nc =
rcross(g, r, scratch);
1645 for (i = 1; (e = fl[i]); i++)
1655 for (i = 1; (e = fl[i]); i++)
1666#define VAL(node,port) (MC_SCALE * ND_order(node) + (port).order)
1670 int i, j0, lspan, rspan, *list;
1673 bool hasfixed =
false;
1677 for (i = 0; i <
GD_rank(g)[r0].n; i++) {
1681 for (j0 = 0; (e =
ND_out(n).list[j0]); j0++) {
1685 for (j0 = 0; (e =
ND_in(n).list[j0]); j0++) {
1697 ND_mval(n) = (list[0] + list[1]) / 2;
1707 rspan = list[j - 1] - list[
rm];
1708 lspan = list[lm] - list[0];
1712 double w = list[lm] * (double)rspan + list[
rm] * (
double)lspan;
1713 ND_mval(n) = w / (lspan + rspan);
1718 for (i = 0; i <
GD_rank(g)[r0].n; i++) {
1720 if ((
ND_out(n).size == 0) && (
ND_in(n).size == 0))
1731#pragma GCC diagnostic push
1732#pragma GCC diagnostic ignored "-Wcast-qual"
1737#pragma GCC diagnostic pop
1753#pragma GCC diagnostic push
1754#pragma GCC diagnostic ignored "-Wcast-qual"
1759#pragma GCC diagnostic pop
1773#define VIRTUALNODE 2
1804 agerrorf(
"overflow when calculating virtual weight of edge\n");
1812void check_rs(
graph_t * g,
int null_ok)
1817 fprintf(stderr,
"\n\n%s:\n",
agnameof(g));
1819 fprintf(stderr,
"%d: ", r);
1821 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1824 fprintf(stderr,
"NULL\t");
1834 fprintf(stderr,
"\n");
1838void check_order(
void)
1846 for (i = 0; (v =
GD_rank(g)[r].v[i]); i++) {
1863 p =
agget(g,
"mclimit");
1864 if (p && (f = atof(p)) > 0.0) {
1896 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1911void node_in_root_vlist(
node_t * n)
static agxbuf last
last message
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 int scale_clamp(int original, double scale)
scale up or down a non-negative integer, clamping to [0, INT_MAX]
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)