Graphviz  2.41.20170921.2350
overlap.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 #include "config.h"
15 
16 #if ((defined(HAVE_GTS) || defined(HAVE_TRIANGLE)) && defined(SFDP))
17 
18 #include "SparseMatrix.h"
19 #include "overlap.h"
20 #include "call_tri.h"
21 #include "red_black_tree.h"
22 #include "types.h"
23 #include "memory.h"
24 #include "globals.h"
25 #include <time.h>
26 
27 static void ideal_distance_avoid_overlap(int dim, SparseMatrix A, real *x, real *width, real *ideal_distance, real *tmax, real *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  real dist, dx, dy, wx, wy, t;
36  real expandmax = 1.5, expandmin = 1;
37 
38  *tmax = 0;
39  *tmin = 1.e10;
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 = ABS(x[i*dim] - x[jj*dim]);
47  dy = ABS(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] = sqrt(wx*wx+wy*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 = MIN(wx/dx, wy/dy);
60  }
61  if (t > 1) t = MAX(t, 1.001);/* no point in things like t = 1.00000001 as this slow down convergence */
62  *tmax = MAX(*tmax, t);
63  *tmin = MIN(*tmin, t);
64  t = MIN(expandmax, t);
65  t = MAX(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  return;
76 }
77 
78 #define collide(i,j) ((ABS(x[(i)*dim] - x[(j)*dim]) < width[(i)*dim]+width[(j)*dim]) || (ABS(x[(i)*dim+1] - x[(j)*dim+1]) < width[(i)*dim+1]+width[(j)*dim+1]))
79 
80 enum {INTV_OPEN, INTV_CLOSE};
81 
82 struct scan_point_struct{
83  int node;
84  real x;
85  int status;
86 };
87 
88 typedef struct scan_point_struct scan_point;
89 
90 
91 static int comp_scan_points(const void *p, const void *q){
92  scan_point *pp = (scan_point *) p;
93  scan_point *qq = (scan_point *) q;
94  if (pp->x > qq->x){
95  return 1;
96  } else if (pp->x < qq->x){
97  return -1;
98  } else {
99  if (pp->node > qq->node){
100  return 1;
101  } else if (pp->node < qq->node){
102  return -1;
103  }
104  return 0;
105  }
106  return 0;
107 }
108 
109 
110 void NodeDest(void* a) {
111  /* free((int*)a);*/
112 }
113 
114 
115 
116 int NodeComp(const void* a,const void* b) {
117  return comp_scan_points(a,b);
118 
119 }
120 
121 void NodePrint(const void* a) {
122  scan_point *aa;
123 
124  aa = (scan_point *) a;
125  fprintf(stderr, "node {%d, %f, %d}\n", aa->node, aa->x, aa->status);
126 
127 }
128 
129 void InfoPrint(void* a) {
130  ;
131 }
132 
133 void InfoDest(void *a){
134  ;
135 }
136 
137 static SparseMatrix get_overlap_graph(int dim, int n, real *x, real *width, int check_overlap_only){
138  /* if check_overlap_only = TRUE, we only check whether there is one overlap */
139  scan_point *scanpointsx, *scanpointsy;
140  int i, k, neighbor;
141  SparseMatrix A = NULL, B = NULL;
142  rb_red_blk_node *newNode, *newNode0, *newNode2 = NULL;
143  rb_red_blk_tree* treey;
144  real one = 1;
145 
147 
148  scanpointsx = N_GNEW(2*n,scan_point);
149  for (i = 0; i < n; i++){
150  scanpointsx[2*i].node = i;
151  scanpointsx[2*i].x = x[i*dim] - width[i*dim];
152  scanpointsx[2*i].status = INTV_OPEN;
153  scanpointsx[2*i+1].node = i+n;
154  scanpointsx[2*i+1].x = x[i*dim] + width[i*dim];
155  scanpointsx[2*i+1].status = INTV_CLOSE;
156  }
157  qsort(scanpointsx, 2*n, sizeof(scan_point), comp_scan_points);
158 
159  scanpointsy = N_GNEW(2*n,scan_point);
160  for (i = 0; i < n; i++){
161  scanpointsy[i].node = i;
162  scanpointsy[i].x = x[i*dim+1] - width[i*dim+1];
163  scanpointsy[i].status = INTV_OPEN;
164  scanpointsy[i+n].node = i;
165  scanpointsy[i+n].x = x[i*dim+1] + width[i*dim+1];
166  scanpointsy[i+n].status = INTV_CLOSE;
167  }
168 
169 
170  treey = RBTreeCreate(NodeComp,NodeDest,InfoDest,NodePrint,InfoPrint);
171 
172  for (i = 0; i < 2*n; i++){
173 #ifdef DEBUG_RBTREE
174  fprintf(stderr," k = %d node = %d x====%f\n",(scanpointsx[i].node)%n, (scanpointsx[i].node), (scanpointsx[i].x));
175 #endif
176 
177  k = (scanpointsx[i].node)%n;
178 
179 
180  if (scanpointsx[i].status == INTV_OPEN){
181 #ifdef DEBUG_RBTREE
182  fprintf(stderr, "inserting...");
183  treey->PrintKey(&(scanpointsy[k]));
184 #endif
185 
186  RBTreeInsert(treey, &(scanpointsy[k]), NULL); /* add both open and close int for y */
187 
188 #ifdef DEBUG_RBTREE
189  fprintf(stderr, "inserting2...");
190  treey->PrintKey(&(scanpointsy[k+n]));
191 #endif
192 
193  RBTreeInsert(treey, &(scanpointsy[k+n]), NULL);
194  } else {
195  real bsta, bbsta, bsto, bbsto; int ii;
196 
197  assert(scanpointsx[i].node >= n);
198 
199  newNode = newNode0 = RBExactQuery(treey, &(scanpointsy[k + n]));
200  ii = ((scan_point *)newNode->key)->node;
201  assert(ii < n);
202  bsta = scanpointsy[ii].x; bsto = scanpointsy[ii+n].x;
203 
204 #ifdef DEBUG_RBTREE
205  fprintf(stderr, "poping..%d....yinterval={%f,%f}\n", scanpointsy[k + n].node, bsta, bsto);
206  treey->PrintKey(newNode->key);
207 #endif
208 
209  assert(treey->nil != newNode);
210  while ((newNode) && ((newNode = TreePredecessor(treey, newNode)) != treey->nil)){
211  neighbor = (((scan_point *)newNode->key)->node)%n;
212  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) */
213 #ifdef DEBUG_RBTREE
214  fprintf(stderr," predecessor is node %d y = %f\n", ((scan_point *)newNode->key)->node, ((scan_point *)newNode->key)->x);
215 #endif
216  if (neighbor != k){
217  if (ABS(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 */
218  A = SparseMatrix_coordinate_form_add_entries(A, 1, &neighbor, &k, &one);
219 #ifdef DEBUG_RBTREE
220  fprintf(stderr,"====================================== %d %d\n",k,neighbor);
221 #endif
222  if (check_overlap_only) goto check_overlap_RETURN;
223  }
224  } else {
225  newNode2 = newNode;
226  }
227 
228  }
229 
230 #ifdef DEBUG_RBTREE
231  fprintf(stderr, "deleteing...");
232  treey->PrintKey(newNode0->key);
233 #endif
234 
235  if (newNode0) RBDelete(treey,newNode0);
236 
237 
238  if (newNode2 && newNode2 != treey->nil && newNode2 != newNode0) {
239 
240 #ifdef DEBUG_RBTREE
241  fprintf(stderr, "deleteing2...");
242  treey->PrintKey(newNode2->key);
243 #endif
244 
245  if (newNode0) RBDelete(treey,newNode2);
246  }
247 
248  }
249  }
250 
251 check_overlap_RETURN:
252  FREE(scanpointsx);
253  FREE(scanpointsy);
254  RBTreeDestroy(treey);
255 
260  if (Verbose) fprintf(stderr, "found %d clashes\n", A->nz);
261  return A;
262 }
263 
264 
265 
266 /* ============================== label overlap smoother ==================*/
267 
268 
269 static void relative_position_constraints_delete(void *d){
271  if (!d) return;
273  if (data->irn) FREE(data->irn);
274  if (data->jcn) FREE(data->jcn);
275  if (data->val) FREE(data->val);
276  /* other stuff inside relative_position_constraints is assed back to the user hence no need to deallocator*/
277  FREE(d);
278 }
279 
280 static relative_position_constraints relative_position_constraints_new(SparseMatrix A_constr, int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes){
282  assert(A_constr);
283  data = MALLOC(sizeof(struct relative_position_constraints_struct));
284  data->constr_penalty = 1;
285  data->edge_labeling_scheme = edge_labeling_scheme;
286  data->n_constr_nodes = n_constr_nodes;
287  data->constr_nodes = constr_nodes;
288  data->A_constr = A_constr;
289  data->irn = NULL;
290  data->jcn = NULL;
291  data->val = NULL;
292 
293  return data;
294 }
295 static void scale_coord(int dim, int m, real *x, real scale){
296  int i;
297  for (i = 0; i < dim*m; i++) {
298  x[i] *= scale;
299  }
300 }
301 
302 real overlap_scaling(int dim, int m, real *x, real *width, real scale_sta, real scale_sto, real epsilon, int maxiter){
303  /* 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
304  m: number of points
305  x: the coordinates
306  width: label size
307  scale_sta: starting bracket. If <= 0, assumed 0. If > 0, we will test this first and if no overlap, return.
308  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.
309  typically usage:
310  - 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.
311  - for scaling up, we assume scale_sta, scale_sto <= 0
312  */
313  real scale = -1, scale_best = -1;
314  SparseMatrix C = NULL;
315  int check_overlap_only = 1;
316  int overlap = 0;
317  real two = 2;
318  int iter = 0;
319 
320  assert(epsilon > 0);
321 
322  if (scale_sta <= 0) {
323  scale_sta = 0;
324  } else {
325  scale_coord(dim, m, x, scale_sta);
326  C = get_overlap_graph(dim, m, x, width, check_overlap_only);
327  if (!C || C->nz == 0) {
328  if (Verbose) fprintf(stderr," shrinking with %f works\n", scale_sta);
330  return scale_sta;
331  }
332  scale_coord(dim, m, x, 1./scale_sta);
334  }
335 
336  if (scale_sto < 0){
337  if (scale_sta == 0) {
338  scale_sto = epsilon;
339  } else {
340  scale_sto = scale_sta;
341  }
342  scale_coord(dim, m, x, scale_sto);
343  do {
344  scale_sto *= two;
345  scale_coord(dim, m, x, two);
346  C = get_overlap_graph(dim, m, x, width, check_overlap_only);
347  overlap = (C && C->nz > 0);
349  } while (overlap);
350  scale_coord(dim, m, x, 1/scale_sto);/* unscale */
351  }
352 
353  scale_best = scale_sto;
354  while (iter++ < maxiter && scale_sto - scale_sta > epsilon){
355 
356  if (Verbose) fprintf(stderr,"in overlap_scaling iter=%d, maxiter=%d, scaling bracket: {%f,%f}\n", iter, maxiter, scale_sta, scale_sto);
357 
358  scale = 0.5*(scale_sta + scale_sto);
359  scale_coord(dim, m, x, scale);
360  C = get_overlap_graph(dim, m, x, width, check_overlap_only);
361  scale_coord(dim, m, x, 1./scale);/* unscale */
362  overlap = (C && C->nz > 0);
364  if (overlap){
365  scale_sta = scale;
366  } else {
367  scale_best = scale_sto = scale;
368  }
369  }
370 
371  /* final scaling */
372  scale_coord(dim, m, x, scale_best);
373  return scale_best;
374 }
375 
377  int dim, real lambda0, real *x, real *width, int include_original_graph, int neighborhood_only,
378  real *max_overlap, real *min_overlap,
379  int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, int shrink
380  ){
381  OverlapSmoother sm;
382  int i, j, k, *iw, *jw, jdiag;
383  SparseMatrix B;
384  real *lambda, *d, *w, diag_d, diag_w, dist;
385 
387 
388  sm = GNEW(struct OverlapSmoother_struct);
389  sm->scheme = SM_SCHEME_NORMAL;
390  if (constr_nodes && n_constr_nodes > 0 && edge_labeling_scheme != ELSCHEME_NONE){
392  sm->data = relative_position_constraints_new(A_constr, edge_labeling_scheme, n_constr_nodes, constr_nodes);
393  sm->data_deallocator = relative_position_constraints_delete;
394  } else {
395  sm->data = NULL;
396  }
397 
398  sm->tol_cg = 0.01;
399  sm->maxit_cg = sqrt((double) A->m);
400 
401  lambda = sm->lambda = N_GNEW(m,real);
402  for (i = 0; i < m; i++) sm->lambda[i] = lambda0;
403 
404  B= call_tri(m, dim, x);
405 
406  if (!neighborhood_only){
407  SparseMatrix C, D;
408  C = get_overlap_graph(dim, m, x, width, 0);
409  D = SparseMatrix_add(B, C);
412  B = D;
413  }
414  if (include_original_graph){
415  sm->Lw = SparseMatrix_add(A, B);
417  } else {
418  sm->Lw = B;
419  }
420  sm->Lwd = SparseMatrix_copy(sm->Lw);
421 
422 #ifdef DEBUG
423  {
424  FILE *fp;
425  fp = fopen("/tmp/111","w");
426  export_embedding(fp, dim, sm->Lwd, x, NULL);
427  fclose(fp);
428  }
429 #endif
430 
431  if (!(sm->Lw) || !(sm->Lwd)) {
433  return NULL;
434  }
435 
436  assert((sm->Lwd)->type == MATRIX_TYPE_REAL);
437 
438  ideal_distance_avoid_overlap(dim, sm->Lwd, x, width, (real*) (sm->Lwd->a), max_overlap, min_overlap);
439 
440  /* no overlap at all! */
441  if (*max_overlap < 1 && shrink){
442  real scale_sta = MIN(1, *max_overlap*1.0001), scale_sto = 1;
443 
444  if (Verbose) fprintf(stderr," no overlap (overlap = %f), rescale to shrink\n", *max_overlap - 1);
445 
446  scale_sta = overlap_scaling(dim, m, x, width, scale_sta, scale_sto, 0.0001, 15);
447 
448  *max_overlap = 1;
449  goto RETURN;
450  }
451 
452  iw = sm->Lw->ia; jw = sm->Lw->ja;
453  w = (real*) sm->Lw->a; d = (real*) sm->Lwd->a;
454 
455  for (i = 0; i < m; i++){
456  diag_d = diag_w = 0;
457  jdiag = -1;
458  for (j = iw[i]; j < iw[i+1]; j++){
459  k = jw[j];
460  if (k == i){
461  jdiag = j;
462  continue;
463  }
464  if (d[j] > 0){/* those edges that needs expansion */
465  w[j] = -100/d[j]/d[j];
466  /*w[j] = 100/d[j]/d[j];*/
467  } else {/* those that needs shrinking is set to negative in ideal_distance_avoid_overlap */
468  /*w[j] = 1/d[j]/d[j];*/
469  w[j] = -1/d[j]/d[j];
470  d[j] = -d[j];
471  }
472  dist = d[j];
473  diag_w += w[j];
474  d[j] = w[j]*dist;
475  diag_d += d[j];
476 
477  }
478 
479  lambda[i] *= (-diag_w);/* alternatively don't do that then we have a constant penalty term scaled by lambda0 */
480 
481  assert(jdiag >= 0);
482  w[jdiag] = -diag_w + lambda[i];
483  d[jdiag] = -diag_d;
484  }
485  RETURN:
486  return sm;
487 }
488 
490 
492 
493 }
494 
496  int maxit_sm = 1;/* only using 1 iteration of stress majorization
497  is found to give better results and save time! */
498  real res = StressMajorizationSmoother_smooth(sm, dim, x, maxit_sm, 0.001);
499 #ifdef DEBUG
500  {FILE *fp;
501  fp = fopen("/tmp/222","w");
502  export_embedding(fp, dim, sm->Lwd, x, NULL);
503  fclose(fp);}
504 #endif
505  return res;
506 }
507 
508 /*================================= end OverlapSmoother =============*/
509 
510 static void scale_to_edge_length(int dim, SparseMatrix A, real *x, real avg_label_size){
511  real dist;
512  int i;
513 
514  if (!A) return;
515  dist = average_edge_length(A, dim, x);
516  if (Verbose) fprintf(stderr,"avg edge len=%f avg_label-size= %f\n", dist, avg_label_size);
517 
518 
519  dist = avg_label_size/MAX(dist, MACHINEACC);
520 
521  for (i = 0; i < dim*A->m; i++) x[i] *= dist;
522 }
523 
524 static void print_bounding_box(int n, int dim, real *x){
525  real *xmin, *xmax;
526  int i, k;
527 
528  xmin = N_GNEW(dim,real);
529  xmax = N_GNEW(dim,real);
530 
531  for (i = 0; i < dim; i++) xmin[i]=xmax[i] = x[i];
532 
533  for (i = 0; i < n; i++){
534  for (k = 0; k < dim; k++){
535  xmin[k] = MIN(xmin[k],x[i*dim+k]);
536  xmax[k] = MAX(xmax[k],x[i*dim+k]);
537  }
538  }
539  fprintf(stderr,"bounding box = \n");
540  for (i = 0; i < dim; i++) fprintf(stderr,"{%f,%f}, ",xmin[i], xmax[i]);
541  fprintf(stderr,"\n");
542 
543  FREE(xmin);
544  FREE(xmax);
545 }
546 
547 static int check_convergence(real max_overlap, real res, int has_penalty_terms, real epsilon){
548  if (!has_penalty_terms) return (max_overlap <= 1);
549  return res < epsilon;
550 }
551 
552 void remove_overlap(int dim, SparseMatrix A, real *x, real *label_sizes, int ntry, real initial_scaling,
553  int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, int do_shrinking, int *flag){
554  /*
555  edge_labeling_scheme: if ELSCHEME_NONE, n_constr_nodes/constr_nodes/A_constr are not used
556 
557  n_constr_nodes: number of nodes that has constraints, these are nodes that is
558  . constrained to be close to the average of its neighbors.
559  constr_nodes: a list of nodes that need to be constrained. If NULL, unused.
560  A_constr: neighbors of node i are in the row i of this matrix. i needs to sit
561  . in between these neighbors as much as possible. this must not be NULL
562  . if constr_nodes != NULL.
563 
564  */
565 
566  real lambda = 0.00;
567  OverlapSmoother sm;
568  int include_original_graph = 0, i;
569  real LARGE = 100000;
570  real avg_label_size, res = LARGE;
571  real max_overlap = 0, min_overlap = 999;
572  int neighborhood_only = TRUE;
573  int has_penalty_terms = FALSE;
574  real epsilon = 0.005;
575  int shrink = 0;
576 
577 #ifdef TIME
578  clock_t cpu;
579 #endif
580 
581 #ifdef TIME
582  cpu = clock();
583 #endif
584 
585  if (!label_sizes) return;
586 
587  if (initial_scaling < 0) {
588  avg_label_size = 0;
589  for (i = 0; i < A->m; i++) avg_label_size += label_sizes[i*dim]+label_sizes[i*dim+1];
590  /* for (i = 0; i < A->m; i++) avg_label_size += 2*MAX(label_sizes[i*dim],label_sizes[i*dim+1]);*/
591  avg_label_size /= A->m;
592  scale_to_edge_length(dim, A, x, -initial_scaling*avg_label_size);
593  } else if (initial_scaling > 0){
594  scale_to_edge_length(dim, A, x, initial_scaling);
595  }
596 
597  if (!ntry) return;
598 
599  *flag = 0;
600 
601 #ifdef DEBUG
602  _statistics[0] = _statistics[1] = 0.;
603  {FILE*fp;
604  fp = fopen("x1","w");
605  for (i = 0; i < A->m; i++){
606  fprintf(fp, "%f %f\n",x[i*2],x[i*2+1]);
607  }
608  fclose(fp);
609  }
610 #endif
611 
612 #ifdef ANIMATE
613  {FILE*fp;
614  fp = fopen("/tmp/m","wa");
615  fprintf(fp,"{");
616 #endif
617 
618  has_penalty_terms = (edge_labeling_scheme != ELSCHEME_NONE && n_constr_nodes > 0);
619  for (i = 0; i < ntry; i++){
620  if (Verbose) print_bounding_box(A->m, dim, x);
621  sm = OverlapSmoother_new(A, A->m, dim, lambda, x, label_sizes, include_original_graph, neighborhood_only,
622  &max_overlap, &min_overlap, edge_labeling_scheme, n_constr_nodes, constr_nodes, A_constr, shrink);
623  if (Verbose) fprintf(stderr, "overlap removal neighbors only?= %d iter -- %d, overlap factor = %g underlap factor = %g\n", neighborhood_only, i, max_overlap - 1, min_overlap);
624  if (check_convergence(max_overlap, res, has_penalty_terms, epsilon)){
625 
627  if (neighborhood_only == FALSE){
628  break;
629  } else {
630  res = LARGE;
631  neighborhood_only = FALSE; if (do_shrinking) shrink = 1;
632  continue;
633  }
634  }
635 
636  res = OverlapSmoother_smooth(sm, dim, x);
637  if (Verbose) fprintf(stderr,"res = %f\n",res);
638 #ifdef ANIMATE
639  if (i != 0) fprintf(fp,",");
640  export_embedding(fp, dim, A, x, label_sizes);
641 #endif
643  }
644  if (Verbose) fprintf(stderr, "overlap removal neighbors only?= %d iter -- %d, overlap factor = %g underlap factor = %g\n", neighborhood_only, i, max_overlap - 1, min_overlap);
645 
646 #ifdef ANIMATE
647  fprintf(fp,"}");
648  fclose(fp);
649  }
650 #endif
651 
652  if (has_penalty_terms){
653  /* now do without penalty */
654  remove_overlap(dim, A, x, label_sizes, ntry, 0.,
655  ELSCHEME_NONE, 0, NULL, NULL, do_shrinking, flag);
656  }
657 
658 #ifdef DEBUG
659  fprintf(stderr," number of cg iter = %f, number of stress majorization iter = %f number of overlap removal try = %d\n",
660  _statistics[0], _statistics[1], i - 1);
661 
662  {FILE*fp;
663  fp = fopen("x2","w");
664  for (i = 0; i < A->m; i++){
665  fprintf(fp, "%f %f\n",x[i*2],x[i*2+1]);
666  }
667  fclose(fp);
668  }
669 #endif
670 
671 #ifdef DEBUG
672  {FILE*fp;
673  fp = fopen("/tmp/m","w");
674  if (A) export_embedding(fp, dim, A, x, label_sizes);
675  fclose(fp);
676  }
677 #endif
678 #ifdef TIME
679  fprintf(stderr, "post processing %f\n",((real) (clock() - cpu)) / CLOCKS_PER_SEC);
680 #endif
681 }
682 
683 #else
684 #include "types.h"
685 #include "SparseMatrix.h"
686 void remove_overlap(int dim, SparseMatrix A, int m, real *x, real *label_sizes, int ntry, real initial_scaling, int do_shrinking, int *flag)
687 {
688  static int once;
689 
690  if (once == 0) {
691  once = 1;
692  agerr(AGERR, "remove_overlap: Graphviz not built with triangulation library\n");
693  }
694 }
695 #endif
#define MAX(a, b)
Definition: agerror.c:17
void StressMajorizationSmoother_delete(StressMajorizationSmoother sm)
Definition: cgraph.h:388
#define ABS(a)
Definition: arith.h:45
double xmax
Definition: geometry.c:20
#define MIN(a, b)
Definition: arith.h:35
real OverlapSmoother_smooth(OverlapSmoother sm, int dim, real *x)
SparseMatrix SparseMatrix_copy(SparseMatrix A)
#define C
Definition: pack.c:29
#define FREE
Definition: PriorityQueue.c:23
SparseMatrix SparseMatrix_new(int m, int n, int nz, int type, int format)
Definition: SparseMatrix.c:384
#define assert(x)
Definition: cghdr.h:47
OverlapSmoother OverlapSmoother_new(SparseMatrix A, int m, int dim, real lambda0, real *x, real *width, int include_original_graph, int neighborhood_only, real *max_overlap, real *min_overlap, int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, int shrink)
void InfoPrint(void *a)
rb_red_blk_node * nil
rb_red_blk_node * RBTreeInsert(rb_red_blk_tree *tree, void *key, void *info)
void InfoDest(void *a)
double xmin
Definition: geometry.c:20
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
real distance(real *x, int dim, int i, int j)
int SparseMatrix_is_symmetric(SparseMatrix A, int test_pattern_symmetry_only)
Definition: SparseMatrix.c:178
void(* PrintKey)(const void *a)
void OverlapSmoother_delete(OverlapSmoother sm)
void export_embedding(FILE *fp, int dim, SparseMatrix A, real *x, real *width)
void RBDelete(rb_red_blk_tree *tree, rb_red_blk_node *z)
real overlap_scaling(int dim, int m, real *x, real *width, real scale_sta, real scale_sto, real epsilon, int maxiter)
real average_edge_length(SparseMatrix A, int dim, real *coord)
#define overlap(pb, qb)
Definition: constraint.c:549
real StressMajorizationSmoother_smooth(StressMajorizationSmoother sm, int dim, real *x, int maxit_sm, real tol)
Definition: post_process.c:812
#define MALLOC
Definition: PriorityQueue.c:21
SparseMatrix SparseMatrix_symmetrize(SparseMatrix A, int pattern_symmetric_only)
Definition: SparseMatrix.c:151
void SparseMatrix_delete(SparseMatrix A)
Definition: SparseMatrix.c:411
struct relative_position_constraints_struct * relative_position_constraints
Definition: overlap.h:51
SparseMatrix call_tri(int n, int dim, real *x)
Definition: call_tri.c:21
#define NULL
Definition: logic.h:39
#define GNEW(t)
Definition: memory.h:37
Definition: post_process.h:19
EXTERN unsigned char Verbose
Definition: globals.h:64
Definition: post_process.h:19
rb_red_blk_tree * RBTreeCreate(int(*CompFunc)(const void *, const void *), void(*DestFunc)(void *), void(*InfoDestFunc)(void *), void(*PrintFunc)(const void *), void(*PrintInfo)(void *))
Agnode_t * node(Agraph_t *g, char *name)
Definition: gv.cpp:103
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)
double dist(Site *s, Site *t)
Definition: site.c:41
#define OverlapSmoother_struct
Definition: overlap.h:21
SparseMatrix SparseMatrix_add(SparseMatrix A, SparseMatrix B)
Definition: SparseMatrix.c:966
SparseMatrix SparseMatrix_coordinate_form_add_entries(SparseMatrix A, int nentries, int *irn, int *jcn, void *val)
#define MACHINEACC
Definition: general.h:120
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define FALSE
Definition: cgraph.h:35
SparseMatrix SparseMatrix_from_coordinate_format(SparseMatrix A)
Definition: SparseMatrix.c:797
Definition: legal.c:60
void remove_overlap(int dim, SparseMatrix A, int m, real *x, real *label_sizes, int ntry, real initial_scaling, int do_shrinking, int *flag)
Definition: overlap.c:686
#define TRUE
Definition: cgraph.h:38
#define real
Definition: general.h:34