53 const size_t index =
row * me->
ncols + col;
54 const size_t byte_index = index / 8;
55 const size_t bit_index = index % 8;
60 return (me->
data[byte_index] >> bit_index) & 1;
72 const size_t index =
row * me->
ncols + col;
73 const size_t byte_index = index / 8;
74 const size_t bit_index = index % 8;
81 me->
data[byte_index] |= (uint8_t)(UINT8_C(1) << bit_index);
85#define MARK(v) (ND_mark(v))
86#define saveorder(v) (ND_coord(v)).x
87#define flatindex(v) ((size_t)ND_low(v))
92static int edgeidcmpf(
const void *,
const void *);
110static int ordercmpf(
const void *,
const void *);
111static int64_t
ncross(
void);
113void check_rs(
graph_t * g,
int null_ok);
114void check_order(
void);
116void node_in_root_vlist(
node_t * n);
130#if defined(DEBUG) && DEBUG > 1
134 fprintf (stderr,
" ");
140static void nname(
node_t *v, FILE *stream) {
145 fprintf(stream,
"v_%p", v);
155 fprintf (stderr,
"digraph A {\n");
157 fprintf (stderr,
" subgraph {rank=same ");
158 for (i = 0; i <
GD_rank(g)[r].n; i++) {
161 fputs(
" -> ", stderr);
164 if (i > 1) fprintf (stderr,
" [style=invis]}\n");
165 else fprintf (stderr,
" }\n");
168 for (i = 0; i <
GD_rank(g)[r].n; i++) {
170 for (j = 0; (e =
ND_out(v).list[j]); j++) {
172 fputs(
" -> ", stderr);
178 fprintf (stderr,
"}\n");
180static void dumpr (
graph_t* g,
int edges)
187 fprintf (stderr,
"[%d] ", r);
188 for (i = 0; i <
GD_rank(g)[r].n; i++) {
193 fprintf (stderr,
"\n");
195 if (edges == 0)
return;
197 for (i = 0; i <
GD_rank(g)[r].n; i++) {
199 for (j = 0; (e =
ND_out(v).list[j]); j++) {
201 fputs(
" -> ", stderr);
216#define ND_x(n) (((info_t*)AGDATA(n))->x)
217#define ND_lo(n) (((info_t*)AGDATA(n))->lo)
218#define ND_hi(n) (((info_t*)AGDATA(n))->hi)
219#define ND_np(n) (((info_t*)AGDATA(n))->np)
220#define ND_idx(n) (ND_order(ND_np(n)))
234#define isBackedge(e) (ND_idx(aghead(e)) > ND_idx(agtail(e)))
242 if (
agdegree(g,n,1,0) == 0)
return n;
257 for (e =
agfstout(g, n); e; e = nxte) {
292 bool haveBackedge =
false;
310 if (!haveBackedge)
return;
312 sg =
agsubg(g,
"comp", 1);
318 if (
getComp(g, n, sg, indices)) {
323 for (i = 0; i < sz; i++) {
325 rk->
v[indices[i]] = arr[i];
354 for (j = 0; j < rk->
n; j++) {
406 for (nc = 0, comp = 0; comp <
GD_comp(g).size; comp++) {
490 for (i = ne = 0; (e =
ND_out(n).list[i]); i++)
494 for (i = ne = 0; (e =
ND_in(n).list[i]); i++)
503 qsort(sortlist, ne,
sizeof(sortlist[0]),
edgeidcmpf);
504 for (ne = 1; (f = sortlist[ne]); ne++) {
505 e = sortlist[ne - 1];
534 const char *ordering;
538 if (
streq(ordering,
"out"))
540 else if (
streq(ordering,
"in"))
542 else if (ordering[0])
543 agerrorf(
"ordering '%s' not recognized for node '%s'.\n", ordering,
agnameof(n));
561 if (
streq(ordering,
"out"))
563 else if (
streq(ordering,
"in"))
565 else if (ordering[0])
566 agerrorf(
"ordering '%s' not recognized.\n", ordering);
636 for (e2 =
ND_in(w).list; *e2; e2++) {
641 for (e1 =
ND_in(v).list; *e1; e1++) {
653 int inv,
cross = 0, t;
655 for (e2 =
ND_out(w).list; *e2; e2++) {
659 for (e1 =
ND_out(v).list; *e1; e1++) {
687 GD_rank(g)[r].candidate =
false;
688 for (i = 0; i <
GD_rank(g)[r].n - 1; i++) {
704 if (c1 < c0 || (c0 > 0 && reverse && c1 == c0)) {
708 GD_rank(g)[r].candidate =
true;
712 GD_rank(g)[r - 1].candidate =
true;
716 GD_rank(g)[r + 1].candidate =
true;
728 GD_rank(g)[r].candidate =
true;
737 }
while (
delta >= 1);
741 const int endpass = 2;
742 int maxthispass = 0, iter, trying, pass;
743 int64_t cur_cross, best_cross;
746 cur_cross = best_cross =
ncross();
749 cur_cross = best_cross = INT64_MAX;
750 for (pass = startpass; pass <= endpass; pass++) {
761 if ((cur_cross =
ncross()) <= best_cross) {
763 best_cross = cur_cross;
767 if (cur_cross > best_cross)
769 cur_cross = best_cross;
772 for (iter = 0; iter < maxthispass; iter++) {
775 "mincross: pass %d iter %d trying %d cur_cross %" PRId64
" best_cross %"
777 pass, iter, trying, cur_cross, best_cross);
783 if ((cur_cross =
ncross()) <= best_cross) {
787 best_cross = cur_cross;
793 if (cur_cross > best_cross)
795 if (best_cross > 0) {
809 for (i = 0; i <
GD_rank(g)[r].n; i++) {
826 for (i = 0; i <
GD_rank(g)[r].n; i++) {
841 for (
size_t c = 0; c <
GD_comp(g).size; c++) {
870 for (i = 0; i <
GD_rank(g)[r].n; i++) {
875 "merge2: graph %s, rank %d has only %d < %d nodes\n",
904 for (i = 0; i <
GD_rank(g)[r].n; i++) {
920 fprintf(stderr,
"mincross %s: %" PRId64
" crossings, %.2f secs.\n",
1002 node_in_root_vlist(v);
1166 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1178 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1205 for (r = low + 1; r < high; r++)
1224 agerrorf(
"install_in_rank, line %d: %s %s rank %d i = %d an = 0\n",
1244 agerrorf(
"install_in_rank, line %d: ND_order(%s) [%d] > GD_rank(Root)[%d].an [%d]\n",
1249 agerrorf(
"install_in_rank, line %d: rank %d not in rank range [%d,%d]\n",
1255 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",
1270 node_queue_t q = {0};
1278 for (i = 0; (e =
ND_out(n).list[i]); i++)
1280 for (i = 0; (e =
ND_in(n).list[i]); i++)
1289 const bool walkbackwards = g !=
agroot(g);
1292 if (walkbackwards) {
1300 otheredges = pass == 0 ?
ND_in(n).list :
ND_out(n).list;
1301 if (otheredges[0] !=
NULL)
1305 node_queue_push_back(&q, n);
1306 while (!node_queue_is_empty(&q)) {
1307 node_t *n0 = node_queue_pop_front(&q);
1310 node_queue_free(&q);
1317 node_queue_free(&q);
1324 assert(node_queue_is_empty(&q));
1329 int num_nodes_1 =
GD_rank(g)[i].n - 1;
1330 int half_num_nodes_1 = num_nodes_1 / 2;
1331 for (j = 0; j <= half_num_nodes_1; j++)
1332 exchange(vlist[j], vlist[num_nodes_1 - j]);
1338 node_queue_free(&q);
1346 for (
size_t i = 0; i <
ND_out(n0).size; i++) {
1350 node_queue_push_back(q,
aghead(e));
1354 for (
size_t i = 0; i <
ND_in(n0).size; i++) {
1355 e =
ND_in(n0).list[i];
1358 node_queue_push_back(q,
agtail(e));
1392 nodes_append(list, v);
1397 int i, r, local_in_cnt, local_out_cnt, base_order;
1399 nodes_t temprank = {0};
1405 if (
GD_rank(g)[r].n == 0)
continue;
1407 for (i = 0; i <
GD_rank(g)[r].n; i++)
1409 nodes_clear(&temprank);
1412 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1416 local_in_cnt = local_out_cnt = 0;
1417 for (
size_t j = 0; j <
ND_flat_in(v).size; j++) {
1421 for (
size_t j = 0; j <
ND_flat_out(v).size; j++) {
1425 if (local_in_cnt == 0 && local_out_cnt == 0)
1426 nodes_append(&temprank, v);
1428 if (!
MARK(v) && local_in_cnt == 0) {
1434 if (nodes_size(&temprank) > 0) {
1436 nodes_reverse(&temprank);
1438 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1439 v =
GD_rank(g)[r].v[i] = nodes_get(&temprank, (
size_t)i);
1444 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1447 for (
size_t j = 0; (e =
ND_flat_out(v).list[j]); j++) {
1463 nodes_free(&temprank);
1468 int changed = 0, nelt;
1472 for (nelt =
GD_rank(g)[r].n - 1; nelt >= 0; nelt--) {
1476 while (lp < ep &&
ND_mval(*lp) < 0)
1481 bool sawclust =
false;
1482 bool muststay =
false;
1483 for (rp = lp + 1; rp < ep; rp++) {
1498 const double p1 =
ND_mval(*lp);
1499 const double p2 =
ND_mval(*rp);
1500 if (p1 > p2 || (p1 >= p2 && reverse)) {
1507 if (!hasfixed && !reverse)
1520 int r, other, first,
last, dir;
1522 bool reverse = pass % 4 < 2;
1524 if (pass % 2 == 0) {
1538 for (r = first; r !=
last + dir; r += dir) {
1540 bool hasfixed =
medians(g, r, other);
1541 reorder(g, r, reverse, hasfixed);
1551 bool is_out = dir > 0;
1552 for (i = 0; (e = l.
list[i]); i++) {
1554 for (j = i + 1; (f = l.
list[j]); j++) {
1559 for (j = i + 1; (f = l.
list[j]); j++) {
1569 int top, bot, max, i, k;
1581 for (i = 0; (e =
ND_out(rtop[
top]).list[i]); i++) {
1586 for (i = 0; (e =
ND_out(rtop[
top]).list[i]); i++) {
1598 for (bot = 0; bot <
GD_rank(g)[r + 1].n; bot++) {
1614 count +=
GD_rank(g)[r].cache_nc;
1654 for (i = 1; (e = fl[i]); i++)
1664 for (i = 1; (e = fl[i]); i++)
1675#define VAL(node,port) (MC_SCALE * ND_order(node) + (port).order)
1679 int i, j0, lspan, rspan, *list;
1682 bool hasfixed =
false;
1686 for (i = 0; i <
GD_rank(g)[r0].n; i++) {
1690 for (j0 = 0; (e =
ND_out(n).list[j0]); j0++) {
1694 for (j0 = 0; (e =
ND_in(n).list[j0]); j0++) {
1706 ND_mval(n) = (list[0] + list[1]) / 2;
1716 rspan = list[j - 1] - list[
rm];
1717 lspan = list[lm] - list[0];
1721 double w = list[lm] * (double)rspan + list[
rm] * (
double)lspan;
1722 ND_mval(n) = w / (lspan + rspan);
1727 for (i = 0; i <
GD_rank(g)[r0].n; i++) {
1740#pragma GCC diagnostic push
1741#pragma GCC diagnostic ignored "-Wcast-qual"
1746#pragma GCC diagnostic pop
1762#pragma GCC diagnostic push
1763#pragma GCC diagnostic ignored "-Wcast-qual"
1768#pragma GCC diagnostic pop
1782#define VIRTUALNODE 2
1813 agerrorf(
"overflow when calculating virtual weight of edge\n");
1821void check_rs(
graph_t * g,
int null_ok)
1826 fprintf(stderr,
"\n\n%s:\n",
agnameof(g));
1828 fprintf(stderr,
"%d: ", r);
1830 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1833 fprintf(stderr,
"NULL\t");
1843 fprintf(stderr,
"\n");
1847void check_order(
void)
1855 for (i = 0; (v =
GD_rank(g)[r].v[i]); i++) {
1872 p =
agget(g,
"mclimit");
1873 if (p && (f = atof(p)) > 0.0) {
1905 for (i = 0; i <
GD_rank(g)[r].n; i++) {
1920void node_in_root_vlist(
node_t * n)
static agxbuf last
last message
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
API for compacted arrays of booleans.
static bitarray_t bitarray_new(size_t size_bits)
create an array of the given element length
static void bitarray_clear(bitarray_t *self)
clear all bits in a bit array
static bool bitarray_get(bitarray_t self, size_t index)
get the value of the given element
static void bitarray_set(bitarray_t *self, size_t index, bool value)
set or clear the value of the given element
static void bitarray_reset(bitarray_t *self)
free underlying resources and leave a bit array empty
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)
static void free_matrix(adjmatrix_t *p)
static bool flat_mval(node_t *n)
static bool inside_cluster(graph_t *g, node_t *v)
static int64_t mincross(graph_t *g, int startpass)
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 rcross(graph_t *g, int r)
static Agraph_t * realFillRanks(Agraph_t *g, bitarray_t *ranks, Agraph_t *sg)
static int64_t transpose_step(graph_t *g, int r, bool reverse)
static void fixLabelOrder(graph_t *g, rank_t *rk)
for each pair of nodes (labels), we add an edge
void virtual_weight(edge_t *e)
static void merge2(graph_t *g)
static int64_t mincross_clust(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)
static void matrix_set(adjmatrix_t *me, size_t row, size_t col)
void checkLabelOrder(graph_t *g)
static const double Convergence
int build_ranks(graph_t *g, int pass)
static adjmatrix_t * new_matrix(size_t i, size_t j)
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 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 int64_t ncross(void)
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 matrix_get(adjmatrix_t *me, size_t row, size_t col)
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
uint8_t * data
bit-packed backing memory
size_t allocated
how many bytes have been allocated backing data?
#define elist_append(item, L)
#define alloc_elist(n, L)