From e095893f5c00089bd144ba494d5f62558e5c7d8b Mon Sep 17 00:00:00 2001 From: Emden Gansner Date: Thu, 5 Jan 2012 17:04:26 -0500 Subject: [PATCH] Remove use of exit() from neatogen --- lib/neatogen/adjust.c | 18 +- lib/neatogen/compute_hierarchy.c | 146 ++-- lib/neatogen/conjgrad.c | 40 +- lib/neatogen/conjgrad.h | 6 +- lib/neatogen/constrained_majorization.c | 763 ++++++++++-------- lib/neatogen/constrained_majorization_ipsep.c | 49 +- lib/neatogen/digcola.h | 6 +- lib/neatogen/fPQ.h | 7 +- lib/neatogen/legal.c | 12 +- lib/neatogen/multispline.c | 17 +- lib/neatogen/neatoinit.c | 14 +- lib/neatogen/opt_arrangement.c | 112 +-- lib/neatogen/poly.c | 10 +- lib/neatogen/poly.h | 4 +- lib/neatogen/quad_prog_vpsc.c | 4 +- lib/neatogen/smart_ini_x.c | 11 +- lib/neatogen/stress.c | 59 +- 17 files changed, 703 insertions(+), 575 deletions(-) diff --git a/lib/neatogen/adjust.c b/lib/neatogen/adjust.c index 9bef15874..8c15e2e85 100644 --- a/lib/neatogen/adjust.c +++ b/lib/neatogen/adjust.c @@ -148,13 +148,13 @@ static void chkBoundBox(Agraph_t * graph) /* makeInfo: * For each node in the graph, create a Info data structure */ -static void makeInfo(Agraph_t * graph) +static int makeInfo(Agraph_t * graph) { Agnode_t *node; int i; Info_t *ip; expand_t pmargin; - void (*polyf)(Poly *, Agnode_t *, float, float); + int (*polyf)(Poly *, Agnode_t *, float, float); nsites = agnnodes(graph); geominit(); @@ -178,7 +178,11 @@ static void makeInfo(Agraph_t * graph) ip->site.coord.x = ND_pos(node)[0]; ip->site.coord.y = ND_pos(node)[1]; - polyf(&ip->poly, node, pmargin.x, pmargin.y); + if (polyf(&ip->poly, node, pmargin.x, pmargin.y)) { + free (nodeInfo); + nodeInfo = NULL; + return 1; + } ip->site.sitenbr = i; ip->site.refcnt = 1; @@ -187,6 +191,7 @@ static void makeInfo(Agraph_t * graph) node = agnxtnode(graph, node); ip++; } + return 0; } /* sort sites on y, then x, coord */ @@ -1108,7 +1113,12 @@ removeOverlapWith (graph_t * G, adjust_data* am) /* create main array */ /* start_timer(); */ - makeInfo(G); + if (makeInfo(G)) { + freeNodes(); + free(sites); + sites = 0; + return 0; + } /* establish and verify bounding box */ chkBoundBox(G); diff --git a/lib/neatogen/compute_hierarchy.c b/lib/neatogen/compute_hierarchy.c index 59667dec9..1602a7549 100644 --- a/lib/neatogen/compute_hierarchy.c +++ b/lib/neatogen/compute_hierarchy.c @@ -15,7 +15,7 @@ #ifdef DIGCOLA #include "kkutils.h" -static int* given_levels = NULL; +static int *given_levels = NULL; /* * This function partitions the graph nodes into levels * according to the minimizer of the hierarchy energy. @@ -46,90 +46,92 @@ static int* given_levels = NULL; * Please note that 'ordering[levels[i]]' contains the first node at level i+1, * and not the last node of level i. */ -double -compute_hierarchy(vtx_data* graph, int n, double abs_tol, double relative_tol, - double* given_coords, int** orderingp, int** levelsp, int* num_levelsp) +int +compute_hierarchy(vtx_data * graph, int n, double abs_tol, + double relative_tol, double *given_coords, + int **orderingp, int **levelsp, int *num_levelsp) { - double* y; - int i; - double spread; - int use_given_levels=FALSE; - int* ordering; - int* levels; - double tol; /* node 'i' precedes 'j' in hierachy iff y[i]-y[j]>tol */ - double hierarchy_span; + double *y; + int i, rv=0; + double spread; + int use_given_levels = FALSE; + int *ordering; + int *levels; + double tol; /* node 'i' precedes 'j' in hierachy iff y[i]-y[j]>tol */ + double hierarchy_span; int num_levels; - /* compute optimizer of hierarchy energy: 'y' */ - if (given_coords) { - y = given_coords; - } - else { - y = N_GNEW(n,double); - compute_y_coords(graph, n, y, n); + /* compute optimizer of hierarchy energy: 'y' */ + if (given_coords) { + y = given_coords; + } else { + y = N_GNEW(n, double); + if (compute_y_coords(graph, n, y, n)) { + rv = 1; + goto finish; } + } - /* sort nodes accoridng to their y-ordering */ - *orderingp = ordering = N_NEW(n, int); - for (i=0; i=0; - } + spread = y[ordering[n - 1]] - y[ordering[0]]; + + /* after spread is computed, we may take the y-coords as the given levels */ + if (given_levels) { + use_given_levels = TRUE; + for (i = 0; i < n; i++) { + use_given_levels = use_given_levels && given_levels[i] >= 0; } - if (use_given_levels) { - for (i=0; i tol) { - num_levels++; - } - } - *num_levelsp = num_levels; - if (num_levels==0) { - *levelsp = levels = N_GNEW(1, int); - levels[0] = n; + num_levels = 0; + for (i = 1; i < n; i++) { + if (y[ordering[i]] - y[ordering[i - 1]] > tol) { + num_levels++; } - else { - int count=0; - *levelsp = levels = N_GNEW(num_levels, int); - for (i=1; i tol) { - levels[count++] = i; - } - } - } - if (!given_coords) { - free(y); + } + *num_levelsp = num_levels; + if (num_levels == 0) { + *levelsp = levels = N_GNEW(1, int); + levels[0] = n; + } else { + int count = 0; + *levelsp = levels = N_GNEW(num_levels, int); + for (i = 1; i < n; i++) { + if (y[ordering[i]] - y[ordering[i - 1]] > tol) { + levels[count++] = i; + } } + } +finish: + if (!given_coords) { + free(y); + } - return spread; + return rv; } -#endif /* DIGCOLA */ - +#endif /* DIGCOLA */ diff --git a/lib/neatogen/conjgrad.c b/lib/neatogen/conjgrad.c index f5cc3467a..b90f0a409 100644 --- a/lib/neatogen/conjgrad.c +++ b/lib/neatogen/conjgrad.c @@ -22,13 +22,13 @@ ** C.G. method - SPARSE * *************************/ -void conjugate_gradient +int conjugate_gradient (vtx_data * A, double *x, double *b, int n, double tol, int max_iterations) { /* Solves Ax=b using Conjugate-Gradients method */ /* 'x' and 'b' are orthogonalized against 1 */ - int i; + int i, rv = 0; double alpha, beta, r_r, r_r_new, p_Ap; double *r = N_GNEW(n, double); @@ -67,8 +67,11 @@ void conjugate_gradient /* vectors_subtraction(n,b,Ax,r); */ r_r_new = vectors_inner_product(n, r, r); - if (r_r == 0) - exit(1); + if (r_r == 0) { + agerr (AGERR, "conjugate_gradient: unexpected length 0 vector\n"); + rv = 1; + goto cleanup0; + } beta = r_r_new / r_r; r_r = r_r_new; vectors_scalar_mult(n, p, beta, p); @@ -76,6 +79,7 @@ void conjugate_gradient } } +cleanup0 : free(r); free(p); free(Ap); @@ -83,6 +87,7 @@ void conjugate_gradient free(alphap); free(orth_b); + return rv; } @@ -90,13 +95,13 @@ void conjugate_gradient ** C.G. method - DENSE * ****************************/ -void conjugate_gradient_f +int conjugate_gradient_f (float **A, double *x, double *b, int n, double tol, int max_iterations, boolean ortho1) { /* Solves Ax=b using Conjugate-Gradients method */ /* 'x' and 'b' are orthogonalized against 1 if 'ortho1=true' */ - int i; + int i, rv = 0; double alpha, beta, r_r, r_r_new, p_Ap; double *r = N_GNEW(n, double); @@ -137,15 +142,18 @@ void conjugate_gradient_f /* vectors_subtraction(n,b,Ax,r); */ r_r_new = vectors_inner_product(n, r, r); - if (r_r == 0) - exit(1); + if (r_r == 0) { + rv = 1; + agerr (AGERR, "conjugate_gradient: unexpected length 0 vector\n"); + goto cleanup1; + } beta = r_r_new / r_r; r_r = r_r_new; vectors_scalar_mult(n, p, beta, p); vectors_addition(n, r, p, p); } } - +cleanup1: free(r); free(p); free(Ap); @@ -153,9 +161,10 @@ void conjugate_gradient_f free(alphap); free(orth_b); + return rv; } -void +int conjugate_gradient_mkernel(float *A, float *x, float *b, int n, double tol, int max_iterations) { @@ -163,7 +172,7 @@ conjugate_gradient_mkernel(float *A, float *x, float *b, int n, /* A is a packed symmetric matrix */ /* matrux A is "packed" (only upper triangular portion exists, row-major); */ - int i; + int i, rv = 0; double alpha, beta, r_r, r_r_new, p_Ap; float *r = N_NEW(n, float); @@ -209,8 +218,11 @@ conjugate_gradient_mkernel(float *A, float *x, float *b, int n, r_r_new = vectors_inner_productf(n, r, r); - if (r_r == 0) - exit(1); + if (r_r == 0) { + rv = 1; + agerr (AGERR, "conjugate_gradient: unexpected length 0 vector\n"); + goto cleanup2; + } beta = r_r_new / r_r; r_r = r_r_new; @@ -220,8 +232,10 @@ conjugate_gradient_mkernel(float *A, float *x, float *b, int n, } } +cleanup2 : free(r); free(p); free(Ap); free(Ax); + return rv; } diff --git a/lib/neatogen/conjgrad.h b/lib/neatogen/conjgrad.h index 09b54baa5..58b5fa789 100644 --- a/lib/neatogen/conjgrad.h +++ b/lib/neatogen/conjgrad.h @@ -26,17 +26,17 @@ extern "C" { * C.G. method - SPARSE * ************************/ - extern void conjugate_gradient(vtx_data *, double *, double *, int, + extern int conjugate_gradient(vtx_data *, double *, double *, int, double, int); /************************* * C.G. method - DENSE * ************************/ - extern void conjugate_gradient_f(float **, double *, double *, int, + extern int conjugate_gradient_f(float **, double *, double *, int, double, int, boolean); - extern void conjugate_gradient_mkernel(float *, float *, float *, int, + extern int conjugate_gradient_mkernel(float *, float *, float *, int, double, int); #endif diff --git a/lib/neatogen/constrained_majorization.c b/lib/neatogen/constrained_majorization.c index 776e3f00c..c8362386f 100644 --- a/lib/neatogen/constrained_majorization.c +++ b/lib/neatogen/constrained_majorization.c @@ -30,21 +30,18 @@ #define localConstrMajorIterations 15 #define levels_sep_tol 1e-1 -int -stress_majorization_with_hierarchy( - vtx_data* graph, /* Input graph in sparse representation */ - int n, /* Number of nodes */ - int nedges_graph, /* Number of edges */ - double** d_coords, /* Coordinates of nodes (output layout) */ - node_t** nodes, /* Original nodes */ - int dim, /* Dimemsionality of layout */ - int opts, /* options */ - int model, /* difference model */ - int maxi, /* max iterations */ - double levels_gap -) +int stress_majorization_with_hierarchy(vtx_data * graph, /* Input graph in sparse representation */ + int n, /* Number of nodes */ + int nedges_graph, /* Number of edges */ + double **d_coords, /* Coordinates of nodes (output layout) */ + node_t ** nodes, /* Original nodes */ + int dim, /* Dimemsionality of layout */ + int opts, /* options */ + int model, /* difference model */ + int maxi, /* max iterations */ + double levels_gap) { - int iterations = 0; /* Output: number of iteration of the process */ + int iterations = 0; /* Output: number of iteration of the process */ /************************************************* ** Computation of full, dense, unrestricted k-D ** @@ -52,137 +49,164 @@ stress_majorization_with_hierarchy( ** This function imposes HIERARCHY CONSTRAINTS ** *************************************************/ - int i,j,k; - boolean directionalityExist = FALSE; - float * lap1 = NULL; - float * dist_accumulator = NULL; - float * tmp_coords = NULL; - float ** b = NULL; + int i, j, k; + boolean directionalityExist = FALSE; + float *lap1 = NULL; + float *dist_accumulator = NULL; + float *tmp_coords = NULL; + float **b = NULL; #ifdef NONCORE - FILE * fp=NULL; + FILE *fp = NULL; #endif - double * degrees = NULL; - float * lap2=NULL; - int lap_length; - float * f_storage=NULL; - float ** coords=NULL; - - double conj_tol=tolerance_cg; /* tolerance of Conjugate Gradient */ - float ** unpackedLap = NULL; - CMajEnv *cMajEnv = NULL; - double y_0; - int length; - int smart_ini = opts & opt_smart_init; - DistType diameter; - float * Dij=NULL; + double *degrees = NULL; + float *lap2 = NULL; + int lap_length; + float *f_storage = NULL; + float **coords = NULL; + + double conj_tol = tolerance_cg; /* tolerance of Conjugate Gradient */ + float **unpackedLap = NULL; + CMajEnv *cMajEnv = NULL; + double y_0; + int length; + int smart_ini = opts & opt_smart_init; + DistType diameter; + float *Dij = NULL; /* to compensate noises, we never consider gaps smaller than 'abs_tol' */ - double abs_tol=1e-2; + double abs_tol = 1e-2; /* Additionally, we never consider gaps smaller than 'abs_tol'* */ - double relative_tol=levels_sep_tol; - int *ordering=NULL, *levels=NULL; - float constant_term; - int count; - double degree; - int step; - float val; - double old_stress, new_stress; - boolean converged; - int len; + double relative_tol = levels_sep_tol; + int *ordering = NULL, *levels = NULL; + float constant_term; + int count; + double degree; + int step; + float val; + double old_stress, new_stress; + boolean converged; + int len; int num_levels; float *hierarchy_boundaries; - if (graph[0].edists!=NULL) { - for (i=0; i2) { - /* the dim==2 case is handled below */ - stress_majorization_kD_mkernel(graph, n, nedges_graph, d_coords+1, nodes, dim-1, opts, model, 15); - /* now copy the y-axis into the (dim-1)-axis */ - for (i=0; i 2) { + /* the dim==2 case is handled below */ + if (stress_majorization_kD_mkernel(graph, n, nedges_graph, + d_coords + 1, nodes, dim - 1, + opts, model, 15) < 0) + return -1; + /* now copy the y-axis into the (dim-1)-axis */ + for (i = 0; i < n; i++) { + d_coords[dim - 1][i] = d_coords[1][i]; + } + } - x = d_coords[0]; y = d_coords[1]; - compute_y_coords(graph, n, y, n); - compute_hierarchy(graph, n, abs_tol, relative_tol, y, &ordering, &levels, &num_levels); - if (num_levels<=1) { - /* no hierarchy found, use faster algorithm */ - return stress_majorization_kD_mkernel(graph, n, nedges_graph, d_coords, nodes, dim, opts, model, maxi); - } + x = d_coords[0]; + y = d_coords[1]; + if (compute_y_coords(graph, n, y, n)) { + iterations = -1; + goto finish; + } + if (compute_hierarchy(graph, n, abs_tol, relative_tol, y, &ordering, + &levels, &num_levels)) { + iterations = -1; + goto finish; + } + if (num_levels <= 1) { + /* no hierarchy found, use faster algorithm */ + return stress_majorization_kD_mkernel(graph, n, nedges_graph, + d_coords, nodes, dim, + opts, model, maxi); + } - if (levels_gap>0) { - /* ensure that levels are separated in the initial layout */ - double displacement = 0; - int stop; - for (i=0; i 0) { + /* ensure that levels are separated in the initial layout */ + double displacement = 0; + int stop; + for (i = 0; i < num_levels; i++) { + displacement += + MAX((double) 0, + levels_gap - (y[ordering[levels[i]]] + + displacement - + y[ordering[levels[i] - 1]])); + stop = i < num_levels - 1 ? levels[i + 1] : n; + for (j = levels[i]; j < stop; j++) { + y[ordering[j]] += displacement; } + } + } + if (dim == 2) { + if (IMDS_given_dim(graph, n, y, x, Epsilon)) { + iterations = -1; + goto finish; + } } - else { - initLayout(graph, n, dim, d_coords, nodes); - compute_hierarchy(graph, n, abs_tol, relative_tol, NULL, &ordering, &levels, &num_levels); + } else { + initLayout(graph, n, dim, d_coords, nodes); + if (compute_hierarchy(graph, n, abs_tol, relative_tol, NULL, &ordering, + &levels, &num_levels)) { + iterations = -1; + goto finish; } - if (n == 1) return 0; + } + if (n == 1) + return 0; - hierarchy_boundaries = N_GNEW(num_levels, float); + hierarchy_boundaries = N_GNEW(num_levels, float); /**************************************************** ** Compute the all-pairs-shortest-distances matrix ** ****************************************************/ - if (maxi==0) - return iterations; + if (maxi == 0) + return iterations; if (Verbose) start_timer(); if (model == MODEL_SUBSET) { - /* weight graph to separate high-degree nodes */ - /* and perform slower Dijkstra-based computation */ - if (Verbose) - fprintf(stderr, "Calculating subset model"); - Dij = compute_apsp_artifical_weights_packed(graph, n); + /* weight graph to separate high-degree nodes */ + /* and perform slower Dijkstra-based computation */ + if (Verbose) + fprintf(stderr, "Calculating subset model"); + Dij = compute_apsp_artifical_weights_packed(graph, n); } else if (model == MODEL_CIRCUIT) { - Dij = circuitModel(graph, n); - if (!Dij) { - agerr(AGWARN, - "graph is disconnected. Hence, the circuit model\n"); - agerr(AGPREV, - "is undefined. Reverting to the shortest path model.\n"); - } + Dij = circuitModel(graph, n); + if (!Dij) { + agerr(AGWARN, + "graph is disconnected. Hence, the circuit model\n"); + agerr(AGPREV, + "is undefined. Reverting to the shortest path model.\n"); + } } else if (model == MODEL_MDS) { if (Verbose) fprintf(stderr, "Calculating MDS model"); Dij = mdsModel(graph, n); } if (!Dij) { - if (Verbose) - fprintf(stderr, "Calculating shortest paths"); - Dij = compute_apsp_packed(graph, n); + if (Verbose) + fprintf(stderr, "Calculating shortest paths"); + Dij = compute_apsp_packed(graph, n); } if (Verbose) { fprintf(stderr, ": %.2f sec\n", elapsed_sec()); @@ -190,308 +214,331 @@ stress_majorization_with_hierarchy( start_timer(); } - diameter=-1; - length = n+n*(n-1)/2; - for (i=0; idiameter) { - diameter = (int)Dij[i]; - } + diameter = -1; + length = n + n * (n - 1) / 2; + for (i = 0; i < length; i++) { + if (Dij[i] > diameter) { + diameter = (int) Dij[i]; } + } - if (!smart_ini) { - /* for numerical stability, scale down layout */ - /* No Jiggling, might conflict with constraints */ - double max=1; - for (i=0; imax) { - max=fabs(d_coords[i][j]); - } - } - } - for (i=0; i0) { - int length = n+n*(n-1)/2; - double sum1, sum2, scale_ratio; - int count; - sum1=(float)(n*(n-1)/2); - sum2=0; - for (count=0, i=0; i max) { + max = fabs(d_coords[i][j]); } + } } + for (i = 0; i < dim; i++) { + for (j = 0; j < n; j++) { + d_coords[i][j] *= 10 / max; + } + } + } + + if (levels_gap > 0) { + int length = n + n * (n - 1) / 2; + double sum1, sum2, scale_ratio; + int count; + sum1 = (float) (n * (n - 1) / 2); + sum2 = 0; + for (count = 0, i = 0; i < n - 1; i++) { + count++; // skip self distance + for (j = i + 1; j < n; j++, count++) { + sum2 += distance_kD(d_coords, dim, i, j) / Dij[count]; + } + } + scale_ratio = sum2 / sum1; + /* double scale_ratio=10; */ + for (i = 0; i < length; i++) { + Dij[i] *= (float) scale_ratio; + } + } /************************** ** Layout initialization ** **************************/ - for (i=0; imax_nodes_in_mem) { - #define FILENAME "tmp_Dij$$$.bin" - fp = fopen(FILENAME, "wb"); - fwrite(lap2, sizeof(float), lap_length, fp); - fclose(fp); - fp = NULL; - } + fpos_t pos; + if (n > max_nodes_in_mem) { +#define FILENAME "tmp_Dij$$$.bin" + fp = fopen(FILENAME, "wb"); + fwrite(lap2, sizeof(float), lap_length, fp); + fclose(fp); + fp = NULL; + } #endif - + /************************* ** Layout optimization ** *************************/ - - b = N_GNEW (dim, float*); - b[0] = N_GNEW (dim*n, float); - for (k=1; k=FLT_MAX || dist_accumulator[j]<0) { - dist_accumulator[j]=0; - } - } - - count++; /* save place for the main diagonal entry */ - degree=0; - for (j=0; j= FLT_MAX + || dist_accumulator[j] < 0) { + dist_accumulator[j] = 0; } + } + + count++; /* save place for the main diagonal entry */ + degree = 0; + for (j = 0; j < len; j++, count++) { + val = lap1[count] *= dist_accumulator[j]; + degree += val; + degrees[i + j + 1] -= val; + } + degrees[i] -= degree; + } + for (step = n, count = 0, i = 0; i < n; i++, count += step, step--) { + lap1[count] = (float) degrees[i]; + } - /* Now compute b[] (L^(X(t))*X(t)) */ - for (k=0; kmax_nodes_in_mem) { - /* restore lap2 from disk */ - fsetpos(fp, &pos); - fread(lap2, sizeof(float), lap_length, fp); - } + if (n > max_nodes_in_mem) { + /* restore lap2 from disk */ + fsetpos(fp, &pos); + fread(lap2, sizeof(float), lap_length, fp); + } #endif - for (k=0; k0.001) { - fprintf(stderr,"Diff stress vals: %lf %lf (iteration #%d)\n", mat_stress, new_stress,iterations); - } - } -#endif - /* check for convergence */ - converged = fabs(new_stress-old_stress)/fabs(old_stress+1e-10) < Epsilon; - converged = converged || (iterations>1 && new_stress>old_stress); - /* in first iteration we allowed stress increase, which - * might result ny imposing constraints - */ - old_stress = new_stress; - - for (k=0; k 0.001) { + fprintf(stderr, + "Diff stress vals: %lf %lf (iteration #%d)\n", + mat_stress, new_stress, iterations); + } } - free (hierarchy_boundaries); - deleteCMajEnv(cMajEnv); - - if (coords!=NULL) { - for (i=0; i 1 + && new_stress > old_stress); + /* in first iteration we allowed stress increase, which + * might result ny imposing constraints + */ + old_stress = new_stress; + + for (k = 0; k < dim; k++) { + /* now we find the optimizer of trace(X'LX)+X'B by solving 'dim' + * system of equations, thereby obtaining the new coordinates. + * If we use the constraints (given by the var's: 'ordering', + * 'levels' and 'num_levels'), we cannot optimize + * trace(X'LX)+X'B by simply solving equations, but we have + * to use a quadratic programming solver + * note: 'lap2' is a packed symmetric matrix, that is its + * upper-triangular part is arranged in a vector row-wise + * also note: 'lap2' is really the negated laplacian (the + * laplacian is -'lap2') + */ + + if (k == 1) { + /* use quad solver in the y-dimension */ + constrained_majorization_new_with_gaps(cMajEnv, b[k], + coords, dim, k, + localConstrMajorIterations, + hierarchy_boundaries, + levels_gap); + + } else { + /* use conjugate gradient for all dimensions except y */ + if (conjugate_gradient_mkernel(lap2, coords[k], b[k], n, + conj_tol, n)) { + iterations = -1; + goto finish; } - free (coords[0]); free (coords); + } } - - if (b) { - free (b[0]); free (b); + } + free(hierarchy_boundaries); + deleteCMajEnv(cMajEnv); + + if (coords != NULL) { + for (i = 0; i < dim; i++) { + for (j = 0; j < n; j++) { + d_coords[i][j] = coords[i][j]; + } } - free (tmp_coords); - free (dist_accumulator); - free (degrees); - free (lap2); - + free(coords[0]); + free(coords); + } + + if (b) { + free(b[0]); + free(b); + } + free(tmp_coords); + free(dist_accumulator); + free(degrees); + free(lap2); + #ifdef NONCORE - if (n<=max_nodes_in_mem) { + if (n <= max_nodes_in_mem) { #endif - free (lap1); + free(lap1); #ifdef NONCORE - } - if (fp) - fclose (fp); + } + if (fp) + fclose(fp); #endif - free (ordering); - - free (levels); +finish: + free(ordering); - if (unpackedLap) { - free (unpackedLap[0]); free (unpackedLap); - } + free(levels); + + if (unpackedLap) { + free(unpackedLap[0]); + free(unpackedLap); + } return iterations; } -#endif /* DIGCOLA */ - +#endif /* DIGCOLA */ diff --git a/lib/neatogen/constrained_majorization_ipsep.c b/lib/neatogen/constrained_majorization_ipsep.c index ff15067d9..cd0540251 100644 --- a/lib/neatogen/constrained_majorization_ipsep.c +++ b/lib/neatogen/constrained_majorization_ipsep.c @@ -54,18 +54,17 @@ #define localConstrMajorIterations 1000 -int stress_majorization_cola( - vtx_data * graph, /* Input graph in sparse representation */ - int n, /* Number of nodes */ - int nedges_graph, /* Number of edges */ - double **d_coords, /* Coordinates of nodes (output layout) */ - node_t **nodes, /* Original nodes */ - int dim, /* Dimemsionality of layout */ - int model, /* difference model */ - int maxi, /* max iterations */ - ipsep_options * opt) +int stress_majorization_cola(vtx_data * graph, /* Input graph in sparse representation */ + int n, /* Number of nodes */ + int nedges_graph, /* Number of edges */ + double **d_coords, /* Coordinates of nodes (output layout) */ + node_t ** nodes, /* Original nodes */ + int dim, /* Dimemsionality of layout */ + int model, /* difference model */ + int maxi, /* max iterations */ + ipsep_options * opt) { - int iterations = 0; /* Output: number of iteration of the process */ + int iterations = 0; /* Output: number of iteration of the process */ /************************************************* ** Computation of full, dense, unrestricted k-D ** @@ -190,7 +189,8 @@ int stress_majorization_cola( for (i = 0; i < n; i++) { d_coords[1][i] -= y_0; } - if (Verbose) fprintf(stderr, ": %.2f sec", elapsed_sec()); + if (Verbose) + fprintf(stderr, ": %.2f sec", elapsed_sec()); /************************** ** Laplacian computation ** @@ -279,8 +279,14 @@ int stress_majorization_cola( old_stress = DBL_MAX; /* at least one iteration */ - cMajEnvHor = initCMajVPSC(n, lap2, graph, opt, 0); - cMajEnvVrt = initCMajVPSC(n, lap2, graph, opt, opt->diredges); + if ((cMajEnvHor = initCMajVPSC(n, lap2, graph, opt, 0)) == NULL) { + iterations = -1; + goto finish; + } + if ((cMajEnvVrt = initCMajVPSC(n, lap2, graph, opt, opt->diredges)) == NULL) { + iterations = -1; + goto finish; + } lap1 = N_GNEW(lap_length, float); @@ -425,8 +431,11 @@ int stress_majorization_cola( /* if there are no constraints then use conjugate gradient * optimisation which should be considerably faster */ - conjugate_gradient_mkernel(lap2, coords[0], b[0], n, - tolerance_cg, n); + if (conjugate_gradient_mkernel(lap2, coords[0], b[0], n, + tolerance_cg, n) < 0) { + iterations = -1; + goto finish; + } } if (opt->noverlap == 1 && nsizeScale > 0.001) { generateNonoverlapConstraints(cMajEnvVrt, nsizeScale, coords, @@ -439,8 +448,11 @@ int stress_majorization_cola( coords[1]); } else #endif /* MOSEK */ - constrained_majorization_vpsc(cMajEnvVrt, b[1], coords[1], - localConstrMajorIterations); + if (constrained_majorization_vpsc(cMajEnvVrt, b[1], coords[1], + localConstrMajorIterations) < 0) { + iterations = -1; + goto finish; + } } else { conjugate_gradient_mkernel(lap2, coords[1], b[1], n, tolerance_cg, n); @@ -458,6 +470,7 @@ int stress_majorization_cola( removeoverlaps(orig_n, coords, opt); } +finish: if (coords != NULL) { for (i = 0; i < dim; i++) { for (j = 0; j < orig_n; j++) { diff --git a/lib/neatogen/digcola.h b/lib/neatogen/digcola.h index 25d59ed33..84143a294 100644 --- a/lib/neatogen/digcola.h +++ b/lib/neatogen/digcola.h @@ -20,10 +20,10 @@ extern "C" { #include #ifdef DIGCOLA -extern void compute_y_coords(vtx_data*, int, double*, int); -extern double compute_hierarchy(vtx_data*, int, double, double, +extern int compute_y_coords(vtx_data*, int, double*, int); +extern int compute_hierarchy(vtx_data*, int, double, double, double*, int**, int**, int*); -extern void IMDS_given_dim(vtx_data*, int, double*, double*, double); +extern int IMDS_given_dim(vtx_data*, int, double*, double*, double); extern int stress_majorization_with_hierarchy(vtx_data*, int, int, double**, node_t**, int, int, int, int, double); #ifdef IPSEPCOLA diff --git a/lib/neatogen/fPQ.h b/lib/neatogen/fPQ.h index 24464f109..5fe0041f3 100644 --- a/lib/neatogen/fPQ.h +++ b/lib/neatogen/fPQ.h @@ -92,12 +92,12 @@ PQupheap(PQ* ppq, int k) N_IDX(ppq,x) = k; } -static void +static int PQinsert(PQ* pq, PQTYPE np) { if (pq->PQcnt == pq->PQsize) { - fprintf (stderr, "Heap overflow\n"); - exit (1); + agerr (AGERR, "Heap overflow\n"); + return (1); } pq->PQcnt++; pq->pq[pq->PQcnt] = np; @@ -105,6 +105,7 @@ PQinsert(PQ* pq, PQTYPE np) #ifdef PQCHECK PQcheck(pq); #endif + return 0; } static void diff --git a/lib/neatogen/legal.c b/lib/neatogen/legal.c index ff1008c36..91ae3b46a 100644 --- a/lib/neatogen/legal.c +++ b/lib/neatogen/legal.c @@ -13,6 +13,9 @@ #include "neato.h" #include "pathutil.h" +#include + +static jmp_buf jbuf; #define MAXINTS 10000 /* modify this line to reflect the max no. of intersections you want reported -- 50000 seems to break the program */ @@ -333,8 +336,8 @@ find_ints(vertex vertex_list[], case 1: /* backward edge, delete */ if ((tempa = templ->active) == 0) { - agerr(AGERR, "trying to delete a non line\n"); - exit(1); + agerr(AGERR, "trying to delete a non-line\n"); + longjmp(jbuf, 1); } if (all.number == 1) all.final = all.first = 0; /* delete the line */ @@ -447,6 +450,11 @@ int Plegal_arrangement(Ppoly_t ** polys, int n_polys) input.nvertices = nverts; input.npolygons = n_polys; + if (setjmp(jbuf)) { + free(polygon_list); + free(vertex_list); + return 0; + } found = find_ints(vertex_list, polygon_list, &input, ilist); if (!found) { diff --git a/lib/neatogen/multispline.c b/lib/neatogen/multispline.c index bb20df879..7d0bdc65f 100644 --- a/lib/neatogen/multispline.c +++ b/lib/neatogen/multispline.c @@ -1279,7 +1279,8 @@ triPath(tgraph * g, int n, int v0, int v1, PQ * pq) PQinit(pq); N_DAD(v0) = -1; N_VAL(pq, v0) = 0; - PQinsert(pq, v0); + if (PQinsert(pq, v0)) + return NULL; while ((i = PQremove(pq)) != -1) { N_VAL(pq, i) *= -1; @@ -1297,7 +1298,7 @@ triPath(tgraph * g, int n, int v0, int v1, PQ * pq) if (N_VAL(pq, adjn) == UNSEEN) { N_VAL(pq, adjn) = d; N_DAD(adjn) = i; - PQinsert(pq, adjn); + if (PQinsert(pq, adjn)) return NULL; } else if (N_VAL(pq, adjn) < d) { PQupdate(pq, adjn, d); N_DAD(adjn) = i; @@ -1351,13 +1352,15 @@ int makeMultiSpline(graph_t* g, edge_t* e, router_t * rtr, int doPolyline) PQfree(&(pq.pq), 0); /* Use path of triangles to generate guiding polygon */ - poly = mkPoly(rtr, sp, h_id, t_id, h_p, t_p, &idx); - - free(sp); + if (sp) { + poly = mkPoly(rtr, sp, h_id, t_id, h_p, t_p, &idx); + free(sp); /* Generate multiple splines using polygon */ - ret = genroute(g, poly, 0, idx, e, doPolyline); - freeTripoly (poly); + ret = genroute(g, poly, 0, idx, e, doPolyline); + freeTripoly (poly); + } + else ret = -1; resetGraph(rtr->tg, rtr->tn, ecnt); return ret; diff --git a/lib/neatogen/neatoinit.c b/lib/neatogen/neatoinit.c index 866274fc0..c0bf7315b 100644 --- a/lib/neatogen/neatoinit.c +++ b/lib/neatogen/neatoinit.c @@ -1303,7 +1303,7 @@ majorization(graph_t *mg, graph_t * g, int nv, int mode, int model, int dim, int { double **coords; int ne; - int i; + int i, rv = 0; node_t *v; vtx_data *gp; node_t** nodes; @@ -1344,7 +1344,7 @@ majorization(graph_t *mg, graph_t * g, int nv, int mode, int model, int dim, int if (mode != MODE_MAJOR) { double lgap = late_double(g, agfindgraphattr(g, "levelsgap"), 0.0, -MAXDOUBLE); if (mode == MODE_HIER) { - stress_majorization_with_hierarchy(gp, nv, ne, coords, nodes, Ndim, + rv = stress_majorization_with_hierarchy(gp, nv, ne, coords, nodes, Ndim, opts, model, MaxIter, lgap); } #ifdef IPSEPCOLA @@ -1414,7 +1414,7 @@ majorization(graph_t *mg, graph_t * g, int nv, int mode, int model, int dim, int fprintf (stderr, "\n"); dumpOpts (&opt, nv); #endif - stress_majorization_cola(gp, nv, ne, coords, nodes, Ndim, model, MaxIter, &opt); + rv = stress_majorization_cola(gp, nv, ne, coords, nodes, Ndim, model, MaxIter, &opt); freeClusterData(cs); free (nsize); } @@ -1422,10 +1422,12 @@ majorization(graph_t *mg, graph_t * g, int nv, int mode, int model, int dim, int } else #endif - stress_majorization_kD_mkernel(gp, nv, ne, coords, nodes, Ndim, opts, model, MaxIter); + rv = stress_majorization_kD_mkernel(gp, nv, ne, coords, nodes, Ndim, opts, model, MaxIter); - /* store positions back in nodes */ - for (v = agfstnode(g); v; v = agnxtnode(g, v)) { + if (rv < 0) { + agerr(AGPREV, "layout aborted\n"); + } + else for (v = agfstnode(g); v; v = agnxtnode(g, v)) { /* store positions back in nodes */ int idx = ND_id(v); int i; for (i = 0; i < Ndim; i++) { diff --git a/lib/neatogen/opt_arrangement.c b/lib/neatogen/opt_arrangement.c index 4f543c32a..54ff4c1df 100644 --- a/lib/neatogen/opt_arrangement.c +++ b/lib/neatogen/opt_arrangement.c @@ -16,75 +16,77 @@ #include "matrix_ops.h" #include "conjgrad.h" -static void -construct_b(vtx_data* graph, int n, double *b) +static void construct_b(vtx_data * graph, int n, double *b) { - /* construct a vector - b s.t. -b[i]=\sum_j -w_{ij}*\delta_{ij} - * (the "balance vector") - * Note that we build -b and not b, since our matrix is not the - * real laplacian L, but its negation: -L. - * So instead of solving Lx=b, we will solve -Lx=-b + /* construct a vector - b s.t. -b[i]=\sum_j -w_{ij}*\delta_{ij} + * (the "balance vector") + * Note that we build -b and not b, since our matrix is not the + * real laplacian L, but its negation: -L. + * So instead of solving Lx=b, we will solve -Lx=-b */ - int i,j; + int i, j; - double b_i = 0; - - for (i=0; iname); - exit(1); + return 1; } pp->verts = verts; @@ -269,9 +269,10 @@ void makeAddPoly(Poly * pp, Agnode_t * n, float xmargin, float ymargin) if (sides > maxcnt) maxcnt = sides; + return 0; } -void makePoly(Poly * pp, Agnode_t * n, float xmargin, float ymargin) +int makePoly(Poly * pp, Agnode_t * n, float xmargin, float ymargin) { int i; int sides; @@ -332,7 +333,7 @@ void makePoly(Poly * pp, Agnode_t * n, float xmargin, float ymargin) default: agerr(AGERR, "makePoly: unknown shape type %s\n", ND_shape(n)->name); - exit(1); + return 1; } #ifdef OLD @@ -349,6 +350,7 @@ void makePoly(Poly * pp, Agnode_t * n, float xmargin, float ymargin) if (sides > maxcnt) maxcnt = sides; + return 0; } static int diff --git a/lib/neatogen/poly.h b/lib/neatogen/poly.h index fd92a6cc6..16a43aad0 100644 --- a/lib/neatogen/poly.h +++ b/lib/neatogen/poly.h @@ -30,8 +30,8 @@ extern "C" { extern void polyFree(void); extern int polyOverlap(Point, Poly *, Point, Poly *); - extern void makePoly(Poly *, Agnode_t *, float, float); - extern void makeAddPoly(Poly *, Agnode_t *, float, float); + extern int makePoly(Poly *, Agnode_t *, float, float); + extern int makeAddPoly(Poly *, Agnode_t *, float, float); extern void breakPoly(Poly *); #endif diff --git a/lib/neatogen/quad_prog_vpsc.c b/lib/neatogen/quad_prog_vpsc.c index cfe11ce1b..3621e6c52 100644 --- a/lib/neatogen/quad_prog_vpsc.c +++ b/lib/neatogen/quad_prog_vpsc.c @@ -241,8 +241,8 @@ CMajEnvVPSC *initCMajVPSC(int n, float *packedMat, vtx_data * graph, DigColaLevel *levels; Variable **vs = e->vs; /* e->ndv is the number of dummy variables required, one for each boundary */ - compute_hierarchy(graph, e->nv, 1e-2, 1e-1, NULL, &ordering, &ls, - &e->ndv); + if (compute_hierarchy(graph, e->nv, 1e-2, 1e-1, NULL, &ordering, &ls, + &e->ndv)) return NULL; levels = assign_digcola_levels(ordering, e->nv, ls, e->ndv); if (Verbose) fprintf(stderr, "Found %d DiG-CoLa boundaries\n", e->ndv); diff --git a/lib/neatogen/smart_ini_x.c b/lib/neatogen/smart_ini_x.c index 28c0cb26f..7a20a0b38 100644 --- a/lib/neatogen/smart_ini_x.c +++ b/lib/neatogen/smart_ini_x.c @@ -249,11 +249,11 @@ CMDS_orthog(vtx_data* graph, int n, int dim, double** eigs, double tol, #define SCALE_FACTOR 256 -void IMDS_given_dim(vtx_data* graph, int n, double* given_coords, +int IMDS_given_dim(vtx_data* graph, int n, double* given_coords, double* new_coords, double conj_tol) { int iterations2; - int i,j; + int i,j, rv = 0; DistType** Dij; float* f_storage = NULL; double* x = given_coords; @@ -350,7 +350,10 @@ void IMDS_given_dim(vtx_data* graph, int n, double* given_coords, } for (converged=FALSE,iterations2=0; iterations2<200 && !converged; iterations2++) { - conjugate_gradient_f(lap, y, balance, n, conj_tol, n, TRUE); + if (conjugate_gradient_f(lap, y, balance, n, conj_tol, n, TRUE) < 0) { + rv = 1; + goto cleanup; + } converged=TRUE; for (i=0; i