32#if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
45static const double incr = 0.05;
70 for (
size_t i = 0; i <
nsites; i++) {
88 double x_min = DBL_MAX;
89 double y_min = DBL_MAX;
90 double x_max = -DBL_MAX;
91 double y_max = -DBL_MAX;
93 for (
size_t i = 0; i <
nsites; ++i) {
98 x_min = fmin(x_min, pp->
origin.
x + x);
99 y_min = fmin(y_min, pp->
origin.
y + y);
100 x_max = fmax(x_max, pp->
corner.
x + x);
101 y_max = fmax(y_max, pp->
corner.
y + y);
107 const double margin = (marg && *marg !=
'\0') ? atof(marg) : 0.05;
108 double ydelta = margin * (y_max - y_min);
109 double xdelta = margin * (x_max - x_min);
110 ll.
x = x_min - xdelta;
111 ll.
y = y_min - ydelta;
112 ur.
x = x_max + xdelta;
113 ur.
y = y_max + ydelta;
141 for (
size_t i = 0; i <
nsites; i++) {
146 if (polyf(&ip->
poly,
node, pmargin.
x, pmargin.
y)) {
162static int scomp(
const void *S1,
const void *S2)
165 const Site *s2 = *(
Site *
const *)S2;
185 for (
size_t i = 0; i <
nsites; i++) {
207 for (
size_t i = 0; i <
nsites; ++i) {
233 (*jp)->
coord.
x != (*ip)->coord.x ||
234 (*jp)->coord.y != (*ip)->coord.y) {
242 while (kp < st->endSite &&
243 (*kp)->coord.x == (*ip)->coord.x &&
244 (*kp)->coord.y == (*ip)->coord.y) {
251 if (kp < st->endSite && (*kp)->coord.y == (*ip)->coord.y) {
252 const double xdel = ((*kp)->coord.x - (*ip)->coord.x) /
cnt;
254 for (jp = ip + 1; jp < kp; jp++) {
255 (*jp)->
coord.
x += i * xdel;
260 for (jp = ip + 1; jp < kp; ip++, jp++) {
262 double xdel =
info->poly.corner.x -
info->poly.origin.x;
264 xdel +=
info->poly.corner.x -
info->poly.origin.x;
265 (*jp)->coord.x = (*ip)->coord.x + xdel / 2;
277 for (
size_t i = 0; i <
nsites; i++)
280 for (
size_t i = 0; i <
nsites - 1; i++) {
282 for (
size_t j = i + 1; j <
nsites; j++) {
293 fprintf(stderr,
"overlap [%d] : %d\n", iter, count);
301 const double ydelta =
incr * (ur.
y - ll.
y);
302 const double xdelta =
incr * (ur.
x - ll.
x);
315 return fabs(a.
x * (b.
y - c.
y) + b.
x * (c.
y - a.
y) + c.
x * (a.
y - b.
y)) / 2;
323 *x = (a.
x + b.
x + c.
x) / 3;
324 *y = (a.
y + b.
y + c.
y) / 3;
333 double totalArea = 0.0;
342 const double area =
areaOf(anchor->
p, p->
p, q->
p);
369 for (
size_t i = 1; i <
nsites; i++) {
411 for (
size_t i = 0; i <
nsites; i++) {
445 for (
bool doAll =
false;;) {
452 if (
cnt >= overlapCnt)
474 fprintf(stderr,
"Number of iterations = %d\n", iterCnt);
475 fprintf(stderr,
"Number of increases = %d\n", increaseCnt);
484 double f = 1.0 +
incr;
486 for (
size_t i = 0; i <
nsites; i++) {
513 fprintf(stderr,
"Number of iterations = %d\n", iterCnt);
522 for (
size_t i = 0; i <
nsites; i++) {
529#define ELS "|edgelabel|"
531#define IS_LNODE(n) startswith(agnameof(n), ELS)
540 if (elabels &&
IS_LNODE(n)) nedge_nodes++;
542 const int i =
ND_id(n);
547 if (elabels && nedge_nodes) {
548 int* elabs =
gv_calloc(nedge_nodes,
sizeof(
int));
552 elabs[nedge_nodes++] =
ND_id(n);
555 *n_elabels = nedge_nodes;
588 if (!sym || sscanf(
agxget(e, sym),
"%lf", &v) != 1)
608#if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
627 for (
int i = 0; i <
Ndim; i++) {
644 for (
int i = 0; i <
Ndim; i++) {
666 float *f_storage =
gv_calloc(dim * nnodes,
sizeof(
float));
668 for (
size_t i = 0; i < dim; i++) {
669 coords[i] = f_storage + i * nnodes;
674 for (
size_t i = 0; i < dim; i++) {
675 coords[i][j] = (float)
ND_pos(v)[i];
685 opt.clusters = (cluster_data){0};
688 if (exp_margin.
doAdd) {
689 opt.gap.x = 2.0*
PS2INCH(exp_margin.
x);
690 opt.gap.y = 2.0*
PS2INCH(exp_margin.
y);
697 removeoverlaps(nnodes, coords, &opt);
701 for (
size_t i = 0; i < dim; i++) {
702 ND_pos(v)[i] = coords[i][j];
721 char* a =
agget(g,
"normalize");
723 if (!a || *a ==
'\0')
725 double ang = strtod (a, &p);
732 while (ang > 180) ang -= 360;
733 while (ang <= -180) ang += 360;
758 if (p.
x || p.
y) ret = 1;
775 const double cosv = cos(phi);
776 const double sinv = sin(phi);
780 ND_pos(v)[0] = p.
x * cosv - p.
y * sinv + orig.
x;
781 ND_pos(v)[1] = p.
x * sinv + p.
y * cosv + orig.
y;
800#if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
803 {
AM_VOR,
"voronoi",
"Voronoi"},
808 {
AM_SCALE,
"oscale",
"old scaling"},
810 {
AM_ORTHO,
"ortho",
"orthogonal constraints"},
811 {
AM_ORTHO_YX,
"ortho_yx",
"orthogonal constraints"},
812 {
AM_ORTHOXY,
"orthoxy",
"xy orthogonal constraints"},
813 {
AM_ORTHOYX,
"orthoyx",
"yx orthogonal constraints"},
814 {
AM_PORTHO,
"portho",
"pseudo-orthogonal constraints"},
815 {
AM_PORTHO_YX,
"portho_yx",
"pseudo-orthogonal constraints"},
816 {
AM_PORTHOXY,
"porthoxy",
"xy pseudo-orthogonal constraints"},
817 {
AM_PORTHOYX,
"porthoyx",
"yx pseudo-orthogonal constraints"},
818#if !((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
828 if (sscanf (
s,
"%d", &v) > 0 && v >= 0)
838 if (
s ==
NULL || *
s ==
'\0') {
844 bool matches = strcasecmp(
s, ap->
attrib) == 0;
863 bool unmappable = v !=
mapBool(
s,
true);
865 agwarningf(
"Unrecognized overlap value \"%s\" - using false\n",
s);
881 fprintf(stderr,
"overlap: %s value %d scaling %.04f\n", dp->
print, dp->
value, dp->
scaling);
886 char* am =
agget(
G,
"overlap");
890#define ISZERO(d) (fabs(d) < 0.000000001)
898 if ((p =
agget(g,
"scale"))) {
899 if ((i = sscanf(p,
"%lf,%lf", &sc.
x, &sc.
y))) {
901 if (i == 1) sc.
y = sc.
x;
902 else if (
ISZERO(sc.
y))
return 0;
903 if (sc.
y == 1 && sc.
x == 1)
return 0;
905 fprintf (stderr,
"scale = (%.03f,%.03f)\n", sc.
x, sc.
y);
935 fprintf(stderr,
"Adjusting %s using %s\n",
agnameof(
G), am->
print);
965#if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
1045 else pp->
doAdd =
false;
1048 if ((i = sscanf(
s,
"%lf,%lf", &x, &y))) {
1052 pp->
x = fmin(dflt, x / sepfact);
1053 pp->
y = fmin(dflt, y / sepfact);
1055 else if (sepfact < 1) {
1056 pp->
x = fmax(dflt, x / sepfact);
1057 pp->
y = fmax(dflt, y / sepfact);
1065 pp->
x = 1.0 + x / sepfact;
1066 pp->
y = 1.0 + y / sepfact;
1085 pmargin.
doAdd =
true;
1088 fprintf (stderr,
"Node separation: add=%d (%f,%f)\n",
1089 pmargin.
doAdd, pmargin.
x, pmargin.
y);
1106 else if ((marg =
agget(g,
"sep")) &&
1111 pmargin.
doAdd =
true;
1114 fprintf (stderr,
"Edge separation: add=%d (%f,%f)\n",
1115 pmargin.
doAdd, pmargin.
x, pmargin.
y);
bool SparseMatrix_is_symmetric(SparseMatrix A, bool test_pattern_symmetry_only)
SparseMatrix SparseMatrix_from_coordinate_arrays(int nz, int m, int n, int *irn, int *jcn, void *val0, int type, size_t sz)
void SparseMatrix_delete(SparseMatrix A)
SparseMatrix SparseMatrix_get_real_adjacency_matrix_symmetrized(SparseMatrix A)
SparseMatrix SparseMatrix_remove_diagonal(SparseMatrix A)
static void newpos(Info_t *ip)
static int sAdjust(state_t *st)
static void sortSites(state_t *st)
Fill array of pointer to sites and sort the sites using scomp.
static void newPos(const state_t *st, bool doAll)
static void updateGraph(void)
Enter new node positions into the graph.
expand_t esepFactor(graph_t *g)
static void centroidOf(Point a, Point b, Point c, double *x, double *y)
static void chkBoundBox(state_t *st, Agraph_t *graph)
static void freeNodes(void)
Free node resources.
SparseMatrix makeMatrix(Agraph_t *g)
static void setBoundBox(state_t *st, Point *ll, Point *ur)
expand_t sepFactor(graph_t *g)
static void getAdjustMode(Agraph_t *g, const char *s, adjust_data *dp)
Convert string value to internal value of adjustment mode.
static const lookup_t adjustMode[]
int removeOverlapAs(graph_t *G, char *flag)
Use flag value to determine if and how to remove node overlaps.
double * getSizes(Agraph_t *g, pointf pad, int *n_elabels, int **elabels)
Set up array of half sizes in inches.
static void cleanup(void)
static int parseFactor(char *s, expand_t *pp, double sepfact, double dflt)
static int scomp(const void *S1, const void *S2)
static double areaOf(Point a, Point b, Point c)
Area of triangle whose vertices are a,b,c.
static Site * nextOne(void *state)
static void rmEquality(state_t *st)
Check for nodes with identical positions and tweak the positions.
static int makeInfo(Agraph_t *graph)
For each node in the graph, create a Info data structure.
static int vAdjust(state_t *st)
static void geomUpdate(state_t *st, int doSort)
int adjustNodes(graph_t *G)
static int countOverlap(int iter)
Count number of node-node overlaps at iteration iter.
int normalize(graph_t *g)
static void increaseBoundBox(state_t *st)
static double rePos(void)
static void addCorners(const state_t *st)
static int angleSet(graph_t *g, double *phi)
static int simpleScale(graph_t *g)
static void setPrismValues(Agraph_t *g, const char *s, adjust_data *dp)
Initialize and set prism values.
void graphAdjustMode(graph_t *G, adjust_data *dp, char *dflt)
int removeOverlapWith(graph_t *G, adjust_data *am)
int cAdjust(graph_t *, int)
int scAdjust(graph_t *, int)
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
bool mapbool(const char *p)
double late_double(void *obj, attrsym_t *attr, double defaultValue, double minimum)
bool mapBool(const char *p, bool defaultValue)
static int overlaps(nitem *p, int cnt)
#define PS2INCH(a_points)
double dist_2(Point pp, Point qp)
distance squared between two points
static int cnt(Dict_t *d, Dtlink_t **set)
int agnedges(Agraph_t *g)
int agnnodes(Agraph_t *g)
char * agget(void *obj, char *name)
char * agxget(void *obj, Agsym_t *sym)
#define agfindedgeattr(g, a)
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
void agwarningf(const char *fmt,...)
#define agfindgraphattr(g, a)
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Agnode_t * agfstnode(Agraph_t *g)
char * agnameof(void *)
returns a string descriptor for the object.
Agraph_t * graph(char *name)
replacements for ctype.h functions
static bool gv_isspace(int c)
void addVertex(Site *s, double x, double y)
NEATOPROCS_API void s1(graph_t *, node_t *)
void remove_overlap(int dim, SparseMatrix A, double *x, double *label_sizes, int ntry, double initial_scaling, int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, bool do_shrinking)
int polyOverlap(Point p, Poly *pp, Point q, Poly *qp)
int makePoly(Poly *pp, Agnode_t *n, double xmargin, double ymargin)
int makeAddPoly(Poly *pp, Agnode_t *n, double xmargin, double ymargin)
static int nedges
total no. of edges used in routing
int fdpAdjust(graph_t *g)
platform abstraction for case-insensitive string functions
information the ID allocator needs to do its job
Site ** sites
array of pointers to sites; used in qsort
Site ** endSite
sentinel on sites array
Point se
corners of clipping window
void voronoi(Site *(*nextsite)(void *context), void *context)