41#define MARK(v) (ND_mark(v))
42#define saveorder(v) (ND_coord(v)).x
43#define flatindex(v) ((size_t)ND_low(v))
48static int edgeidcmpf(
const void *,
const void *);
64static int ordercmpf(
const void *,
const void *);
65static int ncross(ints_t *scratch);
73void check_rs(
graph_t * g,
int null_ok);
74void check_order(
void);
76void node_in_root_vlist(
node_t * n);
90#if defined(DEBUG) && DEBUG > 1
94 fprintf (stderr,
" ");
99static char* nname(
node_t* v)
101 static char buf[1000];
106 snprintf(buf,
sizeof(buf),
"v_%p", v);
108 snprintf(buf,
sizeof(buf),
"%s",
agnameof(v));
117 fprintf (stderr,
"digraph A {\n");
119 fprintf (stderr,
" subgraph {rank=same ");
120 for (i = 0; i <
GD_rank(g)[r].n; i++) {
123 fprintf (stderr,
" -> %s", nname(v));
125 fprintf (stderr,
"%s", nname(v));
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++) {
134 fprintf (stderr,
"%s -> ", nname(v));
135 fprintf (stderr,
"%s\n", nname(
aghead(e)));
139 fprintf (stderr,
"}\n");
141static void dumpr (
graph_t* g,
int edges)
148 fprintf (stderr,
"[%d] ", r);
149 for (i = 0; i <
GD_rank(g)[r].n; i++) {
153 fprintf (stderr,
"\n");
155 if (edges == 0)
return;
157 for (i = 0; i <
GD_rank(g)[r].n; i++) {
159 for (j = 0; (e =
ND_out(v).list[j]); j++) {
160 fprintf (stderr,
"%s -> ", nname(v));
161 fprintf (stderr,
"%s\n", nname(
aghead(e)));
174#define ND_x(n) (((info_t*)AGDATA(n))->x)
175#define ND_lo(n) (((info_t*)AGDATA(n))->lo)
176#define ND_hi(n) (((info_t*)AGDATA(n))->hi)
177#define ND_np(n) (((info_t*)AGDATA(n))->np)
178#define ND_idx(n) (ND_order(ND_np(n)))
192#define isBackedge(e) (ND_idx(aghead(e)) > ND_idx(agtail(e)))
200 if (
agdegree(g,n,1,0) == 0)
return n;
215 for (e =
agfstout(g, n); e; e = nxte) {
252 bool haveBackedge =
false;
270 if (!haveBackedge)
return;
272 sg =
agsubg(g,
"comp", 1);
278 if (
getComp(g, n, sg, indices)) {
283 for (i = 0; i < sz; i++) {
285 rk->
v[indices[i]] = arr[i];
316 for (j = 0; j < rk->
n; j++) {
373 ints_t scratch = {0};
376 for (nc = 0, comp = 0; comp <
GD_comp(g).size; comp++) {
421#define ELT(M,i,j) (M->data[((i)*M->ncols)+(j)])
451 for (i = ne = 0; (e =
ND_out(n).list[i]); i++)
455 for (i = ne = 0; (e =
ND_in(n).list[i]); i++)
464 qsort(sortlist, ne,
sizeof(sortlist[0]),
edgeidcmpf);
465 for (ne = 1; (f = sortlist[ne]); ne++) {
466 e = sortlist[ne - 1];
495 const char *ordering;
499 if (
streq(ordering,
"out"))
501 else if (
streq(ordering,
"in"))
503 else if (ordering[0])
504 agerrorf(
"ordering '%s' not recognized for node '%s'.\n", ordering,
agnameof(n));
523 if (
streq(ordering,
"out"))
525 else if (
streq(ordering,
"in"))
527 else if (ordering[0])
528 agerrorf(
"ordering '%s' not recognized.\n", ordering);
590 int inv,
cross = 0, t;
592 for (e2 =
ND_in(w).list; *e2; e2++) {
597 for (e1 =
ND_in(v).list; *e1; e1++) {
609 int inv,
cross = 0, t;
611 for (e2 =
ND_out(w).list; *e2; e2++) {
615 for (e1 =
ND_out(v).list; *e1; e1++) {
644 GD_rank(g)[r].candidate =
false;
645 for (i = 0; i <
GD_rank(g)[r].n - 1; i++) {
660 if (c1 < c0 || (c0 > 0 && reverse && c1 == c0)) {
664 GD_rank(g)[r].candidate =
true;
668 GD_rank(g)[r - 1].candidate =
true;
672 GD_rank(g)[r + 1].candidate =
true;
684 GD_rank(g)[r].candidate =
true;
692 }
while (
delta >= 1);
696 const int endpass = 2;
697 int maxthispass = 0, iter, trying, pass;
698 int cur_cross, best_cross;
701 cur_cross = best_cross =
ncross(scratch);
704 cur_cross = best_cross = INT_MAX;
705 for (pass = startpass; pass <= endpass; pass++) {
714 if ((cur_cross =
ncross(scratch)) <= best_cross) {
716 best_cross = cur_cross;
720 if (cur_cross > best_cross)
722 cur_cross = best_cross;
725 for (iter = 0; iter < maxthispass; iter++) {
728 "mincross: pass %d iter %d trying %d cur_cross %d best_cross %d\n",
729 pass, iter, trying, cur_cross, best_cross);
735 if ((cur_cross =
ncross(scratch)) <= best_cross) {
739 best_cross = cur_cross;
745 if (cur_cross > best_cross)
747 if (best_cross > 0) {
749 best_cross =
ncross(scratch);
761 for (i = 0; i <
GD_rank(g)[r].n; i++) {
778 for (i = 0; i <
GD_rank(g)[r].n; i++) {
793 for (
size_t c = 0; c <
GD_comp(g).size; c++) {
822 for (i = 0; i <
GD_rank(g)[r].n; i++) {
827 "merge2: graph %s, rank %d has only %d < %d nodes\n",
857 for (i = 0; i <
GD_rank(g)[r].n; i++) {
873 fprintf(stderr,
"mincross %s: %d crossings, %.2f secs.\n",
959 node_in_root_vlist(v);
996 memset (rnks, 0,
sizeof(
int)*rnks_sz);
1027 int *rnks =
gv_calloc(rnks_sz,
sizeof(
int));
1126 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1138 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1168 for (r = low + 1; r < high; r++)
1188 agerrorf(
"install_in_rank, line %d: %s %s rank %d i = %d an = 0\n",
1208 agerrorf(
"install_in_rank, line %d: ND_order(%s) [%d] > GD_rank(Root)[%d].an [%d]\n",
1213 agerrorf(
"install_in_rank, line %d: rank %d not in rank range [%d,%d]\n",
1219 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",
1241 for (i = 0; (e =
ND_out(n).list[i]); i++)
1243 for (i = 0; (e =
ND_in(n).list[i]); i++)
1252 const bool walkbackwards = g !=
agroot(g);
1255 if (walkbackwards) {
1263 otheredges = pass == 0 ?
ND_in(n).list :
ND_out(n).list;
1264 if (otheredges[0] !=
NULL)
1284 int num_nodes_1 =
GD_rank(g)[i].n - 1;
1285 int half_num_nodes_1 = num_nodes_1 / 2;
1286 for (j = 0; j <= half_num_nodes_1; j++)
1287 exchange(vlist[j], vlist[num_nodes_1 - j]);
1300 for (
size_t i = 0; i <
ND_out(n0).size; i++) {
1308 for (
size_t i = 0; i <
ND_in(n0).size; i++) {
1309 e =
ND_in(n0).list[i];
1346 nodes_append(list, v);
1351 int i, r, local_in_cnt, local_out_cnt, base_order;
1353 nodes_t temprank = {0};
1359 if (
GD_rank(g)[r].n == 0)
continue;
1361 for (i = 0; i <
GD_rank(g)[r].n; i++)
1363 nodes_clear(&temprank);
1366 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1370 local_in_cnt = local_out_cnt = 0;
1371 for (
size_t j = 0; j <
ND_flat_in(v).size; j++) {
1375 for (
size_t j = 0; j <
ND_flat_out(v).size; j++) {
1379 if ((local_in_cnt == 0) && (local_out_cnt == 0))
1380 nodes_append(&temprank, v);
1382 if (!
MARK(v) && local_in_cnt == 0) {
1388 if (nodes_size(&temprank) > 0) {
1390 nodes_reverse(&temprank);
1392 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1393 v =
GD_rank(g)[r].v[i] = nodes_get(&temprank, (
size_t)i);
1398 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1401 for (
size_t j = 0; (e =
ND_flat_out(v).list[j]); j++) {
1417 nodes_free(&temprank);
1422 int changed = 0, nelt;
1426 for (nelt =
GD_rank(g)[r].n - 1; nelt >= 0; nelt--) {
1430 while (lp < ep &&
ND_mval(*lp) < 0)
1435 bool sawclust =
false;
1436 bool muststay =
false;
1437 for (rp = lp + 1; rp < ep; rp++) {
1452 const double p1 =
ND_mval(*lp);
1453 const double p2 =
ND_mval(*rp);
1454 if (p1 > p2 || (p1 >= p2 && reverse)) {
1461 if (!hasfixed && !reverse)
1474 int r, other, first,
last, dir;
1476 bool reverse = pass % 4 < 2;
1478 if (pass % 2 == 0) {
1492 for (r = first; r !=
last + dir; r += dir) {
1494 bool hasfixed =
medians(g, r, other);
1495 reorder(g, r, reverse, hasfixed);
1505 bool is_out = dir > 0;
1506 for (i = 0; (e = l.
list[i]); i++) {
1508 for (j = i + 1; (f = l.
list[j]); j++) {
1513 for (j = i + 1; (f = l.
list[j]); j++) {
1536 for (i = 0; (e =
ND_out(rtop[
top]).list[i]); i++) {
1538 cross += ints_size(Count) <= (size_t)k
1543 for (i = 0; (e =
ND_out(rtop[
top]).list[i]); i++) {
1547 const size_t inv_z = (size_t)inv;
1548 if (ints_size(Count) <= inv_z) {
1549 ints_resize(Count, inv_z + 1, 0);
1551 ints_set(Count, inv_z, ints_get(Count, inv_z) +
ED_xpenalty(e));
1559 for (bot = 0; bot <
GD_rank(g)[r + 1].n; bot++) {
1568 assert(scratch !=
NULL);
1575 count +=
GD_rank(g)[r].cache_nc;
1616 for (i = 1; (e = fl[i]); i++)
1626 for (i = 1; (e = fl[i]); i++)
1637#define VAL(node,port) (MC_SCALE * ND_order(node) + (port).order)
1641 int i, j0, lspan, rspan, *list;
1644 bool hasfixed =
false;
1648 for (i = 0; i <
GD_rank(g)[r0].n; i++) {
1652 for (j0 = 0; (e =
ND_out(n).list[j0]); j0++) {
1656 for (j0 = 0; (e =
ND_in(n).list[j0]); j0++) {
1668 ND_mval(n) = (list[0] + list[1]) / 2;
1678 rspan = list[j - 1] - list[
rm];
1679 lspan = list[lm] - list[0];
1683 double w = list[lm] * (double)rspan + list[
rm] * (
double)lspan;
1684 ND_mval(n) = w / (lspan + rspan);
1689 for (i = 0; i <
GD_rank(g)[r0].n; i++) {
1691 if ((
ND_out(n).size == 0) && (
ND_in(n).size == 0))
1702#pragma GCC diagnostic push
1703#pragma GCC diagnostic ignored "-Wcast-qual"
1708#pragma GCC diagnostic pop
1724#pragma GCC diagnostic push
1725#pragma GCC diagnostic ignored "-Wcast-qual"
1730#pragma GCC diagnostic pop
1744#define VIRTUALNODE 2
1775 agerrorf(
"overflow when calculating virtual weight of edge\n");
1783void check_rs(
graph_t * g,
int null_ok)
1788 fprintf(stderr,
"\n\n%s:\n",
agnameof(g));
1790 fprintf(stderr,
"%d: ", r);
1792 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1795 fprintf(stderr,
"NULL\t");
1805 fprintf(stderr,
"\n");
1809void check_order(
void)
1817 for (i = 0; (v =
GD_rank(g)[r].v[i]); i++) {
1834 p =
agget(g,
"mclimit");
1835 if (p && (f = atof(p)) > 0.0) {
1867 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1882void 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 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(gv_stack_t *sp)
void install_cluster(graph_t *g, node_t *n, int pass, queue_t *q)
void expand_cluster(graph_t *subg)
void mark_lowclusters(Agraph_t *root)
#define DEFINE_LIST(name, type)
#define neighbor(t, i, edim, elist)
static int rcross(graph_t *g, int r, ints_t *Count)
static int betweenclust(edge_t *e)
static int mincross(graph_t *g, int startpass, ints_t *scratch)
static void free_matrix(adjmatrix_t *p)
static bool flat_mval(node_t *n)
static int in_cross(node_t *v, node_t *w)
static bool inside_cluster(graph_t *g, node_t *v)
static int mincross_clust(graph_t *g, ints_t *scratch)
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)
void build_ranks(graph_t *g, int pass, ints_t *scratch)
static void reorder(graph_t *g, int r, bool reverse, bool hasfixed)
static int edgeidcmpf(const void *, const void *)
static int ncross(ints_t *scratch)
static void flat_breakcycles(graph_t *g)
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 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 *)
static void do_ordering(graph_t *g, bool outflag)
void checkLabelOrder(graph_t *g)
static const double Convergence
void install_in_rank(graph_t *g, node_t *n)
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 dot_mincross(graph_t *g)
void rec_save_vlists(graph_t *g)
static void do_ordering_node(graph_t *g, node_t *n, bool outflag)
static void flat_search(graph_t *g, node_t *v)
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)
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)
void enqueue_neighbors(queue_t *q, node_t *n0, int pass)
static void flat_rev(Agraph_t *g, Agedge_t *e)
static int transpose_step(graph_t *g, int r, bool reverse)
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 *)
static void cleanup2(graph_t *g, int nc)
void save_vlist(graph_t *g)
generic first-in-first-out buffer (queue)
static void queue_free(queue_t *q)
static void queue_push(queue_t *q, void *item)
static void * queue_pop(queue_t *q)
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)