44#define GRAPHTYPEMASK 192
79static int edgecmp(
const void *,
const void *);
81 unsigned,
unsigned,
int);
83 unsigned,
unsigned,
int);
143 const size_t sz = b->
size;
144 for (
size_t i = 0; i < sz / 2; ++i) {
153 const size_t sz =
s->size;
156 for (
size_t i = 0; i < sz / 2; ++i) {
161 for (
size_t i = 0; i < sz; ++i) {
237 edge_t *e, *e0, *e1, *ea, *eb, *le0, *le1;
248 agwarningf(
"edge labels with splines=curved not supported in dot - use "
285 for (j = 0; j <
GD_rank(g)[i].n; j++) {
298 for (
int k = 0; (e =
ND_out(n).list[k]); k++) {
305 for (
int k = 0; (e =
ND_flat_out(n).list[k]); k++) {
318 for (
int k = 0; (e =
ND_other(n).list[k]); k++) {
347 for (
unsigned l = 0; l <
LIST_SIZE(&edges);) {
348 const unsigned ind = l;
349 le0 = getmainedge((e0 =
LIST_GET(&edges, l++)));
361 if (le0 != (le1 = getmainedge((e1 =
LIST_GET(&edges, l)))))
388 for (
unsigned ii = 1; ii <
cnt; ii++)
406 sizey =
MIN(upy, dwny);
410 for (
unsigned b = 0; b <
cnt; b++) {
493 if (
ND_in(n).size == 0)
542static int edgecmp(
const void *p0,
const void *p1) {
547 edge_t *ea, *eb, *le0, *le1;
563 le0 = getmainedge(e0);
564 le1 = getmainedge(e1);
569 const int v0 = abs(rank_diff0);
570 const int v1 = abs(rank_diff1);
582 const double v0 = fabs(t0);
583 const double v1 = fabs(t1);
918#pragma GCC diagnostic push
919#pragma GCC diagnostic ignored "-Wcast-qual"
924#pragma GCC diagnostic pop
961 unsigned ind,
unsigned cnt,
int et,
966 double leftend, rightend, ctrx, ctry, miny, maxy;
968 double lminx = 0.0, lmaxx = 0.0;
972 for (
unsigned i = 0; i <
cnt; i++) {
973 earray[i] = edges[ind + i];
981 leftend = tp.
x +
ND_rw(tn);
982 rightend = hp.
x -
ND_lw(hn);
983 ctrx = (leftend + rightend) / 2.0;
999 uminx = ctrx -
ED_label(e)->dimen.x / 2.0;
1000 umaxx = ctrx +
ED_label(e)->dimen.x / 2.0;
1003 for (i = 1; i < n_lbls; i++) {
1007 lminx = ctrx -
ED_label(e)->dimen.x / 2.0;
1008 lmaxx = ctrx +
ED_label(e)->dimen.x / 2.0;
1025 ctry = miny +
ED_label(e)->dimen.y / 2.0;
1049 if (
ps ==
NULL || pn == 0) {
1062 for (; i <
cnt; i++) {
1066 lminx = (2 * leftend + rightend) / 3.0;
1067 lmaxx = (leftend + 2 * rightend) / 3.0;
1106 if (
ps ==
NULL || pn == 0) {
1119 unsigned cnt,
int et) {
1127 stepy =
cnt > 1 ?
ND_ht(tn) / (double)(
cnt - 1) : 0.;
1130 for (
unsigned i = 0; i <
cnt; i++) {
1174 double midx, midy, leftx, rightx;
1177 static atomic_flag warned;
1181 if (!atomic_flag_test_and_set(&warned)) {
1182 agwarningf(
"flat edge between adjacent nodes one of which has a record "
1183 "shape - replace records with HTML-like labels\n");
1189 unsigned labels = 0;
1191 for (
unsigned i = 0; i <
cnt; i++) {
1213 subg =
agsubg(auxg,
"xxx", 1);
1215 agset(subg,
"rank",
"source");
1223 for (
unsigned i = 0; i <
cnt; i++) {
1260 }
else if (n == auxh) {
1281 for (
unsigned i = 0; i <
cnt; i++) {
1289 if ((auxe == hvye) & !
ED_alg(auxe))
1297 for (
size_t j = 0; j < auxbz->
size;) {
1301 if (j >= auxbz->
size)
1356 bool ps_needs_free =
false;
1432 const size_t boxn =
sizeof(boxes) /
sizeof(boxes[0]);
1434 for (i = 0; i < tend.
boxn; i++)
1436 for (
size_t j = 0; j < boxn; j++)
1438 for (i = hend.
boxn - 1; i >= 0; i--)
1441 ps_needs_free =
true;
1457 edge_t **edges,
unsigned ind,
unsigned cnt,
1458 edge_t *e,
bool use_splines) {
1461 double stepx, stepy, vspace;
1476 stepy = vspace / (
cnt + 1);
1481 for (
unsigned i = 0; i <
cnt; i++) {
1489 boxes[boxn].
LL.
x = b.
LL.
x;
1490 boxes[boxn].
UR.
y = b.
LL.
y;
1491 boxes[boxn].
UR.
x = b.
UR.
x + (i + 1) * stepx;
1492 boxes[boxn].
LL.
y = b.
LL.
y - (i + 1) * stepy;
1495 boxes[boxn].
UR.
y = boxes[boxn - 1].
LL.
y;
1497 boxes[boxn].
LL.
y = boxes[boxn].
UR.
y - stepy;
1500 boxes[boxn].
UR.
x = b.
UR.
x;
1501 boxes[boxn].
UR.
y = b.
LL.
y;
1502 boxes[boxn].
LL.
x = b.
LL.
x - (i + 1) * stepx;
1503 boxes[boxn].
LL.
y = boxes[boxn - 1].
UR.
y;
1505 assert(boxn ==
sizeof(boxes) /
sizeof(boxes[0]));
1507 for (j = 0; j < tend.
boxn; j++)
1509 for (
size_t k = 0; k < boxn; k++)
1511 for (j = hend.
boxn - 1; j >= 0; j--)
1541 edge_t **edges,
unsigned ind,
unsigned cnt,
int et) {
1547 double stepx, stepy, vspace;
1560 for (
unsigned i = 1; i <
cnt; i++) {
1604 stepy = vspace / (
cnt + 1);
1609 for (
unsigned i = 0; i <
cnt; i++) {
1617 boxes[boxn].
LL.
x = b.
LL.
x;
1618 boxes[boxn].
LL.
y = b.
UR.
y;
1619 boxes[boxn].
UR.
x = b.
UR.
x + (i + 1) * stepx;
1620 boxes[boxn].
UR.
y = b.
UR.
y + (i + 1) * stepy;
1623 boxes[boxn].
LL.
y = boxes[boxn - 1].
UR.
y;
1625 boxes[boxn].
UR.
y = boxes[boxn].
LL.
y + stepy;
1628 boxes[boxn].
UR.
x = b.
UR.
x;
1629 boxes[boxn].
LL.
y = b.
UR.
y;
1630 boxes[boxn].
LL.
x = b.
LL.
x - (i + 1) * stepx;
1631 boxes[boxn].
UR.
y = boxes[boxn - 1].
LL.
y;
1633 assert(boxn ==
sizeof(boxes) /
sizeof(boxes[0]));
1635 for (j = 0; j < tend.
boxn; j++)
1637 for (
size_t k = 0; k < boxn; k++)
1639 for (j = hend.
boxn - 1; j >= 0; j--)
1661 return (p1.
y - p2.
y) * (p3.
x - p2.
x) - (p3.
y - p2.
y) * (p1.
x - p2.
x) > 0;
1685 double width, height;
1715 if (
leftOf(endp, startp, lp)) {
1716 lp.
x += width / 2.0;
1717 lp.
y -= height / 2.0;
1719 lp.
x -= width / 2.0;
1720 lp.
y += height / 2.0;
1743 edge_t **edges,
unsigned ind,
unsigned cnt,
1752 points_t pointfs = {0};
1753 points_t pointfs2 = {0};
1761 bool hackflag =
false;
1780 le = getmainedge(e);
1803 boxes_t boxes = {0};
1823 if (!smode || si > 0) {
1847 ps[3] =
ps[2] =
ps[pn - 1];
1859 for (
size_t i = 0; i < pn; i++) {
1882 b.
UR.
y = hend.boxes[hend.boxn - 1].UR.y;
1883 b.
LL.
y = hend.boxes[hend.boxn - 1].LL.y;
1886 hend.boxes[hend.boxn++] = b;
1901 ps[3] =
ps[2] =
ps[pn - 1];
1910 for (
size_t i = 0; i < pn; i++) {
1928 for (
size_t k = 1; k + 1 <
LIST_SIZE(&pointfs); k++)
1931 for (
size_t k = 0; k <
LIST_SIZE(&pointfs); k++)
1935 for (
unsigned j = 1; j <
cnt; j++) {
1941 for (
size_t k = 1; k + 1 <
LIST_SIZE(&pointfs); k++)
1944 for (
size_t k = 0; k <
LIST_SIZE(&pointfs); k++)
1958 const boxes_t *boxes) {
1959 edge_t *uleft, *uright, *lleft, *lright;
1961 uleft = uright =
NULL;
1971 lleft = lright =
NULL;
1981 for (
int i = 0; i < tendp->
boxn; i++)
1983 const size_t fb = P->
nbox + 1;
1984 const size_t lb = fb +
LIST_SIZE(boxes) - 3;
1985 for (
size_t i = 0; i <
LIST_SIZE(boxes); i++)
1987 for (
int i = hendp->
boxn - 1; i >= 0; i--)
2021 for (
size_t i = fb - 1; i < lb + 1; i++) {
2023 if ((i - fb) % 2 == 0) {
2024 if (bp1->
LL.
x >= bp1->
UR.
x) {
2025 double x = (bp1->
LL.
x + bp1->
UR.
x) / 2;
2031 double x = (bp1->
LL.
x + bp1->
UR.
x) / 2;
2037 for (
size_t i = 0; i + 1 < P->
nbox; i++) {
2039 if (i >= fb && i <= lb && (i - fb) % 2 == 0) {
2042 if (bp1->
UR.
x - MINW < bp2->LL.x)
2044 }
else if (i + 1 >= fb && i < lb && (i + 1 - fb) % 2 == 0) {
2047 if (bp1->
UR.
x - MINW < bp2->LL.x)
2145 for (i = 0; (f =
ND_in(
aghead(e)).list[i]); i++) {
2169#define REAL_CLUSTER(n) (ND_clust(n) == g ? NULL : ND_clust(n))
2187 if (cl && cl != tcl && cl != hcl)
2192 if (cl && cl != tcl && cl != hcl &&
cl_vninside(cl, adj))
2196 if (cl && cl != tcl && cl != hcl &&
cl_vninside(cl, adj))
2219 left_cl = right_cl =
NULL;
2277 for (i =
ND_order(vn) + dir; i >= 0 && i <
rank->n; i += dir) {
2304 if (
ND_out(n0).size == 1 && e1) {
2320 if (
ND_in(n0).size == 1 && e1) {
2321 e0 =
ND_in(n0).list[0];
2329 e0 =
ND_in(na).list[0];
2332 e1 =
ND_in(nb).list[0];
2339void showpath(
path *p) {
2342 fprintf(stderr,
"%%!PS\n");
2343 for (
size_t i = 0; i < p->
nbox; i++) {
2347 "newpath %.04f %.04f moveto %.04f %.04f lineto %.04f %.04f lineto "
2348 "%.04f %.04f lineto closepath stroke\n",
2349 LL.
x, LL.
y, UR.
x, LL.
y, UR.
x, UR.
y, LL.
x, UR.
y);
2351 fprintf(stderr,
"showpage\n");
int normalize(graph_t *g)
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)
void setEdgeType(graph_t *g, int defaultValue)
void updateBB(graph_t *g, textlabel_t *lp)
void dot_init_node_edge(graph_t *g)
void dot_cleanup(graph_t *g)
int dot_mincross(Agraph_t *)
void dot_sameports(Agraph_t *)
void dot_rank(Agraph_t *)
void dot_position(Agraph_t *)
static bool leftOf(pointf p1, pointf p2, pointf p3)
Return true if p3 is to left of ray p1->p2.
static edge_t * top_bound(edge_t *e, int side)
static void makeBottomFlatEnd(graph_t *g, const spline_info_t sp, path *P, node_t *n, edge_t *e, pathend_t *endp, bool isBegin)
static void make_flat_labeled_edge(graph_t *g, const spline_info_t sp, path *P, edge_t *e, int et)
static void recover_slack(edge_t *e, path *p)
static void swap_bezier(bezier *b)
static bool cl_vninside(graph_t *cl, node_t *n)
static Agraph_t * cl_bound(graph_t *g, node_t *n, node_t *adj)
static int make_flat_adj_edges(graph_t *g, edge_t **edges, unsigned ind, unsigned cnt, edge_t *e0, int et)
static edge_t * bot_bound(edge_t *e, int side)
int dot_splines(graph_t *g)
static edge_t * cloneEdge(graph_t *g, node_t *tn, node_t *hn, edge_t *orig)
static void setState(graph_t *auxg, attr_state_t *attr_state)
static void edge_normalize(graph_t *g)
static void makeSimpleFlatLabels(node_t *tn, node_t *hn, edge_t **edges, unsigned ind, unsigned cnt, int et, unsigned n_lbls)
static int makeLineEdge(graph_t *g, edge_t *fe, points_t *points, node_t **hp)
static int make_flat_edge(graph_t *g, const spline_info_t sp, path *P, edge_t **edges, unsigned ind, unsigned cnt, int et)
static bool swap_ends_p(edge_t *e)
int portcmp(port p0, port p1)
static bool spline_merge(node_t *n)
static void makeFlatEnd(graph_t *g, const spline_info_t sp, path *P, node_t *n, edge_t *e, pathend_t *endp, bool isBegin)
static void place_vnlabel(node_t *n)
static void setEdgeLabelPos(graph_t *g)
static void completeregularpath(path *P, edge_t *first, edge_t *last, pathend_t *tendp, pathend_t *hendp, const boxes_t *boxes)
static int edgecmp(const void *p0, const void *p1)
static graph_t * cloneGraph(graph_t *g, attr_state_t *attr_state)
static void adjustregularpath(path *P, size_t fb, size_t lb)
static void makefwdedge(edge_t *new, edge_t *old)
static bool pathscross(node_t *n0, node_t *n1, edge_t *ie1, edge_t *oe1)
static void make_regular_edge(graph_t *g, spline_info_t *sp, path *P, edge_t **edges, unsigned ind, unsigned cnt, int et)
static void cleanupCloneGraph(graph_t *g, attr_state_t *attr_state)
static int straight_len(node_t *n)
static int edgelblcmpfn(const void *x, const void *y)
static void make_flat_bottom_edges(graph_t *g, const spline_info_t sp, path *P, edge_t **edges, unsigned ind, unsigned cnt, edge_t *e, bool use_splines)
static boxf rank_box(spline_info_t *sp, graph_t *g, int r)
static void resetRW(graph_t *g)
static void makeSimpleFlat(node_t *tn, node_t *hn, edge_t **edges, unsigned ind, unsigned cnt, int et)
static pointf transformf(pointf p, pointf del, int flip)
rotate, if necessary, then translate points
static int dot_splines_(graph_t *g, int normalize)
static boxf makeregularend(boxf b, int side, double y)
static void swap_spline(splines *s)
static void setflags(edge_t *e, int hint1, int hint2, int f3)
static boxf maximal_bbox(graph_t *g, const spline_info_t sp, node_t *vn, edge_t *ie, edge_t *oe)
static void resize_vn(node_t *vn, double lx, double cx, double rx)
static edge_t * straight_path(edge_t *e, int cnt, points_t *plist)
static node_t * cloneNode(graph_t *g, node_t *orign)
static void del(Dict_t *d, Dtlink_t **set, Agedge_t *e)
void update_bb_bz(boxf *bb, pointf *cp)
static pointf add_pointf(pointf p, pointf q)
Agsym_t * E_labelfontsize
Agsym_t * E_labelfontname
Agsym_t * E_labelfontcolor
Agsym_t * E_labeldistance
static int cnt(Dict_t *d, Dtlink_t **set)
Agsym_t * agattr_text(Agraph_t *g, int kind, char *name, const char *value)
creates or looks up text attributes of a graph
int agset(void *obj, char *name, const char *value)
Agsym_t * agnxtattr(Agraph_t *g, int kind, Agsym_t *attr)
permits traversing the list of attributes of a given type
int agxset(void *obj, Agsym_t *sym, const char *value)
int agcopyattr(void *oldobj, void *newobj)
copies all of the attributes from one object to another
Agsym_t * agattr_html(Agraph_t *g, int kind, char *name, const char *value)
agattr_text, but creates HTML-like values
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
#define agfindedgeattr(g, a)
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)
#define AGOUT2IN(outedge)
Agedgepair_s.out -> Agedgepair_s.in/*#end#*/.
void agwarningf(const char *fmt,...)
int agerr(agerrlevel_t level, const char *fmt,...)
#define agfindgraphattr(g, a)
Agdesc_t Agundirected
undirected
int agisdirected(Agraph_t *g)
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
creates a new graph with the given name and kind
Agdesc_t Agdirected
directed
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)
#define agfindnodeattr(g, a)
Agraph_t * agraphof(void *obj)
char * agnameof(void *)
returns a string descriptor for the object.
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
int aghtmlstr(const char *)
Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Arithmetic helper functions.
void mark_lowclusters(Agraph_t *root)
type-generic dynamically expanding list
#define LIST_AT(list, index)
#define LIST_APPEND(list, item)
#define LIST_SORT(list, cmp)
#define LIST_IS_EMPTY(list)
#define LIST_GET(list, index)
#define neighbor(t, i, edim, elist)
int rank(graph_t *g, int balance, int maxiter)
void orthoEdges(Agraph_t *g, bool useLbls)
void dotneato_postprocess(Agraph_t *g)
bezier * new_spline(edge_t *e, size_t sz)
splines * getsplinepoints(edge_t *e)
void clip_and_install(edge_t *fe, node_t *hn, pointf *ps, size_t pn, splineInfo *info)
pointf * simpleSplineRoute(pointf, pointf, Ppoly_t, size_t *, int)
Given a simple (ccw) polygon, route an edge from tp to hp.
int routesplinesinit(void)
shape_kind shapeOf(node_t *)
void add_box(path *, boxf)
void beginpath(path *, Agedge_t *, int, pathend_t *, bool)
pointf * routesplines(path *, size_t *)
void routesplinesterm(void)
void makeSelfEdge(edge_t *edges[], size_t ind, size_t cnt, double sizex, double sizey, splineInfo *sinfo)
void endpath(path *, Agedge_t *, int, pathend_t *, bool)
pointf * routepolylines(path *pp, size_t *npoints)
int place_portlabel(edge_t *e, bool head_p)
void makeStraightEdges(graph_t *g, edge_t **edges, size_t e_cnt, int et, splineInfo *sinfo)
Agrec_t * data
stores programmer-defined data, access with AGDATA
Agraph_t * root
subgraphs - ancestors
attrsym_t * N_peripheries
attrsym_t * E_label_float
attrsym_t * E_labelfontname
attrsym_t * E_labelfontcolor
attrsym_t * N_orientation
attrsym_t * E_labelfontsize
size_t nbox
number of subdivisions
bool(* swapEnds)(edge_t *e)
bool(* splineMerge)(node_t *n)
#define SET_RANKDIR(g, rd)