From 28782fcd01e38d28c19f65b0c6f02ee1c55a1255 Mon Sep 17 00:00:00 2001
From: Ian Jackson <ian@davenant.greenend.org.uk>
Date: Thu, 3 Jan 2008 19:11:04 +0000
Subject: [PATCH] wip new graph layout stuff before abandoning

---
 bgl.cpp  | 87 +++++++++++++++++++++++++++++++++++++++++---------------
 bgl.h    |  1 +
 energy.c |  2 ++
 mgraph.h |  4 +--
 4 files changed, 69 insertions(+), 25 deletions(-)

diff --git a/bgl.cpp b/bgl.cpp
index 5d1e0ad..c35110b 100644
--- a/bgl.cpp
+++ b/bgl.cpp
@@ -170,7 +170,34 @@ static void single_source_shortest_paths(int v1,
      vertex_index_map(identity_property_map()).
      distance_map(vertex_distances));
 }
-    
+
+static int distances[N][N];
+
+void graph_layout_prepare() {
+  Graph g;
+  int v1, v2;
+  
+  FOR_VERTEX(v1) {
+    int *d= distances[v1];
+    FOR_VERTEX(v2) d[v2]= -1;
+    d[v1]= 0;
+    breadth_first_search
+      (g, v1,
+       vertex_index_map(identity_property_map()).
+       visitor(make_bfs_visitor(record_distances(d,on_tree_edge()))));
+    printf("%02x:",v1);
+    FOR_VERTEX(v2) printf(" %02x:%d",v2,d[v2]);
+    putchar('\n');
+  }
+  printf("---\n");
+  FOR_VERTEX(v1) {
+    int *d= distances[v1];
+    printf("%02x:",v1);
+    FOR_VERTEX(v2) printf(" %02x:%d",v2,d[v2]);
+    putchar('\n');
+  }  
+}
+
 double graph_layout_cost(const Vertices v, const double vertex_areas[N]) {
   /* For each (vi,vj) computes shortest path s_ij = |vi..vj|
    * along edges, and actual distance d_ij = |vi-vj|.
@@ -189,34 +216,48 @@ double graph_layout_cost(const Vertices v, const double vertex_areas[N]) {
    *  divisions, to avoid division by zero.)
    */
   static const double d2_epsilon= 1e-6;
-  
-  double edge_weights[V6<<ESHIFT], vertex_distances[N], total_cost=0;
-  int v1,v2,e,f;
 
-  FOR_VERTEX(v1)
-    FOR_VEDGE_X(v1,e,v2,
-		f= v1 | e << ESHIFT,
-		edge_weights[f]= NAN)
-      edge_weights[f]= hypotD(v[v1], v[v2]);
+  //  double edge_weights[V6<<ESHIFT], vertex_distances[N],
+  double total_cost=0;
+  int v1,v2,e, nedges=0;
+  double totaledgelength=0, meanedgelength;
+
+  FOR_EDGE(v1,e,v2) {
+    totaledgelength += hypotD(v[v1], v[v2]);
+    nedges++;
+  }
 
+  meanedgelength= totaledgelength / nedges;
+    
   FOR_VERTEX(v1) {
-    //double a1= vertex_areas[v1];
-    single_source_shortest_paths(v1, edge_weights, vertex_distances);
     FOR_VERTEX(v2) {
       if (v1 == v2) continue;
-      //double a2= vertex_areas[v2];
-      double d2= hypotD2plus(v[v1],v[v2], d2_epsilon);
-      double s= vertex_distances[v2];
-      double s2= s*s + d2_epsilon;
-      double sd2= s2 / d2;
+
+      double d= hypotD(v[v1],v[v2]);
+      
+      int dist= distances[v1][v2];
+      assert(dist>=0);
+
+      double s= dist * meanedgelength * 0.03;
+
+      double enoughdistance= d - s;
+      if (enoughdistance > 1e-6) continue;
+
+      /* energy = 1/2 stiffness deviation^2
+       * where stiffness = 1/d
+       */
+
+      double cost= pow(enoughdistance,4);
+      
+      //double s2= s*s + d2_epsilon;
+      //double sd2= s2 / d2;
       //double cost_contrib= a1*a2 * (sd2 - 1) / (d2*d2);
-      double cost_contrib= sd2;
-      //if (cost_contrib < -1e-4) {
-      //	printf("layout %03x..%03x (a=%g,%g) s=%g s2=%g d2=%g sd2=%g"
-      //	       " cost+=%g\n", v1,v2, a1,a2, s,s2,d2,sd2, cost_contrib);
-      //	abort();
-      //      }
-      total_cost += cost_contrib;
+      //double cost_contrib= sd2;
+
+      printf("layout %03x..%03x dist=%d mean=%g s=%g d=%g enough=%g"
+      	       " cost+=%g\n", v1,v2, dist, meanedgelength,
+	     s,d, enoughdistance, cost);
+      total_cost += cost;
     }
   }
   return total_cost;
diff --git a/bgl.h b/bgl.h
index 34736bb..0013f7e 100644
--- a/bgl.h
+++ b/bgl.h
@@ -8,6 +8,7 @@
 #include "mgraph.h"
 
 double graph_layout_cost(const Vertices v, const double vertex_areas[N]);
+void graph_layout_prepare();
 
 double noncircular_rim_cost(const Vertices vertices);
 double edgewise_vertex_displacement_cost(const Vertices vertices);
diff --git a/energy.c b/energy.c
index 9887ccb..07a4100 100644
--- a/energy.c
+++ b/energy.c
@@ -133,6 +133,8 @@ int main(int argc, const char *const *argv) {
   output_file= argv[2]+2;
   if (asprintf(&output_file_tmp,"%s.new",output_file) <= 0) diee("asprintf");
 
+  graph_layout_prepare();
+  
   minimiser= gsl_multimin_fminimizer_alloc
     (gsl_multimin_fminimizer_nmsimplex, DIM);
   if (!minimiser) { perror("alloc minimiser"); exit(-1); }
diff --git a/mgraph.h b/mgraph.h
index eb4bd12..12f57ab 100644
--- a/mgraph.h
+++ b/mgraph.h
@@ -62,9 +62,9 @@
 
 #include "common.h"
 
-#define XBITS 3
+#define XBITS 4
 #define X (1<<XBITS)
-#define YBITS 3
+#define YBITS 4
 #define Y ((1<<YBITS) - 1)
 
 /* vertex number:   0000 | y     | x
-- 
2.30.2