/*
This software may only be used by you under license from AT&T Corp.
("AT&T"). A copy of AT&T's Source Code Agreement is available at
AT&T's Internet website having the URL:
<http://www.research.att.com/sw/tools/graphviz/license/source.html>
If you received this software without first entering into a license
with AT&T, you have an infringing copy of this software and cannot use
it without violating AT&T's intellectual property rights.
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include "neato.h"
#include "pathplan.h"
#include "vispath.h"
#ifndef HAVE_DRAND48
extern double drand48(void);
#endif
#define P2PF(p, pf) (pf.x = p.x, pf.y = p.y)
#define PF2P(pf, p) (p.x = ROUND (pf.x), p.y = ROUND (pf.y))
extern void printvis (vconfig_t *cp);
static void place_portlabel (edge_t *e, boolean head_p);
static splines *getsplinepoints (edge_t* e);
extern int in_poly(Ppoly_t argpoly, Ppoint_t q);
static boolean spline_merge(node_t *n)
{
return FALSE;
}
static boolean swap_ends_p (edge_t *e)
{
return FALSE;
}
static splineInfo sinfo = {swap_ends_p, spline_merge};
void neato_compute_bb(graph_t *g)
{
node_t *n;
edge_t *e;
box b,bb;
point pt,s2;
int i,j;
bb.LL = pointof(MAXINT,MAXINT);
bb.UR = pointof(-MAXINT,-MAXINT);
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
pt = coord(n);
s2.x = ND_xsize(n)/2+1; s2.y = ND_ysize(n)/2+1;
b.LL = sub_points(pt,s2);
b.UR = add_points(pt,s2);
bb.LL.x = MIN(bb.LL.x,b.LL.x);
bb.LL.y = MIN(bb.LL.y,b.LL.y);
bb.UR.x = MAX(bb.UR.x,b.UR.x);
bb.UR.y = MAX(bb.UR.y,b.UR.y);
for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
if (ED_spl(e) == 0) continue;
for (i = 0; i < ED_spl(e)->size; i++) {
for (j = 0; j < ED_spl(e)->list[i].size; j++) {
pt = ED_spl(e)->list[i].list[j];
if (bb.LL.x > pt.x) bb.LL.x = pt.x;
if (bb.LL.y > pt.y) bb.LL.y = pt.y;
if (bb.UR.x < pt.x) bb.UR.x = pt.x;
if (bb.UR.y < pt.y) bb.UR.y = pt.y;
}
}
}
}
for (i = 1; i <= GD_n_cluster(g); i++) {
bb.LL.x = MIN(bb.LL.x,GD_clust(g)[i]->u.bb.LL.x);
bb.LL.y = MIN(bb.LL.y,GD_clust(g)[i]->u.bb.LL.y);
bb.UR.x = MAX(bb.UR.x,GD_clust(g)[i]->u.bb.UR.x);
bb.UR.y = MAX(bb.UR.y,GD_clust(g)[i]->u.bb.UR.y);
}
GD_bb(g) = bb;
}
static Ppoint_t mkPoint(point p) {Ppoint_t rv; rv.x = p.x; rv.y = p.y; return rv;}
static void
make_barriers(Ppoly_t **poly, int npoly, int pp, int qp, Pedge_t **barriers, int *n_barriers){
int i, j, k, n, b;
Pedge_t *bar;
n = 0;
for (i = 0; i < npoly; i++) {
if (i == pp) continue;
if (i == qp) continue;
n = n + poly[i]->pn;
}
bar = N_GNEW(n, Pedge_t);
b = 0;
for (i = 0; i < npoly; i++) {
if (i == pp) continue;
if (i == qp) continue;
for (j = 0; j < poly[i]->pn; j++) {
k = j + 1;
if (k >= poly[i]->pn) k = 0;
bar[b].a = poly[i]->ps[j];
bar[b].b = poly[i]->ps[k];
b++;
}
}
assert(b == n);
*barriers = bar;
*n_barriers = n;
}
extern int Plegal_arrangement( Ppoly_t **polys, int n_polys);
/* recPt:
*/
static Ppoint_t
recPt (double x, double y, point c, double sep)
{
Ppoint_t p;
p.x = (x * sep) + c.x;
p.y = (y * sep) + c.y;
return p;
}
/* spline_edges0:
* Main body for constructing edges.
* Assumes u.bb for has been computed for g and all clusters
* (not just top-level clusters), and
* that GD_bb(g).LL is at the origin.
*
* This last criterion is, I believe, mainly to simplify the code
* in neato_set_aspect. It would be good to remove this constraint,
* as this would allow nodes pinned on input to have the same coordinates
* when output in dot or plain format.
*
* As a side-effect, this function sets the u.coord attribute of nodes
* from the u.pos attribute. This is needed for output. In addition,
* it guarantees that all bounding
* boxes are current; in particular, the bounding box of g reflects the
* addition of edges. NOTE: intra-cluster edges are not constrained to
* remain in the cluster's bounding box and, conversely, a cluster's box
* is not altered to reflect intra-cluster edges.
*
* Note that, currently, edge labels are not used in bounding box
* calculations.
*/
void spline_edges0(graph_t *g)
{
node_t *n;
edge_t *e;
point dumb[4],d,ld;
pointf polyp;
Ppoly_t **obs;
polygon_t *poly;
int i=0, j, npoly, sides;
extern void poly_init(node_t *);
Ppoint_t p,q;
vconfig_t *vconfig;
Pedge_t *barriers;
double adj=0.0, SEP;
char *str;
if ((str = agget(g,"sep"))) {SEP = 1.0 + atof(str);}
else SEP = 1.01;
neato_set_aspect(g);
/* build configuration */
if (mapbool(agget(g,"splines"))) {
obs = N_NEW (agnnodes(g), Ppoly_t*);
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
ND_coord_i(n).x = POINTS(ND_pos(n)[0]);
ND_coord_i(n).y = POINTS(ND_pos(n)[1]);
if (ND_shape(n)->initfn == poly_init) {
obs[i] = NEW(Ppoly_t);
poly = (polygon_t*) ND_shape_info(n);
if (poly->sides >= 3) {
sides = poly->sides;
}
else { /* ellipse */
sides = 8;
adj = drand48() * .01;
}
obs[i]->pn = sides;
obs[i]->ps = N_NEW(sides, Ppoint_t);
/* assuming polys are in CCW order, and pathplan needs CW */
for (j = 0; j < sides; j++) {
if (poly->sides >= 3) {
polyp.x = POINTS(poly->vertices[j].x) * SEP;
polyp.y = POINTS(poly->vertices[j].y) * SEP;
}
else {
double c, s;
c = cos(2.0 * PI * j / sides + adj);
s = sin(2.0 * PI * j / sides + adj);
polyp.x = SEP * c * (ND_lw_i(n) + ND_rw_i(n)) / 2.0;
polyp.y = SEP * s * ND_ht_i(n) / 2.0;
}
obs[i]->ps[sides - j - 1].x = polyp.x + ND_coord_i(n).x;
obs[i]->ps[sides - j - 1].y = polyp.y + ND_coord_i(n).y;
}
i++;
}
else if (ND_shape(n)->initfn == record_init) {
box b;
point pt;
field_t *fld = (field_t*) ND_shape_info(n);
b = fld->b;
obs[i] = NEW(Ppoly_t);
obs[i]->pn = 4;
obs[i]->ps = N_NEW(4, Ppoint_t);
/* CW order */
pt = ND_coord_i(n);
obs[i]->ps[0] = recPt (b.LL.x,b.LL.y, pt, SEP);
obs[i]->ps[1] = recPt (b.LL.x,b.UR.y, pt, SEP);
obs[i]->ps[2] = recPt (b.UR.x,b.UR.y, pt, SEP);
obs[i]->ps[3] = recPt (b.UR.x,b.LL.y, pt, SEP);
i++;
}
}
}
else {
obs = 0;
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
ND_coord_i(n).x = POINTS(ND_pos(n)[0]);
ND_coord_i(n).y = POINTS(ND_pos(n)[1]);
}
}
npoly = i;
if (obs && NOT(Plegal_arrangement(obs,npoly))) {
if (Verbose) fprintf(stderr,"nodes touch - falling back to straight line edges\n");
vconfig = 0;
}
else {
if (obs) vconfig = Pobsopen(obs,npoly);
else vconfig = 0;
}
/* route edges */
if (Verbose) fprintf(stderr,"Creating edges using %s\n",
(vconfig ? "splines" : "line segments"));
if (vconfig) {
/* path-finding pass */
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
Ppolyline_t line;
int pp, qp;
p = mkPoint(add_points(ND_coord_i(n), ED_tail_port(e).p));
q = mkPoint(add_points(ND_coord_i(e->head), ED_head_port(e).p));
/* determine the polygons (if any) that contain the endpoints */
pp = qp = POLYID_NONE;
for (i = 0; i < npoly; i++) {
if ((pp == POLYID_NONE) && in_poly(*obs[i], p)) pp = i;
if ((qp == POLYID_NONE) && in_poly(*obs[i], q)) qp = i;
}
/*Pobspath(vconfig, p, POLYID_UNKNOWN, q, POLYID_UNKNOWN, &line);*/
Pobspath(vconfig, p, pp, q, qp, &line);
ED_path(e) = line;
}
}
}
/* spline-drawing pass */
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
node_t* head = e->head;
if ((Nop > 1) && ED_spl(e)) {
p = mkPoint(add_points(ND_coord_i(n), ED_tail_port(e).p));
q = mkPoint(add_points(ND_coord_i(head), ED_head_port(e).p));
}
else if (vconfig && (n != head)) {
Ppolyline_t line, spline;
Pvector_t slopes[2];
int n_barriers;
int pp, qp;
point *ispline;
line = ED_path(e);
p = line.ps[0];
q = line.ps[line.pn-1];
/* determine the polygons (if any) that contain the endpoints */
pp = qp = POLYID_NONE;
for (i = 0; i < npoly; i++) {
if ((pp == POLYID_NONE) && in_poly(*obs[i], p)) pp = i;
if ((qp == POLYID_NONE) && in_poly(*obs[i], q)) qp = i;
}
make_barriers(obs, npoly, pp, qp, &barriers, &n_barriers);
slopes[0].x = slopes[0].y = 0.0;
slopes[1].x = slopes[1].y = 0.0;
Proutespline (barriers, n_barriers, line, slopes, &spline);
/* north why did you ever use int coords */
ispline = N_GNEW(spline.pn,point);
for (i = 0; i < spline.pn; i++) {
ispline[i].x = ROUND(spline.ps[i].x);
ispline[i].y = ROUND(spline.ps[i].y);
}
if (Verbose > 1)
fprintf(stderr,"spline %s %s\n",n->name,head->name);
clip_and_install(e,e,ispline,spline.pn,&sinfo);
free(ispline);
free(barriers);
}
else {
dumb[0] = add_points(ND_coord_i(n), ED_tail_port(e).p);
dumb[3] = add_points(ND_coord_i(head), ED_head_port(e).p);
p = mkPoint(dumb[0]);
q = mkPoint(dumb[3]);
if (n != head) {
d = sub_points(dumb[3],dumb[0]);
d.x = d.x / 3;
d.y = d.y / 3;
dumb[1] = add_points(dumb[0],d);
dumb[2] = sub_points(dumb[3],d);
}
else { /* self arc */
pointf del;
del.x = dumb[0].x - dumb[3].x;
del.y = dumb[0].y - dumb[3].y;
if ((del.x == 0) && (del.y == 0)) {
d.x = ND_rw_i(head) + POINTS(.66 * SEP);
d.y = 0;
dumb[1] = dumb[2] = add_points(dumb[0],d);
dumb[1].y += d.x;
dumb[2].y -= d.x;
}
else {
pointf perp, base;
double l_del, l_perp, sz, l, L;
perp.x = -del.y;
perp.y = del.x;
l_del = sqrt(del.x*del.x + del.y*del.y);
l_perp = sqrt(perp.x*perp.x + perp.y*perp.y);
if (abs(del.y) <= abs(del.x)) { /* horizontal */
sz = ND_ht_i(head)/2.0;
if (del.y >= ND_coord_i(n).y) {
if (perp.y < 0) {
perp.y *= -1;
perp.x *= -1;
}
}
else {
if (perp.y > 0) {
perp.y *= -1;
perp.x *= -1;
}
}
}
else { /* vertical */
sz = ND_rw_i(head);
if (del.x >= ND_coord_i(n).x) {
if (perp.x < 0) {
perp.x *= -1;
perp.y *= -1;
}
}
else {
if (perp.x > 0) {
perp.y *= -1;
perp.x *= -1;
}
}
}
l = sz + POINTS(.66 * SEP);
L = l/l_del + 0.5;
base.x = dumb[3].x + (del.x/2) + (l*perp.x)/l_perp;
base.y = dumb[3].y + (del.y/2) + (l*perp.y)/l_perp;
dumb[1].x = base.x + L*del.x;
dumb[1].y = base.y + L*del.y;
dumb[2].x = base.x - L*del.x;
dumb[2].y = base.y - L*del.y;
}
}
clip_and_install(e,e,dumb,4,&sinfo);
}
/* This can only hope to work for straight edges.
* FIX for loops and curves; also if nop > 1, use
* label position if provided
*/
if (ED_label(e) && !ED_label(e)->set) {
d.x = (q.x + p.x)/ 2;
d.y = (p.y + q.y)/ 2;
if (abs(p.x - q.x) > abs(p.y - q.y)) {
ld.x = 0; ld.y = POINTS(ED_label(e)->dimen.y)/2 + 2;
}
else {
ld.x = POINTS(ED_label(e)->dimen.y)/2+ED_label(e)->fontsize;
ld.y = 0;
}
d = add_points(d,ld);
ED_label(e)->p = d;
ED_label(e)->set = TRUE;
}
}
}
/* GD_bb(g).UR = sub_points(GD_bb(g).UR,GD_bb(g).LL); */
/* GD_bb(g).LL = pointof(0,0); */
/* We do not need to recompute the bounding box here because
* it was computed before entry, and a side-effect of adding edges
* with clip_and_install is to update the bounding box.
*/
/* neato_compute_bb(g); */
/* vladimir: place port labels */
if (E_headlabel || E_taillabel)
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
if (E_headlabel) for (e = agfstin(g,n); e; e = agnxtin(g,e))
if (ED_head_label(e)) place_portlabel (e, TRUE);
if (E_taillabel) for (e = agfstout(g,n); e; e = agnxtout(g,e))
if (ED_tail_label(e)) place_portlabel (e, FALSE);
}
/* end vladimir */
State = GVSPLINES;
}
/* spline_edges:
* Construct all edges. We assume the graph
* has no clusters, and only nodes have been
* positioned.
*/
void spline_edges(graph_t *g)
{
node_t *n;
pointf offset;
neato_compute_bb(g);
offset = cvt2ptf(GD_bb(g).LL);
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
ND_pos(n)[0] -= offset.x;
ND_pos(n)[1] -= offset.y;
}
GD_bb(g).UR.x -= GD_bb(g).LL.x;
GD_bb(g).UR.y -= GD_bb(g).LL.y;
GD_bb(g).LL.x = 0;
GD_bb(g).LL.y = 0;
spline_edges0(g);
}
/* scaleEdge:
* Scale edge by given factor.
* Assume ED_spl != NULL.
*/
static void
scaleEdge(edge_t *e, double xf, double yf)
{
int i, j;
point* pt;
bezier* bez;
bez = ED_spl(e)->list;
for (i = 0; i < ED_spl(e)->size; i++) {
pt = bez->list;
for (j = 0; j < bez->size; j++) {
pt->x *= xf;
pt->y *= yf;
pt++;
}
if (bez->sflag) {
bez->sp.x *= xf;
bez->sp.y *= yf;
}
if (bez->eflag) {
bez->ep.x *= xf;
bez->ep.y *= yf;
}
bez++;
}
if (ED_label(e) && ED_label(e)->set) {
ED_label(e)->p.x *= xf;
ED_label(e)->p.y *= yf;
}
if (ED_head_label(e) && ED_head_label(e)->set) {
ED_head_label(e)->p.x *= xf;
ED_head_label(e)->p.y *= yf;
}
if (ED_tail_label(e) && ED_tail_label(e)->set) {
ED_tail_label(e)->p.x *= xf;
ED_tail_label(e)->p.y *= yf;
}
}
/* scaleBB:
* Scale bounding box of clusters of g by given factors.
*/
static void
scaleBB(graph_t *g, double xf, double yf)
{
int i;
GD_bb(g).UR.x *= xf;
GD_bb(g).UR.y *= yf;
GD_bb(g).LL.x *= xf;
GD_bb(g).LL.y *= yf;
if (GD_label(g) && GD_label(g)->set) {
GD_label(g)->p.x *= xf;
GD_label(g)->p.y *= yf;
}
for (i = 1; i <= GD_n_cluster(g); i++)
scaleBB(GD_clust(g)[i],xf,yf);
}
/* neato_set_aspect;
* Assume all bounding boxes are correct and
* that GD_bb(g).LL is at origin.
*/
void
neato_set_aspect(graph_t *g)
{
/* int i; */
double xf,yf,actual,desired;
char *str;
node_t *n;
/* neato_compute_bb(g); */
if (/* (GD_maxrank(g) > 0) && */(str = agget(g,"ratio"))) {
/* normalize */
assert (GD_bb(g).LL.x == 0);
assert (GD_bb(g).LL.y == 0);
/* GD_bb(g).UR.x -= GD_bb(g).LL.x; */
/* GD_bb(g).UR.y -= GD_bb(g).LL.y; */
if (GD_left_to_right(g))
{int t = GD_bb(g).UR.x; GD_bb(g).UR.x = GD_bb(g).UR.y; GD_bb(g).UR.y = t;}
if (strcmp(str,"fill") == 0) {
/* fill is weird because both X and Y can stretch */
if (GD_drawing(g)->size.x <= 0) return;
xf = (double)GD_drawing(g)->size.x / (double)GD_bb(g).UR.x;
yf = (double)GD_drawing(g)->size.y / (double)GD_bb(g).UR.y;
if ((xf < 1.0) || (yf < 1.0)) {
if (xf < yf) {yf = yf / xf; xf = 1.0;}
else {xf = xf / yf; yf = 1.0;}
}
}
else {
desired = atof(str);
if (desired == 0.0) return;
actual = ((double)GD_bb(g).UR.y)/((double)GD_bb(g).UR.x);
if (actual < desired) {yf = desired/actual; xf = 1.0;}
else {xf = actual/desired; yf = 1.0;}
}
if (GD_left_to_right(g)) {double t = xf; xf = yf; yf = t;}
/* Not relying on neato_nlist here allows us not to have to
* allocate it in the root graph and the connected components.
*/
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
/* for (i = 0; (n = GD_neato_nlist(g)[i]); i++) { */
ND_pos(n)[0] = ND_pos(n)[0] * xf;
ND_pos(n)[1] = ND_pos(n)[1] * yf;
}
scaleBB (g, xf, yf);
if (Nop > 1) {
edge_t* e;
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
for (e = agfstout(g,n); e; e = agnxtout(g,e))
if (ED_spl(e)) scaleEdge (e, xf, yf);
}
}
}
}
/* vladimir */
static void place_portlabel (edge_t *e, boolean head_p)
/* place the {head,tail}label (depending on HEAD_P) of edge E */
{
textlabel_t *l;
splines *spl;
bezier *bez;
double dist, angle;
point p;
pointf c[4], pf;
int i;
l = head_p ? ED_head_label(e) : ED_tail_label(e);
if (swap_ends_p(e)) head_p = !head_p;
spl = getsplinepoints(e);
if (!head_p) {
bez = &spl->list[0];
if (bez->sflag != ARR_NONE
&& bez->sflag != ARR_OPEN
&& bez->sflag != ARR_HALFOPEN) {
p = bez->sp;
P2PF(bez->list[0],pf);
}
else {
p = bez->list[0];
for (i=0; i<4; i++) P2PF(bez->list[i], c[i]);
pf = Bezier (c, 3, 0.1, NULL, NULL);
}
} else {
bez = &spl->list[spl->size-1];
if (bez->eflag != ARR_NONE
&& bez->eflag != ARR_OPEN
&& bez->eflag != ARR_HALFOPEN) {
p = bez->ep;
P2PF(bez->list[bez->size-1],pf);
}
else {
p = bez->list[bez->size-1];
for (i=0; i<4; i++) P2PF(bez->list[bez->size-4+i], c[i]);
pf = Bezier (c, 3, 0.9, NULL, NULL);
}
}
angle = atan2 (pf.y-p.y, pf.x-p.x) +
RADIANS(late_double(e,E_labelangle,PORT_LABEL_ANGLE,-180.0));
dist = PORT_LABEL_DISTANCE * late_double(e,E_labeldistance,1.0,0.0);
l->p.x = p.x + ROUND(dist * cos(angle));
l->p.y = p.y + ROUND(dist * sin(angle));
l->set = TRUE;
}
static splines *getsplinepoints (edge_t* e)
{
splines *sp;
sp = ED_spl(e);
if (sp == NULL) abort ();
return sp;
}
|
