44#define GRAPHTYPEMASK 192
46#define MAKEFWDEDGE(new, old) \
51 info = (Agedgeinfo_t *)newp->base.data; \
52 *info = *(Agedgeinfo_t *)old->base.data; \
54 newp->base.data = (Agrec_t *)info; \
55 AGTAIL(newp) = AGHEAD(old); \
56 AGHEAD(newp) = AGTAIL(old); \
57 ED_tail_port(newp) = ED_head_port(old); \
58 ED_head_port(newp) = ED_tail_port(old); \
59 ED_edge_type(newp) = VIRTUAL; \
60 ED_to_orig(newp) = old; \
80static int edgecmp(
const void *,
const void *);
82 unsigned,
unsigned,
int);
84 unsigned,
unsigned,
int);
100 edges = gv_recalloc(edges, n_edges, n_edges + CHUNK, sizeof(edge_t *)); \
149 const size_t sz = b->
size;
150 for (
size_t i = 0; i < sz / 2; ++i) {
159 const size_t sz =
s->size;
162 for (
size_t i = 0; i < sz / 2; ++i) {
167 for (
size_t i = 0; i < sz; ++i) {
242 int i, j, k, n_nodes;
246 edge_t *e, *e0, *e1, *ea, *eb, *le0, *le1, **edges =
NULL;
257 agwarningf(
"edge labels with splines=curved not supported in dot - use "
283 unsigned n_edges = 0;
294 for (j = 0; j <
GD_rank(g)[i].n; j++) {
307 for (k = 0; (e =
ND_out(n).list[k]); k++) {
311 edges[n_edges++] = e;
312 if (n_edges %
CHUNK == 0)
318 edges[n_edges++] = e;
319 if (n_edges %
CHUNK == 0)
331 for (k = 0; (e =
ND_other(n).list[k]); k++) {
333 edges[n_edges++] = e;
334 if (n_edges %
CHUNK == 0)
347 qsort(edges, n_edges,
sizeof(edges[0]),
edgecmp);
362 for (
unsigned l = 0; l < n_edges;) {
363 const unsigned ind = l;
375 for (
cnt = 1; l < n_edges;
cnt++, l++) {
403 for (
unsigned ii = 1; ii <
cnt; ii++)
422 sizey =
MIN(upy, dwny);
425 for (
unsigned b = 0; b <
cnt; b++) {
507 if (
ND_in(n).size == 0)
557static int edgecmp(
const void *x,
const void *y) {
562#pragma GCC diagnostic push
563#pragma GCC diagnostic ignored "-Wcast-qual"
568#pragma GCC diagnostic pop
572 edge_t *e0, *e1, *ea, *eb, *le0, *le1;
573 int et0, et1, v0, v1, rv;
946#pragma GCC diagnostic push
947#pragma GCC diagnostic ignored "-Wcast-qual"
952#pragma GCC diagnostic pop
990 unsigned ind,
unsigned cnt,
int et,
995 double leftend, rightend, ctrx, ctry, miny, maxy;
997 double lminx = 0.0, lmaxx = 0.0;
1001 for (
unsigned i = 0; i <
cnt; i++) {
1002 earray[i] = edges[ind + i];
1010 leftend = tp.
x +
ND_rw(tn);
1011 rightend = hp.
x -
ND_lw(hn);
1012 ctrx = (leftend + rightend) / 2.0;
1027 maxy = miny +
ED_label(e)->dimen.y;
1028 uminx = ctrx -
ED_label(e)->dimen.x / 2.0;
1029 umaxx = ctrx +
ED_label(e)->dimen.x / 2.0;
1032 for (i = 1; i < n_lbls; i++) {
1036 lminx = ctrx -
ED_label(e)->dimen.x / 2.0;
1037 lmaxx = ctrx +
ED_label(e)->dimen.x / 2.0;
1054 ctry = miny +
ED_label(e)->dimen.y / 2.0;
1078 if (
ps ==
NULL || pn == 0) {
1091 for (; i <
cnt; i++) {
1095 lminx = (2 * leftend + rightend) / 3.0;
1096 lmaxx = (leftend + 2 * rightend) / 3.0;
1135 if (
ps ==
NULL || pn == 0) {
1148 unsigned cnt,
int et) {
1156 stepy =
cnt > 1 ?
ND_ht(tn) / (double)(
cnt - 1) : 0.;
1159 for (
unsigned i = 0; i <
cnt; i++) {
1204 double midx, midy, leftx, rightx;
1207 static atomic_flag warned;
1211 if (!atomic_flag_test_and_set(&warned)) {
1212 agwarningf(
"flat edge between adjacent nodes one of which has a record "
1213 "shape - replace records with HTML-like labels\n");
1219 unsigned labels = 0;
1221 for (
unsigned i = 0; i <
cnt; i++) {
1243 subg =
agsubg(auxg,
"xxx", 1);
1245 agset(subg,
"rank",
"source");
1253 for (
unsigned i = 0; i <
cnt; i++) {
1290 }
else if (n == auxh) {
1311 for (
unsigned i = 0; i <
cnt; i++) {
1319 if ((auxe == hvye) & !
ED_alg(auxe))
1327 for (
size_t j = 0; j < auxbz->
size;) {
1331 if (j >= auxbz->
size)
1389 bool ps_needs_free =
false;
1465 const size_t boxn =
sizeof(boxes) /
sizeof(boxes[0]);
1467 for (i = 0; i < tend.
boxn; i++)
1469 for (
size_t j = 0; j < boxn; j++)
1471 for (i = hend.
boxn - 1; i >= 0; i--)
1474 ps_needs_free =
true;
1490 edge_t **edges,
unsigned ind,
unsigned cnt,
1491 edge_t *e,
bool use_splines) {
1494 double stepx, stepy, vspace;
1509 stepy = vspace / (
cnt + 1);
1514 for (
unsigned i = 0; i <
cnt; i++) {
1522 boxes[boxn].
LL.
x = b.
LL.
x;
1523 boxes[boxn].
UR.
y = b.
LL.
y;
1524 boxes[boxn].
UR.
x = b.
UR.
x + (i + 1) * stepx;
1525 boxes[boxn].
LL.
y = b.
LL.
y - (i + 1) * stepy;
1528 boxes[boxn].
UR.
y = boxes[boxn - 1].
LL.
y;
1530 boxes[boxn].
LL.
y = boxes[boxn].
UR.
y - stepy;
1533 boxes[boxn].
UR.
x = b.
UR.
x;
1534 boxes[boxn].
UR.
y = b.
LL.
y;
1535 boxes[boxn].
LL.
x = b.
LL.
x - (i + 1) * stepx;
1536 boxes[boxn].
LL.
y = boxes[boxn - 1].
UR.
y;
1538 assert(boxn ==
sizeof(boxes) /
sizeof(boxes[0]));
1540 for (j = 0; j < tend.
boxn; j++)
1542 for (
size_t k = 0; k < boxn; k++)
1544 for (j = hend.
boxn - 1; j >= 0; j--)
1575 edge_t **edges,
unsigned ind,
unsigned cnt,
int et) {
1581 double stepx, stepy, vspace;
1594 for (
unsigned i = 1; i <
cnt; i++) {
1638 stepy = vspace / (
cnt + 1);
1643 for (
unsigned i = 0; i <
cnt; i++) {
1651 boxes[boxn].
LL.
x = b.
LL.
x;
1652 boxes[boxn].
LL.
y = b.
UR.
y;
1653 boxes[boxn].
UR.
x = b.
UR.
x + (i + 1) * stepx;
1654 boxes[boxn].
UR.
y = b.
UR.
y + (i + 1) * stepy;
1657 boxes[boxn].
LL.
y = boxes[boxn - 1].
UR.
y;
1659 boxes[boxn].
UR.
y = boxes[boxn].
LL.
y + stepy;
1662 boxes[boxn].
UR.
x = b.
UR.
x;
1663 boxes[boxn].
LL.
y = b.
UR.
y;
1664 boxes[boxn].
LL.
x = b.
LL.
x - (i + 1) * stepx;
1665 boxes[boxn].
UR.
y = boxes[boxn - 1].
LL.
y;
1667 assert(boxn ==
sizeof(boxes) /
sizeof(boxes[0]));
1669 for (j = 0; j < tend.
boxn; j++)
1671 for (
size_t k = 0; k < boxn; k++)
1673 for (j = hend.
boxn - 1; j >= 0; j--)
1695 return (p1.
y - p2.
y) * (p3.
x - p2.
x) - (p3.
y - p2.
y) * (p1.
x - p2.
x) > 0;
1720 double width, height;
1750 if (
leftOf(endp, startp, lp)) {
1751 lp.
x += width / 2.0;
1752 lp.
y -= height / 2.0;
1754 lp.
x -= width / 2.0;
1755 lp.
y += height / 2.0;
1758 points_append(
points, startp);
1759 points_append(
points, startp);
1760 points_append(
points, lp);
1761 points_append(
points, lp);
1762 points_append(
points, lp);
1763 points_append(
points, endp);
1764 points_append(
points, endp);
1767 points_append(
points, startp);
1768 points_append(
points, startp);
1769 points_append(
points, endp);
1770 points_append(
points, endp);
1778 edge_t **edges,
unsigned ind,
unsigned cnt,
1787 points_t pointfs = {0};
1788 points_t pointfs2 = {0};
1796 bool hackflag =
false;
1836 boxes_t boxes = {0};
1856 if (!smode || si > 0) {
1880 ps[3] =
ps[2] =
ps[pn - 1];
1887 points_free(&pointfs);
1888 points_free(&pointfs2);
1892 for (
size_t i = 0; i < pn; i++) {
1893 points_append(&pointfs,
ps[i]);
1901 boxes_clear(&boxes);
1915 b.
UR.
y = hend.boxes[hend.boxn - 1].UR.y;
1916 b.
LL.
y = hend.boxes[hend.boxn - 1].LL.y;
1919 hend.boxes[hend.boxn++] = b;
1934 ps[3] =
ps[2] =
ps[pn - 1];
1939 points_free(&pointfs);
1940 points_free(&pointfs2);
1943 for (
size_t i = 0; i < pn; i++) {
1944 points_append(&pointfs,
ps[i]);
1954 points_sync(&pointfs);
1957 points_free(&pointfs);
1958 points_free(&pointfs2);
1962 for (
size_t k = 1; k + 1 < points_size(&pointfs); k++)
1963 points_at(&pointfs, k)->x -=
dx;
1965 for (
size_t k = 0; k < points_size(&pointfs); k++)
1966 points_append(&pointfs2, points_get(&pointfs, k));
1967 points_sync(&pointfs2);
1970 for (
unsigned j = 1; j <
cnt; j++) {
1976 for (
size_t k = 1; k + 1 < points_size(&pointfs); k++)
1977 points_at(&pointfs, k)->x += sp->
Multisep;
1978 points_clear(&pointfs2);
1979 for (
size_t k = 0; k < points_size(&pointfs); k++)
1980 points_append(&pointfs2, points_get(&pointfs, k));
1981 points_sync(&pointfs2);
1983 points_size(&pointfs2), &
sinfo);
1985 points_free(&pointfs);
1986 points_free(&pointfs2);
1993 const boxes_t *boxes) {
1994 edge_t *uleft, *uright, *lleft, *lright;
1996 uleft = uright =
NULL;
2006 lleft = lright =
NULL;
2016 for (
int i = 0; i < tendp->
boxn; i++)
2018 const size_t fb = P->
nbox + 1;
2019 const size_t lb = fb + boxes_size(boxes) - 3;
2020 for (
size_t i = 0; i < boxes_size(boxes); i++)
2021 add_box(P, boxes_get(boxes, i));
2022 for (
int i = hendp->
boxn - 1; i >= 0; i--)
2058 for (
size_t i = fb - 1; i < lb + 1; i++) {
2060 if ((i - fb) % 2 == 0) {
2061 if (bp1->
LL.
x >= bp1->
UR.
x) {
2062 double x = (bp1->
LL.
x + bp1->
UR.
x) / 2;
2068 double x = (bp1->
LL.
x + bp1->
UR.
x) / 2;
2074 for (
size_t i = 0; i + 1 < P->
nbox; i++) {
2076 if (i >= fb && i <= lb && (i - fb) % 2 == 0) {
2079 if (bp1->
UR.
x - MINW < bp2->LL.x)
2081 }
else if (i + 1 >= fb && i < lb && (i + 1 - fb) % 2 == 0) {
2084 if (bp1->
UR.
x - MINW < bp2->LL.x)
2097 left1 =
GD_rank(g)[r + 1].v[0];
2131 assert(!points_is_empty(plist));
2132 points_append(plist, points_get(plist, points_size(plist) - 1));
2133 points_append(plist, points_get(plist, points_size(plist) - 1));
2185 for (i = 0; (f =
ND_in(
aghead(e)).list[i]); i++) {
2209#define REAL_CLUSTER(n) (ND_clust(n) == g ? NULL : ND_clust(n))
2227 if (cl && cl != tcl && cl != hcl)
2232 if (cl && cl != tcl && cl != hcl &&
cl_vninside(cl, adj))
2236 if (cl && cl != tcl && cl != hcl &&
cl_vninside(cl, adj))
2260 left_cl = right_cl =
NULL;
2318 for (i =
ND_order(vn) + dir; i >= 0 && i <
rank->n; i += dir) {
2345 if (
ND_out(n0).size == 1 && e1) {
2361 if (
ND_in(n0).size == 1 && e1) {
2362 e0 =
ND_in(n0).list[0];
2370 e0 =
ND_in(na).list[0];
2373 e1 =
ND_in(nb).list[0];
2380void showpath(
path *p) {
2383 fprintf(stderr,
"%%!PS\n");
2384 for (
size_t i = 0; i < p->
nbox; i++) {
2388 "newpath %.04f %.04f moveto %.04f %.04f lineto %.04f %.04f lineto "
2389 "%.04f %.04f lineto closepath stroke\n",
2390 LL.
x, LL.
y, UR.
x, LL.
y, UR.
x, UR.
y, LL.
x, UR.
y);
2392 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 boxf maximal_bbox(graph_t *g, spline_info_t *, Agnode_t *, Agedge_t *, Agedge_t *)
static void make_flat_bottom_edges(graph_t *g, spline_info_t *sp, path *P, edge_t **edges, unsigned ind, unsigned cnt, edge_t *e, bool use_splines)
static void swap_bezier(bezier *b)
static int make_flat_adj_edges(graph_t *g, edge_t **edges, unsigned ind, unsigned cnt, edge_t *e0, int et)
int dot_splines(graph_t *g)
static int straight_len(Agnode_t *)
static bool pathscross(Agnode_t *, Agnode_t *, Agedge_t *, Agedge_t *)
static edge_t * cloneEdge(graph_t *g, node_t *tn, node_t *hn, edge_t *orig)
static int make_flat_edge(graph_t *, spline_info_t *, path *, Agedge_t **, unsigned, unsigned, int)
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 Agedge_t * top_bound(Agedge_t *, int)
static bool swap_ends_p(edge_t *e)
int portcmp(port p0, port p1)
static void make_flat_labeled_edge(graph_t *g, spline_info_t *sp, path *P, edge_t *e, int et)
static bool spline_merge(node_t *n)
static void setEdgeLabelPos(graph_t *g)
static bool cl_vninside(Agraph_t *, Agnode_t *)
static void place_vnlabel(Agnode_t *)
static Agraph_t * cl_bound(graph_t *, Agnode_t *, Agnode_t *)
static void make_regular_edge(graph_t *g, spline_info_t *, path *, Agedge_t **, unsigned, unsigned, int)
static void adjustregularpath(path *, size_t, size_t)
static graph_t * cloneGraph(graph_t *g, attr_state_t *attr_state)
#define MAKEFWDEDGE(new, old)
static boxf makeregularend(boxf, int, double)
static edge_t * getmainedge(edge_t *e)
static boxf rank_box(spline_info_t *sp, Agraph_t *, int)
static void cleanupCloneGraph(graph_t *g, attr_state_t *attr_state)
static void makeBottomFlatEnd(graph_t *g, spline_info_t *sp, path *P, node_t *n, edge_t *e, pathend_t *endp, bool isBegin)
static void recover_slack(Agedge_t *, path *)
static void makeFlatEnd(graph_t *g, spline_info_t *sp, path *P, node_t *n, edge_t *e, pathend_t *endp, bool isBegin)
static Agedge_t * straight_path(Agedge_t *, int, points_t *)
static int edgecmp(const void *, const void *)
static int edgelblcmpfn(const void *x, const void *y)
static void resize_vn(Agnode_t *, double, double, double)
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 void completeregularpath(path *, Agedge_t *, Agedge_t *, pathend_t *, pathend_t *, const boxes_t *)
static void setflags(Agedge_t *, int, int, int)
static pointf transformf(pointf p, pointf del, int flip)
static int dot_splines_(graph_t *g, int normalize)
static void swap_spline(splines *s)
static Agedge_t * bot_bound(Agedge_t *, int)
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)
#define DEFINE_LIST(name, type)
#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
implementation of Agrec_t
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)