Graphviz 13.0.0~dev.20250424.1043
Loading...
Searching...
No Matches
overlap.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include "config.h"
12#include <neatogen/overlap.h>
13#include <stdatomic.h>
14#include <util/alloc.h>
15
16#if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
17
18#include <sparse/SparseMatrix.h>
19#include <neatogen/call_tri.h>
21#include <common/types.h>
22#include <math.h>
23#include <common/globals.h>
24#include <stdbool.h>
25#include <time.h>
26
27static void ideal_distance_avoid_overlap(int dim, SparseMatrix A, double *x, double *width, double *ideal_distance, double *tmax, double *tmin){
28 /* if (x1>x2 && y1 > y2) we want either x1 + t (x1-x2) - x2 > (width1+width2), or y1 + t (y1-y2) - y2 > (height1+height2),
29 hence t = MAX(expandmin, MIN(expandmax, (width1+width2)/(x1-x2) - 1, (height1+height2)/(y1-y2) - 1)), and
30 new ideal distance = (1+t) old_distance. t can be negative sometimes.
31 The result ideal distance is set to negative if the edge needs shrinking
32 */
33 int i, j, jj;
34 int *ia = A->ia, *ja = A->ja;
35 double dist, dx, dy, wx, wy, t;
36 double expandmax = 1.5, expandmin = 1;
37
38 *tmax = 0;
39 *tmin = 1.e10;
40 assert(SparseMatrix_is_symmetric(A, false));
41 for (i = 0; i < A->m; i++){
42 for (j = ia[i]; j < ia[i+1]; j++){
43 jj = ja[j];
44 if (jj == i) continue;
45 dist = distance(x, dim, i, jj);
46 dx = fabs(x[i*dim] - x[jj*dim]);
47 dy = fabs(x[i*dim+1] - x[jj*dim+1]);
48 wx = width[i*dim]+width[jj*dim];
49 wy = width[i*dim+1]+width[jj*dim+1];
50 if (dx < MACHINEACC*wx && dy < MACHINEACC*wy){
51 ideal_distance[j] = hypot(wx, wy);
52 *tmax = 2;
53 } else {
54 if (dx < MACHINEACC*wx){
55 t = wy/dy;
56 } else if (dy < MACHINEACC*wy){
57 t = wx/dx;
58 } else {
59 t = fmin(wx / dx, wy / dy);
60 }
61 if (t > 1) t = fmax(t, 1.001);/* no point in things like t = 1.00000001 as this slow down convergence */
62 *tmax = fmax(*tmax, t);
63 *tmin = fmin(*tmin, t);
64 t = fmin(expandmax, t);
65 t = fmax(expandmin, t);
66 if (t > 1) {
67 ideal_distance[j] = t*dist;
68 } else {
69 ideal_distance[j] = -t*dist;
70 }
71 }
72
73 }
74 }
75}
76
77enum {INTV_OPEN, INTV_CLOSE};
78
79typedef struct {
80 int node;
81 double x;
82 int status;
83} scan_point;
84
85static int comp_scan_points(const void *p, const void *q){
86 const scan_point *pp = p;
87 const scan_point *qq = q;
88 if (pp->x > qq->x){
89 return 1;
90 } else if (pp->x < qq->x){
91 return -1;
92 } else {
93 if (pp->node > qq->node){
94 return 1;
95 } else if (pp->node < qq->node){
96 return -1;
97 }
98 return 0;
99 }
100 return 0;
101}
102
103static void NodeDest(void* a) {
104 (void)a;
105 /* free((int*)a);*/
106}
107
108static SparseMatrix get_overlap_graph(int dim, int n, double *x, double *width, int check_overlap_only){
109 /* if check_overlap_only = TRUE, we only check whether there is one overlap */
110 int i, k, neighbor;
111 SparseMatrix A = NULL, B = NULL;
112 rb_red_blk_node *newNode, *newNode0;
113 rb_red_blk_tree* treey;
114 double one = 1;
115
117
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;
126 }
127 qsort(scanpointsx, 2*n, sizeof(scan_point), comp_scan_points);
128
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;
137 }
138
139 treey = RBTreeCreate(comp_scan_points, NodeDest);
140
141 for (i = 0; i < 2*n; i++){
142#ifdef DEBUG_RBTREE
143 fprintf(stderr," k = %d node = %d x====%f\n",(scanpointsx[i].node)%n, (scanpointsx[i].node), (scanpointsx[i].x));
144#endif
145
146 k = (scanpointsx[i].node)%n;
147
148
149 if (scanpointsx[i].status == INTV_OPEN){
150#ifdef DEBUG_RBTREE
151 fprintf(stderr, "inserting...");
152 treey->PrintKey(&(scanpointsy[k]));
153#endif
154
155 RBTreeInsert(treey, &scanpointsy[k]); // add both open and close int for y
156
157#ifdef DEBUG_RBTREE
158 fprintf(stderr, "inserting2...");
159 treey->PrintKey(&(scanpointsy[k+n]));
160#endif
161
162 RBTreeInsert(treey, &scanpointsy[k + n]);
163 } else {
164 double bsta, bbsta, bsto, bbsto; int ii;
165
166 assert(scanpointsx[i].node >= n);
167
168 newNode = newNode0 = RBExactQuery(treey, &(scanpointsy[k + n]));
169 ii = ((scan_point *)newNode->key)->node;
170 assert(ii < n);
171 bsta = scanpointsy[ii].x; bsto = scanpointsy[ii+n].x;
172
173#ifdef DEBUG_RBTREE
174 fprintf(stderr, "popping..%d....yinterval={%f,%f}\n", scanpointsy[k + n].node, bsta, bsto);
175 treey->PrintKey(newNode->key);
176#endif
177
178 assert(treey->nil != newNode);
179 while ((newNode) && ((newNode = TreePredecessor(treey, newNode)) != treey->nil)){
180 neighbor = (((scan_point *)newNode->key)->node)%n;
181 bbsta = scanpointsy[neighbor].x; bbsto = scanpointsy[neighbor+n].x;/* the y-interval of the node that has one end of the interval lower than the top of the leaving interval (bsto) */
182#ifdef DEBUG_RBTREE
183 fprintf(stderr," predecessor is node %d y = %f\n", ((scan_point *)newNode->key)->node, ((scan_point *)newNode->key)->x);
184#endif
185 if (neighbor != k){
186 if (fabs(0.5*(bsta+bsto) - 0.5*(bbsta+bbsto)) < 0.5*(bsto-bsta) + 0.5*(bbsto-bbsta)){/* if the distance of the centers of the interval is less than sum of width, we have overlap */
188#ifdef DEBUG_RBTREE
189 fprintf(stderr,"====================================== %d %d\n",k,neighbor);
190#endif
191 if (check_overlap_only) goto check_overlap_RETURN;
192 }
193 }
194 }
195
196#ifdef DEBUG_RBTREE
197 fprintf(stderr, "deleting...");
198 treey->PrintKey(newNode0->key);
199#endif
200
201 if (newNode0) RBDelete(treey,newNode0);
202 }
203 }
204
205check_overlap_RETURN:
206 free(scanpointsx);
207 free(scanpointsy);
208 RBTreeDestroy(treey);
209
212 A = SparseMatrix_symmetrize(B, false);
214 if (Verbose) fprintf(stderr, "found %d clashes\n", A->nz);
215 return A;
216}
217
218
219
220/* ============================== label overlap smoother ==================*/
221
222
223static void relative_position_constraints_delete(void *d){
224 if (!d) return;
226 free(data->irn);
227 free(data->jcn);
228 free(data->val);
229 // other stuff inside `relative_position_constraints` is passed back to the
230 // user hence no need to deallocate
231 free(d);
232}
233
234static relative_position_constraints relative_position_constraints_new(SparseMatrix A_constr, int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes){
235 assert(A_constr);
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;
242 data->irn = NULL;
243 data->jcn = NULL;
244 data->val = NULL;
245
246 return data;
247}
248static void scale_coord(int dim, int m, double *x, double scale){
249 int i;
250 for (i = 0; i < dim*m; i++) {
251 x[i] *= scale;
252 }
253}
254
255static double overlap_scaling(int dim, int m, double *x, double *width,
256 double scale_sta, double scale_sto,
257 double epsilon, int maxiter) {
258 /* do a bisection between scale_sta and scale_sto, up to maxiter iterations or till interval <= epsilon, to find the best scaling to avoid overlap
259 m: number of points
260 x: the coordinates
261 width: label size
262 scale_sta: starting bracket. If <= 0, assumed 0. If > 0, we will test this first and if no overlap, return.
263 scale_sto: stopping bracket. This must be overlap free if positive. If <= 0, we will find automatically by doubling from scale_sta, or epsilon if scale_sta <= 0.
264 typically usage:
265 - for shrinking down a layout to reduce white space, we will assume scale_sta and scale_sto are both given and positive, and scale_sta is the current guess.
266 - for scaling up, we assume scale_sta, scale_sto <= 0
267 */
268 double scale = -1, scale_best = -1;
270 int check_overlap_only = 1;
271 int overlap = 0;
272 double two = 2;
273 int iter = 0;
274
275 assert(epsilon > 0);
276
277 if (scale_sta <= 0) {
278 scale_sta = 0;
279 } else {
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);
285 return scale_sta;
286 }
287 scale_coord(dim, m, x, 1./scale_sta);
289 }
290
291 if (scale_sto < 0){
292 if (scale_sta == 0) {
293 scale_sto = epsilon;
294 } else {
295 scale_sto = scale_sta;
296 }
297 scale_coord(dim, m, x, scale_sto);
298 do {
299 scale_sto *= two;
300 scale_coord(dim, m, x, two);
301 C = get_overlap_graph(dim, m, x, width, check_overlap_only);
302 overlap = (C && C->nz > 0);
304 } while (overlap);
305 scale_coord(dim, m, x, 1/scale_sto);/* unscale */
306 }
307
308 scale_best = scale_sto;
309 while (iter++ < maxiter && scale_sto - scale_sta > epsilon){
310
311 if (Verbose) fprintf(stderr,"in overlap_scaling iter=%d, maxiter=%d, scaling bracket: {%f,%f}\n", iter, maxiter, scale_sta, scale_sto);
312
313 scale = 0.5*(scale_sta + scale_sto);
314 scale_coord(dim, m, x, scale);
315 C = get_overlap_graph(dim, m, x, width, check_overlap_only);
316 scale_coord(dim, m, x, 1./scale);/* unscale */
317 overlap = (C && C->nz > 0);
319 if (overlap){
320 scale_sta = scale;
321 } else {
322 scale_best = scale_sto = scale;
323 }
324 }
325
326 /* final scaling */
327 scale_coord(dim, m, x, scale_best);
328 return scale_best;
329}
330
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
335 ){
336 int i, j, k, *iw, *jw, jdiag;
338 double *d, *w, diag_d, diag_w, dist;
339
340 assert((!A) || SparseMatrix_is_symmetric(A, false));
341
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);
347 sm->data_deallocator = relative_position_constraints_delete;
348 } else {
349 sm->data = NULL;
350 }
351
352 sm->tol_cg = 0.01;
353 sm->maxit_cg = floor(sqrt(A->m));
354
355 sm->lambda = gv_calloc(m, sizeof(double));
356
357 B= call_tri(m, x);
358
359 if (!neighborhood_only){
361 C = get_overlap_graph(dim, m, x, width, 0);
362 D = SparseMatrix_add(B, C);
365 B = D;
366 }
367 sm->Lw = B;
368 sm->Lwd = SparseMatrix_copy(sm->Lw);
369
370 if (!(sm->Lw) || !(sm->Lwd)) {
372 return NULL;
373 }
374
375 assert((sm->Lwd)->type == MATRIX_TYPE_REAL);
376
377 ideal_distance_avoid_overlap(dim, sm->Lwd, x, width, sm->Lwd->a, max_overlap, min_overlap);
378
379 /* no overlap at all! */
380 if (*max_overlap < 1 && shrink){
381 double scale_sta = fmin(1, *max_overlap * 1.0001);
382 const double scale_sto = 1;
383
384 if (Verbose) fprintf(stderr," no overlap (overlap = %f), rescale to shrink\n", *max_overlap - 1);
385
386 scale_sta = overlap_scaling(dim, m, x, width, scale_sta, scale_sto, 0.0001, 15);
387
388 *max_overlap = 1;
389 goto RETURN;
390 }
391
392 iw = sm->Lw->ia; jw = sm->Lw->ja;
393 w = sm->Lw->a;
394 d = sm->Lwd->a;
395
396 for (i = 0; i < m; i++){
397 diag_d = diag_w = 0;
398 jdiag = -1;
399 for (j = iw[i]; j < iw[i+1]; j++){
400 k = jw[j];
401 if (k == i){
402 jdiag = j;
403 continue;
404 }
405 if (d[j] > 0){/* those edges that needs expansion */
406 w[j] = -100/d[j]/d[j];
407 } else {/* those that needs shrinking is set to negative in ideal_distance_avoid_overlap */
408 w[j] = -1/d[j]/d[j];
409 d[j] = -d[j];
410 }
411 dist = d[j];
412 diag_w += w[j];
413 d[j] = w[j]*dist;
414 diag_d += d[j];
415
416 }
417
418 assert(jdiag >= 0);
419 w[jdiag] = -diag_w;
420 d[jdiag] = -diag_d;
421 }
422 RETURN:
423 return sm;
424}
425
427
429
430}
431
432double OverlapSmoother_smooth(OverlapSmoother sm, int dim, double *x){
433 int maxit_sm = 1;/* only using 1 iteration of stress majorization
434 is found to give better results and save time! */
435 return StressMajorizationSmoother_smooth(sm, dim, x, maxit_sm);
436}
437
438/*================================= end OverlapSmoother =============*/
439
440static void scale_to_edge_length(int dim, SparseMatrix A, double *x, double avg_label_size){
441 double dist;
442 int i;
443
444 if (!A) return;
446 if (Verbose) fprintf(stderr,"avg edge len=%f avg_label-size= %f\n", dist, avg_label_size);
447
448
449 dist = avg_label_size / fmax(dist, MACHINEACC);
450
451 for (i = 0; i < dim*A->m; i++) x[i] *= dist;
452}
453
454static void print_bounding_box(int n, int dim, double *x){
455 int i, k;
456
457 double *xmin = gv_calloc(dim, sizeof(double));
458 double *xmax = gv_calloc(dim, sizeof(double));
459
460 for (i = 0; i < dim; i++) xmin[i]=xmax[i] = x[i];
461
462 for (i = 0; i < n; i++){
463 for (k = 0; k < dim; k++){
464 xmin[k] = fmin(xmin[k], x[i * dim + k]);
465 xmax[k] = fmax(xmax[k], x[i * dim + k]);
466 }
467 }
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");
471
472 free(xmin);
473 free(xmax);
474}
475
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;
481}
482
483void remove_overlap(int dim, SparseMatrix A, double *x, double *label_sizes, int ntry, double initial_scaling,
484 int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, bool do_shrinking) {
485 /*
486 edge_labeling_scheme: if ELSCHEME_NONE, n_constr_nodes/constr_nodes/A_constr are not used
487
488 n_constr_nodes: number of nodes that has constraints, these are nodes that is
489 . constrained to be close to the average of its neighbors.
490 constr_nodes: a list of nodes that need to be constrained. If NULL, unused.
491 A_constr: neighbors of node i are in the row i of this matrix. i needs to sit
492 . in between these neighbors as much as possible. this must not be NULL
493 . if constr_nodes != NULL.
494
495 */
496
498 int i;
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;
504 int shrink = 0;
505
506#ifdef TIME
507 clock_t cpu;
508#endif
509
510#ifdef TIME
511 cpu = clock();
512#endif
513
514 if (!label_sizes) return;
515
516 if (initial_scaling < 0) {
517 avg_label_size = 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);
523 }
524
525 if (!ntry) return;
526
527#ifdef DEBUG
528 _statistics[0] = _statistics[1] = 0.;
529#endif
530
531 bool has_penalty_terms =
532 edge_labeling_scheme != ELSCHEME_NONE && n_constr_nodes > 0;
533 for (i = 0; i < ntry; i++){
534 if (Verbose) print_bounding_box(A->m, dim, x);
535 sm = OverlapSmoother_new(A, A->m, dim, x, label_sizes, neighborhood_only,
536 &max_overlap, &min_overlap, edge_labeling_scheme, n_constr_nodes, constr_nodes, A_constr, shrink);
537 if (Verbose) {
538 fprintf(stderr,
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);
541 }
542 if (check_convergence(max_overlap, res, has_penalty_terms, epsilon)) {
543
545 if (!neighborhood_only){
546 break;
547 } else {
548 res = LARGE;
549 neighborhood_only = false;
550 if (do_shrinking) {
551 shrink = 1;
552 }
553 continue;
554 }
555 }
556
557 res = OverlapSmoother_smooth(sm, dim, x);
558 if (Verbose) fprintf(stderr,"res = %f\n",res);
560 }
561 if (Verbose) {
562 fprintf(stderr,
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);
565 }
566
567 if (has_penalty_terms){
568 /* now do without penalty */
569 remove_overlap(dim, A, x, label_sizes, ntry, 0.,
570 ELSCHEME_NONE, 0, NULL, NULL, do_shrinking);
571 }
572
573#ifdef DEBUG
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);
576#endif
577
578#ifdef TIME
579 fprintf(stderr, "post processing %f\n",((double) (clock() - cpu)) / CLOCKS_PER_SEC);
580#endif
581}
582
583#else
584#include <common/types.h>
585#include <sparse/SparseMatrix.h>
586void remove_overlap(int dim, SparseMatrix A, double *x, double *label_sizes, int ntry, double initial_scaling,
587 int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, bool do_shrinking)
588{
589 static atomic_flag once;
590
591 (void)dim;
592 (void)A;
593 (void)x;
594 (void)label_sizes;
595 (void)ntry;
596 (void)initial_scaling;
597 (void)edge_labeling_scheme;
598 (void)n_constr_nodes;
599 (void)constr_nodes;
600 (void)A_constr;
601 (void)do_shrinking;
602
603 if (!atomic_flag_test_and_set(&once)) {
604 agerrorf("remove_overlap: Graphviz not built with triangulation library\n");
605 }
606}
607#endif
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)
@ FORMAT_COORD
@ MATRIX_TYPE_REAL
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static void * gv_alloc(size_t size)
Definition alloc.h:47
SparseMatrix call_tri(int n, double *x)
Definition call_tri.c:19
static float dy
Definition draw.c:37
static float dx
Definition draw.c:36
#define A(n, t)
Definition expr.h:76
static double dist(int dim, double *x, double *y)
double distance(double *x, int dim, int i, int j)
Definition general.c:121
#define MACHINEACC
Definition general.h:72
double xmax
Definition geometry.c:15
double xmin
Definition geometry.c:15
static pointf scale(double c, pointf p)
Definition geomprocs.h:155
static bool Verbose
Definition gml2gv.c:23
void free(void *)
node NULL
Definition grammar.y:163
static node_list * newNode(Grid *g, Agnode_t *n, node_list *nxt)
Definition grid.c:138
void agerrorf(const char *fmt,...)
Definition agerror.c:165
#define B
Definition hierarchy.c:118
#define D
Definition hierarchy.c:120
#define neighbor(t, i, edim, elist)
Definition make_map.h:41
static const int dim
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)
Definition overlap.c:586
#define OverlapSmoother_struct
Definition overlap.h:18
@ ELSCHEME_NONE
Definition overlap.h:29
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)
#define C
Definition pack.c:30
double StressMajorizationSmoother_smooth(StressMajorizationSmoother sm, int dim, double *x, int maxit_sm)
void StressMajorizationSmoother_delete(StressMajorizationSmoother sm)
@ SM_SCHEME_NORMAL_ELABEL
@ SM_SCHEME_NORMAL
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)
Definition routespl.c:574
double average_edge_length(SparseMatrix A, int dim, double *coord)
#define RETURN(v)
Definition strmatch.c:144
Definition legal.c:50
rb_red_blk_node * nil
graphs, nodes and edges info: Agraphinfo_t, Agnodeinfo_t and Agedgeinfo_t