minor improvements

diff --git a/energy.c b/energy.c
index a54cfe2f93bf07ab70d0f9bce02639a868bd9b1b..2bbf0492a5a41312d6819907995857bce9d1e180 100644 (file)
--- 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 74d93bfd6dd454164d6c1cf0b02a652e04a5a927..f0ce19db99fe08a1d2a0d82ab2f1746db1bae483 100644 (file)
--- 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 23a10e352ffa69bc91f9a4c9185fd911e90dbfd1..4b708e5bd12c247ca21e78e6a1d082217908702d 100644 (file)
--- 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 714ff7ffb72319e2d9a874e615ad7cf8b0814fa1..43494c7ebc9c38246b97222582f71dbe1476d3b7 100644 (file)
--- 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)<V6; (e)++)
 
-extern int edge_end2(unsigned v1, int e);
+int edge_end2(unsigned v1, int e);
 #define EDGE_END2 edge_end2
 
+/* given v1,e  s.t.  v2==EDGE_END2(v1,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 74788d3fbe862b55e3ba4459adbf98dd58dd6685..4ac64a93ab88e9b5b6a0ea37cb612562d979c14b 100644 (file)
--- 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;