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
27static 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;
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 = 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
80enum {INTV_OPEN, INTV_CLOSE};
81
82struct scan_point_struct{
83 int node;
84 real x;
85 int status;
86};
87
88typedef struct scan_point_struct scan_point;
89
90
91static 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
110void NodeDest(void* a) {
111 /* free((int*)a);*/
112}
113
114
115
116int NodeComp(const void* a,const void* b) {
117 return comp_scan_points(a,b);
118
119}
120
121void 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
129void InfoPrint(void* a) {
130 ;
131}
132
133void InfoDest(void *a){
134 ;
135}
136
137static 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
146 A = SparseMatrix_new(n, n, 1, MATRIX_TYPE_REAL, FORMAT_COORD);
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
251check_overlap_RETURN:
252 FREE(scanpointsx);
253 FREE(scanpointsy);
254 RBTreeDestroy(treey);
255
256 B = SparseMatrix_from_coordinate_format(A);
257 SparseMatrix_delete(A);
258 A = SparseMatrix_symmetrize(B, FALSE);
259 SparseMatrix_delete(B);
260 if (Verbose) fprintf(stderr, "found %d clashes\n", A->nz);
261 return A;
262}
263
264
265
266/* ============================== label overlap smoother ==================*/
267
268
269static void relative_position_constraints_delete(void *d){
270 relative_position_constraints data;
271 if (!d) return;
272 data = (relative_position_constraints) d;
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
280static relative_position_constraints relative_position_constraints_new(SparseMatrix A_constr, int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes){
281 relative_position_constraints data;
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}
295static 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
302real 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);
329 SparseMatrix_delete(C);
330 return scale_sta;
331 }
332 scale_coord(dim, m, x, 1./scale_sta);
333 SparseMatrix_delete(C);
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);
348 SparseMatrix_delete(C);
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);
363 SparseMatrix_delete(C);
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
376OverlapSmoother OverlapSmoother_new(SparseMatrix A, int m,
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
386 assert((!A) || SparseMatrix_is_symmetric(A, FALSE));
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){
391 sm->scheme = SM_SCHEME_NORMAL_ELABEL;
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);
410 SparseMatrix_delete(B);
411 SparseMatrix_delete(C);
412 B = D;
413 }
414 if (include_original_graph){
415 sm->Lw = SparseMatrix_add(A, B);
416 SparseMatrix_delete(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)) {
432 OverlapSmoother_delete(sm);
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
489void OverlapSmoother_delete(OverlapSmoother sm){
490
491 StressMajorizationSmoother_delete(sm);
492
493}
494
495real OverlapSmoother_smooth(OverlapSmoother sm, int dim, real *x){
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
510static 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
524static 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
547static 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
552void 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
626 OverlapSmoother_delete(sm);
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
642 OverlapSmoother_delete(sm);
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"
686void 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
696