From ab6efcd006b81fa8e5df0f9432a9e4856b75c1d5 Mon Sep 17 00:00:00 2001 From: erg Date: Mon, 28 Feb 2011 16:17:40 +0000 Subject: [PATCH] Add new functions and features for sfdp and gvmap --- lib/neatogen/adjust.c | 50 +++++++++++-- lib/neatogen/adjust.h | 4 +- lib/neatogen/delaunay.c | 84 +++++++++++++++++++++ lib/neatogen/delaunay.h | 2 + lib/neatogen/overlap.c | 162 ++++++++++++++++++++++++++++------------ lib/neatogen/overlap.h | 38 ++++++++-- 6 files changed, 276 insertions(+), 64 deletions(-) diff --git a/lib/neatogen/adjust.c b/lib/neatogen/adjust.c index 7fcdfd99f..678389257 100644 --- a/lib/neatogen/adjust.c +++ b/lib/neatogen/adjust.c @@ -655,21 +655,40 @@ static void updateGraph(Agraph_t * graph) } } +#define ELS "|edgelabel|" +#define ELSN (sizeof(ELS)-1) + /* Return true if node name starts with ELS */ +#define IS_LNODE(n) (!strncmp(agnameof(n),ELS,ELSN)) + /* getSizes: * Set up array of half sizes in inches. */ -double *getSizes(Agraph_t * g, pointf pad) +double *getSizes(Agraph_t * g, pointf pad, int* n_elabels, int** elabels) { Agnode_t *n; real *sizes = N_GNEW(2 * agnnodes(g), real); - int i; + int i, nedge_nodes; + int* elabs; for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + if (elabels && IS_LNODE(n)) nedge_nodes++; + i = ND_id(n); sizes[i * 2] = ND_width(n) * .5 + pad.x; sizes[i * 2 + 1] = ND_height(n) * .5 + pad.y; } + if (elabels && nedge_nodes) { + elabs = N_GNEW(nedge_nodes, int); + nedge_nodes = 0; + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + if (IS_LNODE(n)) + elabs[nedge_nodes++] = ND_id(n); + } + *elabels = elabs; + *n_elabels = nedge_nodes; + } + return sizes; } @@ -677,7 +696,7 @@ double *getSizes(Agraph_t * g, pointf pad) * Assumes g is connected and simple, i.e., we can have a->b and b->a * but not a->b and a->b */ -SparseMatrix makeMatrix(Agraph_t * g, int dim) +SparseMatrix makeMatrix(Agraph_t* g, int dim, SparseMatrix *D) { SparseMatrix A = 0; Agnode_t *n; @@ -691,6 +710,8 @@ SparseMatrix makeMatrix(Agraph_t * g, int dim) real *val; real v; int type = MATRIX_TYPE_REAL; + Agsym_t* symD = NULL; + real* valD = NULL; if (!g) return NULL; @@ -707,6 +728,11 @@ SparseMatrix makeMatrix(Agraph_t * g, int dim) val = N_GNEW(nedges, real); sym = agfindedgeattr(g, "weight"); + if (D) { + symD = agfindedgeattr(g, "len"); + valD = N_NEW(nedges, real); + } + i = 0; for (n = agfstnode(g); n; n = agnxtnode(g, n)) { row = ND_id(n); @@ -720,6 +746,14 @@ SparseMatrix makeMatrix(Agraph_t * g, int dim) #endif v = 1; val[i] = v; + /* edge length */ + if (symD) { +#ifndef WITH_CGRAPH +#else + if (sscanf (agxget (e, symD->index), "%lf", &v) != 1) v = 1; +#endif + valD[i] = v; + } i++; } } @@ -727,9 +761,12 @@ SparseMatrix makeMatrix(Agraph_t * g, int dim) A = SparseMatrix_from_coordinate_arrays(nedges, nnodes, nnodes, I, J, val, type); + if (D) *D = SparseMatrix_from_coordinate_arrays(nedges, nnodes, nnodes, I, J, valD, type); + free(I); free(J); free(val); + if (valD) free (valD); return A; } @@ -738,7 +775,7 @@ SparseMatrix makeMatrix(Agraph_t * g, int dim) static int fdpAdjust (graph_t* g, adjust_data* am) { - SparseMatrix A0 = makeMatrix(g, Ndim); + SparseMatrix A0 = makeMatrix(g, Ndim, NULL); SparseMatrix A = A0; real *sizes; real *pos = N_NEW(Ndim * agnnodes(g), real); @@ -754,7 +791,7 @@ fdpAdjust (graph_t* g, adjust_data* am) pad.x = PS2INCH(DFLT_MARGIN); pad.y = PS2INCH(DFLT_MARGIN); } - sizes = getSizes(g, pad); + sizes = getSizes(g, pad, NULL, NULL); for (n = agfstnode(g); n; n = agnxtnode(g, n)) { real* npos = pos + (Ndim * ND_id(n)); @@ -770,7 +807,8 @@ fdpAdjust (graph_t* g, adjust_data* am) A = SparseMatrix_remove_diagonal(A); } - remove_overlap(Ndim, A, A->m, pos, sizes, am->value, am->scaling, &flag); + remove_overlap(Ndim, A, pos, sizes, am->value, am->scaling, + ELSCHEME_NONE, 0, NULL, NULL, &flag); for (n = agfstnode(g); n; n = agnxtnode(g, n)) { real *npos = pos + (Ndim * ND_id(n)); diff --git a/lib/neatogen/adjust.h b/lib/neatogen/adjust.h index 9c0c9ba00..31fbbc37b 100644 --- a/lib/neatogen/adjust.h +++ b/lib/neatogen/adjust.h @@ -54,8 +54,8 @@ typedef struct { extern int cAdjust(graph_t *, int); extern int scAdjust(graph_t *, int); extern adjust_data *graphAdjustMode(graph_t *G, adjust_data*, char* dflt); - extern double *getSizes(Agraph_t * g, pointf pad); - extern SparseMatrix makeMatrix(Agraph_t * g, int dim); + extern double *getSizes(Agraph_t * g, pointf pad, int *n_elabels, int **elabels); + extern SparseMatrix makeMatrix(Agraph_t* g, int dim, SparseMatrix *D); #ifdef __cplusplus } diff --git a/lib/neatogen/delaunay.c b/lib/neatogen/delaunay.c index 161a3b828..bce17a334 100644 --- a/lib/neatogen/delaunay.c +++ b/lib/neatogen/delaunay.c @@ -469,6 +469,17 @@ mkSurface (double *x, double *y, int n, int* segs, int nsegs) return sf; } +int* +get_triangles (double *x, int n, int* tris) +{ + int* trilist = NULL; + + if (n <= 2) return NULL; + agerr (AGERR, "get_triangles not yet implemented using GTS library\n"); + + return trilist; +} + void freeSurface (surface_t* s) { @@ -481,6 +492,74 @@ freeSurface (surface_t* s) #include "triangle.c" #include "assert.h" +int* +get_triangles (double *x, int n, int* tris) +{ + struct triangulateio in, mid, vorout; + + if (n <= 2) return NULL; + + in.numberofpoints = n; + in.numberofpointattributes = 0; + in.pointlist = (REAL *) N_GNEW(in.numberofpoints * 2, REAL); + + for (i = 0; i < n; i++){ + in.pointlist[i*2] = x[i*2]; + in.pointlist[i*2 + 1] = x[i*2 + 1]; + } + in.pointattributelist = NULL; + in.pointmarkerlist = NULL; + in.numberofsegments = 0; + in.numberofholes = 0; + in.numberofregions = 0; + in.regionlist = NULL; + mid.pointlist = (REAL *) NULL; /* Not needed if -N switch used. */ + mid.pointattributelist = (REAL *) NULL; + mid.pointmarkerlist = (int *) NULL; /* Not needed if -N or -B switch used. */ + mid.trianglelist = (int *) NULL; /* Not needed if -E switch used. */ + mid.triangleattributelist = (REAL *) NULL; + mid.neighborlist = (int *) NULL; /* Needed only if -n switch used. */ + mid.segmentlist = (int *) NULL; + mid.segmentmarkerlist = (int *) NULL; + mid.edgelist = (int *) NULL; /* Needed only if -e switch used. */ + mid.edgemarkerlist = (int *) NULL; /* Needed if -e used and -B not used. */ + vorout.pointlist = (REAL *) NULL; /* Needed only if -v switch used. */ + vorout.pointattributelist = (REAL *) NULL; + vorout.edgelist = (int *) NULL; /* Needed only if -v switch used. */ + vorout.normlist = (REAL *) NULL; /* Needed only if -v switch used. */ + + /* Triangulate the points. Switches are chosen to read and write a */ + /* PSLG (p), preserve the convex hull (c), number everything from */ + /* zero (z), assign a regional attribute to each element (A), and */ + /* produce an edge list (e), a Voronoi diagram (v), and a triangle */ + /* neighbor list (n). */ + + triangulate("Qenv", &in, &mid, &vorout); + assert (mid.numberofcorners == 3); + + *tris = mid.numberoftriangles; + + FREE(in.pointlist); + FREE(in.pointattributelist); + FREE(in.pointmarkerlist); + FREE(in.regionlist); + FREE(mid.pointlist); + FREE(mid.pointattributelist); + FREE(mid.pointmarkerlist); + FREE(mid.triangleattributelist); + FREE(mid.neighborlist); + FREE(mid.segmentlist); + FREE(mid.segmentmarkerlist); + FREE(mid.edgelist); + FREE(mid.edgemarkerlist); + FREE(vorout.pointlist); + FREE(vorout.pointattributelist); + FREE(vorout.edgelist); + FREE(vorout.normlist); + + return mid.trianglelist; +} + // maybe it should be replaced by RNG - relative neigborhood graph, or by GG - gabriel graph int* delaunay_tri (double *x, double *y, int n, int* nedges) @@ -609,6 +688,11 @@ freeSurface (surface_t* s) } #else static char* err = "Graphviz built without any triangulation library\n"; +int* get_triangles (double *x, int n, int* tris) +{ + agerr(AGERR, "get_triangles: %s\n", err); + return 0; +} v_data *delaunay_triangulation(double *x, double *y, int n) { agerr(AGERR, "delaunay_triangulation: %s\n", err); diff --git a/lib/neatogen/delaunay.h b/lib/neatogen/delaunay.h index 7bdc8efb8..c178a5a93 100644 --- a/lib/neatogen/delaunay.h +++ b/lib/neatogen/delaunay.h @@ -28,6 +28,8 @@ v_data *delaunay_triangulation(double *x, double *y, int n); int *delaunay_tri (double *x, double *y, int n, int* nedges); +int *get_triangles (double *x, int n, int* ntris); + v_data *UG_graph(double *x, double *y, int n, int accurate_computation); surface_t* mkSurface (double *x, double *y, int n, int* segs, int nsegs); diff --git a/lib/neatogen/overlap.c b/lib/neatogen/overlap.c index 2dc4d6ad8..d4978c40e 100644 --- a/lib/neatogen/overlap.c +++ b/lib/neatogen/overlap.c @@ -25,21 +25,6 @@ #include "memory.h" #include "globals.h" #include -#define MALLOC gmalloc -#define REALLOC grealloc -#define FREE free -#define MEMCPY memcpy - -#define MACHINEACC 1.0e-16 - -#ifndef SMOOTHER -#include "post_process.h" - -typedef StressMajorizationSmoother OverlapSmoother; - -#define OverlapSmoother_struct StressMajorizationSmoother_struct - -#endif static void ideal_distance_avoid_overlap(int dim, SparseMatrix A, real *x, real *width, real *ideal_distance, real *tmax, real *tmin){ /* if (x1>x2 && y1 > y2) we want either x1 + t (x1-x2) - x2 > (width1+width2), or y1 + t (y1-y2) - y2 > (height1+height2), @@ -218,7 +203,7 @@ static SparseMatrix get_overlap_graph(int dim, int n, real *x, real *width){ #endif assert(treey->nil != newNode); - while (((newNode = TreePredecessor(treey, newNode)) != treey->nil) && ((scan_point *)newNode->key)->node != k){ + while ((newNode) && ((newNode = TreePredecessor(treey, newNode)) != treey->nil) && ((scan_point *)newNode->key)->node != k){ neighbor = (((scan_point *)newNode->key)->node)%n; A = SparseMatrix_coordinate_form_add_entries(A, 1, &neighbor, &k, &one); #ifdef DEBUG_RBTREE @@ -232,7 +217,7 @@ static SparseMatrix get_overlap_graph(int dim, int n, real *x, real *width){ treey->PrintKey(newNode0->key); #endif - RBDelete(treey,newNode0); + if (newNode0) RBDelete(treey,newNode0); if (newNode != treey->nil && newNode != newNode0) { #ifdef DEBUG_RBTREE @@ -240,7 +225,7 @@ static SparseMatrix get_overlap_graph(int dim, int n, real *x, real *width){ treey->PrintKey(newNode->key) #endif - RBDelete(treey,newNode); + if (newNode0) RBDelete(treey,newNode); } } } @@ -262,15 +247,38 @@ static SparseMatrix get_overlap_graph(int dim, int n, real *x, real *width){ /* ============================== label overlap smoother ==================*/ -void OverlapSmoother_delete(OverlapSmoother sm){ - - StressMajorizationSmoother_delete(sm); +static void relative_position_constraints_delete(void *d){ + relative_position_constraints data; + if (!d) return; + data = (relative_position_constraints) d; + if (data->irn) FREE(data->irn); + if (data->jcn) FREE(data->jcn); + if (data->val) FREE(data->val); + /* other stuff inside relative_position_constraints is assed back to the user hence no need to deallocator*/ + FREE(d); +} +static relative_position_constraints relative_position_constraints_new(SparseMatrix A_constr, int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes){ + relative_position_constraints data; + assert(A_constr); + data = MALLOC(sizeof(struct relative_position_constraints_struct)); + data->constr_penalty = 1; + data->edge_labeling_scheme = edge_labeling_scheme; + data->n_constr_nodes = n_constr_nodes; + data->constr_nodes = constr_nodes; + data->A_constr = A_constr; + data->irn = NULL; + data->jcn = NULL; + data->val = NULL; + + return data; } 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 shrink){ + real *max_overlap, real *min_overlap, + int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, int shrink + ){ OverlapSmoother sm; int i, j, k, *iw, *jw, *id, *jd, jdiag; SparseMatrix B; @@ -278,9 +286,16 @@ OverlapSmoother OverlapSmoother_new(SparseMatrix A, int m, assert((!A) || SparseMatrix_is_symmetric(A, FALSE)); - assert((!A) || m == A->m); + sm = GNEW(struct OverlapSmoother_struct); + sm->scheme = SM_SCHEME_NORMAL; + if (constr_nodes && n_constr_nodes > 0 && edge_labeling_scheme != ELSCHEME_NONE){ + sm->scheme = SM_SCHEME_NORMAL_ELABEL; + sm->data = relative_position_constraints_new(A_constr, edge_labeling_scheme, n_constr_nodes, constr_nodes); + sm->data_deallocator = relative_position_constraints_delete; + } else { + sm->data = NULL; + } - sm = N_GNEW(1, struct OverlapSmoother_struct); lambda = sm->lambda = N_GNEW(m,real); for (i = 0; i < m; i++) sm->lambda[i] = lambda0; @@ -344,9 +359,11 @@ OverlapSmoother OverlapSmoother_new(SparseMatrix A, int m, continue; } if (d[j] > 0){/* those edges that needs expansion */ - w[j] = 100/d[j]/d[j]; + w[j] = -100/d[j]/d[j]; + /*w[j] = 100/d[j]/d[j];*/ } else {/* those that needs shrinking is set to negative in ideal_distance_avoid_overlap */ - w[j] = 1/d[j]/d[j]; + /*w[j] = 1/d[j]/d[j];*/ + w[j] = -1/d[j]/d[j]; d[j] = -d[j]; } dist = d[j]; @@ -366,16 +383,23 @@ OverlapSmoother OverlapSmoother_new(SparseMatrix A, int m, return sm; } -void OverlapSmoother_smooth(OverlapSmoother sm, int dim, real *x){ +void OverlapSmoother_delete(OverlapSmoother sm){ + + StressMajorizationSmoother_delete(sm); + +} + +real OverlapSmoother_smooth(OverlapSmoother sm, int dim, real *x){ int maxit_sm = 1;/* only using 1 iteration of stress majorization is found to give better results and save time! */ - StressMajorizationSmoother_smooth(sm, dim, x, maxit_sm); + real res = StressMajorizationSmoother_smooth(sm, dim, x, maxit_sm, 0.001); #ifdef DEBUG {FILE *fp; fp = fopen("/tmp/222","w"); export_embedding(fp, dim, sm->Lwd, x, NULL); fclose(fp);} #endif + return res; } /*================================= end OverlapSmoother =============*/ @@ -417,16 +441,36 @@ static void print_bounding_box(int n, int dim, real *x){ FREE(xmax); } +static int check_convergence(real max_overlap, real res, int has_penalty_terms, real epsilon){ + if (!has_penalty_terms) return (max_overlap <= 1); + return res < epsilon; +} + +void remove_overlap(int dim, SparseMatrix A, real *x, real *label_sizes, int ntry, real initial_scaling, + int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, int *flag){ + /* + edge_labeling_scheme: if ELSCHEME_NONE, n_constr_nodes/constr_nodes/A_constr are not used + + n_constr_nodes: number of nodes that has constraints, these are nodes that is + . constrained to be close to the average of its neighbors. + constr_nodes: a list of nodes that need to be constrained. If NULL, unused. + A_constr: neighbors of node i are in the row i of this matrix. i needs to sit + . in between these neighbors as much as possible. this must not be NULL + . if constr_nodes != NULL. + + */ -void remove_overlap(int dim, SparseMatrix A, int m, real *x, real *label_sizes, int ntry, real initial_scaling, int *flag){ real lambda = 0.00; OverlapSmoother sm; int include_original_graph = 0, i; - real avg_label_size; + real LARGE = 100000; + real avg_label_size, res = LARGE; real max_overlap = 0, min_overlap = 999; int neighborhood_only = TRUE; + int has_penalty_terms = FALSE; + real epsilon = 0.005; int shrink = 0; - + #ifdef TIME clock_t cpu; #endif @@ -435,21 +479,19 @@ void remove_overlap(int dim, SparseMatrix A, int m, real *x, real *label_sizes, cpu = clock(); #endif - if (!label_sizes) return; - + if (!label_sizes) return; if (initial_scaling < 0) { avg_label_size = 0; - for (i = 0; i < m; i++) avg_label_size += label_sizes[i*dim]+label_sizes[i*dim+1]; - /* for (i = 0; i < m; i++) avg_label_size += 2*MAX(label_sizes[i*dim],label_sizes[i*dim+1]);*/ - avg_label_size /= m; + for (i = 0; i < A->m; i++) avg_label_size += label_sizes[i*dim]+label_sizes[i*dim+1]; + /* for (i = 0; i < A->m; i++) avg_label_size += 2*MAX(label_sizes[i*dim],label_sizes[i*dim+1]);*/ + avg_label_size /= A->m; scale_to_edge_length(dim, A, x, -initial_scaling*avg_label_size); - } - else if (initial_scaling > 0) { + } else if (initial_scaling > 0){ scale_to_edge_length(dim, A, x, initial_scaling); } - if (!ntry) return; + if (!ntry) return; *flag = 0; @@ -457,34 +499,58 @@ void remove_overlap(int dim, SparseMatrix A, int m, real *x, real *label_sizes, _statistics[0] = _statistics[1] = 0.; {FILE*fp; fp = fopen("x1","w"); - for (i = 0; i < m; i++){ + for (i = 0; i < A->m; i++){ fprintf(fp, "%f %f\n",x[i*2],x[i*2+1]); } fclose(fp); } #endif +#ifdef ANIMATE + {FILE*fp; + fp = fopen("/tmp/m","wa"); + fprintf(fp,"{"); +#endif + has_penalty_terms = (edge_labeling_scheme != ELSCHEME_NONE && n_constr_nodes > 0); for (i = 0; i < ntry; i++){ - if (Verbose) print_bounding_box(m, dim, x); - sm = OverlapSmoother_new(A, m, dim, lambda, x, label_sizes, include_original_graph, neighborhood_only, - &max_overlap, &min_overlap, shrink); + if (Verbose) print_bounding_box(A->m, dim, x); + sm = OverlapSmoother_new(A, A->m, dim, lambda, x, label_sizes, include_original_graph, neighborhood_only, + &max_overlap, &min_overlap, edge_labeling_scheme, n_constr_nodes, constr_nodes, A_constr, shrink); 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); - if (max_overlap <= 1){ + if (check_convergence(max_overlap, res, has_penalty_terms, epsilon)){ + OverlapSmoother_delete(sm); if (neighborhood_only == FALSE){ break; } else { + res = LARGE; neighborhood_only = FALSE; shrink = 1; continue; } } - OverlapSmoother_smooth(sm, dim, x); - + res = OverlapSmoother_smooth(sm, dim, x); + if (Verbose) fprintf(stderr,"res = %f\n",res); +#ifdef ANIMATE + if (i != 0) fprintf(fp,","); + export_embedding(fp, dim, A, x, label_sizes); +#endif + OverlapSmoother_delete(sm); + } + 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); +#ifdef ANIMATE + fprintf(fp,"}"); + fclose(fp); + } +#endif - OverlapSmoother_delete(sm); + if (has_penalty_terms){ + /* now do without penalty */ + remove_overlap(dim, A, x, label_sizes, ntry, 0., + ELSCHEME_NONE, 0, NULL, NULL, flag); } #ifdef DEBUG @@ -493,7 +559,7 @@ void remove_overlap(int dim, SparseMatrix A, int m, real *x, real *label_sizes, {FILE*fp; fp = fopen("x2","w"); - for (i = 0; i < m; i++){ + for (i = 0; i < A->m; i++){ fprintf(fp, "%f %f\n",x[i*2],x[i*2+1]); } fclose(fp); diff --git a/lib/neatogen/overlap.h b/lib/neatogen/overlap.h index d3a6efad6..06f82ed42 100644 --- a/lib/neatogen/overlap.h +++ b/lib/neatogen/overlap.h @@ -14,7 +14,6 @@ #ifndef OVERLAP_H #define OVERLAP_H -#ifdef SMOOTHER #include "post_process.h" typedef StressMajorizationSmoother OverlapSmoother; @@ -23,14 +22,37 @@ typedef StressMajorizationSmoother OverlapSmoother; void OverlapSmoother_delete(OverlapSmoother sm); -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 shrink); +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 OverlapSmoother_smooth(OverlapSmoother sm, int dim, real *x); +enum {ELSCHEME_NONE = 0, ELSCHEME_PENALTY, ELSCHEME_PENALTY2, ELSCHEME_STRAIGHTLINE_PENALTY, ELSCHEME_STRAIGHTLINE_PENALTY2}; -#else -#include "SparseMatrix.h" -#endif +struct relative_position_constraints_struct{ + real constr_penalty; /* penalty parameter used in making edge labels as much on the line as possible */ + int edge_labeling_scheme;/* specifying whether to treat node of the form |edgelabel|* as a special node representing an edge label. + 0 (no action, default), 1 (penalty based method to make that kind of node close to the center of its neighbor), + 2 (penalty based method to make that kind of node close to the "old" center of its neighbor), + 3 (two step process of overlap removal and straightening) */ + int n_constr_nodes;/*n_constr_nodes: number of nodes that has constraints, these are nodes that is + constrained to be close to the average of its neighbors.*/ + int *constr_nodes;/*constr_nodes: a list of nodes that need to be constrained. If NULL, unused.*/ + int *irn;/* working arrays to hold the Laplacian of the constrain graph */ + int *jcn; + real *val; + SparseMatrix A_constr; /*A_constr: neighbors of node i are in the row i of this matrix. i needs to sit + in between these neighbors as much as possible. this must not be NULL + if constr_nodes != NULL.*/ + +}; + +typedef struct relative_position_constraints_struct* relative_position_constraints; + +real OverlapSmoother_smooth(OverlapSmoother sm, int dim, real *x); + +void remove_overlap(int dim, SparseMatrix A, real *x, real *label_sizes, int ntry, real initial_scaling, + int edge_labeling_scheme, int n_constr_nodes, int *constr_nodes, SparseMatrix A_constr, int *flag); -void remove_overlap(int dim, SparseMatrix A, int m, real *x, real *label_sizes, int ntry, real initial_scaling, int *flag); #endif -- 2.40.0