From 1c7ff481d533519f0310b0ce69de4e3702c59c04 Mon Sep 17 00:00:00 2001 From: "Emden R. Gansner" Date: Tue, 20 Aug 2013 09:26:58 -0400 Subject: [PATCH] Remove HAVE_ANN conditions as mingle is only built if libann is available; check graph for loops and multiedges; fix -v to correctly allow verbose values; implement gv output using original graph with attached attributes. --- cmd/mingle/minglemain.c | 205 ++++++++++++++++++++++++++++++++++------ 1 file changed, 178 insertions(+), 27 deletions(-) diff --git a/cmd/mingle/minglemain.c b/cmd/mingle/minglemain.c index 40174f23e..62e69cc55 100644 --- a/cmd/mingle/minglemain.c +++ b/cmd/mingle/minglemain.c @@ -25,6 +25,7 @@ #endif /* not WIN32_DLL */ #include +#include #include #ifdef HAVE_GETOPT_H #include @@ -75,7 +76,6 @@ static FILE *openFile(char *name, char *mode, char* cmd) } static char* use_msg = -#ifdef HAVE_ANN "Usage: mingle \n\ -a t - max. turning angle [0-180] (40)\n\ -c i - compatability measure; 0 : distance, 1: full (default)\n\ @@ -89,21 +89,6 @@ static char* use_msg = -r R - max. recursion level with agglomerative ink saving method (100)\n\ -T fmt - output format: gv (default) or simple\n\ -v - verbose\n"; -#else -"Usage: mingle \n\ - -a t - max. turning angle [0-180] (40)\n\ - -c i - compatability measure; 0 : distance, 1: full (default)\n\ - -i iter: number of outer iterations/subdivisions (4)\n\ - -k k - number of neighbors in the nearest neighbor graph of edges (10)\n\ - -K k - the force constant\n\ - -m method - method used. 0 (force directed, default), 2 (cluster+ink saving)\n\ - -o fname - write output to file fname (stdout)\n\ - -p t - balance for avoiding sharp angles\n\ - The larger the t, the more sharp angles are allowed\n\ - -r R - max. recursion level with agglomerative ink saving method (100)\n\ - -T fmt - output format: gv (default) or simple\n\ - -v - verbose\n"; -#endif static void usage (int eval) @@ -112,6 +97,29 @@ usage (int eval) if (eval >= 0) exit (eval); } +/* checkG: + * Return non-zero if g has loops or multiedges. + * Relies on multiedges occurring consecutively in edge list. + */ +static int +checkG (Agraph_t* g) +{ + Agedge_t* e; + Agnode_t* n; + Agnode_t* h; + Agnode_t* prevh = NULL; + + for (n = agfstnode (g); n; n = agnxtnode (g, n)) { + for (e = agfstout (g, n); e; e = agnxtout (g, e)) { + if ((h = aghead(e)) == n) return 1; // loop + if (h == prevh) return 1; // multiedge + prevh = h; + } + prevh = NULL; // reset + } + return 0; +} + static void init(int argc, char *argv[], opts_t* opts) { unsigned int c; @@ -121,11 +129,7 @@ static void init(int argc, char *argv[], opts_t* opts) opterr = 0; opts->outer_iter = 4; -#ifdef HAVE_ANN opts->method = METHOD_INK_AGGLOMERATE; -#else - opts->method = METHOD_FD; -#endif opts->compatibility_method = COMPATIBILITY_FULL; opts->K = -1; opts->fmt = FMT_GV; @@ -167,11 +171,7 @@ static void init(int argc, char *argv[], opts_t* opts) fprintf (stderr, "-K arg %s must be positive real - ignored\n", optarg); break; case 'm': - if ((sscanf(optarg,"%d",&i) > 0) && (0 <= i) && (i <= METHOD_INK) -#ifndef HAVE_ANN - && (i != METHOD_INK_AGGLOMERATE) -#endif - ) + if ((sscanf(optarg,"%d",&i) > 0) && (0 <= i) && (i <= METHOD_INK)) opts->method = i; else fprintf (stderr, "-k arg %s must be an integer >= 2 - ignored\n", optarg); @@ -204,7 +204,7 @@ static void init(int argc, char *argv[], opts_t* opts) if ((sscanf(optarg,"%d",&i) > 0) && (i >= 0)) Verbose = i; else - fprintf (stderr, "-v arg %s must be a non-negative integer - ignored\n", optarg); + optind--; break; case ':': if (optopt == 'v') @@ -242,6 +242,153 @@ static void init(int argc, char *argv[], opts_t* opts) } } +/* genBundleSpline: + * We have ninterval+1 points. We drop the ninterval-1 internal points, and add 4 points to the first + * and last intervals, and 3 to the rest, giving the needed 3*ninterval+4 points. + */ +static void +genBundleSpline (pedge edge, agxbuf* xb) +{ + int k, j, mm, kk; + char buf[BUFSIZ]; + int dim = edge->dim; + real* x = edge->x; + real tt1[3]={0.15,0.5,0.85}; + real tt2[4]={0.15,0.4,0.6,0.85}; + real t, *tt; + + for (j = 0; j < edge->npoints; j++){ + if (j != 0) { + agxbputc(xb, ' '); + if ((j == 1) || (j == edge->npoints - 1)) { + tt = tt2; + mm = 4; + } else { + tt = tt1; + mm = 3; + } + for (kk = 1; kk <= mm; kk++){ + t = tt[kk-1]; + for (k = 0; k < dim; k++) { + if (k != 0) agxbputc(xb,','); + sprintf(buf, "%.03f", (x[(j-1)*dim+k]*(1-t)+x[j*dim+k]*(t))); + agxbput(xb, buf); + } + agxbputc(xb,' '); + } + } + if ((j == 0) || (j == edge->npoints - 1)) { + for (k = 0; k < dim; k++) { + if (k != 0) agxbputc(xb,','); + sprintf(buf, "%.03f", x[j*dim+k]); + agxbput(xb, buf); + } + } + } +} + +static void +genBundleInfo (pedge edge, agxbuf* xb) +{ + int k, j; + char buf[BUFSIZ]; + int dim = edge->dim; + real* x = edge->x; + + for (j = 0; j < edge->npoints; j++){ + if (j != 0) agxbputc(xb, ':'); + for (k = 0; k < dim; k++) { + if (k != 0) agxbputc(xb, ','); + sprintf(buf, "%.03f", x[j*dim+k]); + agxbput(xb, buf); + } + + if ((j < edge->npoints-1) && (edge->wgts)) { + sprintf(buf, ";%.03f", edge->wgts[j]); + agxbput(xb, buf); + } + } +} + +static void +genBundleColors (pedge edge, agxbuf* xb, real maxwgt) +{ + int k, j, r, g, b; + real len, t, len_total0 = 0; + int dim = edge->dim; + real* x = edge->x; + real* lens = MALLOC(sizeof(real)*edge->npoints); + char buf[BUFSIZ]; + + for (j = 0; j < edge->npoints - 1; j++){ + len = 0; + for (k = 0; k < dim; k++){ + len += (x[dim*j+k] - x[dim*(j+1)+k])*(x[dim*j+k] - x[dim*(j+1)+k]); + } + lens[j] = len = sqrt(len/k); + len_total0 += len; + } + for (j = 0; j < edge->npoints - 1; j++){ + t = edge->wgts[j]/maxwgt; + /* interpolate between red (t = 1) to blue (t = 0) */ + r = 255*t; g = 0; b = 255*(1-t); + if (j != 0) agxbputc(xb,':'); + sprintf(buf, "#%02x%02x%02x%02x", r, g, b, 85); + agxbput(xb, buf); + if (j < edge->npoints-2) { + sprintf(buf,";%f",lens[j]/len_total0); + agxbput(xb, buf); + } + } + free (lens); +} + +static void +export_dot (FILE* fp, int ne, pedge *edges, Agraph_t* g) +{ + Agsym_t* epos = agattr (g, AGEDGE, "pos", ""); + Agsym_t* esects = agattr (g, AGEDGE, "bundle", ""); + Agsym_t* eclrs = NULL; + Agnode_t* n; + Agedge_t* e; + int i, j; + real maxwgt = 0; + pedge edge; + agxbuf xbuf; + unsigned char buf[BUFSIZ]; + + /* figure out max number of bundled origional edges in a pedge */ + for (i = 0; i < ne; i++){ + edge = edges[i]; + if (edge->wgts){ + for (j = 0; j < edge->npoints - 1; j++){ + maxwgt = MAX(maxwgt, edge->wgts[j]); + } + } + } + + agxbinit(&xbuf, BUFSIZ, buf); + for (i = 0, n = agfstnode (g); n; n = agnxtnode (g, n)) { + for (e = agfstout (g, n); e; e = agnxtout (g, e)) { + edge = edges[i++]; + + genBundleSpline (edge, &xbuf); + agxset (e, epos, agxbuse(&xbuf)); + + genBundleInfo (edge, &xbuf); + agxset (e, esects, agxbuse(&xbuf)); + + if (edge->wgts) { + if (!eclrs) eclrs = agattr (g, AGEDGE, "color", ""); + genBundleColors (edge, &xbuf, maxwgt); + agxset (e, eclrs, agxbuse(&xbuf)); + } + } + } + agxbfree(&xbuf); + agwrite(g, fp); +} + static int bundle (Agraph_t* g, opts_t* opts) { @@ -257,6 +404,10 @@ bundle (Agraph_t* g, opts_t* opts) int *ia, *ja, i, j; int rv = 0; + if (checkG(g)) { + agerr (AGERR, "Graph %s (%s) contains loops or multiedges\n"); + return 1; + } initDotIO(g); A = SparseMatrix_import_dot(g, dim, &label_sizes, &x, &n_edge_label_nodes, NULL, FORMAT_CSR, NULL); if (!A){ @@ -300,7 +451,7 @@ bundle (Agraph_t* g, opts_t* opts) edges = edge_bundling(A, 2, x, opts->outer_iter, opts->K, opts->method, opts->nneighbors, opts->compatibility_method, opts->max_recursion, opts->angle_param, opts->angle, 0); if (opts->fmt == FMT_GV) - pedge_export_gv(outfile, A->m, edges); /* FIX */ + export_dot (outfile, A->m, edges, g); /* FIX */ else pedge_export_gv(outfile, A->m, edges); return rv; -- 2.40.0