From: Ian Jackson Date: Sun, 6 Jan 2008 20:32:20 +0000 (+0000) Subject: minor improvements X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=moebius2.git;a=commitdiff_plain;h=7968bc4aca3306473e7ab0a55d4bdc721a3eacd5 minor improvements --- diff --git a/energy.c b/energy.c index a54cfe2..2bbf049 100644 --- a/energy.c +++ b/energy.c @@ -6,7 +6,8 @@ #include "minimise.h" #include "mgraph.h" -static void compute_vertex_areas(const Vertices vertices, double areas[N]); +double vertex_areas[N], vertex_mean_edge_lengths[N], edge_lengths[N][V6]; + static double best_energy= DBL_MAX; static void addcost(double *energy, double tweight, double tcost, int pr); @@ -15,10 +16,11 @@ static void addcost(double *energy, double tweight, double tcost, int pr); /*---------- main energy computation and subroutines ----------*/ double compute_energy(const struct Vertices *vs) { - double vertex_areas[N], energy; + double energy; int printing; - compute_vertex_areas(vs->a, vertex_areas); + compute_edge_lengths(vs->a); + compute_vertex_areas(vs->a); energy= 0; printing= printing_check(pr_cost); @@ -26,8 +28,9 @@ double compute_energy(const struct Vertices *vs) { if (printing) printf("cost > energy |"); COST(1e2, edgewise_vertex_displacement_cost(vs->a)); - COST(1e2, graph_layout_cost(vs->a,vertex_areas)); - COST(1e6, noncircular_rim_cost(vs->a)); + COST(1e2, graph_layout_cost(vs->a)); + COST(1e3, edge_length_variation_cost(vs->a)); +// COST(1e6, noncircular_rim_cost(vs->a)); if (printing) printf("| total %# e |", energy); @@ -58,11 +61,20 @@ static void addcost(double *energy, double tweight, double tcost, int pr) { *energy += tenergy; } -static void compute_vertex_areas(const Vertices vertices, double areas[N]) { +/*---------- Precomputations ----------*/ + +void compute_edge_lengths(const Vertices vertices) { + int v1,e,v2; + + FOR_EDGE(v1,e,v2) + edge_lengths[v1][e]= hypotD(vertices[v1],vertices[v2]); +} + +void compute_vertex_areas(const Vertices vertices) { int v0,v1,v2, e1,e2, k; FOR_VERTEX(v0) { - double total= 0.0; + double total= 0.0, edges_total=0; int count= 0; FOR_VEDGE(v0,e1,v1) { @@ -70,6 +82,8 @@ static void compute_vertex_areas(const Vertices vertices, double areas[N]) { v2= EDGE_END2(v0,e2); if (v2<0) continue; + edges_total += edge_lengths[v0][e1]; + double e1v[D3], e2v[D3], av[D3]; K { e1v[k]= vertices[v1][k] - vertices[v0][k]; @@ -77,9 +91,11 @@ static void compute_vertex_areas(const Vertices vertices, double areas[N]) { } xprod(av, e1v, e2v); total += magnD(av); + count++; } - areas[v0]= total / count; + vertex_areas[v0]= total / count; + vertex_mean_edge_lengths[v0]= edges_total / count; } } @@ -151,6 +167,20 @@ double edgewise_vertex_displacement_cost(const Vertices vertices) { return total_cost; } +/*---------- edge length variation ----------*/ + +double edge_length_variation_cost(const Vertices vertices) { + double diff, cost= 0; + int v0, efwd,vfwd, eback; + + FOR_EDGE(v0,efwd,vfwd) { + eback= edge_reverse(v0,efwd); + diff= edge_lengths[v0][efwd] - edge_lengths[v0][eback]; + cost += diff*diff; + } + return cost; +} + /*---------- noncircular rim cost ----------*/ double noncircular_rim_cost(const Vertices vertices) { diff --git a/graph.c b/graph.c index 74d93bf..f0ce19d 100644 --- a/graph.c +++ b/graph.c @@ -35,6 +35,9 @@ static void breadth_first_search(int start, int sqdistances_r[N]) { assert(d[v] >= 0); sqdistances_r[v]= d[v] * d[v]; } + +// FOR_VERTEX(v) { +// } void graph_layout_prepare() { @@ -50,7 +53,7 @@ void graph_layout_prepare() { } -double graph_layout_cost(const Vertices v, const double vertex_areas[N]) { +double graph_layout_cost(const Vertices v) { /* For each (vi,vj) computes shortest path s_ij = |vi..vj| * along edges, and actual distance d_ij = |vi-vj|. * @@ -98,7 +101,7 @@ double graph_layout_cost(const Vertices v, const double vertex_areas[N]) { * let beta' = (1-beta)/2 */ - double cost= pow(d2/s2, beta_prime); + double cost= (vertex_mean_edge_lengths[v1]) * pow(d2/s2, beta_prime); //printf("layout %03x..%03x dist^2=%d s^2=%g d^2=%g " //" cost+=%g\n", v1,v2, dist2, @@ -106,5 +109,5 @@ double graph_layout_cost(const Vertices v, const double vertex_areas[N]) { total_cost += cost; } } - return total_cost; + return total_cost/meanedgelength; } diff --git a/mgraph.c b/mgraph.c index 23a10e3..4b708e5 100644 --- a/mgraph.c +++ b/mgraph.c @@ -24,3 +24,15 @@ int edge_end2(unsigned v1, int e) { return x | y; } + +static const unsigned reverse[2][V6]= {{ 3, 4, 5, 0, 1, 2 }, + { 3, 2, 1, 0, 5, 4 }}; + +int edge_reverse(int v1, int e) { + unsigned x2; + int flip; + + x2= (v1 & XMASK) + dx[(v1 >> YSHIFT) & 1][e]; + flip= !!(x2 & ~XMASK); + return reverse[flip][e]; +} diff --git a/mgraph.h b/mgraph.h index 714ff7f..43494c7 100644 --- a/mgraph.h +++ b/mgraph.h @@ -9,7 +9,7 @@ * | : * ___ X-2 ___ X-1 ___| 0 ___ 1 ___ 2 ___ 3 ___ 4 __ * Y-1 Y-1 |0: 0 0 0 0 - * / \ / \ / :\ / \ / \ / \ / !! \ + * / \ / \ / :\ / \ / \ / \ / \ * / \ / \ /| : \ / \ / \ / \ / \ * X-3 ___ X-2 ___ X-1|___ 0 ___ 1 ___ 2 ___ 3 ___ 4 * Y-2 Y-2 Y-2| : 1 1 1 1 1 @@ -42,7 +42,7 @@ * * Node x,y for * 0 <= x < X = 2^XBITS x = distance along - * 0 <= y < Y = 2^YBITS-1 y = distance across + * 0 <= y < Y = 2^YBITS-1 y = distance across * * Vertices are in reading order from diagram above ie x varies fastest. * @@ -88,9 +88,13 @@ #define FOR_VPEDGE(v,e) \ for ((e)=0; (e)= 0, + * returns eprime s.t. v1==EDGE_END2(v2,eprime) */ +int edge_reverse(int v1, int e); + #define RIM_VERTEX_P(v) (((v) & YMASK) == 0 || ((v) & YMASK) == (Y-1)*Y1) #define FOR_VEDGE_X(v1,e,v2,init,otherwise) \ diff --git a/minimise.h b/minimise.h index 74788d3..4ac64a9 100644 --- a/minimise.h +++ b/minimise.h @@ -9,11 +9,16 @@ double compute_energy(const struct Vertices *vs); -double graph_layout_cost(const Vertices v, const double vertex_areas[N]); +double graph_layout_cost(const Vertices v); void graph_layout_prepare(); +void compute_vertex_areas(const Vertices vertices); +void compute_edge_lengths(const Vertices vertices); +extern double vertex_areas[N], vertex_mean_edge_lengths[N], edge_lengths[N][V6]; + double noncircular_rim_cost(const Vertices vertices); double edgewise_vertex_displacement_cost(const Vertices vertices); +double edge_length_variation_cost(const Vertices vertices); extern const char *input_file, *output_file; extern char *output_file_tmp;