16#if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
27static void ideal_distance_avoid_overlap(
int dim,
SparseMatrix A,
double *x,
double *width,
double *ideal_distance,
double *tmax,
double *tmin){
34 int *ia =
A->ia, *ja =
A->ja;
36 double expandmax = 1.5, expandmin = 1;
41 for (i = 0; i <
A->m; i++){
42 for (j = ia[i]; j < ia[i+1]; j++){
44 if (jj == i)
continue;
48 wx = width[i*
dim]+width[jj*
dim];
49 wy = width[i*
dim+1]+width[jj*
dim+1];
51 ideal_distance[j] = hypot(wx, wy);
59 t = fmin(wx /
dx, wy /
dy);
61 if (t > 1) t = fmax(t, 1.001);
62 *tmax = fmax(*tmax, t);
63 *tmin = fmin(*tmin, t);
64 t = fmin(expandmax, t);
65 t = fmax(expandmin, t);
67 ideal_distance[j] = t*
dist;
69 ideal_distance[j] = -t*
dist;
77enum {INTV_OPEN, INTV_CLOSE};
85static int comp_scan_points(
const void *p,
const void *q){
86 const scan_point *pp = p;
87 const scan_point *qq = q;
90 }
else if (pp->x < qq->x){
93 if (pp->node > qq->node){
95 }
else if (pp->node < qq->node){
103static void NodeDest(
void* a) {
108static SparseMatrix get_overlap_graph(
int dim,
int n,
double *x,
double *width,
int check_overlap_only){
118 scan_point *scanpointsx =
gv_calloc(2 * n,
sizeof(scan_point));
119 for (i = 0; i < n; i++){
120 scanpointsx[2*i].node = i;
121 scanpointsx[2*i].x = x[i*
dim] - width[i*
dim];
122 scanpointsx[2*i].status = INTV_OPEN;
123 scanpointsx[2*i+1].node = i+n;
124 scanpointsx[2*i+1].x = x[i*
dim] + width[i*
dim];
125 scanpointsx[2*i+1].status = INTV_CLOSE;
127 qsort(scanpointsx, 2*n,
sizeof(scan_point), comp_scan_points);
129 scan_point *scanpointsy =
gv_calloc(2 * n,
sizeof(scan_point));
130 for (i = 0; i < n; i++){
131 scanpointsy[i].node = i;
132 scanpointsy[i].x = x[i*
dim+1] - width[i*
dim+1];
133 scanpointsy[i].status = INTV_OPEN;
134 scanpointsy[i+n].node = i;
135 scanpointsy[i+n].x = x[i*
dim+1] + width[i*
dim+1];
136 scanpointsy[i+n].status = INTV_CLOSE;
141 for (i = 0; i < 2*n; i++){
143 fprintf(stderr,
" k = %d node = %d x====%f\n",(scanpointsx[i].
node)%n, (scanpointsx[i].
node), (scanpointsx[i].x));
146 k = (scanpointsx[i].node)%n;
149 if (scanpointsx[i].status == INTV_OPEN){
151 fprintf(stderr,
"inserting...");
152 treey->PrintKey(&(scanpointsy[k]));
158 fprintf(stderr,
"inserting2...");
159 treey->PrintKey(&(scanpointsy[k+n]));
164 double bsta, bbsta, bsto, bbsto;
int ii;
166 assert(scanpointsx[i].
node >= n);
169 ii = ((scan_point *)
newNode->key)->node;
171 bsta = scanpointsy[ii].x; bsto = scanpointsy[ii+n].x;
174 fprintf(stderr,
"popping..%d....yinterval={%f,%f}\n", scanpointsy[k + n].
node, bsta, bsto);
183 fprintf(stderr,
" predecessor is node %d y = %f\n", ((scan_point *)
newNode->key)->node, ((scan_point *)
newNode->key)->x);
186 if (fabs(0.5*(bsta+bsto) - 0.5*(bbsta+bbsto)) < 0.5*(bsto-bsta) + 0.5*(bbsto-bbsta)){
189 fprintf(stderr,
"====================================== %d %d\n",k,
neighbor);
191 if (check_overlap_only)
goto check_overlap_RETURN;
197 fprintf(stderr,
"deleting...");
198 treey->PrintKey(newNode0->
key);
201 if (newNode0)
RBDelete(treey,newNode0);
214 if (
Verbose) fprintf(stderr,
"found %d clashes\n",
A->nz);
223static void relative_position_constraints_delete(
void *d){
237 data->constr_penalty = 1;
238 data->edge_labeling_scheme = edge_labeling_scheme;
239 data->n_constr_nodes = n_constr_nodes;
240 data->constr_nodes = constr_nodes;
241 data->A_constr = A_constr;
248static void scale_coord(
int dim,
int m,
double *x,
double scale){
250 for (i = 0; i <
dim*m; i++) {
255static double overlap_scaling(
int dim,
int m,
double *x,
double *width,
256 double scale_sta,
double scale_sto,
257 double epsilon,
int maxiter) {
268 double scale = -1, scale_best = -1;
270 int check_overlap_only = 1;
277 if (scale_sta <= 0) {
280 scale_coord(
dim, m, x, scale_sta);
281 C = get_overlap_graph(
dim, m, x, width, check_overlap_only);
282 if (!
C ||
C->nz == 0) {
283 if (
Verbose) fprintf(stderr,
" shrinking with %f works\n", scale_sta);
287 scale_coord(
dim, m, x, 1./scale_sta);
292 if (scale_sta == 0) {
295 scale_sto = scale_sta;
297 scale_coord(
dim, m, x, scale_sto);
300 scale_coord(
dim, m, x, two);
301 C = get_overlap_graph(
dim, m, x, width, check_overlap_only);
305 scale_coord(
dim, m, x, 1/scale_sto);
308 scale_best = scale_sto;
309 while (iter++ < maxiter && scale_sto - scale_sta > epsilon){
311 if (
Verbose) fprintf(stderr,
"in overlap_scaling iter=%d, maxiter=%d, scaling bracket: {%f,%f}\n", iter, maxiter, scale_sta, scale_sto);
313 scale = 0.5*(scale_sta + scale_sto);
315 C = get_overlap_graph(
dim, m, x, width, check_overlap_only);
322 scale_best = scale_sto =
scale;
327 scale_coord(
dim, m, x, scale_best);
332 int dim,
double *x,
double *width,
bool neighborhood_only,
333 double *max_overlap,
double *min_overlap,
334 int edge_labeling_scheme,
int n_constr_nodes,
int *constr_nodes,
SparseMatrix A_constr,
int shrink
336 int i, j, k, *iw, *jw, jdiag;
338 double *d, *w, diag_d, diag_w,
dist;
344 if (constr_nodes && n_constr_nodes > 0 && edge_labeling_scheme !=
ELSCHEME_NONE){
346 sm->
data = relative_position_constraints_new(A_constr, edge_labeling_scheme, n_constr_nodes, constr_nodes);
359 if (!neighborhood_only){
361 C = get_overlap_graph(
dim, m, x, width, 0);
370 if (!(sm->
Lw) || !(sm->
Lwd)) {
377 ideal_distance_avoid_overlap(
dim, sm->
Lwd, x, width, sm->
Lwd->
a, max_overlap, min_overlap);
380 if (*max_overlap < 1 && shrink){
381 double scale_sta = fmin(1, *max_overlap * 1.0001);
382 const double scale_sto = 1;
384 if (
Verbose) fprintf(stderr,
" no overlap (overlap = %f), rescale to shrink\n", *max_overlap - 1);
386 scale_sta = overlap_scaling(
dim, m, x, width, scale_sta, scale_sto, 0.0001, 15);
396 for (i = 0; i < m; i++){
399 for (j = iw[i]; j < iw[i+1]; j++){
406 w[j] = -100/d[j]/d[j];
440static void scale_to_edge_length(
int dim,
SparseMatrix A,
double *x,
double avg_label_size){
446 if (
Verbose) fprintf(stderr,
"avg edge len=%f avg_label-size= %f\n",
dist, avg_label_size);
451 for (i = 0; i <
dim*
A->m; i++) x[i] *=
dist;
454static void print_bounding_box(
int n,
int dim,
double *x){
462 for (i = 0; i < n; i++){
463 for (k = 0; k <
dim; k++){
468 fprintf(stderr,
"bounding box = \n");
469 for (i = 0; i <
dim; i++) fprintf(stderr,
"{%f,%f}, ",
xmin[i],
xmax[i]);
470 fprintf(stderr,
"\n");
476static int check_convergence(
double max_overlap,
double res,
477 bool has_penalty_terms,
double epsilon) {
478 if (!has_penalty_terms)
479 return (max_overlap <= 1);
480 return res < epsilon;
484 int edge_labeling_scheme,
int n_constr_nodes,
int *constr_nodes,
SparseMatrix A_constr,
bool do_shrinking) {
499 double LARGE = 100000;
500 double avg_label_size, res = LARGE;
501 double max_overlap = 0, min_overlap = 999;
502 bool neighborhood_only =
true;
503 double epsilon = 0.005;
514 if (!label_sizes)
return;
516 if (initial_scaling < 0) {
518 for (i = 0; i <
A->m; i++) avg_label_size += label_sizes[i*
dim]+label_sizes[i*
dim+1];
519 avg_label_size /=
A->m;
520 scale_to_edge_length(
dim,
A, x, -initial_scaling*avg_label_size);
521 }
else if (initial_scaling > 0){
522 scale_to_edge_length(
dim,
A, x, initial_scaling);
528 _statistics[0] = _statistics[1] = 0.;
531 bool has_penalty_terms =
533 for (i = 0; i < ntry; i++){
536 &max_overlap, &min_overlap, edge_labeling_scheme, n_constr_nodes, constr_nodes, A_constr, shrink);
539 "overlap removal neighbors only?= %d iter -- %d, overlap factor = %g underlap factor = %g\n",
540 (
int)neighborhood_only, i, max_overlap - 1, min_overlap);
542 if (check_convergence(max_overlap, res, has_penalty_terms, epsilon)) {
545 if (!neighborhood_only){
549 neighborhood_only =
false;
558 if (
Verbose) fprintf(stderr,
"res = %f\n",res);
563 "overlap removal neighbors only?= %d iter -- %d, overlap factor = %g underlap factor = %g\n",
564 (
int)neighborhood_only, i, max_overlap - 1, min_overlap);
567 if (has_penalty_terms){
574 fprintf(stderr,
" number of cg iter = %f, number of stress majorization iter = %f number of overlap removal try = %d\n",
575 _statistics[0], _statistics[1], i - 1);
579 fprintf(stderr,
"post processing %f\n",((
double) (clock() - cpu)) / CLOCKS_PER_SEC);
587 int edge_labeling_scheme,
int n_constr_nodes,
int *constr_nodes,
SparseMatrix A_constr,
bool do_shrinking)
589 static atomic_flag once;
596 (void)initial_scaling;
597 (void)edge_labeling_scheme;
598 (void)n_constr_nodes;
603 if (!atomic_flag_test_and_set(&once)) {
604 agerrorf(
"remove_overlap: Graphviz not built with triangulation library\n");
SparseMatrix SparseMatrix_from_coordinate_format(SparseMatrix A)
SparseMatrix SparseMatrix_symmetrize(SparseMatrix A, bool pattern_symmetric_only)
SparseMatrix SparseMatrix_coordinate_form_add_entry(SparseMatrix A, int irn, int jcn, const void *val)
bool SparseMatrix_is_symmetric(SparseMatrix A, bool test_pattern_symmetry_only)
void SparseMatrix_delete(SparseMatrix A)
SparseMatrix SparseMatrix_copy(SparseMatrix A)
SparseMatrix SparseMatrix_add(SparseMatrix A, SparseMatrix B)
SparseMatrix SparseMatrix_new(int m, int n, int nz, int type, int format)
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
SparseMatrix call_tri(int n, double *x)
static double dist(int dim, double *x, double *y)
double distance(double *x, int dim, int i, int j)
static pointf scale(double c, pointf p)
static node_list * newNode(Grid *g, Agnode_t *n, node_list *nxt)
void agerrorf(const char *fmt,...)
#define neighbor(t, i, edim, elist)
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)
#define OverlapSmoother_struct
OverlapSmoother OverlapSmoother_new(SparseMatrix A, int m, int dim, double *x, double *width, bool neighborhood_only, double *max_overlap, double *min_overlap, int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, int shrink)
void OverlapSmoother_delete(OverlapSmoother sm)
double OverlapSmoother_smooth(OverlapSmoother sm, int dim, double *x)
double StressMajorizationSmoother_smooth(StressMajorizationSmoother sm, int dim, double *x, int maxit_sm)
void StressMajorizationSmoother_delete(StressMajorizationSmoother sm)
@ SM_SCHEME_NORMAL_ELABEL
void RBDelete(rb_red_blk_tree *tree, rb_red_blk_node *z)
rb_red_blk_node * TreePredecessor(rb_red_blk_tree *tree, rb_red_blk_node *x)
void RBTreeDestroy(rb_red_blk_tree *tree)
rb_red_blk_node * RBExactQuery(rb_red_blk_tree *tree, void *q)
rb_red_blk_node * RBTreeInsert(rb_red_blk_tree *tree, void *key)
rb_red_blk_tree * RBTreeCreate(int(*CompFunc)(const void *, const void *), void(*DestFunc)(void *))
static double overlap(double i0, double i1, double j0, double j1)
double average_edge_length(SparseMatrix A, int dim, double *coord)
void(* data_deallocator)(void *)
graphs, nodes and edges info: Agraphinfo_t, Agnodeinfo_t and Agedgeinfo_t